The goal for this part is to implement primitive procedures, apply and a method of setting new primitives.

The first thing we need to do is figure out a way to represent our primitive procedures. SICP uses tagged lists, which are just regular lists with the first element designated as a tag. We’re going to use define-record to define a primitive type, which is more flexible and a little easier to use.

If the symbol of an expression of the form (symbol args …) is not found in global-syntax-definitions it must be a primitive procedure application (or not exist). To apply a primitive procedure we evaluate all the arguments using lispy-eval. We use that list as the args value to (apply primitive args). The primitive returns a Lispy value and we continue on.

For now we’re going to hardcode one primitive + into our interpreter. We’ll come up with something a little more elegant next.

(use srfi-69)

(define global-syntax-definitions (make-hash-table))
(define frame (make-hash-table))
(define-record primitive function)

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

(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))
              (lispy-apply (lispy-eval (car expr)) (eval-arguments (cdr expr)))))))

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

(define (lispy-apply procedure arguments)
  (if (primitive? procedure)
    (apply (primitive-function procedure) arguments)
    "Error: Undefined procedure"))

(set-symbol! '+ (make-primitive +))

(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 'load
  (lambda (expr)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e)
                             (loop (read f)))))))

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

(define (repl)
  (define input (read))
  (print ";>>> " (lispy-eval input))
  (repl))

(repl)

(+ 3 4)
;===> 7
(- 3 4)
;===> Error: Undefined procedure

The next step is to open up that functionality to Lispy. We’ll implement define-primitive as a scheme-syntax macro. First remove the line that sets the + symbol. We’re only going to be modifying the syntax.chicken file for now so that’s all I’ll show you.

We need to create a scheme-syntax macro that makes a procedure type and sets it as the value of a symbol. This macro is a lot like the define macro that we wrote earlier. The only difference is instead of calling lispy-eval on the cadr we call eval and pass that result to make-primitive.

syntax.chicken

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

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

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

With that we can define all sorts of primitives for our language…

(repl)
(define-primitive + +)
;===> #<unspecified>
(+ 3 4)
;===> 7
(- 3 4)
;===> Error: Undefined procedure

(define-primitive - -)
;===> #<unspecified>
(- 3 4)
;===> -1

(define-primitive square (lambda (x) (* x x)))
;===> #<unspecified>
(square 4)
;===> 16

You can start a new file and define a bunch of primitives, load it the same way you load syntax.chicken. I’m not going to define any primitives just yet but you are more than welcome to. Instead in the next post we’ll implement environments and then it’s on to implementing lambda!

GOTO Part 6 – Environments

GOTO Table of Contents

In the last part I said that we were going to be doing some refactoring. Let’s start with a little of that and a recap. The first thing that we’re going to do is remove define and if from our language. We’ll put them back in later, but first let’s look at what our language looks like with only scheme-syntax defined.

(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))

(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)))))

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

Let’s take a moment to consider what these 25 lines of code can do. We now have a language that can understand self-evaluating Scheme values and lookup symbol values. In addition to that it has exactly one primitive, a macro that defines other primitives and gives us access to the underlying Scheme.

You may consider this language lacking, and I admit it does not have many features. However it is now possible to define any language construct (including procedures, eval and apply) from within Lispy with the help of scheme-syntax and the Scheme underneath. After writing these 25 lines we could define the rest of the language 100% from within Lispy.

However there are a few more things that conceptually belong in the core language. One of those things is the ability to load a Lispy file. This will let us break out our syntax definitions into another file and load it automatically before we start the repl.

(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))

(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 'load
  (lambda (expr)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e)
                             (loop (read f)))))))

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

Now that we have load, we need something to load. Create a new file called syntax.chicken, or whatever you prefer. This is where we will define our primitive syntax forms like define, if and lambda.

(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))

(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 'load
  (lambda (expr)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e)
                             (loop (read f)))))))

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

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

syntax.chicken

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

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

(repl)
(define a 5)
;===> #<unspecified>
a
;===> 5
(if 1 2 3)
;===> 2

Now that we have implemented load we are one step closer to having a platform that we can build any language we want with. To change languages all we would have to do is load a different syntax file.

I encourage you to play around with that concept for a little while. Write two different syntax.chicken files and implement a couple of basic forms like define, or and if. Try to make your two implementations as different as possible even if making it different doesn’t make sense. For instance in one implementation if could take a mandatory keyword before the alternate branch (if pred consequent else alt) or it could act like and, taking two predicates and only evaluating the consequent branch if both predicates evaluate to true.

Since one of the goals of Lispy is to experiment with language features this ability will come in very useful. In the future we will extend this concept to make our interpreter more of a language platform than a language itself.

This article is a little short on code because we made some larger conceptual changes that I did not want to breeze past. In the next article we’ll implement primitive procedures and apply. The ability to define procedures from within Lispy is just around the corner.

GOTO Part 5 | Primitive Procedures and apply

GOTO Table of Contents

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