Lispy in Scheme | Lispy Procedures

The goal for this part is to implement procedures in Lispy.

To begin implementing Lispy procedures we have to define a procedure type, just like we did with primitives. A procedure has 3 basic parts. A list of parameters, a body and an environment. So we’ll set up our new procedure type with these fields and call it proc to avoid a name clash with Scheme’s procedure?.

Like primitives, procedures are handled by the lispy-apply procedure. We’ll change lispy-apply to use a cond instead of nested ifs and temporarily put in a placeholder for procedures. In addition we need a way to define new procedures from within Lispy. If we were writing a Scheme, the define form would allow us to both set symbols and procedures. For the moment we’ll separate the two usual jobs of define and create a new form (function (parameters) body) to set procedures.

(use srfi-69)

(define global-syntax-definitions (make-hash-table))
(define-record primitive function)
(define-record proc parameters body environment)

(define (current-environment env) (car env))
(define (enclosing-environment env) (cdr env))

(define (extend-environment bindings base-environment)
  (cons (alist->hash-table bindings) base-environment))

(define the-global-environment (extend-environment '() '()))

(define (set-symbol! symbol value env)
  (hash-table-set! (current-environment env) symbol value))

(define (lookup-symbol-value symbol environment)
  (if (null? environment)
    (error 'unbound-symbol "Unbound symbol:  " symbol)
    (if (hash-table-exists? (current-environment environment) symbol)
        (hash-table-ref (current-environment environment) symbol)
        (lookup-symbol-value symbol (enclosing-environment environment)))))

(define (self-evaluating? expr)
  (or (number? expr) (string? expr) (char? expr) (boolean? expr)))

(define (lispy-eval expr env)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-symbol-value expr env))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr) env)
              (lispy-apply (lispy-eval (car expr) env) (eval-arguments (cdr expr) env))))))

(define (eval-arguments args env)
  (map (lambda (x) (lispy-eval x env)) args))

(define (lispy-apply procedure arguments) 
  (cond ((primitive? procedure)
           (apply (primitive-function procedure) arguments))
        ((proc? procedure)
           "Attempted to apply a Lispy procedure")
        (else
           "Error: Undefined procedure")))

(hash-table-set! global-syntax-definitions 'scheme-syntax
  (lambda (expr env)
    (hash-table-set! global-syntax-definitions (car expr) (eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'load
  (lambda (expr env)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e env)
                             (loop (read f)))))))

((hash-table-ref global-syntax-definitions 'load) '("syntax.chicken") the-global-environment)

(define (repl)
  (define input (read))
  (print ";===> " (lispy-eval input the-global-environment))
  (repl))

syntax.chicken

(scheme-syntax define
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr))))))

(scheme-syntax function
  (lambda (expr env)
    (set-symbol! (caar expr)
                 (make-procedure (cdar expr)
                                 (cdr expr)
                                 env) env)))
(function (a x) x)
;===> #<unspecified>
a
;===> #<proc>
(a 42)
;===> Attempted to apply a Lispy procedure

Now that we have a basic outline for what our procedures will look like, we can focus on making them work!

To apply a procedure we have to evaluate the body. In the example above the body of the procedure is just x. However we can’t just evaluate x because x is not bound to anything yet.

First we need to create a new environment and bind the parameters to the arguments supplied in the procedure call. In this case we have to bind x to the value 42. For this we’ll use a helper procedure called assign-values.

The body is evaluated in the same way that we evaluate arguments. The difference is that we only return the last expression of the body. For now we’ll create a procedure named eval-body that will call eval-arguments, then return the last evaluated argument (it’s not the most efficient implementation, but it is simple and reuses code that we have already wrote).

(use srfi-69)
(use srfi-1)

(define global-syntax-definitions (make-hash-table))
(define-record primitive function)
(define-record proc parameters body environment)

(define (current-environment env) (car env))
(define (enclosing-environment env) (cdr env))

(define (extend-environment bindings base-environment)
  (cons (alist->hash-table bindings) base-environment))

(define the-global-environment (extend-environment '() '()))

(define (set-symbol! symbol value env)
  (hash-table-set! (current-environment env) symbol value))

(define (lookup-symbol-value symbol environment)
  (if (null? environment)
    "Error: Unbound symbol";(error 'unbound-symbol "Unbound symbol:  " symbol)
    (if (hash-table-exists? (current-environment environment) symbol)
        (hash-table-ref (current-environment environment) symbol)
        (lookup-symbol-value symbol (enclosing-environment environment)))))

(define (self-evaluating? expr)
  (or (number? expr) (string? expr) (char? expr) (boolean? expr)))

(define (lispy-eval expr env)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-symbol-value expr env))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr) env)
              (lispy-apply (lispy-eval (car expr) env) (eval-arguments (cdr expr) env))))))

(define (eval-arguments args env)
  (map (lambda (x) (lispy-eval x env)) args))

(define (eval-body args env)
  (last (eval-arguments args env)))

(define (assign-values procedure args)
  (map cons (proc-parameters procedure) args))

(define (lispy-apply procedure arguments) 
  (cond ((primitive? procedure)
           (apply (primitive-function procedure) arguments))
        ((proc? procedure)
           (eval-body (proc-body procedure)
                      (extend-environment (assign-values procedure arguments)
                                          (proc-environment procedure))))
        (else
           "Error: Undefined procedure")))

(hash-table-set! global-syntax-definitions 'scheme-syntax
  (lambda (expr env)
    (hash-table-set! global-syntax-definitions (car expr) (eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'load
  (lambda (expr env)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e env)
                             (loop (read f)))))))

((hash-table-ref global-syntax-definitions 'load) '("syntax.chicken") the-global-environment)

(define (repl)
  (define input (read))
  (print ";===> " (lispy-eval input the-global-environment))
  (repl))
(function (test pred conseq alt)
  (if pred conseq alt))
;===> #<unspecified>
(test 1 2 3)
;===> 2

With that, we have implemented procedures in Lispy! In 58 lines we have defined an interpreter framework that we can use to write just about any parenthesized, applicative-order, lexically scoped language. In the next few parts we’ll implement a very basic Scheme, then McCarthy’s LISP and finally begin work on the implementation of Lispy.

Also note that there is very little error-checking going on here. For instance calling a procedure with the wrong number of arguments results in the whole interpreter crashing. This would not be good in a production language. However including error checking in this code would probably triple its size at least. The point of this exercise is to learn the concepts, not write a bullet-proof language.

GOTO Table of Contents

Advertisements