Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Shortest self-evaluating evaluator

134 views
Skip to first unread message

Erann Gat

unread,
Oct 9, 2002, 4:42:08 PM10/9/02
to

The topic of self-generating programs (a program whose output is itself)
comes up periodically here, but I've never seen the topic of a
self-evaluating program discussed. Of course, meta-circular interpreters
are ubiquitous, but the usual metacircular interpreter you find in
textbooks typically evaluates a slightly different dialect than it is
actually written in. My question is: what is the shortest meta-circular
interpreter that is actually capable of evaluating itself? When I tried
this excercise I ended up writing about 75 lines of code. What is the
shortest self-evaluating program?

Erann Gat
g...@jpl.nasa.gov

Marc Feeley

unread,
Oct 9, 2002, 9:15:07 PM10/9/02
to
> The topic of self-generating programs (a program whose output is itself)
> comes up periodically here, but I've never seen the topic of a
> self-evaluating program discussed. Of course, meta-circular interpreters
> are ubiquitous, but the usual metacircular interpreter you find in
> textbooks typically evaluates a slightly different dialect than it is
> actually written in. My question is: what is the shortest meta-circular
> interpreter that is actually capable of evaluating itself? When I tried
> this excercise I ended up writing about 75 lines of code.

I have an evaluator of a subset of Scheme that is about 100 lines of
code (see below). It even includes a macro expander and repl. Of
course, you could reduce the size of the language (up to a certain
point) and your evaluator would probably be smaller.

> What is the shortest self-evaluating program?

How about:

0

If that seems like cheating, try:

