Lambda the Ultimate

I should probably be ashamed to admit that it was Paul Graham's promotion of Lisp as the mind-tool of the programming übermensch that made me want to give it a try. I settled on Scheme because I had GNU Guile already up and running on my Linux box at home, although I suppose Emacs Lisp would have done just as well.

I started out by reading through The Little Schemer and The Seasoned Schemer, and would recommend them to anyone at the beginner level who doesn't tire quickly of pizza. Meanwhile a CS-graduate colleague of mine was amusing himself by taking my snippets of Scheme code and rewriting them for me in Haskell. Later on he lent me his copy of Bird's Introduction to Functional Programming using Haskell, which helped move things along quite a lot. It is always useful to know people who know just a bit more than you.

Non-programming books that have helped me a great deal are Hodges's Logic and Helmös's Naive Set Theory. There may be better books on both topics, but those are the ones I read.

The venerable SICP is available online, of course, and it's still possible to hunt down the draft pdf of CTM (although I really would recommend buying it).

I found Hutton and Meijer's paper on Monadic Parser Combinators brought a lot of functional programming topics into perspective for me. Hutton's Tutorial on the universality and expressiveness of fold is also a gem. Proceed from there to Meijer, Fokkinger and Paterson's Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire.

I think I've got most of the basics of Scheme down, can any recommend a book that covers more than an overview of some of the more advanced topics like call-cc, macros, the Y combinator, etc.?

...perhaps with the guide of SICP. That will expose enough detail of the language model to make both call/cc and macros clear. As for the Y combinator, I don't have any recommendations offhand... probably time to start digging in the papers indexed on readscheme.org.

I just finished my first lisp interpreter (in perl). I found Paul Graham's Roots of Lisp to be a simple and straight forward guide. But will implementing call/cc and macros in an interpreter really give a person a sense of how to put them to good use in practice? (No doubt it'll flesh out how they really work).

As to Y: Take a look at this paper. The paper uses ML, if you want Scheme versions of the code, email me and I'll try to dig them out for you.

Y in Practical Programs

Although I don't fully understand the Y combinator yet, I found Richard Gabriel's short essay helpful.

What in God's good name does that mean?

For starters, no square roots of negative numbers:-)

Oh, and there I thought "keep it real" was an appeal for solid foundations and robust epistemology! ;)

For example, the OP might be interested in denotational semantics, because of the mapping it provides from programming languages to well-defined Math, right down to the appeal to geometric intuition regarding lattices. Assuming one is willing to acknowledge the reality of anything, how much more real than that does it get?

Speaking of which, I mentioned it the other day, but I liked Schmidt's Denotational Semantics: A Methodology for Language Development, and the first few chapters could be useful as a general intro to some formal PL topics.

Another resource I haven't seen mentioned is Frank Attanassow's Programming language theory texts online, a list of online books, lectures, tutorials etc. on programming language theory.

Frank Atanassow's PLT is no longer at that location (and his homepage listed in his LtU profile also went 404; I don't know if this is permanent or transient).

However, I did find a copy here which Frank posted on The Software Technologist wiki.

LiSP is a bit better if you are really interested in building Lisp/Scheme interpreters.

Notice that TAPL is the first theoy book mentioned: the others don't teach formal techiques.

Notice that TAPL is the first theory book mentioned: the others don't teach formal techniques.

Actually, this is not quite true. CTM gives a formal semantics for all the concepts it introduces in the main body of the book, both as an abstract machine and as a structural operational semantics. It also explains logical semantics and axiomatic semantics, and gives a nod to denotational semantics. From our experience in teaching the semantics to engineering students, we find that the level of semantics given in CTM is just about right for a practicing programmer.

I agree that EOPL is a bit weak on OOP and typing. Obviously, my feeling is that TAPL addresses those weaknesses, but it's definitely richer meat, if you will, than EOPL, while I feel EOPL will prepare the reader so that their entry into TAPL will be somewhat easier.

LiSP I appreciate mostly for its coverage of the issues in continuations and closures, but also in its treatment of issues in namespaces.

TAPL, then, seems to expand on all of these subjects, deepen them, and put them on a truly rigorous footing—but calling EOPL "informal" may be accurate in some, er, formal sense, but its treatment of algebraic methods and the CPS transformation seems quite formal to me, albeit presented informally.

So not only do I recommend the texts I mentioned, but apparently I also recommend them in the order that I mentioned them.

Lest it be misunderstood, let me clarify that I am a fan of EOPL2. I just meant that by itself it doesn't provide you with the formal notation you will find in many of the papers discussed on LtU.

I've always been interested in mathematics and have been interested in programming for about as long. So looking for the theory side of things seemed natural. However, since I was (and am) a self-taught programmer and had nothing to guide me; the mainstream dominated my view of programming. That would've been fine except there is a rather wide chasm between theory and practice for mainstream languages (C++ for me) and techniques (read OOP). While I certainly looked at non-mainstream languages (including Scheme), the language that prompted my programming theory renaissance was Haskell (admittedly Scheme was the closest language to Haskell that I knew at the time, but at the time, I was explicitly looking to learn pure FP). One of the most striking things about Haskell is how close theory and practice are. The main examples are: monads, folds and unfolds, and the Curry-Howard correspondence holding fairly strongly.

