3
\$\begingroup\$

I wrote this interpreter a little while ago and was hoping I could get some comments/criticisms. It it somewhat similar to the "languages as libraries" concept of Racket, though obviously with less features.

Another goal was to see how little I could implement and still have a usable language. I chose to implement a Scheme FFI (scheme-syntax ...) that allows defining of primitive syntax forms in the "language layer".

Is this a good/bad approach? Are there any problems with the implementation in general? I've never had a code review before and, save for one commenter on Reddit yesterday, I've never had someone read/comment on my code before.

This particular interpreter was written for a series of blog posts in the style of "An Incremental Approach to Compiler Construction". It is meant to be as simplistic as possible. If you want to review that as well I would appreciate it (though don't expect it at all).

(use srfi-69)
(use srfi-1)

(define global-syntax-definitions (make-hash-table))
(define-record primitive function)
(define-record proc parameters body environment)

(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)
    (conc "Error: 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) (proc? 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) env) (eval-arguments (cdr expr) env))))))

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

(define (eval-body args env)
  (last (eval-arguments args env)))

(define (assign-values procedure args)
  (map cons (proc-parameters procedure) args))

(define (lispy-apply procedure arguments) 
  (cond ((primitive? procedure)
           (apply (primitive-function procedure) arguments))
        ((proc? procedure)
           (eval-body (proc-body procedure)
                      (extend-environment (assign-values procedure arguments)
                                          (proc-environment procedure))))
        (else
           (conc "Error: Undefined procedure: " (->string 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) '("scheme_in_lispy.chicken") the-global-environment)

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

(repl)

And here's an example of a very small subset of Scheme implemented in this framework:

(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)
\$\endgroup\$
2
\$\begingroup\$

There is a hidden bug in the interpreter.

Your eval-body calls eval-arguments to evaluate the body expressions of a compound procedure, but the evaluation order of map it not defined in Scheme. The procedure bodies should be evaluated with for-each as it has well-defined evaluation order from left to right. Both the following are correct implementations of Scheme map (for simplicity, shown with unary function arguments only):

  (define (map f ls) ;; evaluates in left-to-right order
    (if (null? ls) '()
        (let ((val (f (car ls))))
          (cons val (map f (cdr ls))))))

  (define (map f ls) ;; evaluates in right-to-left order
    (if (null? ls) '()
        (let ((rs (map f (cdr ls))))
          (cons (f (car ls)) rs))))
\$\endgroup\$
  • \$\begingroup\$ Thanks for pointing that out. That was the result of oversimplifying this: (define (eval-arguments exps env) (if (null? exps) '() (cons (meta-eval (car exps) env) (eval-arguments (cdr exps) env)))) I'll look into using for-each. I've never used it before and this seems as good an excuse as any. \$\endgroup\$ – Nick Frezynski Apr 16 '11 at 22:38
  • \$\begingroup\$ Yes, for-each is like map but used when you evaluate the expression for their side-effects instead of their values; because of this emphasis, for-each has a well-defined execution order. \$\endgroup\$ – antti.huima Apr 17 '11 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.