Lispy in Scheme | scheme-syntax macro

The goal for this part is to implement (if predicate consequent alternate).

We’re going to start by implementing if the same way we implemented define. The first thing to do is test if the car of the pair equals if, then call apply-if.

We know that if will have to evaluate the predicate argument to determine whether to evaluate the consequent or alternate arguments. If the predicate is true we will evaluate the consequent expression and not the alternate. If the predicate is false we will evaluate the alternate expression and not the consequent.

(use srfi-69)

(define frame (make-hash-table))

(define (set-symbol! symbol value)
  (hash-table-set! frame symbol value))

(set-symbol! 'test "Value retrieved successfully")

(define (lookup-variable-value symbol)
  (if (hash-table-exists? frame symbol)
      (hash-table-ref frame symbol)
      "Error: Unbound variable"))

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

(define (lispy-eval expr)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-variable-value expr))
        ((pair? expr)
          (if (equal? (car expr) 'define)
              (set-symbol! (cadr expr) (lispy-eval (caddr expr)))
              (if (equal? (car expr) 'if)
                  (apply-if (lispy-eval (cadr expr)) (caddr expr) (cadddr expr))
                  "Not implemented")))
        (else "Not implemented")))

(define (apply-if pred consequent alternate)
  (if pred
      (lispy-eval consequent)
      (lispy-eval alternate)))

(define (repl)
  (define input (read))
  (print ";===>" (lispy-eval input))
  (repl))
(repl)
(if 1 2 3)
;===> 2

Anyone who has ever used Scheme or Lisp is probably cringing at the use of nested ifs here, when I could have used a cond (like SICP). I did this to illustrate a point, using if or cond is fine while you have a small number of primitive syntax forms. However once you implement a large number of primitive syntax forms this method of dispatch becomes cumbersome. Also note that it is not possible to extend the primitive syntax forms except by modifying the original source by hand.

 

Reusing the Frame

On top of that we have already implemented a mechanism of associating and storing symbol and value pairs. Let’s try something like that first, we’ll start by making another global hash table called global-syntax-definitions. Then we’ll modify eval to check these definitions.

(use srfi-69)

(define global-syntax-definitions (make-hash-table))
(define frame (make-hash-table))

(define (set-symbol! symbol value)
  (hash-table-set! frame symbol value))

(set-symbol! 'test "Value retrieved successfully")

(define (lookup-variable-value symbol)
  (if (hash-table-exists? frame symbol)
      (hash-table-ref frame symbol)
      "Error: Unbound variable"))

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

(define (lispy-eval expr)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-variable-value expr))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr))
              "Not implemented"))))

(hash-table-set! global-syntax-definitions 'define
  (lambda (expr)
    (set-symbol! (car expr) (lispy-eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'if
  (lambda (expr)
    (if (lispy-eval (car expr))
        (lispy-eval (cadr expr))
        (lispy-eval (caddr expr)))))

(define (repl)
  (define input (read))
  (print ";===>" (lispy-eval input))
  (repl))
(repl)
(define a 5)
;===> #<unspecified>
a
;===> 5
(if 1 2 3)
;===> 2
(hello)
;===> Not implemented

With that addition we are finished with the first level of the eval function. An expression can only be one of three things: self-evaluating, a symbol or an application (either syntax or procedure which we’ll cover later).

How does it work? global-syntax-definitions is used to store anonymous procedures that each take a single argument (the rest of the expression after the name). If a given symbol matches a key in global-syntax-definitions the value of that key is called with the unevaluated list of arguments as the only argument.

In other words, when lispy-eval comes across a primitive syntax definition it transfers control to a Scheme procedure located in the global-syntax-definitions table. That Scheme procedure is responsible for evaluating the arguments and returning a Lispy value.

Now that we have a data structure to hold our global-syntax-definitions it would be a good idea to supply an easy mechanism to set a new syntax definition. For this purpose we’ll design a macro in Lispy that will set a new syntax definition called scheme-syntax.

(use srfi-69)

(define global-syntax-definitions (make-hash-table))
(define frame (make-hash-table))

(define (set-symbol! symbol value)
  (hash-table-set! frame symbol value))

(set-symbol! 'test "Value retrieved successfully")

(define (lookup-variable-value symbol)
  (if (hash-table-exists? frame symbol)
      (hash-table-ref frame symbol)
      "Error: Unbound variable"))

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

(define (lispy-eval expr)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-variable-value expr))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr))
              "Not implemented"))))

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

(hash-table-set! global-syntax-definitions 'define
  (lambda (expr)
    (set-symbol! (car expr) (lispy-eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'if
  (lambda (expr)
    (if (lispy-eval (car expr))
        (lispy-eval (cadr expr))
        (lispy-eval (caddr expr)))))

(define (repl)
  (define input (read))
  (print ";===>" (lispy-eval input))
  (repl))
(repl)
(scheme-syntax quote (lambda (expr) (car expr)))
;===> #<unspecified>
(quote (1 2 3))
;===> (1 2 3)
(1 2 3)
;===> Not implemented

With the addition of scheme-syntax it is now possible to write Scheme directly in Lispy. Because of this we can now implement all of the primitive syntax forms in Lispy. Some might consider this cheating, but eventually we’re going to want a way to interface with Chicken. Why not implement it right away, use it, test it and make it solid by implementing everything else in it? We’ll still have to make some modifications to the core interpreter to implement procedures and a load form later.

We haven’t even gotten to the mutually recursive yin-yang that is the eval/apply cycle yet. However, thanks to piggy-backing on Chicken, we already have a somewhat useful language. A language without procedures is a pretty bad one, so we’ll keep pressing on, but check out some of the things that are possible already…

(repl)
(scheme-syntax print
  (lambda (expr)
    (print (car expr))))
;===> #<unspecified>
(scheme-syntax loop
  (lambda (expr)
    (let loop ((n (car expr)))
      (begin
        (lispy-eval (cadr expr))
        (if (> n 0)
            (loop (- n 1)))))))
;===> #<unspecified>
(loop 2 (print "Hi"))
;===> Hi
;===> Hi
;===> Hi
;===> #<unspecified>

In the next article we’ll do a little refactoring, remove define and if from the core of the interpreter and implement a load function so we can remove our syntax definitions out of the main interpreter file.

GOTO Part 4 | Refactor and load

GOTO Table of Contents

Advertisements