I do want to emphasize the Curry-Howard correspondence to those unfamiliar with it. Lectures on the Curry-Howard Isomorphism (pdf) is a large, comprehensive paper covering it. Google will turn up lighter articles, but some minimal familiarity with the ideas in programming language theory (or related fields) is probably required to know and appreciate what it is saying.

Haskell is also how I got interested in Category Theory, Barr and Well's lecture notes are still one of my favorite online resources. It doesn't require much of the reader, and does a reasonably good job of motivating you to find out about the things that it does assume you know.

Just a random request to finish the Moonbase tutorial.

Maybe you find this book usefull:
Syntax and Semantics of Programming Languages. It introduces denotational, algebric and axiomatic semantics.

I'm assuming you mean programming languages rather than programming. Otherwise it sounds analogous to "all you need to know about bridge-building can be learned from the first volume of the Feynman notes." I'm trying to think of how knowing about the universality of fold will help my students program their compilers...

Fold for implementing programming languages:

• Many analyses and transformations are expressible as folds
• Compositional interpreters/compilers are exactly the ones expressible as folds,i.e. if you express your interpreter as a fold, it's immediately compositional
• Folds always terminate (if their argument always terminate)
• More generally, proving that each argument is correct implies that the whole fold is correct by universality

Folds for language design:

• Folds are the only elimination form you need for a(n inductive) data type
• And they're polytypic (so a compiler can generate them automatically)
• Again, folds always terminate if their arguments do (can be used for a strongly normalizing (subset of the) language or at the type level)
• Folds have nice properties
• Folds have clear categorical and type theoretical interpretations making it easy to combine, extend, and analyse them with those frameworks
• And of course, this leads to unfolds, hylomorphisms, etc.

Two ideas that may make an interesting component or basis for a language are:
Dealing with Large Bananas and
Metamorphic Programming

I was really just making the following uninteresting observation: The OP's claim that "all you need to know about programming [which to him evidently means 'functional programming'] is folds" is absurd. Lambda is, and should remain, a forum primarily for PL theory, and PL theory is part of practical programming knowledge. However, there is much to practical programming beyond PL theory, and precise language cools flamefests like the one on OO, and avoids the appearance of arrogance and condescencion.

The OP's claim that "all you need to know about programming [which to him evidently means 'functional programming'] is folds" is absurd.

Actually, what the OP wrote was "all you need to know about functional programming (or programming in general) and programming languages can be learned from HTDP", which is rather more defensible, if one is talking about students. You were the one who raised the question of how folds apply to compilers, which was answered quite comprehensively.

But have you ever been a student at, or TAed at, an American state university?

HTDP is being used at high schools and universities, including state universities. Indications are that it gives students a better grounding for learning and understanding languages like Java and C++ than more traditional approaches.

Are there other things students might need to learn? Of course. But if you were putting together a list of core concepts they should understand well, the contents of HTDP would rank very high.

You were the one who raised the question of how folds apply to compilers, which was answered quite comprehensively.

In my opinion, the students' difficulties stem from varied and poor backgrounds acquired at a dozen universities and community colleges, and from a lack of basic engineering skills (abstraction, modeling, automation of mundane tasks, ordering of one's environment, etc.). You may reply that knowing some PLT will encourage these skills, and I would agree, but only in so far as any mathematical training teaches one to think abstractly.

if you were putting together a list of core concepts they should understand well, the contents of HTDP would rank very high.

But have you ever been a student at, or TAed at, an American state university? They are training a lot of potential programmers, and hylomorphisms (had to look that up) and folds are not even on the radar.

Well, I have in fact been a TA at an American state university. I even held the lofty position of full-time "instructor" there for a year.

I can report that catamorphisms (folds) and anamorphisms (unfolds) did cross students' radar, right in CS1.

Lest you think this is some sort of anomaly, I can also report that many schools teach catamorphisms and (list) anamorphisms by at least CS2, using terms like "visitor pattern" and "implement the Iterator interface".

I guess what you're claiming is that at most places, students are kept in the dark about the fact that visitors and iterators have any mathematical properties at all. This is probably true, but probably also suboptimal when training students who intend to engineer our software.

Well, I have in fact been a TA at an American state university. I even held the lofty position of full-time "instructor" there for a year.

Yet I notice you didn't stick around ;). Your guess about my claims is correct, but not complete. I also claim that a lack of coding skills, from varied and poor backgrounds, makes even upper-division courses more about how to interact with a programming environment than about how to reason abstractly about the structure of programs. There is a large body of "common sense" knowledge necessary to program effectively, normally learned implicitly in the course of some other task (learning about PLT, being a sysadmin, writing a numerical model). I'm claiming that at least at one place, this common sense is not being absorbed, and gets in the way of learning.

