Scheme in Lispy

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

Advertisements