Now that we have our basic interpreter set up, it’s time to start writing some languages. Before we start experimenting with Lispy, we will implement a small subset of Scheme.

Implementing Scheme will let us test our implementation with a language that is already specified.

Create a new file, I’ll call it scheme_in_lispy.lispy, but you can name it whatever you like. We’ll be doing most of our work here so I’ll leave out the main lispy file.

We’ll start with define-primitive which we’ll simply copy from the old syntax.chicken, though we won’t use it until later.

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

The first primitive form we’ll introduce is define. For this we’re going to do a little more copy and paste. Scheme’s define form is just a combination of our previous define and function. define sets a value to a symbol, but it also provides a shorthand for setting a lambda to a symbol (define (a x) x) is equivalent to (define a (lambda (x) x)). To figure out which one we need to produce, we only have to look at the first value in expr. If it is a symbol we just set the symbol name to the evaluated value. If it is a list we create a proc and set that as the value to symbol.

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))

(define a 42)
;===> #<unspecified>
a
;===> 42
(define (b x) x)
;===> #<unspecified>
(b 42)
;===> 42

lambda is simple after that. All we have to do is rip out the (make-proc …) procedure and drop it into lambda with one small change. With define we received a procedure definition as ((name arg-1 arg-2 arg-n) body), however an anonymous function does not have a name. We receive a lambda definition as ((arg-1 arg-2 arg-n) body).

(scheme-syntax lamb
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               env)))

(define c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42
((lambda (y) y) 42)
;===> 42

if is a straight copy/paste from our old syntax file.

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

(if 1 2 3)
;===> 2
(if #f 2 3)
;===> 3

quote is one of the simplest forms in Scheme. All quote does is return its argument unevaluated.

(scheme-syntax quote
  (lambda (expr env)
    (car expr)))

(quote (+ 1 2))
;===> (+ 1 2)

set! is pretty simple too, it’s basically just a limited form of define.

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

(set! a 42)
;===> #<unspecified>
a
;===> 42
(set! b (if #f 2 3))
;===> #<unspecified>
b
;===> 3
(set! c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42

begin is pretty straightforward, in fact we have already implemented it as eval-body (we used it for procedures).

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))

(begin 1 2 3)
;===> 3
(begin (define x 42) x)
;===> 42

let is almost the same as begin, except we have to extend the environment with the given bindings before we evaluate the body of the let. This version uses cons cells instead of 2 element lists to set symbols. You could add support for (let ((x 35) (y 7)) …) if you like. Since making a Scheme is not my goal, I will not do that now.

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))

(let ((x . 35) (y . 7)) (if x x y))
;===> 35
x
;===> Error: Unbound symbol: x

equal? is easily snarfed from the underlying Scheme. equal? could also be defined using define-primitive (define-primitive equal? equal?).

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))

(equal? 2 2)
;===> #t
(equal? 2 (if 1 2 3))
;===> #t
(equal? 1 2)
;===> #f

Finally we’ll snarf some primitives from the underlying Scheme to make our mini-Scheme a little more usable.

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)

(+ 1 2)
;===> 3
(- 3 2)
;===> 1
(< 1 2)
;===> #t
(> 1 2)
;===> #f
(cons 1 2)
;===> (1 . 2)
(car (cons 1 2))
;===> 1
(cdr (cons 1 2))
;===> 2
(define (loop x) (if (< x 0) (print 'finished) (begin (print x) (loop (- x 1)))))
;===> #<unspecified>
(loop 3)
3
2
1
0
finished
;===> #<unspecified>

There is a lot that is left out, error handling and advanced features like call-with-current-continuation or macros, for example. But for a simple Scheme to help test the implementation of our interpreter this is just about all we need.

Most of the rest of Scheme can be implemented as derived forms from the primitives we just defined. What cannot be, can be implemented using our scheme-syntax macro.

Finally, here’s the full source of scheme_in_lispy.lispy for you to play with.

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

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))

(scheme-syntax lambda
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               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 quote
  (lambda (expr env)
    (car expr)))

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

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)

GOTO Table of Contents

GOTO Table of Contents

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 Part 8 | Scheme in Lispy

GOTO Table of Contents