There's a classic thread that's relevant on folds, unfolds and regular programming.

In particular Neel Krishnaswami's post highlights the value of understanding these morphisms:

The reason that unfolds and folds are so convenient is precisely because they are special cases, with powerful invariants coming along for free. Better still, a fold and an unfold composed together can describe any primitive recursive function, and that's a huge class of computations, which describes almost all of the programs I've written.

It's a good exercise to transform operations in either folds or unfolds: it helps to understand better the problem being solved and the specific solutions.

Other people have said lots of worthwhile things in reponse, so I'll just mention a couple points.

1. I've TAed HTDP-based courses at Northeastern University, which is comparable to a middling flagship state university (I think, having not studied at any).

2. HTDP doesn't tell anyone about the universiality of fold. But it's all there, if you look for it.

3. Proving theorems about polytypic programming isn't going to help most programmers, regardless of their background. But the important insights are still comprehensible by anyone.

4. Finally, you should actually take a look at HTDP. It's nothing like Feynman. It's more like saying that a high school physics text can teach you all about string theory (which is ridiculous for physics).

• Wikipedia definition of lambda calculus - fairly detailed.
• Henk P. Barendregt, The Impact Of The Lambda Calculus In Logic And Computer Science - puts lambda calculus in context
• Already mentioned: Henk P. Barendregt, Introduction to Lambda Calculus
• Lloyd Allison, Lambda Calculus (interpreters) - lots of good material, including online lambda calculus interpreters.
• André van Meulebrouck's lambda articles in MacTech - very accessible
  • Lambda Calculus
  • Going Back to Church - Church Numerals
  • The Lambda Lambada: Y Dance? - Mutual Recursion
  • Deriving Miss Daze Y - "Deriving the (applicative order) Y combinator in a concrete way via fact"
• An Introduction to Lambda Calculus and Scheme - gentle but short intro which starts out defining a "chocolate-covering function".
• Kurt Nørmark, Rewrite rules for lambda calculus, part of a comprehensive set of lectures, Functional Programming in Scheme - shows connection between lambda calculus and Scheme

I think it's an excellent book to start with if you're an absolute beginner. A good balance between imperative and functional is maintained so people ingrained in imperative programming will get a gentle introduction to many new concepts. It also includes a large section on object-oriented programming covering Smalltalk, C++ and Java.

This is a truly great (and short) paper. It neatly bundles up a wide range of reasons why functional languages are interesting, and has prompted me to attack Haskell and SML more seriously on at least two occasions.

I think the link from the FAQ should be enough. But if others think we should put it on the sidebar, we can do that.

...for linking this from the sidebar. (I think some people would be more inclined to click on a link called "Getting Started" than an "FAQ", and there's a whole host of really valuable links here).

OK. I added the link to the sidebar.

...but the five that meet the immediate criteria would be:

• Why type systems are interesting
• Why type systems are interesting - part II
• Why type systems are interesting - part III: latent types
• Explaining monads
• Understanding continuations

The operational principle of code interpretation/execution refers to how the instructions are executed. My first sentence is using imperative language terminology (instructions, execution), where an imperative language is normally supposed to be interpreted or executed with a sequential or Von Neumann operational principle.

In a functional language, there should not be instructions or commands, generally, and everything is an expression, which must be evaluated. Expressions may be nested, like in ((a + b) * c), where a + b is the inner expression and x * c with x = a + b is the outer one.
For expression evaluation there may be at least two operational principles, namely data driven (eager evaluation) and demand driven or reduction (lazy evaluation).
In eager evaluation, an expression is evaluated as soon as its operands are known, hence from the inner to the outer expressions. In the above example, first a + b is evaluated, then it is multiplied by c.
In lazy evaluation, an expression is evaluated when it is needed for the final result, hence from the outer to the inner. In the above example, first there is an attempt to compute x * c, then a + b is evaluated only because it is needed. The advantage of lazy evaluation is that unnecessary operations may be skipped.

See also http://en.wikipedia.org/wiki/Lazy_evaluation

It was also used in some experimental massively parallel multicomputer in the late 80s, as an alternative to dataflow computer arrays ( see e.g., http://www.springerlink.com/content/y60648652243l31m )

LtU is not the place to cheat on homework assignments.

This isn't the right forum for your question. There's lots of spin resources here.

Intel has manuals on line.

Google for: "compiler+writer's"+guide
IBM has a great compiler writer's guide for PowerPC.

Hennessy and Patterson have some textbooks that may help with terminology. Traditionally the interface between machine code and the processor is called the "instruction set architecture."

Thanks, this looks like exactly what I needed.

I am not sure what you mean by "supporting". Some people here are interested in APL/J, but that's not a very frequent topic of discussion. This site is not for questions/answers about particular languages or tools (please see the FAQ).