Lispy in Scheme – Environments

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

Advertisements