From: Chase Saunders
Subject: how to write eval in Scheme
Date: 
Message-ID: <F2Du2.905$D_.8799@newsfeed.slurp.net>
I am running LispMe Scheme for the PalmPilot - unfortunately, Eval is
implemented as a global button, rather than a function.  Most of the other
scheme features are fully implemented.

How can I write the Eval function?

From: Jeff Sandys
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <36BB115F.792F1F6D@NOboeingSPAM.com>
eval is function in LispMe (V2.32).
Just use the Symbols pull down list
or stroke it in.

(eval '(+ 2 3))
5

The eval global button is just the LispMe way 
of implementing the read-eval-print loop.

Lisp in the palm of your hand,
what will they think of next?

················@boeing.com

Chase Saunders wrote:
> 
> I am running LispMe Scheme for the PalmPilot - unfortunately, Eval is
> implemented as a global button, rather than a function.  Most of the other
> scheme features are fully implemented.
> 
> How can I write the Eval function?
From: Raymond Wiker
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <87btj8rdl7.fsf@foobar.arendal.orion.no>
Jeff Sandys <················@NOboeingSPAM.com> writes:

> Lisp in the palm of your hand,
> what will they think of next?

        APL on a laptop? Oh, wait a minute... they already did that
(in 1983, I think). 

-- 
Raymond Wiker, Orion Systems AS
+47 370 61150
From: Frank A. Adrian
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <rcGu2.2$rs2.12676@client.news.psi.net>
Actually, it was earlier than that - around '72 or so.  But it WAS an
expensive laptop...
faa
Raymond Wiker wrote in message <··············@foobar.arendal.orion.no>...
>Jeff Sandys <················@NOboeingSPAM.com> writes:
>
>> Lisp in the palm of your hand,
>> what will they think of next?
>
>        APL on a laptop? Oh, wait a minute... they already did that
>(in 1983, I think).
>
>--
>Raymond Wiker, Orion Systems AS
>+47 370 61150
From: Christopher C Stacy
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <x8l1zk2174y.fsf@world.std.com>
I think it was 1976 - the "laptop" (about 30 lbs) ran an emulation of
the IBM 370 instruction set and ran APL/360; the screen was 32 characters
 wide and there was a toggle switch to select display the left or right
64 characters; mass storage was a cartridge tape drive, of course.

My memory is a little hazy and I only played with one of these 
for a few hours, so I don't know if I got all the details exactly right.
From: Chase Saunders
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <baJu2.24$J81.662@newsfeed.slurp.net>
Thanks - I just needed to upgrade.  FYI, its up to version 2.4, which
includes user interface features and bug fixes.

As an academic matter, though - it is possible to write eval in terms of
other primitive functions?
From: Erik Naggum
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <3127250233867839@naggum.no>
* "Chase Saunders" <········@gwi.net>
| As an academic matter, though - it is possible to write eval in terms of
| other primitive functions?

  why, yes, that's a regular exercise in Scheme courses.

#:Erik
-- 
  Y2K conversion simplified: Januark, Februark, March, April, Mak, June,
  Julk, August, September, October, November, December.
From: Chase Saunders
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <qZlv2.2126$1a1.47520@newsfeed.slurp.net>
>  why, yes, that's a regular exercise in Scheme courses.


I would love to spend all day puzzling it out, but I have already given up
to to lack of time and unfamiliarity with the language.  Would anyone mind
posting the solution (to the problem of writing Eval in terms of the other
basic Scheme functions)?
From: Wolfgang Hukriede
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <79l4he$hoq$1@bossix.informatik.uni-kiel.de>
Chase Saunders" <········@gwi.net> wrote

> Eric:
>>  why, yes, that's a regular exercise in Scheme courses.

> I would love to spend all day puzzling it out, but I have already given up
> to to lack of time and unfamiliarity with the language.  Would anyone mind
> posting the solution (to the problem of writing Eval in terms of the other
> basic Scheme functions)?

Ok, here we go. Greetings, Wolfgang.
---

(de Eval (x env)
    (cond ((symbol? x) (Symbol-lookup x env))
          ((atom? x) x)
          ((equal? 'quote (car x)) (cadr x))
          ((equal? 'lambda (car x)) (Build-closure x env))
          ((equal? 'if (car x)) 
	   (if (Eval (cadr x) env) 
	       (Eval (caddr x) env) 
	       (Eval (cadddr x) env))) 
          (else (Apply (Eval (car x) env)
                       (map (lambda (i) (Eval i env)) (cdr x))))))

(de Apply (f args)
    (cond ((Primitive? f) (apply (eval f) args))
          ((Closure? f) (Apply-Closure f args))
          (else (error 'Apply 
		       "expects type <procedure> as 1st argument"))))

(de Primitive? (x) (and (symbol? x) (primitive? (eval x))))

(de Apply-Closure (f args)
    (de bind (varis args)
        (unless (= (length varis) (length args))
                (error 'Apply-Closure
                       "wrong number of arguments, expected ~a, given ~a"
                       (length varis)
                       (length args)))
        (pairlis varis args))
    (de evlis (exprs env)
        (if (pair? (cdr exprs))
            (begin (Eval (car exprs) env) (evlis (cdr exprs env)))
            (Eval (car exprs) env)))
    (evlis (Closure-exprs f)
           (cons (bind (Closure-varis f) args) (Closure-env f))))

(de Symbol-lookup (x env)
    (cond ((null? env)
           (if (primitive? (eval x))
               x
               (error 'Symbol-lookup "~ unbound." x)))
          ((let ((s (assoc x (car env)))) (and s (cadr s))))
          (else (Symbol-lookup x (cdr env)))))

(de New-closure (varis env exprs)
    (list '*closure* varis env exprs))

(de Closure? (x) (and (pair? x) (equal? '*closure* (car x))))

(de Closure-varis (x) (cadr x))

(de Closure-env (x) (caddr x))

(de Closure-exprs (x) (cadddr x))

(de Build-closure (x env)
    (assert (equal? 'lambda (car x)))
    (unless (pair? (cddr x))
            (error 'closure "expression list must not be empty."))
    (New-closure (cadr x) env (cddr x)))

(de test-with-y-combinator ()
    ;;; eval is the ordinary built-in eval, 
    ;;; Eval is what we defined above.
    ;;; this should return (720 720)
    (let ((x '(((lambda (le)
                  ((lambda (f) (lambda (x) ((f f) x)))
                   (lambda (f) (le (lambda (x) ((f f) x))))))
                (lambda (phi)
                  (lambda (n) (if (<= n 1) 1 (* n (phi (1- n)))))))
               6)))
      (list (eval x) (Eval x '()))))

(test-with-y-combinator)
From: Kellom{ki Pertti
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <xfzzp6pcm64.fsf@kuovi.cs.tut.fi>
In article <············@bossix.informatik.uni-kiel.de> Wolfgang Hukriede <·········@ifm.uni-kiel.de> writes:
>   Ok, here we go. Greetings, Wolfgang.
>   ---
>
>   (de Eval (x env)
>       (cond ((symbol? x) (Symbol-lookup x env))
>	     ((atom? x) x)
>	     ((equal? 'quote (car x)) (cadr x))
>	     ((equal? 'lambda (car x)) (Build-closure x env))
>	     ((equal? 'if (car x)) 
>	      (if (Eval (cadr x) env) 
>		  (Eval (caddr x) env) 
>		  (Eval (cadddr x) env))) 
>	     (else (Apply (Eval (car x) env)
>			  (map (lambda (i) (Eval i env)) (cdr x))))))
[...]
>   (de Symbol-lookup (x env)
>       (cond ((null? env)
>	      (if (primitive? (eval x))
>		  x
>		  (error 'Symbol-lookup "~ unbound." x)))
>	     ((let ((s (assoc x (car env)))) (and s (cadr s))))
>	     (else (Symbol-lookup x (cdr env)))))

This is a nice Scheme *interpreter*, but it is not the equivalent of
eval. To appreciate why, consider how variable lookup is done. If I
load the definitions of Eval etc. into a Scheme session, and type

	(define x 1)
	(Eval '(+ x 1) '())		; eval x in a null environment

I will get an error complaining about unbound symbols x and +. This
can be remedied by providing an environment where they are bound:

	(Eval '(+ x 1) (list (list 'x x) (list '+ +)))

which will evaluate to 2 (I hope, I could not actually run the example
because of the nonstandard syntax). Even this does not get us all the
way, however, since changes to the bindings in Eval's environment do
not propagate back to the underlying implementation's
environment. It would be easy enough to augment the interpreter with
set!, but this would work as follows. First we build an environment
where x and + are bound to their current values:

	(define env (list (list 'x x) (list '+ +)))

after which the values of env and x are:

	env   ==> ((x 1) (+ <procedure>))
	x     ==> 1

After evaluating 

	(Eval '(set! x (+ x 1)) env)

the values of env and x are:
	
	env   ==>  ((x 2) (+ <procedure>))
	x     ==>  1

which is clearly not what one would expect from eval. The Revised^5
Report on Scheme allows for some restricted access to the underlying
environment, but even there it is not possible to portably access and
mutate bindings created by the user.

In Common Lisp (Allegro in particular):

	user(1): (setq x 1)
	1
	user(2): (eval '(+ x 1))
	2
	user(3): (eval '(setq x (+ x 1)))
	2
	user(4): x
	2
	
If this is a regular exercise, Erik must be attending some tough
Scheme courses ;-)
-- 
Pertti Kellom\"aki, Tampere Univ. of Technology, Software Systems Lab
From: Kalle Olavi Niemitalo
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <iznvhgsrxi3.fsf@stekt44.oulu.fi>
This message should supersede the previous one which I
accidentally sent unfinished.

Wolfgang Hukriede <·········@ifm.uni-kiel.de> writes:

> (de Eval (x env)
>     (cond ((symbol? x) (Symbol-lookup x env))
>           ((atom? x) x)
>           ((equal? 'quote (car x)) (cadr x))
>           ((equal? 'lambda (car x)) (Build-closure x env))
>           ((equal? 'if (car x)) 
[...]

For fun, I tried implementing a Scheme interpreter in Emacs Lisp.
It works rather well, apart from tail recursion, continuations and
macros.  I guess tail recursion would be the easiest of these.

I chose to represent Scheme-specific types (such as booleans and
procedures) as vectors whose first element is eq to a magic cons
cell.  This way, the Scheme code can't fake them.

One thing in my interpreter works differently from yours.
Namely, my eval does not compare the car of the form to 'quote
and such; rather, it just looks it up in the current environment
like any other symbol.  This lookup normally returns a
magic-tagged vector which represents a builtin macro.  The
evaluator notices this and passes the unevaluated argument list
to the Emacs Lisp function referred to by the vector.  Thus one
can bind quote as a variable or bind another symbol to the value
of quote.

Is this correct behavior?
From: Barry Margolin
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <cPVA2.79$Uu.4288@burlma1-snr2>
In article <···············@stekt44.oulu.fi>,
Kalle Olavi Niemitalo  <····@stekt.oulu.fi> wrote:
>One thing in my interpreter works differently from yours.
>Namely, my eval does not compare the car of the form to 'quote
>and such; rather, it just looks it up in the current environment
>like any other symbol.  This lookup normally returns a
>magic-tagged vector which represents a builtin macro.  The
>evaluator notices this and passes the unevaluated argument list
>to the Emacs Lisp function referred to by the vector.  Thus one
>can bind quote as a variable or bind another symbol to the value
>of quote.
>
>Is this correct behavior?

That's how many real interpreters actually work.  The hard-coded
comparisons are generally only found in pedagogical interpreters, to
emphasize that these symbols really are part of the language's syntax, not
something that users should expect to be able to extend or redefine, just
like keywords in conventional languages.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Jeff Sandys
Subject: Re: how to write eval in Scheme
Date: 
Message-ID: <36BF76BC.41C6@NOboeingSPAM.com>
Chase Saunders wrote:
> 
> Thanks - I just needed to upgrade.  FYI, its up to version 2.4, which
> includes user interface features and bug fixes.

And doubles the max number of nodes to 16K !

> 
> As an academic matter, though - it is possible to write eval in terms of
> other primitive functions?

In Structure and Interpretation of Computer Programs in chapter 4 titled
Metelinguistic Abstraction is a definition for eval and apply, but it 
assumes some procedures that are not available in LispMe.
SICP is a great academic text for Scheme.

You should check out comp.lang.scheme

Thanks,
Jeff Sandys