Out of curiosity I've been Googling for the most minimal implementation of
Lisp I could find that is Turing-complete. What I came up with was Stutter:
http://mitpress.mit.edu/books/FLAOH/cbnhtml/stutter.html
It only has car, cdr, cons, if, set, equal, quote, and lambda.
Does anyone know of anything smaller? I know of the Kamin interpreter, but I
don't think it is Turing-complete (I could be wrong).
Leon
--
Leon Heller, G1HSM
···········@hotmail.com
http://www.geocities.com/leon_heller
On Wed, Jun 11, 2003 at 09:07:33AM +0000, Leon Heller wrote:
> It only has car, cdr, cons, if, set, equal, quote, and lambda.
>
> Does anyone know of anything smaller? I know of the Kamin interpreter, but I
> don't think it is Turing-complete (I could be wrong).
LAMBDA and function application.
Whether this is still Lisp, though, is debatable =) Of course, then we
get to the age old question of "What is Lisp, anyway?"
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
"Leon Heller" <···········@hotmail.com> writes:
> Out of curiosity I've been Googling for the most minimal implementation of
> Lisp I could find that is Turing-complete. What I came up with was Stutter:
>
> http://mitpress.mit.edu/books/FLAOH/cbnhtml/stutter.html
>
> It only has car, cdr, cons, if, set, equal, quote, and lambda.
>
> Does anyone know of anything smaller? I know of the Kamin interpreter, but I
> don't think it is Turing-complete (I could be wrong).
(defun turing-lisp ()
(write-string "Out of Tape."))
That's a meta-circular, fully conforming ANSI Common Lisp. (It may
not succeed well in the commercial market, though.) Turing complete?
Well, you see, it's not that it doesn't _want_ to compute more, it
just doesn't have an adequate supply of tape. As I understand it, all
true Turing machines have an infinite store, and all extant processors
have finite memory, so there's a long tradition of substituting
processors that have memory limitations of various kinds and assuming
that's "good enough". You asked for minimal, so I've ratcheted up the
limitation to its maximal point and then compiled out the excess machinery,
making my implementation much more rigid than some others might be. ;)
You also need to define what you mean by minimal implementation?
Minimal image size? Minimal source text? If source text, written in
what language? e.g., doing
(defun meta-lisp () (loop (print (eval (read)))))
is pretty small textually, but again it's written in Common Lisp to
start with so it will not be a small image size. [The above Turing
Lisp, by contrast, could easily be translated to other languages and
delivered with quite a small image.]
If your minimality metric is number of operators, something about the
set you mentioned above seems WAY too large. Doesn't a Turing Machine
take fewer? Can't you easily construct the set that is required by
Turing Machines in Lisp or a Lispy substrate, and isn't that set
radically smaller than the list you made? I'm very suspicious of the
need for CAR, CDR, CONS, and IF since you can do without these if you
just have LAMBDA. Likewise, you don't need SET since you can do
everything you need for variables with LAMBDA, too. This was the whole
point of the Lambda Calculus--that lambda was enough, no?
(defvar .true. (lambda (then else) (funcall then)))
(defvar .false. (lambda (then else) (funcall else)))
(defun .if. (truth then else) (funcall truth then else))
Examples:
(.if. .true. (lambda () 1) (lambda () 2)) => 1
(.if. .false. (lambda () 1) (lambda () 2)) => 2
(defun .cons. (x y) (lambda (selector) (funcall selector x y)))
(defun .car. (cons) (funcall cons (lambda (x y) x)))
(defun .cdr. (cons) (funcall cons (lambda (x y) y)))
Examples:
(.car. (.cdr. (.cons. 1 (.cons. 2 (.cons. 3 .false.)))))
=> 2
If you've not read about "church numerals", btw, you might find that
fun as well. It would add additional "hair" to the above.
These kinds of accomodations are painful in practice because they don't
print well and debugging is hell. Adding just the few operators you
mention really does make a Lisp way more usable. Nevertheless, if that
is what you're going after you might want to say "minimal usable lisp"
and then start to talk about the subjective quality of usability.
Frankly, I think pinning down the elusive meaning of usability (or even
starting a dialog on the topic) has a lot of merit, whereas I think the
idea of finding minimal Lisps or playing games like the above really
doesn't have much merit-->It's been done. It's cute but not very useful
as other than a chapter in an algorithms class to stretch your brain as
to "possibilities". No one ever really does this and no one misses it.
YMMV.
Kent M Pitman schrieb:
> > It only has car, cdr, cons, if, set, equal, quote, and lambda.
> That's a meta-circular, fully conforming ANSI Common Lisp. ...
...
> ... It's cute but not very useful
> as other than a chapter in an algorithms class to stretch your brain as
> to "possibilities". No one ever really does this and no one misses it.
> YMMV.
Hallo
There is a second side of this.
It comes out of the dna-computing corner. There where chromosomes
defined, binary structures of say 16-bit lenght and these are
interpreted in various ways. Some set a poor instructions set of
assembly language basics (guess I saw it on www.genetic-programming.org,
there are 30 in use and 2 for the search tree) and I assume, this could
also be done in lisp.
So it is wished, to find out a minimal set of 16 or 32 commands to pack
them in a chromosome and interpret this lisp-like. But maybe I'm totaly
wrong ...
stefan
Leon Heller <···········@hotmail.com> wrote:
> Out of curiosity I've been Googling for the most minimal implementation of
> Lisp I could find that is Turing-complete. What I came up with was Stutter:
>
> http://mitpress.mit.edu/books/FLAOH/cbnhtml/stutter.html
>
> It only has car, cdr, cons, if, set, equal, quote, and lambda.
>
> Does anyone know of anything smaller? I know of the Kamin interpreter, but I
> don't think it is Turing-complete (I could be wrong).
You might be interested in unlambda:
http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/#what_is
Its creator describes his goals as representing a cross between those of
Scheme and Intercal...
Really, though -- the obfuscation goal has obscured the minimalism goal.
I'm pretty sure you could get by and be turing complete with fewer
functions. The only problem is that the language would end up looking
much more like Scheme and be a lot easier to read.
To anyone who's never looked at these language monstrosities, it's very
amusing to follow some of the links on that page and see what kind of
lengths people have gone in what is essentially play. I spent a few
hours laughing my ass off, romping around the web looking at various
tarpit languages, after stumbling across someone's page of Hello World
in N languages, for large values of N (I think I got that link from this
froup).
Michael
In article <······························@bcect.com>,
Michael Sullivan <·······@bcect.com> wrote:
> You might be interested in unlambda:
>
> http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/#what_is
>
> Its creator describes his goals as representing a cross between those of
> Scheme and Intercal...
>
> Really, though -- the obfuscation goal has obscured the minimalism goal.
> I'm pretty sure you could get by and be turing complete with fewer
> functions. The only problem is that the language would end up looking
> much more like Scheme and be a lot easier to read.
I think minimalist turing-complete Unlambda has the apply operator,
the s and k combinators, and a function to output a character.
Actual Unlambda has a bunch more stuff (like call/cc.)
> To anyone who's never looked at these language monstrosities, it's very
> amusing to follow some of the links on that page and see what kind of
> lengths people have gone in what is essentially play. I spent a few
> hours laughing my ass off, romping around the web looking at various
> tarpit languages, after stumbling across someone's page of Hello World
> in N languages, for large values of N (I think I got that link from this
> froup).
http://99-bottles-of-beer.ls-la.net/
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
"Brian Downing" <···········@lavos.net> wrote in message
····························@sccrnsc04...
>
> http://99-bottles-of-beer.ls-la.net/
The Whitespace is implementation is really the only way to go, I think. And
so easy to read too.
http://99-bottles-of-beer.ls-la.net/w.html
>
> -bcd
> --
> *** Brian Downing <bdowning at lavos dot net>