Lambda the Ultimate

inactiveTopic The power of small ideas
started 8/7/2000; 12:36:26 PM - last post 9/12/2000; 11:35:22 AM
Ehud Lamm - The power of small ideas  blueArrow
8/7/2000; 12:36:26 PM (reads: 495, responses: 4)
The power of small ideas
This is a large idea, so I will not explore it here. But the link (from comp.lang.lisp) is to a small lisp-like interpreter. It shows how you can build up from simple primitives (it actually uses more than is needed, I think). It starts with car, cdr, cons, if, set, equal, quote, and lambda and there are examples how you can build arithematic from them. Of course you can succeed with just Lambda (the ultimate, as we all know).

I like showing (and seeing) things like that (there are many examples of simple formalisms that give you Turing-completeness). This is, of course, not the smae as 'little languages' in the sense on Bentley. The link itself is also relavent here because it is a simple interpreter, that also has garbage collection.

The book itself seems pretty cool. It deals with many subjects I am interested in. Drop me a note if you think it is NOT worth buying...


The sample programs should also be found here.


Posted to "" by Ehud Lamm on 8/7/00; 12:42:51 PM

andrew cooke - Re: The power of small ideas  blueArrow
8/8/2000; 12:11:50 AM (reads: 524, responses: 1)
Another language that takes a small idea a long way is Io (hope I've remembered that right) that's described in Finkel - it uses continuations as the fundamental control structure. I'm not saying it's a good language, but it looked pretty neat.

(thanks for all the good links recently - I've been reading Finkel's book during dead moments at work and have just added Comp. Beauty to my shopping list).

Ehud Lamm - Re: The power of small ideas  blueArrow
8/8/2000; 3:51:54 AM (reads: 569, responses: 0)
Yes, continuations are a poweful idea. It is, of course, closely related to lambda and anonymous functions.

Let me just quote the concluding remarks about Io from Finkel:

Given that continuations are very powerful, why are they not a part of every language? Why do they not replace the conventional mechanisms of control structure? First, continuations are extremely confusing. The examples given in this section are almost impossible to understand without tracing, and even then, the general flow of control is lost in the details of procedure calls and parameter passing. With experience, programmers might become comfortable with them; however, continuations are so similar to gotos (with the added complexity of parameters) that they make it difficult to structure programs. Second, continuations are not necessarily pleasant to implement. Procedures may be referenced long after they are created, and allocation does not follow a stack discipline, so it appears that activation records must be created in the heap. Luckily, circularities will not exist, so reference counts can govern reclamation of activation records. The implementation and the programmer must be able to distinguish functions that have not yet been bound to parameters (classical closures) from those that are so bound. Both are present in Io. In Figure 2.25 (on page 46), the anonymous procedure in lines 25 is a classical closure, whereas the subsidiary call to write in line 3 includes its parameters (First and WriteList Rest; Continuation). Even though continuations will never be a popular programming method, I like them because they combine several ideas you will see elsewhere in this book. The examples abound with higher-level functions (discussed in Chapter 3) and anonymous functions (also Chapter 3). Continuations can implement coroutines and LISP-style lists (Chapter 4). Finally, denotational semantic definitions of programming languages use continuations directly (Chapter 10).

andrew cooke - Re: The power of small ideas  blueArrow
9/11/2000; 9:42:58 AM (reads: 484, responses: 1)
My copy of this book (Computational Beauty of Nature) finally arrived today (link to book details was a news item here on 7th August). It seems very good (only read about 50 pages so far) - the depth varies a lot, so at times I'm skipping paragraphs and then a page later I'm having to think about each sentence. I guess that means it should appeal to a wide range of people.

So far it's covered diagonal sets, Godel numbering, the halting problem and lambda calculus - not bad for 50 pages (10 of those were Preface). A lot better than Hofstadter's GEB (unless you like all the "whimsical" bits, I guess).

Thanks for the pointer!

Ehud Lamm - Re: The power of small ideas  blueArrow
9/12/2000; 11:35:22 AM (reads: 533, responses: 0)
Great! Now we'll wait for a complete review...

But don't go bashing GEB: it is a great book.

To make this a bit more on topic, let me quote from the EOPL further reading section:

A second mind-exanding book is Goedel, Escher, Bach: an Eternal Golden Braid" by Douglas R. Hofstadter. If you haven't read this, take some time off and get acquainted with it. It is a joy to read, and will open you mind to new and exciting ways to think about recursion...