Lambda the Ultimate

The very first PLT book that I read (it was a booksale find) is quite unusual, and worthy of discussion in itself.

It is called "Programming Linguistics" by David Gelernter and Suresh Jagannathan (both were involved with Linda). (MIT Press; now out of print.)

There are two things that are unusual about this book. The first is that they have a slightly idiosyncratic model for describing the semantics of the languages they cover, called ISM (or ideal software machine).

The basic idea of this ISM is that there are two dimensions to the semantics of a language: space maps and time maps. The former maps data or instructions in a single, simultaneous space, whereas the second maps data or instructions at a particular point in space over time. (The authors interests in parallel processing languages can be seen when you fill in both dimensions and you have different instructions and data moving through the time-map in different part so of the space-map)

The second unusual thing about this book is that it is mainly a brief history of PLs, but the focus is on what they call "hero languages", PLs that they feel made a revolutionary contribution to the expressiveness of PLs. Two that are singled out are Simula 67 and Scheme.

The enthusiasm for PLT that I got from this book has stayed with me since, though, as I say, my subsquent readings in PLT have made me realize it is quite odd.

Has anyone else read this book and been influenced by it positively or negatively? Is there some other book that launched your interest in PLT?

What got me into PLT was Chris Hankin's book on lambda-calculus. It's a nice little slim and non-threatening book which talks mainly about untyped lambda-calculus, but has a section at the end about three typed lambda-calculi. Reading it gave me the confidence to try Carl Gunter's "Semantics of Programming Languages", which is a bit more demanding (and the first place I encountered category theory).

What motivated me to start reading about PLT, though, was Haskell and all the technical papers written by people who frequent the Haskell mailing list. Haskell's was the first language community I had encountered where people made arguments based on facts rather than dogma, and that was a real eye-opener for me.

Before that, I was a complete objecthead, and my favorite language was C++. I thought it was the best thing in the world because it was so complicated I felt it must have been designed by a person whose understanding of programming was so deep that I couldn't comprehend it all at once.

I was also impressed by OO because there were so many people who had opinions about it. It seemed deep. I had a book full of essays about software engineering and OOP and OO design; I think I've lost it now, but I think it was written by Berard. It talked about things like coupling and cohesion, and introduced a bunch of related terminology. Much like SGML.

The idea in my head then was that programming was a vast new frontier, which had to be attacked with new ideas and completely new methods. Such a thing is very attractive, especially when you're young, because a) nobody can tell you what to do, and if they do you know they don't have the moral authority, b) the danger of being criticized for producing low-quality work is very small, since anything is better than nothing, and c) there are lots of things to do and play with, d) you don't have to do research into what has come before.

Needless to say, I believe differently now. There are some things about programming which are new, granted, but it has a very strong connection to existing, even fairly old, mathematical work. It took me a long time to catch up on all those ideas (and I still am, of course).

And, while I think OOP can be made into an effective approach to programming, I think we already had an effective approach when OOP became popular, and OO languages are still playing catch-up. And they're not gaining...

• I think most OO advocates have that `new frontier' attitude. They will not be happy unless everything is OO-ized.

• Mathematics is a necessary tool for doing programming, and research about programming languages and programming.

• I happen to equate OO with coalgebra.

• The existing body of mathematics is not coalgebra, but rather algebra.

• Consequently, OO work which insists on `purity' finds itself without an abstract framework for reasoning..

• The result is that OO advocates who insist on purity can't do work effectively.

If you insist on pure OO reasoning, you need eventually to develop a coalgebraic foundation for mathematics. I think that is possible, and perhaps even already exists in the form of Aczel's non-foundational sets, but that is only a foundation and, anyway, I am about the only person who has ever heard of it. :)

I have that one too, though I don't think I've gotten all the way through yet. Fairly dense reading.

What motivated me to start reading about PLT, though, was Haskell and all the technical papers written by people who frequent the Haskell mailing list.

Though I've never gotten around to learning Haskell properly (I can follow code samples reasonably well in papers), a lot of exciting stuff definitely seems to come from that community. Phil Wadler has been a fav of mine for a while.

but it has a very strong connection to existing, even fairly old, mathematical work

I was amazed when I discovered how much brilliant foundational work was done in the 30s through the 60s. In a field that tends to favour the latest and greatest, it came as a surprise that some people's grandparents understood more about computation than many people do today. ;-)

I think one needs to draw a distinction between the "latest and greatest" crowd, who think newer technology will solve old problems, and the OOers who just find joy in the zen of OO.

There was time not that long ago when I thought there wouldn't be any real progress made until FP ruled the world. ;-)

It just so happens, though, that OO melds somewhat better with the kind of prosaic but fiddly stuff that most application building is about, than FP currently does, so it is easier to find your "purist" joy while making a living using OO. ;-)

I happen to equate OO with coalgebra.

Can you expand on that one? I have a vague notion what you mean, but can't quite get there. ;-)

The existing body of mathematics is not coalgebra, but rather algebra.

No problem... just reverse the arrows. ;-)

Consequently, OO work which insists on `purity' finds itself without an abstract framework for reasoning..

Though I haven't gotten through all of it myself, have you looked at the Object Calculus of Abadi and Cardelli?

already exists in the form of Aczel's non-foundational sets <snip>I am about the only person who has ever heard of it

Not true! ... I've been through Barwise and Moss's Vicious Circles twice already! ;-)

I was drawing a distinction, but not that one. The people who do useful OO work are the ones are non-purists. They're the ones who are aware of and willing to apply existing mathematical techniques to OO.

It just so happens, though, that OO melds somewhat better with the kind of prosaic but fiddly stuff that most application building is about, than FP currently does, so it is easier to find your "purist" joy while making a living using OO. ;-)

If what you're saying is that, because OO has been thoroughly adopted by industry, more practical tools and literature are available to support OO software projects, I can agree. What I cannot agree with is that those tools (including language implementations) and literature are of greater or even equal quality than/as those available for FP.

[OO = coalgebra] Can you expand on that one?

It's explained in two papers by Bart Jacobs, Objects And Classes, Co-Algebraically and Inheritance and Cofree Constructions.

No problem... just reverse the arrows. ;-)

I know you say that with a bit of tongue in cheek, but I'm afraid it's not that simple.

First, the point of having an OO foundation is to see things in a different way, `for themselves', as it were. But if you use duality to treat this problem, then you are still seeing everything through the lense of algebra.

Second, most of the existing mathematical literature is not couched in categorical terms, so to use duality you need to do some extra work and categorify it.

Third, much interesting categorical stuff (for me at least) is the higher-dimensional stuff, such as 2-categories and bicategories. (This is needed in practice anyway since it's hard to do anything useful in CT without functors and natural transformations.) There one has multiple ways of dualizing, so duality becomes less appealingly simple.

Though I haven't gotten through all of it myself, have you looked at the Object Calculus of Abadi and Cardelli?

Yes, I have it also.

I've been through Barwise and Moss's Vicious Circles twice already!

Wow, I think we are two of a kind here on LtU, then.

I haven't read Vicious Circles, though I know of it, though. I don't remember where I first learned of AFA sets, but there is a paper by Turi and Rutten which describes the duality between ZF and AFA set theory as respectively initial algebra and final coalgebra for the powerset functor: On the Foundations of Final Coalgebra Semantics.

Thanks for the references!

I know you say that with a bit of tongue in cheek, but I'm afraid it's not that simple.

I agree that "duality for free" is probably an over-sold property in CT.

Though I do think duality is a deep mathematical property, I'm frequently astounded at how intuitively-unrelated structure can be and still be formally "dual".