Writing a Scheme Interpreter in Scheme 
Author Message
 Writing a Scheme Interpreter in Scheme

  A friend and I were discussing what the *minimum* implementation of Scheme
would look like.  Once this was written, the rest of scheme would follow,
written in scheme, of course.  It would require

lambda
define-syntax of some sort to define keywords like let, letrec, recur, begin...
set!
define
if
<primitive predicates for numbers, booleans, etc.>  -- ?

Then everything else would be written with these basic constuctors.
(case can be written using ifs and quotes and define-syntax; let with lambda)

(define cons
  (lambda (a b)
    (let ([car a]
          [cdr b])
      (lambda (message)
        (case (message)
          [car car]
          [cdr cdr]
          [set-car! (lambda (v) (set! car v))]
          [set-cdr! (lambda (v) (set! cdr v))])))))

(define car (lambda (c) (c 'car)))
(define cdr (lambda (c) (c 'cdr)))
(define set-car! (lambda (c v) ((c 'set-car!) v)))
(define set-cdr! (lambda (c v) ((c 'set-cdr!) v)))

    I am wondering whether I am overlooking something which must be included,
or if I am including something which need not be.  This implementation wouldn't
be terrifically efficient, but it would be conceptually satisfying.

- Sebastian



Fri, 11 Oct 1996 03:45:49 GMT  
 Writing a Scheme Interpreter in Scheme
And of course, with macros, you can leave "if" out, too, if you are willing
to have booleans be procedures, and allow only booleans as test values in
if expressions.  That wouldn't be RnRS scheme anymore, for sufficiently
hign n, though, but conceptually it's nice.

(define #t (lambda (then else) then))
(define #f (lambda (then else) else))

(if test then else)    -->    ((test (lambda () then) (lambda () else)))



Sat, 12 Oct 1996 17:47:47 GMT  
 Writing a Scheme Interpreter in Scheme

Quote:
Sebastian Erich Good writes:

     A friend and I were discussing what the *minimum* implementation of Scheme
   would look like.  Once this was written, the rest of scheme would follow,
   written in scheme, of course.

psi implements a minimal scheme as you describe, and everything else
is built on top of that with macros. this minimal scheme looks almost
straight out of dbyvig's thesis with some additions, ie:

        symbols & constants
        (quote ...)
        (quasiquote ...)
        (define name body) and (define (name args) body)
        (lambda args body)
        (begin ...)
        (if test then [else])
        (set! var val)
        (call/cc ...)
        (macro (name args) body)
        (macro-proc ...)
        (prim ...)
        (proc ...)

   [...]                         This implementation wouldn't
   be terrifically efficient, but it would be conceptually satisfying.

i am not sure why you would think this should not be efficient. psi [with
all of its macro overhead] runs around 30% of another scheme implementation
where *everything* is implemented in C. this is without even trying hard.

oz



Sat, 12 Oct 1996 05:42:31 GMT  
 Writing a Scheme Interpreter in Scheme


Quote:
>  A friend and I were discussing what the *minimum* implementation of Scheme
>would look like.

Shame on you.  If you had taken programming languages from Matthias,
you would already have written a scheme interpreter in scheme.  :) :)
:) :)  (I'll admit that I haven't kept up with who's teaching what and
how at Rice these days.)  At least take a look at _Essentials of
Programming Languages_ by Friedman, Haynes, Wand.  (Chapter 5 starts
you on the interpreter, and subsequent chapters fill you in on more.)

Quote:
> Once this was written, the rest of scheme would follow,
>written in scheme, of course.  It would require

>lambda
>define-syntax of some sort to define keywords like let, letrec, recur, begin
>set!
>define
>if
><primitive predicates for numbers, booleans, etc.>  -- ?

variable reference
literals (constants)

If you want, you can have a line for each of the special forms like
let, letrec, etc., in the main body of your interpreter that simply calls
the interpreter with the transformed expression.  This saves you from
having to provide define-syntax.

Quote:
>Then everything else would be written with these basic constuctors.
>(case can be written using ifs and quotes and define-syntax; let with lambda)

In the usual way.

Quote:
>(define cons

[...])

You don't need to redefine cons if you are willing to use cons from the
underlying system.  Same with most of the other primitives.  Note that
procedure? and map are two examples that you have to write yourself.

Quote:
>    I am wondering whether I am overlooking something which must be included,
>or if I am including something which need not be.  This implementation
>wouldn't
>be terrifically efficient, but it would be conceptually satisfying.

You might leave out some of the primitives, since you are only doing
this as an exercise.  Keep in mind you are using the read procedure
from the underlying system.  Try writing your own, including quasiquote.
(I have never tried parsing quasiquote.  See the R4RS standard if you
are going to attempt this.)

When you get your interpreter going, run your interpreter on your
interpreted interpreter.

Scott



Mon, 14 Oct 1996 02:00:30 GMT  
 Writing a Scheme Interpreter in Scheme

|> And of course, with macros, you can leave "if" out, too, if you are willing
|> to have booleans be procedures, and allow only booleans as test values in
|> if expressions.  That wouldn't be RnRS scheme anymore, for sufficiently
|> hign n, though, but conceptually it's nice.
|>
|> (define #t (lambda (then else) then))
|> (define #f (lambda (then else) else))
|>
|> (if test then else)    -->    ((test (lambda () then) (lambda () else)))

(this followup is a bit late, you don't mind, do you?)

There are at least two other conceptually interesting ways:

1. Make all internal predicates return one of the lambda forms instead of
   booleans. Then you could write:

     (if test then else)
    -->
     (((builtin-eq? test #f) (lambda () else) (lambda () then)))

    (eq? a b)
    -->
     (((builtin-eq? a b) (lambda () #t) (lambda () #f)))

   This removes the need to make booleans procedures etc.

2. Use a procedure builtin-if:
    (if test then else) --> (builtin-if test (lambda () then) (lambda () else))
   This is what Orbit does (of course, it doesn't actually call a procedure!)

   The underlying system could define this builtin in scheme (using the
   underlying `if' of course):

   (define (builtin-if test then else)
      (if test (then) (else)))

- axel



Mon, 21 Oct 1996 00:00:34 GMT  
 Writing a Scheme Interpreter in Scheme

Quote:

>   (define (builtin-if test then else)
>      (if test (then) (else)))

This is a little far afield, but I can't resist showing off how to
write IF in Logo, supposing you didn't have it already:

to if :condition :true :false
output run thing :condition
end

For people not familiar with Logo, this is basically

(define (if condition true false)
  (eval (symeval condition)))

Logo predicates return the word TRUE or the word FALSE, so if, let's
say, the first argument is true, then (symeval condition) means
(symeval 'true) and that returns the second argument, and then you
eval that!  The second and third arguments are lists containing
expressions, so you'd say
        IF :X < 0 [- :X] [:X]
which means
        (if (< x 0) '(- x) '(x))

Isn't dynamic scope great??   :-)



Mon, 21 Oct 1996 04:36:44 GMT  
 Writing a Scheme Interpreter in Scheme

Quote:

> (define (if condition true false)
>   (eval (symeval condition)))

> Isn't dynamic scope great??   :-)

Well, I don't see the realtion with dynamic scope :-)
This is a question of 'symeval' working with local environment
(here we go again).

        Stefan

PS: oh, by the way: your solution depends on eval and hence is pretty
hard to make efficient (possible, but hard)



Mon, 21 Oct 1996 17:16:18 GMT  
 Writing a Scheme Interpreter in Scheme

Quote:
Axel Wienberg writes:
>\begin{garbage}
>  This could be implemented as

>  (define (if-fn a b c)
>     (cdr (assq (not (not a)) (list (cons #t b) (cons #f c)))))

I don't think you buy anything by implementing IF in terms of ASSQ; wouldn't
you rather implement ASSQ in terms of IF?  The point is that you still want
a primitive decision maker that does one thing if true and a different one
if false.

Quote:
>Then we rewrite all ifs:

>(if a b c)
>->
>((if-fn a (lambda () b) (lambda () c)))

Well, you've taken decision-making as primitive, but built IF's evaluation
rules out of lambda instead of being primitive.  But you can build any
evaluation rules out of lambda (I think), because you have explicit control
of when and when not to evaluate an expression, and because lexical
scope does the right thing.  For example:

(begin a b c d)  ->
  ((lambda (ignore) d)
   ((lambda (ignore) c)
    ((lambda (ignore) b)
     a)))

-Matt



Wed, 23 Oct 1996 06:18:57 GMT  
 Writing a Scheme Interpreter in Scheme


|> > (define (if condition true false)
|> >   (eval (symeval condition)))
|> >
|> > Isn't dynamic scope great??   :-)
|>
|> Well, I don't see the relation with dynamic scope :-)
|> This is a question of 'symeval' working with local environment
|> (here we go again).
|>
|>   Stefan
|>
|> PS: oh, by the way: your solution depends on eval and hence is pretty
|> hard to make efficient (possible, but hard)

Last night, I have found the ultimate way of implementing `if': Suppose we
have a builtin procedure if-fn that behaves as if it was defined
(define (if-fn a b c)
  (if a b c))

\begin{garbage}
  This could be implemented as

  (define (if-fn a b c)
     (cdr (assq (not (not a)) (list (cons #t b) (cons #f c)))))

  ..., in direct analogy to the logo version. It might be slightly more
  appropriate to implement `assq' via `if' than the  other way round, though :-)
\end{garbage}

Then we rewrite all ifs:

(if a b c)
->
((if-fn a (lambda () b) (lambda () c)))

Like this, "if-fn" is absolutely side-effect free and could still be sensibly
optimized.

We conclude: `if' doesn't have to be builtin syntax, just like `set!'. You
only need lambda, variable references and procedure calls and a number of
builtin predicates. I suppose that's as basic as you can get concerning the
syntax. Maybe we should start eliminating builtin procedures now...

-- Axel



Tue, 22 Oct 1996 01:47:36 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Scheme Interpreter in Scheme

2. UMB Scheme -- Free Scheme Interpreter

3. Interpreter written in Scheme

4. Optimization of Scheme Interpreter written in c

5. Optimization of Scheme Interpreter written in c

6. Compilers/Interpreters written in Scheme?

7. Scheme Interpreter Written in Prolog

8. writing scheme application extensions in scheme

9. FORTH [Was: Re: threaded scheme interpreters...]

10. Scheme in Haskell - a toy interpreter

11. Announcement: Phantom -- an interpreter for a subset of scheme

12. testers wanted: scheme interpreter for play/hack/test

 

 
Powered by phpBB® Forum Software