From: Reini Urban
Subject: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <3985f411.278996525@judy>
Just detected that the book "The Computional Beauty of Nature"
(called "fish & chips")
http://mitpress.mit.edu/flake/
contains a tiny lisp interpreter (stutter) with only seven primitives
car, cdr, cons, if, set, equal, quote, and lambda.
There are explicitly no numeric primitives.
And a nice sample file float.slp shows how to represent numbers (integer
and floats) and calculate with this. (i.e. lists of t)
free src to download.
(set '0 nil)
(set 'i1+ (lambda (x) (cons t x)))
(set '1 (i1+ 0))
(set '2 (i1+ 1))
...
=> sqrt
Good to link to for students.
for lazy lurkers who don't want to download the complete tarball I have
a copy of the sample file here:
http://xarch.tu-graz.ac.at/autocad/lisp/float.slp
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
······@xarch.tu-graz.ac.at (Reini Urban) writes:
> Just detected that the book "The Computional Beauty of Nature"
> (called "fish & chips")
> http://mitpress.mit.edu/flake/
> contains a tiny lisp interpreter (stutter) with only seven primitives
> car, cdr, cons, if, set, equal, quote, and lambda.
> There are explicitly no numeric primitives.
Interestingly enough, you don't even need CONS, CAR, and CDR as
primitives if you have LAMBDA.
In a Lisp-1 form:
(defun cons (a b)
(lambda (x) (if (equal x (quote car)) a b)))
(defun car (x)
(x 'car))
(defun cdr (x)
(x 'cdr))
From: Reini Urban
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <39873020.48343484@judy>
Colin Walters wrote:
>······@xarch.tu-graz.ac.at (Reini Urban) writes:
>> car, cdr, cons, if, set, equal, quote, and lambda.
>Interestingly enough, you don't even need CONS, CAR, and CDR as
>primitives if you have LAMBDA.
>(defun cons (a b)
> (lambda (x) (if (equal x (quote car)) a b)))
>(defun car (x)
> (x 'car))
>(defun cdr (x)
> (x 'cdr))
=> strictly it's this:
(set 'cons (a b) (lambda (x) (if (equal x (quote car)) a b)))
(set 'car (x) (x (quote car))
(set 'cdr (x) (x (quote cdr))
and EQUAL is a misnomer for EQ.
So you would need only LAMBDA, QUOTE and EQ for everything.
SET is not needed, maybe just for convenience.
And for IF I saw another trick elsewhere. (Queinnec?)
of course eval, read-char and write-char are missing.
From: Robert Monfera
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <39862D08.201D530B@fisec.com>
Reini Urban wrote:
>
> Just detected that the book "The Computional Beauty of Nature"
> (called "fish & chips")
> http://mitpress.mit.edu/flake/
> contains a tiny lisp interpreter (stutter) with only seven primitives
> car, cdr, cons, if, set, equal, quote, and lambda.
> There are explicitly no numeric primitives.
Their lack shows - it can't even count its own primitives :)
Robert
From: Reini Urban
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <39872972.46633114@judy>
Robert Monfera wrote:
>Reini Urban wrote:
>> Just detected that the book "The Computional Beauty of Nature"
>> (called "fish & chips")
>> http://mitpress.mit.edu/flake/
>> contains a tiny lisp interpreter (stutter) with only seven primitives
>> car, cdr, cons, if, set, equal, quote, and lambda.
>> There are explicitly no numeric primitives.
>
>Their lack shows - it can't even count its own primitives :)
A misunderstanding. it does count.
it develops bignums and flonums in ~20 lines of lisp lines and for fun
there's a sqrt also. of course it's just pure fun and terribly slow.
(fib 15) forces ~10 gc's with only the default 10240 cells on the fixed
heap, but then it gives (6 1 0).
(sqrt (float '(4 . 0))) runs out of memory,
>../bin/stutter -heap 50000 <float.slp
fails also, but
>../bin/stutter -heap 100000 <float.slp
worked okay. It needs several minutes though :)
At least now I know why it is called stutter.
--
ich bin am usenet mit jedem per du, das ist wie am berg und ist absicht.
From: Lieven Marchand
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <m3aeexylr7.fsf@localhost.localdomain>
······@xarch.tu-graz.ac.at (Reini Urban) writes:
> And a nice sample file float.slp shows how to represent numbers (integer
> and floats) and calculate with this. (i.e. lists of t)
> free src to download.
>
> (set '0 nil)
> (set 'i1+ (lambda (x) (cons t x)))
> (set '1 (i1+ 0))
> (set '2 (i1+ 1))
> ...
> => sqrt
>
> Good to link to for students.
> for lazy lurkers who don't want to download the complete tarball I have
> a copy of the sample file here:
> http://xarch.tu-graz.ac.at/autocad/lisp/float.slp
This is not even needed. You can get integers with lambda
only. They're called Church numerals.
It's a simple encoding of the Peano axioms.
n is defined as \fx.f^nx
I'm not so sure that it is a good idea to emphasize this stuff to
student. I think this is where a lot of scheme courses go awry. I'd
like the students to come away with the idea that Lisp is an excellent
language to write real applications in, with support for all common
abstractions and data types found in other mainstream languages and
more; not as a language in which you've got to define your own
integers and in which you can write the Y-combinator.
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
From: Barry Margolin
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <l6Gh5.29$PL5.1761@burlma1-snr2>
In article <··············@localhost.localdomain>,
Lieven Marchand <···@bewoner.dma.be> wrote:
>I'm not so sure that it is a good idea to emphasize this stuff to
>student. I think this is where a lot of scheme courses go awry.
It depends on the subject matter of the course. I agree that it's overly
arcane for a programming class, but seems appropriate for a more advanced
class on theoretical issues, automata, etc.
--
Barry Margolin, ······@genuity.net
Genuity, 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: Erik Naggum
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <3174205711241699@naggum.net>
* Barry Margolin <······@genuity.net>
| It depends on the subject matter of the course. I agree that it's
| overly arcane for a programming class, but seems appropriate for a
| more advanced class on theoretical issues, automata, etc.
Suppose the students do not know Lisp until they take such classes.
Some will go away thinking "What a great language! We can even do
<advanced-concept> directly in it!", while others, perhaps the
majority, will go away thinking "What a crummy language! It can
only be used for <advanced-concept>."
#:Erik
--
If this is not what you expected, please alter your expectations.
From: Lieven Marchand
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <m33dknmy3o.fsf@localhost.localdomain>
Barry Margolin <······@genuity.net> writes:
> It depends on the subject matter of the course. I agree that it's overly
> arcane for a programming class, but seems appropriate for a more advanced
> class on theoretical issues, automata, etc.
I agree. But then you're not teaching lisp. You're teaching <advanced
subject> using lisp as a tool, as Chaitin does in one of his recent
books on Algorithmic Information Theory.
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club
From: Rob Warnock
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <8mbhn6$cbhab$1@fido.engr.sgi.com>
Lieven Marchand <···@bewoner.dma.be> wrote:
+---------------
| But then you're not teaching lisp. You're teaching <advanced subject>
| using lisp as a tool, as Chaitin does in one of his recent books on
| Algorithmic Information Theory.
+---------------
Yeah, but I just wish he hadn't mucked up the basic syntax. His "Lisp"
<URL:http://www.cs.umaine.edu/~chaitin/unknowable/ch2.html> is really
not what a casual reader would recognize as such, and he has somehow
picked up some other odd ideas as well, e.g.:
"Programmers usually write M-expressions, and then the LISP
interpreter converts them into S-expressions before processing
them. M-expressions omit some of the parentheses, the ones that
group the primitive built-in functions together with their
arguments. M-expression notation works because all built-in
primitive functions in my LISP have a fixed-number of operands
or arguments."
So having said that, he chooses to write in his reduced-parentheses
"M-expression" notation (which doesn't look much like the M-expressions
in the Lisp 1.5 manual). So instead of:
(define (fact N) (if (= N 0) 1 (* N (fact (- N 1)))))
he writes:
define (fact N) if = N 0 1 * N (fact - N 1)
"This can be interpreted unambiguously if you know that ``define''
always has two operands, and ``if'' always has three."
Yes, it *can*, but the result is hard for a Lisp programmer to read.
The follow excerpts have the in-line embedded comments stripped out
(because they're mostly noise like "[then]" and "[else]"!!), which,
to be fair, makes the code even less readable, so I've added a little
indenting:
define (member? e set)
if atom set
false
if = e car set
true
(member? e cdr set)
define (subset? set1 set2)
if atom set1
true
if (member? car set1 set2)
(subset? cdr set1 set2)
false
O.k., so those aren't so bad, but what about the last line of this one?
define (union x y)
if atom x
y
if (member? car x y)
(union cdr x y)
cons car x (union cdr x y)
Isn't the correct parse instantly obvious...? :-{
I think it's highly unfortunate that he ever (mis)heard about
"M-expressions". His "Lisp" would have been just as useful for
expressing his mathematics if it used S-expressions, and would
be a hell of a lot more readable. As it is, we have yet *another*
weird thing calling itself "Lisp" that students will get exposed to
and come away thinking, "Well, if *that's* Lisp, I don't want any!"
(*sigh*)
-Rob
-----
Rob Warnock, 41L-955 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
From: TheBean
Subject: Re: A tiny lisp without numbers: The Computional Beauty of Nature
Date:
Message-ID: <8m98u5$p1a$1@nnrp1.deja.com>
In article <··················@judy>,
······@sbox.tu-graz.ac.at wrote:
> Just detected that the book "The Computional Beauty of Nature"
> (called "fish & chips")
> http://mitpress.mit.edu/flake/
> contains a tiny lisp interpreter (stutter) with only seven primitives
> car, cdr, cons, if, set, equal, quote, and lambda.
> There are explicitly no numeric primitives.
If I remember correctly, in the theoremm prover NQTHM (aka the
Boyer-Moore theorem prover), which used a dialect of LISP as its
specification language, numbers were defined axiomatically as lists,
much as was described in this post. In addition, one could use the
sytem to perform some very complex proofs .. like, for example,
Goedel's incompletness theorem ..
More info on this system can be found at:
ftp://ftp.cs.utexas.edu/pub/boyer/nqthm/index.html
Dave
Sent via Deja.com http://www.deja.com/
Before you buy.