Posts Tagged write an interpreter

Lispy in Scheme – Environments

Posted by Nick Zarczynski in Lispy on 2011/03/06

We’ve been dealing with an environment ever since part 2 in this series when we implemented define, except we’ve been calling it a frame. Until now our frame has served us well, it has provided a simple environment where we could set and retrieve the value of symbols. However implementing procedures requires us to add a few features to our frame. Consider the code below.

(define x 5)
(define (func x)
  x)
(func 100)
;===> 100

With our frame this wouldn’t work as expected. Because we have already defined x in the global environment, there will be one of two problems with the x in func. Our function could use the global value of x (5) instead of the supplied value (100) or when the supplied value (100) is mapped onto the function body it will overwrite the value of the global value of x (5) with the supplied value (100).

Currently we do not make any distinction between variables in a function body and in the global environment. To properly implement procedures we will have to figure out a way to do that. Consider the next bit of code.

(define x 5)
(define (func y)
  (+ x y))
(func 10)
;===> 15

Even though we need to make a distinction between environments they also need to be connected. In the example above we use the global variable x in func without ever declaring it. This is accomplished by a method called chaining environments. 

(define x 1)
(define (outer-func y)
  (define (inner-func z)
    (+ x y z)
  (inner-func 3))
(outer-func 2)
;===> 6

The environments produced by the above code are best described by the diagram below.

So when x appears in inner-func we have to check inner-func’s environment for x, then outer-func’s environment for x and finally the global environment for x before we raise an undefined symbol error.

You may have noticed that the diagram above looks a lot like a linked list. We can take our frame and combine it with linked lists to form an environment. It is more informative (and closer to the actual design) to view environments from the point of view of eval. This diagram is a view of the environment structure when the code (+ x y z) is evaluated.

I used the names current-environment to refer to the inner-func environment and enclosing-environment to refer to the outer-func environment. We will use these same names in our source code. Note that the global-environment is just the enclosing-environment of outer-func, the only thing special about it is that its enclosing-environment is the empty list.

In addition we need to replace our global frame with the-global-environment, which we’ll do by providing a procedure extend-environment, and change lookup-symbol-value to check enclosing-environments if the symbol is not found.

(use srfi-69)

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

(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)
  (hash-table-set! (current-environment the-global-environment) 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)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-symbol-value expr the-global-environment))
        (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")) 

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

(define a 5)
;===> #<unspecified>
a
;===> 5

To use the full potential of our new environments we are going to have to rewrite our program a little bit to pass them around correctly. Since eval is the main method of dispatch for our interpreter we’ll supply our environment as an argument to eval. We’ll also have to pass an environment variable to procedures like set-symbol! and lookup-symbol-value. One final place we’ll need environments is in scheme-syntax, we’ll have to change the stored procedures there to use (lambda (expr env) …) instead of just (lambda (expr) …).

(use srfi-69)

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

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

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

(define a 5)
;===> #<unspecified>
a
;===> 5

If you still don’t fully understand environments, that’s OK. You’ll get a chance to play around with them in the next part where we’ll finally cover implementing procedures in Lispy!

GOTO Part 7 | Lispy Procedures

GOTO Table of Contents

, , , ,

No Comments

Lispy in Scheme | Primitive Procedures and apply

Posted by Nick Zarczynski in Lispy on 2011/02/26

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

, , , , , , , , , , , , ,

No Comments

Lispy in Scheme | Refactor and load

Posted by Nick Zarczynski in Lispy on 2011/02/26

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

, , , , , , , , , , , , ,

No Comments