((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

Marc

(define global-env
(list '(read . (prim . read )) '(newline . (prim . newline))
'(write . (prim . write )) '(symbol? . (prim . symbol?))
'(null? . (prim . null? )) '(pair? . (prim . pair? ))
'(car . (prim . car )) '(cdr . (prim . cdr ))
'(cadr . (prim . cadr )) '(cons . (prim . cons ))
'(set-cdr! . (prim . set-cdr!)) '(assoc . (prim . assoc ))
'(eq? . (prim . eq? )) '(list . (prim . list ))))

(define env-read
(lambda (env var)
(cdr (assoc var env))))

(define env-set!
(lambda (env var val)
(cond ((eq? (car (car env)) var) (set-cdr! (car env) val))
((null? (cdr env)) (set-cdr! env (list (cons var val))))
(#t (env-set! (cdr env) var val)))))

(define env-extend
(lambda (env parms vals)
(cond ((null? parms) env)
(#t (cons (cons (car parms) (car vals))
(env-extend env (cdr parms) (cdr vals)))))))

(define eval
(lambda (expr env)
(cond ((symbol? expr) (env-read env expr))
((pair? expr) (eval-composite (car expr) (cdr expr) env))
(#t expr))))

(define eval-composite
(lambda (x lst env)
(cond ((assoc x macros) (eval (apply (env-read macros x) lst) env))
((eq? x 'defmacro) (env-set! macros (car lst) (eval (cadr lst) env)))
((eq? x 'set!) (env-set! env (car lst) (eval (cadr lst) env)))
((eq? x 'quote) (car lst))
((eq? x 'lambda) (eval-lambda lst env))
((eq? x 'begin) (eval-begin #f lst env))
((eq? x 'cond) (eval-cond lst env))
(#t (eval-call x lst env)))))

(define eval-lambda
(lambda (parms-and-body def-env)
(cons parms-and-body def-env)))

(define eval-begin
(lambda (val lst env)
(cond ((null? lst) val)
(#t (eval-begin (eval (car lst) env) (cdr lst) env)))))

(define eval-cond
(lambda (lst env)
(cond ((eval (car (car lst)) env) (eval (cadr (car lst)) env))
((pair? (cdr lst)) (eval-cond (cdr lst) env)))))

(define eval-call
(lambda (fn-expr arg-exprs env)
(apply (eval fn-expr env) (eval-list arg-exprs env))))

(define eval-list
(lambda (lst env)
(cond ((null? lst) '())
(#t (cons (eval (car lst) env)
(eval-list (cdr lst) env))))))

(define apply
(lambda (fn lst)
(cond ((eq? (car fn) 'prim)
(cond ((eq? (cdr fn) 'read) (read))
((eq? (cdr fn) 'newline) (newline))
((eq? (cdr fn) 'write) (write (car lst)))
((eq? (cdr fn) 'symbol?) (symbol? (car lst)))
((eq? (cdr fn) 'null?) (null? (car lst)))
((eq? (cdr fn) 'pair?) (pair? (car lst)))
((eq? (cdr fn) 'car) (car (car lst)))
((eq? (cdr fn) 'cdr) (cdr (car lst)))
((eq? (cdr fn) 'cadr) (cadr (car lst)))
((eq? (cdr fn) 'cons) (cons (car lst) (cadr lst)))
((eq? (cdr fn) 'set-cdr!) (set-cdr! (car lst) (cadr lst)))
((eq? (cdr fn) 'assoc) (assoc (car lst) (cadr lst)))
((eq? (cdr fn) 'eq?) (eq? (car lst) (cadr lst)))
((eq? (cdr fn) 'list) lst)))
(#t
(eval (cadr (car fn))
(env-extend (cdr fn) (car (car fn)) lst))))))

(define macros
(list (cons 'define
(eval-lambda '((var expr) (list 'set! var expr)) global-env))))

(define repl
(lambda ()
(begin (write '>) (write (eval (read) global-env)) (newline) (repl))))

Erann Gat

unread,
Oct 9, 2002, 11:31:29 PM10/9/02
to
In article <q6fzvfr...@vor.iro.umontreal.ca>, Marc Feeley
<fee...@IRO.UMontreal.CA> wrote:

> > The topic of self-generating programs (a program whose output is itself)
> > comes up periodically here, but I've never seen the topic of a
> > self-evaluating program discussed. Of course, meta-circular interpreters
> > are ubiquitous, but the usual metacircular interpreter you find in
> > textbooks typically evaluates a slightly different dialect than it is
> > actually written in. My question is: what is the shortest meta-circular
> > interpreter that is actually capable of evaluating itself? When I tried
> > this excercise I ended up writing about 75 lines of code.
>
> I have an evaluator of a subset of Scheme that is about 100 lines of
> code (see below). It even includes a macro expander and repl. Of
> course, you could reduce the size of the language (up to a certain
> point) and your evaluator would probably be smaller.

Yes, that's precisely the question: how much smaller can it (the program
and the language) be made before it loses the power to evaluate itself?

> > What is the shortest self-evaluating program?
>
> How about:
>
> 0

That's self-generating, not self-evaluating. At a minimum, a
self-evaluating program must contain a definition of EVAL, so it can be no
shorter than:

(define eval (expr) ...)

But the shortest self-generating program I can think of is the empty
program. '0' is infinitely longer! :-)

E.

Eli Barzilay

unread,
Oct 10, 2002, 1:05:06 AM10/10/02
to
g...@jpl.nasa.gov (Erann Gat) writes:

> That's self-generating, not self-evaluating. At a minimum, a
> self-evaluating program must contain a definition of EVAL, so it can be no
> shorter than:
>
> (define eval (expr) ...)

Depends on how much you want to inherit from the implementation...

(define my-tiny-evaluator eval)

--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://www.barzilay.org/ Maze is Life!

Tom Lord

unread,
Oct 10, 2002, 3:10:37 AM10/10/02
to

> Depends on how much you want to inherit from the implementation...

> (define my-tiny-evaluator eval)

Gat's Challenge [approximate formulation]:


What is the smallest turing-complete program, whose domain
includes it's own source code (interpreted as such), which is
capable of self-interpretation.


Given the form Gatt posted the challenge here, I guess we are
invited to think of inputs and outputs as s-expressions, with basic
list operators including read and write as the primitives.

Stephan H.M.J. Houben

unread,
Oct 10, 2002, 3:38:40 AM10/10/02
to
In article <sky996c...@mojave.cs.cornell.edu>, Eli Barzilay wrote:
>g...@jpl.nasa.gov (Erann Gat) writes:
>
>> That's self-generating, not self-evaluating. At a minimum, a
>> self-evaluating program must contain a definition of EVAL, so it can be no
>> shorter than:
>>
>> (define eval (expr) ...)
>
>Depends on how much you want to inherit from the implementation...
>
> (define my-tiny-evaluator eval)

Also depends on what a valid eval should be capable of
correctly eval-ling. If it only has to be able to eval itself,
I propose:
(letrec ((eval (lambda (expr) eval))) eval)

This evaluator does the Right Thing when applied to the list structure
(letrec ((eval (lambda (expr) eval))) eval)

Greetings,

Stephan

Eli Barzilay

unread,
Oct 10, 2002, 4:22:42 PM10/10/02
to
lo...@emf.emf.net (Tom Lord) writes:

I was well aware of what we were invited to think -- but I just happen
to use a specific brand of turing machines that have a "run the
following encoded turing machine" as a primitive.

Erann Gat

unread,
Oct 10, 2002, 7:46:03 PM10/10/02
to
In article <skr8eyo...@mojave.cs.cornell.edu>, Eli Barzilay
<e...@barzilay.org> wrote:

> lo...@emf.emf.net (Tom Lord) writes:
>
> > > Depends on how much you want to inherit from the implementation...
> >
> > > (define my-tiny-evaluator eval)
> >
> > Gat's Challenge [approximate formulation]:
> >
> > What is the smallest turing-complete program, whose domain
> > includes it's own source code (interpreted as such), which is
> > capable of self-interpretation.
> >
> > Given the form Gatt posted the challenge here, I guess we are
> > invited to think of inputs and outputs as s-expressions, with basic
> > list operators including read and write as the primitives.
>
> I was well aware of what we were invited to think -- but I just happen
> to use a specific brand of turing machines that have a "run the
> following encoded turing machine" as a primitive.

Your solution doesn't work. EVAL takes two arguments, so
(my-tiny-evaluator my-tiny-evaluator-source-code) will generate an error.
(Do you really want to turn this into a game of
who-can-be-a-bigger-wiseguy?)

There's another property that I was not explicit about, but the evaluator
should be a self-contained virtual machine. In other words, the solution
should have the following property:

(define foo 1)
(my-eval '(define foo 2))
(list foo (my-eval 'foo)) --> (1 2)

Achieving this property makes the solution slightly interesting even if
you use EVAL.

But, of course, the puzzle is a lot more fun if you don't use eval. (And
it's even more fun if you use nothing but LAMBDA :-)

E.

Eli Barzilay

unread,
Oct 10, 2002, 11:44:07 PM10/10/02
to
g...@jpl.nasa.gov (Erann Gat) writes:

> Your solution doesn't work. EVAL takes two arguments, so
> (my-tiny-evaluator my-tiny-evaluator-source-code) will generate an
> error.

That's easy to fix, and won't get a much bigger evaluator...


> (Do you really want to turn this into a game of
> who-can-be-a-bigger-wiseguy?)

Well, I was a wiseguy only in part. The issue is that you always end
up inheriting some of your implementation's environment (I can never
remember it but the 3-lisp paper had some good name for this). For
example, in Macr's evaluator there are some of the primitives that are
inherited from Scheme, and I'm sure that you have some in your own
code. Even when you implement Scheme in C, if you eventually get to
implement Scheme's `and' special form using a C `and', then you
basically just exposed the latter to your implementation in a way that
will propagate any features into your language (i.e, if you use a
buggy C compiler that doesn't short-circuit &&, will your
implementation still work with the intended Scheme semantics?). The
fact that you must rely on some existing functionality, even if you
burn the whole implementation somehow on a microchip, is what leads to
the question of how much you want to re-implement yourself -- you have
a 75-line code, but others might be more pedantic and claim that
you're a wiseguy since you've implemented some `foo' using the Scheme
`foo'...


> There's another property that I was not explicit about, but the evaluator
> should be a self-contained virtual machine. In other words, the solution
> should have the following property:
>
> (define foo 1)
> (my-eval '(define foo 2))
> (list foo (my-eval 'foo)) --> (1 2)
>
> Achieving this property makes the solution slightly interesting even if
> you use EVAL.

It just adds one restriction on the embedding... For example, I can
still keep my wiseguyness just use MzScheme's
`scheme-report-environment' which always returns a fresh namespace:

Welcome to MzScheme version 202, Copyright (c) 1995-2002 PLT
> (define my-eval
(let ((ns (scheme-report-environment 5)))
(lambda (expr) (eval expr ns))))
> (my-eval '(define my-eval
(let ((ns (scheme-report-environment 5)))
(lambda (expr) (eval expr ns)))))


> (define foo 1)
> (my-eval '(define foo 2))

> (my-eval '(my-eval '(define foo 3)))
> (list foo (my-eval 'foo) (my-eval '(my-eval 'foo)))
(1 2 3)


> But, of course, the puzzle is a lot more fun if you don't use eval. (And
> it's even more fun if you use nothing but LAMBDA :-)

Yeah -- that would be more fun... The really amuzing part is when you
realize that such a restriction doesn't only make it harder -- it also
makes it simpler since you only need to have your interpreter handle
lambdas. (Except that you'll have to implement some syntax
representation based on lambdas, and even then you'd have hard time
playing with the result...)

Jens Axel Søgaard

unread,
Oct 11, 2002, 10:59:52 AM10/11/02
to
Erann Gat wrote:

> My question is: what is the
> shortest meta-circular interpreter that is actually capable of
> evaluating itself? When I tried this excercise I ended up writing
> about 75 lines of code. What is the shortest self-evaluating program?


Does the code below qualify?

Features:
- conditional construct
- functions (of one argument)
- application
- quotation

The environment is represented as a function from strings to values.
To look up the name n in the environment r is simply (r n).
Extending the environment is done by function composition.
It is done directly since I have only included no binding construct
besides application. Restricting functions to one variable makes
application simpler. Recursion is done by the trick discussed in
length on c.l.l this week.

There is no mutation - I didn't need it.

; Self evaluating evaluator
; Jens Axel Søgaard, oct 2002

(define first car)
(define second cadr)
(define third caddr)
(define rest cdr)

; Support code for fak-example
(define (plus a) (lambda (b) (+ a b)))
(define (mult a) (lambda (b) (* a b)))
(define (one? x) (= x 1))
(define (sub1 n) (- n 1))

(define fak '(lambda (f)
(lambda (n)
(cond
[(one? n) 1]
[#t ((mult n) ((f f) (sub1 n)))]))))

(define fac-code (list (list fak fak) 5))


; Conventions: n name, r environment, e expression
(define code-jas-eval
'(lambda (ev)
(lambda (e)
(lambda (r)
(cond
[(symbol? e) (r e)]
[(not (pair? e)) e]
[(pair? e) (cond
[(eq? (first e) 'quote) (first (rest e))]
[(eq? (first e) 'cond)
(cond
[(((ev ev) (first (second e))) r) (((ev ev) (second (second e))) r)]
[#t (((ev ev) (cons 'cond (rest (rest e)))) r)])]
[(eq? (first e) 'lambda) (lambda (x)
(((ev ev) (third e))
(lambda (n)
(cond
[(eq? (first (second e)) n) x]
[#t (r n)]))))]
[#t ((((ev ev) (first e)) r)
(((ev ev) (second e)) r))])])))))

; setup initial environment
(define initial-env eval)

; use Scheme-eval to get jas-eval
(define jas-eval (eval code-jas-eval))
(define initial-env eval)

; test it in (fak 5)
(define expression (list (list fak fak) 5))
(((jas-eval jas-eval) expression) initial-env)

; use jas-eval to evaluate (((jas-eval jas-eval) (fak 5)) initial-env)
(define expression (list (list (list code-jas-eval code-jas-eval) (list (list fak fak) 5)) initial-env))
;expression
(((jas-eval jas-eval) expression) initial-env)

--
Jens Axel Søgaard

Joe Marshall

unread,
Oct 11, 2002, 11:06:03 AM10/11/02
to
"Jens Axel Søgaard" <use...@soegaard.net> writes:

> ; test it in (fak 5)
> (define expression (list (list fak fak) 5))
> (((jas-eval jas-eval) expression) initial-env)
>
> ; use jas-eval to evaluate (((jas-eval jas-eval) (fak 5)) initial-env)
> (define expression (list (list (list code-jas-eval code-jas-eval) (list (list fak fak) 5)) initial-env))
> ;expression
> (((jas-eval jas-eval) expression) initial-env)

For the sake of curiosity, how much slower is the extra interpretation layer?

Can you go another level deeper?

Jens Axel Søgaard

unread,
Oct 11, 2002, 12:16:01 PM10/11/02
to
Joe Marshall wrote:
> "Jens Axel Søgaard" <use...@soegaard.net> writes:
>
>> ; test it in (fak 5)
>> (define expression (list (list fak fak) 5))
>> (((jas-eval jas-eval) expression) initial-env)
>>
>> ; use jas-eval to evaluate (((jas-eval jas-eval) (fak 5)) initial-
>> env) (define expression (list (list (list code-jas-eval code-jas-

>> eval) (list (list fak fak) 5)) initial-env)) ;expression
>> (((jas-eval jas-eval) expression) initial-env)
>
> For the sake of curiosity, how much slower is the extra
> interpretation layer?
>
> Can you go another level deeper?

I get almost the same execution time for 1, 2, 3
and 4 layers. Argh. This means that there is a bug
somewhere. A missing quote?

The inquisitive reader will see that eq? is not curried,
so as it is, it is not supposed to work.

I'll find the error after dinner.

--
Jens Axel Søgaard

Jens Axel Søgaard

unread,
Oct 11, 2002, 12:35:07 PM10/11/02
to
Jens Axel Søgaard wrote:
> Joe Marshall wrote:

>> For the sake of curiosity, how much slower is the extra
>> interpretation layer?
>>
>> Can you go another level deeper?
>
> I get almost the same execution time for 1, 2, 3
> and 4 layers. Argh. This means that there is a bug
> somewhere. A missing quote?

Indeed it was a missing quote.

Here are the timings from DrScheme from level 1, 2 and 3.

cpu time: 0 real time: 0 gc time: 0
15
cpu time: 70 real time: 70 gc time: 0
15
cpu time: 5869 real time: 5868 gc time: 1614
15

Here is the revised code:

; Self evaluating evaluator, version 2


; Jens Axel Søgaard, oct 2002

(define first car)
(define second cadr)
(define third caddr)
(define rest cdr)

; Support code for fak-example
(define (plus a) (lambda (b) (+ a b)))
(define (mult a) (lambda (b) (* a b)))
(define (one? x) (= x 1))
(define (sub1 n) (- n 1))

(define fak '(lambda (f)
(lambda (n)
(cond
[(one? n) 1]
[#t ((mult n) ((f f) (sub1 n)))]))))

(define fac-code (list (list fak fak) 5))


; Conventions: n name, v value, r environment, e expression


(define code-jas-eval
'(lambda (ev)
(lambda (e)
(lambda (r)
(cond
[(symbol? e) (r e)]
[(not (pair? e)) e]
[(pair? e) (cond

[((ceq? (first e)) 'quote) (first (rest e))]
[((ceq? (first e)) 'cond)


(cond
[(((ev ev) (first (second e))) r) (((ev ev) (second (second e))) r)]

[#t (((ev ev) ((ccons 'cond) (rest (rest e)))) r)])]
[((ceq? (first e)) 'lambda) (lambda (x)


(((ev ev) (third e))
(lambda (n)
(cond

[((ceq? (first (second e))) n) x]


[#t (r n)]))))]
[#t ((((ev ev) (first e)) r)
(((ev ev) (second e)) r))])])))))

; setup initial environment;
; currying the primitives used in the evaluator
(define (ceq? a)
(lambda (b)
(eq? a b)))

(define (ccons a)
(lambda (b)
(cons a b)))

(define initial-env eval)


; use Scheme-eval to get jas-eval
(define jas-eval (eval code-jas-eval))
(define initial-env eval)

; test it in (fak 5)
(define expression fac-code)
(time (((jas-eval jas-eval) expression) initial-env))

; use jas-eval to evaluate (jas-eval (fak 5) initial-env)
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fac-code)) initial-env))
;expression
(time (((jas-eval jas-eval) expression) initial-env))

; use jas-eval to evaluate (jas-eval (fak 5) initial-env)
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fac-code)) initial-env))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote expression)) initial-env))
;expression
(time (((jas-eval jas-eval) expression) initial-env))

--
Jens Axel Søgaard


Erann Gat

unread,
Oct 11, 2002, 7:36:36 PM10/11/02
to
In article <3da6e80b$0$72303$edfa...@dspool01.news.tele.dk>, "Jens Axel
Søgaard" <use...@soegaard.net> wrote:

> Erann Gat wrote:
>
> > My question is: what is the
> > shortest meta-circular interpreter that is actually capable of
> > evaluating itself? When I tried this excercise I ended up writing
> > about 75 lines of code. What is the shortest self-evaluating program?
>
>
> Does the code below qualify?
>

Yes. I'm impressed. (My head feels like it's about to explode from all
that curry.)

E.

Erann Gat

unread,
Oct 11, 2002, 8:12:11 PM10/11/02
to
In article <skr8exw...@mojave.cs.cornell.edu>, Eli Barzilay
<e...@barzilay.org> wrote:

> Well, I was a wiseguy only in part. The issue is that you always end
> up inheriting some of your implementation's environment

Yes, but if the things you inherit are simpler than the things you are
trying to build then you have made progress towards understanding. If the
thing you inherit *is* the thing you are trying to build then you have
made no progress.

An analogy: once upon a long time ago you could ogo to Radio Shack (or
Heathkit) and buy a "kit", a collection of parts that could be assembled
into a useful device like a radio. (As far as I can tell, the concept of
a kit has sadly all but vanished from the face of the Earth.) There is a
qualitative difference between the experience of building a kit and that
of buying a finished device, despite the fact that the labor required to
assemble a kit is insignificant in comparison to what is required to make
the parts for the kit in the first place.

To claim that (define my-eval eval) solves the problem on the grounds that
you have to inherit *somthing* from the implementation environment is like
buying a finished product and then claiming to have built it because "it's
just like a kit with one part."

Bonus question: what's the smallest number of Lego bricks that can be
assembled into a factory that makes Lego bricks? :-)

E.

Eli Barzilay

unread,
Oct 12, 2002, 2:33:02 AM10/12/02
to
g...@jpl.nasa.gov (Erann Gat) writes:

> In article <skr8exw...@mojave.cs.cornell.edu>, Eli Barzilay
> <e...@barzilay.org> wrote:
>
> > Well, I was a wiseguy only in part. The issue is that you always
> > end up inheriting some of your implementation's environment
>
> Yes, but if the things you inherit are simpler than the things you
> are trying to build then you have made progress towards
> understanding. If the thing you inherit *is* the thing you are
> trying to build then you have made no progress.

Usually that's true -- but then there's some extreme beauty like
3-lisp or clos.


> An analogy: [...]

[But seriously, I really do not disagree with you. I loved those
kits.]

Stephan H.M.J. Houben

unread,
Oct 12, 2002, 8:56:16 AM10/12/02
to
In article <gat-111002...@k-137-79-50-101.jpl.nasa.gov>, Erann Gat wrote:

>Bonus question: what's the smallest number of Lego bricks that can be
>assembled into a factory that makes Lego bricks? :-)

Well, that depends on the inputs to the factory. If I can have
Lego bricks as input, the answer is 0.

Now for extra credit: what is the smallest number of Lego bricks that
can be assembled into a device that reproduces itself from
the mix of gasses typically available in a protostellar nebula.

Stephan

Tony Garnock-Jones

unread,
Oct 14, 2002, 7:59:57 AM10/14/02
to
> Usually that's true -- but then there's some extreme beauty like
> 3-lisp or clos.

What's 3-lisp? Is it related to the Scheme-having-one-namespace,
Common-lisp-having-two-namespaces thing? A quick google didn't turn up much.

Eli Barzilay

unread,
Oct 14, 2002, 12:40:42 PM10/14/02
to
Tony Garnock-Jones <to...@eservglobal.com> writes:

It's an old implementation of a reflective Lisp from Xerox. A really
small and beautiful piece of code that implements its own evaluator in
some sense.

The Lisp-1 and Lisp-2 are (c.l.l) terms that resulted from some bloody
flamewars, and have nothing in common with 3-Lisp.

David Rush

unread,
Oct 14, 2002, 2:51:03 PM10/14/02
to
Eli Barzilay <e...@barzilay.org> writes:
> The Lisp-1 and Lisp-2 are (c.l.l) terms that resulted from some bloody
> flamewars, and have nothing in common with 3-Lisp.

But isn't it lovely that Scheme comes out as Lisp-1? I think that
makes us the winners, no?

david rush
--
Hey Erik! Did you realize the CL is not a Lisp?

Eli Barzilay

unread,
Oct 14, 2002, 7:49:53 PM10/14/02
to
David Rush <ku...@bellsouth.net> writes:

> Eli Barzilay <e...@barzilay.org> writes:
> > The Lisp-1 and Lisp-2 are (c.l.l) terms that resulted from some bloody
> > flamewars, and have nothing in common with 3-Lisp.
>
> But isn't it lovely that Scheme comes out as Lisp-1? I think that
> makes us the winners, no?

It's even better -- a (Common) Lisp programmer would probably feel
better being on version 2 which is better than 1...

David Rush

unread,
Oct 14, 2002, 9:02:09 PM10/14/02
to
Eli Barzilay <e...@barzilay.org> writes:
> David Rush <ku...@bellsouth.net> writes:
>
> > Eli Barzilay <e...@barzilay.org> writes:
> > > The Lisp-1 and Lisp-2 are (c.l.l) terms that resulted from some bloody
> > > flamewars, and have nothing in common with 3-Lisp.
> >
> > But isn't it lovely that Scheme comes out as Lisp-1? I think that
> > makes us the winners, no?
>
> It's even better -- a (Common) Lisp programmer would probably feel
> better being on version 2 which is better than 1...

But on that criteria we win again. We're on version 5, CL is only on
version 2 (CLTL 2 was the last version *I* heard about, but I don't
pay attention...)

david rush
--
X-Windows: It was hard to write; it should be hard to use.
-- Jamie Zawinski

Manfred von Thun

unread,
Nov 11, 2002, 2:33:16 AM11/11/02
to
I'm sorry if this posting is way out of date. I had tried
to post it several times, but did not realise that although
I could see it, it never actually reached the ouside world.
Also, I seem to have done something dreadful to the header,
but this is the first time I am using the google mailer.

Here is a short self-evaluating evaluator in the language Joy.
It is good for interpreting itself but not much else (of course!).

joy0 ==
[ [ [ joy0 body joy0 ]
[ [] ]
[ pop pop pop ]
[ cons pop cons ]
[ opcase pop opcase ]
[ body pop body ]
[ i pop joy0 ]
[ step pop [joy0] cons step ]
[ [] cons i ] ]
opcase
i ]
step

The main page for the language Joy is at
http://www.latrobe.edu.au/philosophy/phimvt/joy.html
In section 2 of that page is a paper
"Design of a Joy interpreter written in Joy"
It contains the design of a larger interpreter, but the
above minimal one is at the very end. There is also a
test file with the interpreter interpreting ... the interpreter
interpreting ... up to several levels.

The full Joy language is of course much larger.
The real implementation is in ANSI-C.

Whereas Lisp and Scheme are based, like the lambda calculus,
on abstraction and application of functions, Joy is based
on just the composition of functions. There are no named
parameters for lambda abstraction, and hence there is no
need for an environment of name/value pairs. This is what
makes the minimal interpreter so short.

- Manfred von Thun

preferred email: phi...@lurac.latrobe.edu.au

Eli Barzilay

unread,
Nov 11, 2002, 11:18:01 AM11/11/02
to
man...@cs.latrobe.edu.au (Manfred von Thun) writes:

> joy0 ==
> [ [ [ joy0 body joy0 ]
> [ [] ]
> [ pop pop pop ]
> [ cons pop cons ]
> [ opcase pop opcase ]
> [ body pop body ]
> [ i pop joy0 ]
> [ step pop [joy0] cons step ]
> [ [] cons i ] ]
> opcase
> i ]
> step

[...resisting obvious pun...]

Steve VanDevender

unread,
Nov 15, 2002, 2:59:34 AM11/15/02
to
man...@cs.latrobe.edu.au (Manfred von Thun) writes:

> The main page for the language Joy is at
> http://www.latrobe.edu.au/philosophy/phimvt/joy.html

You wouldn't happen to have previous experience with the language RPL
used in the HP 28 series, HP 48 series, and HP 49 calculators, would
you? There are an awful lot of similiarities to RPL in Joy, although
the design of RPL was driven more by practical than theoretical
concerns.

For those unfamiliar with it, RPL stands for "Reverse Polish LISP" and
is a sort of unholy hybrid of Forth and LISP. The stack in RPL is a
stack of arbitrary data types, rather than just integers as in Forth.
Data types include real numbers, complex numbers, integers, arrays of
real or complex numbers, character strings, identifiers, lists, and
program objects. RPL lists, though, are just concatenations of objects
rather than the binary-tree lists of LISP. Program objects are almost
exactly like lists in structure (and similar in concept to Forth word
definitions).

--
Steve VanDevender "I ride the big iron" http://jcomm.uoregon.edu/~stevev
ste...@hexadecimal.uoregon.edu PGP keyprint 4AD7AF61F0B9DE87 522902969C0A7EE8
Little things break, circuitry burns / Time flies while my little world turns
Every day comes, every day goes / 100 years and nobody shows -- Happy Rhodes

Manfred von Thun

unread,
Nov 17, 2002, 11:08:58 PM11/17/02
to
Steve VanDevender <ste...@hexadecimal.uoregon.edu> wrote in message news:<87bs4rt...@localhost.efn.org>...
> man...@cs.latrobe.edu.au (Manfred von Thun) writes:
>
> > The main page for the language Joy is at
> > http://www.latrobe.edu.au/philosophy/phimvt/joy.html
>
> You wouldn't happen to have previous experience with the language RPL
> used in the HP 28 series, HP 48 series, and HP 49 calculators, would
> you? There are an awful lot of similiarities to RPL in Joy, although
> the design of RPL was driven more by practical than theoretical
> concerns.

Reverse Polish Notation (RPN) occurs in ancient Sanscrit, modern
Tibetan, modern Japanese, probably in many other natural languages,
and in the artificial Startrek language Klingon. The original
Polish Notation (not reversed) was due to Polish logicians in the
1920s. Its reverse lends itself particularly well for evaluation
on a stack. This is used in computers for evaluating arithmetic
and logical expressions in one guise or another. It is also used
in some programming languages: the HP calculators, the unix utility
dc, the typesetting language Postscript, the language Forth and,
as you point out, Joy.

But in Forth and Joy there are perfectly good expressions which
do not make sense as proper RPN (or postfix) notation: for example
2 + 3
is not an infix expression that has lost its way, but perfectly
legal expression in Forth and Joy: it it defined for any stack
whose top element is a number (say, 10), it will push the 2 on
top of that and then add the two elements to get 12, and finally
it will push the 3 on top of that. So that expression denotes
a function from stacks to stacks, and so do all other expressions
- they do not denote numbers.

> For those unfamiliar with it, RPL stands for "Reverse Polish LISP" and
> is a sort of unholy hybrid of Forth and LISP. The stack in RPL is a
> stack of arbitrary data types, rather than just integers as in Forth.
> Data types include real numbers, complex numbers, integers, arrays of
> real or complex numbers, character strings, identifiers, lists, and
> program objects. RPL lists, though, are just concatenations of objects
> rather than the binary-tree lists of LISP. Program objects are almost
> exactly like lists in structure (and similar in concept to Forth word
> definitions)

I had not heard of RPL before. I shall investigate. Thank you.

- Manfred

0 new messages