Lambda the Ultimate

Online.

It's never too late to familiarize yourself with the classics.

Conrad Barski's Lisp book, Land of Lisp, is out. There's an example chapter implementing a Hunt the Wumpus remake. The book was previously mentioned with an April's 1st special, War of the Worlds.

Comments? Critiques?

Blurb:

Lisp has been hailed as the world’s most powerful programming language, but its cryptic syntax and academic reputation can be enough to scare off even experienced programmers. Those dark days are finally over—Land of Lisp brings the power of functional programming to the people!

With his brilliantly quirky comics and out-of-this-world games, longtime Lisper Conrad Barski teaches you the mysteries of Common Lisp. You’ll start with the basics, like list manipulation, I/O, and recursion, then move on to more complex topics like macros, higher order programming, and domain-specific languages. Then, when your brain overheats, you can kick back with an action-packed comic book interlude!

Along the way you’ll create (and play) games like Wizard Adventure, a text adventure with a whiskey-soaked twist, and Grand Theft Wumpus, the most violent version of Hunt the Wumpus the world has ever seen.

You'll learn to:

* Master the quirks of Lisp’s syntax and semantics
* Write concise and elegant functional programs
* Use macros, create domain-specific languages, and learn other advanced Lisp techniques
* Create your own web server, and use it to play browser-based games
* Put your Lisp skills to the test by writing brain-melting games like Dice of Doom and Orc Battle

With Land of Lisp, the power of functional programming is yours to wield.

I seem to recall seeing this list of free logic books mentioned here, but since I can't find it I guess it won't hurt to (re)post the link.

The manuscript of the book Computational Semantics with Functional Programming by Jan van Eijck and Christina Unger, as well as related software, is available online.

The introductory chapters are probably going to be unnecessary for LtU readers, but once things get going there is a lot to learn here if you are interested in formal semantics of natural language, especially in the Montague-style. And if this doesn't ring a bell - just search for "continutation" in the manuscript, and be prepared to meet old friends (you know who you are) in a new context.

If the contributing editors will neglect their duties, LtU will wither and die. Hint, hint.

Certified Programming With Dependent Types

From the introduction:

We would all like to have programs check that our programs are correct. Due in no small part to some bold but unfulfilled promises in the history of computer science, today most people who write software, practitioners and academics alike, assume that the costs of formal program verification outweigh the benefits. The purpose of this book is to convince you that the technology of program verification is mature enough today that it makes sense to use it in a support role in many kinds of research projects in computer science. Beyond the convincing, I also want to provide a handbook on practical engineering of certified programs with the Coq proof assistant.

This is the best Coq tutorial that I know of, partially for being comprehensive, and partially for taking a very different tack than most with Adam's emphasis on proof automation using Coq's Ltac tactic language. It provides an invaluable education toward understanding what's going on either in LambdaTamer or Ynot, both of which are important projects in their own rights.

Please note that Adam is explicitly requesting feedback on this work.

Barry Jay has recently published a book on the Pattern Calculus (which has been discussed before).

The pattern calculus is a new foundation for computation, in which the expressive power of functions and of data structures are combined within pattern-matching functions. The best existing foundations focus on either functions, as in the lambda-calculus, or on data structures, as in Turing machines, or on compromises involving both, as in object-orientation. By contrast, a small typed pattern calculus is able to support all the main programming styles, including functional, imperative, object-oriented and query-based styles, and there is evidence that it can support a language for Web services, able to exploit data structures about which almost nothing is known.

The book covers the operational semantics of both functional and OO features, as well as static and dynamic pattern-matching. Then it covers type systems necessary to deal with all the wild polymorphism thus gained - in rather readable fashion. Then it covers bondi, a programming language based on ML, Java and (lots of!) pattern-matching.

Larry O'Brien recently interviewed three of the Gang of Four about their seminal work on patterns. Larry teased the interview's readers for awhile, but he eventually asked the pressing question that most language designers ask and debate about patterns ;) Here it is:

Larry: GoF came out relatively early in the ascent of OOP as the mainstream paradigm and, for better or worse, "patterns" seem to be associated with OO approaches. You even hear functional and dynamic advocates boasting that their languages "don't need" patterns. How do you respond to that?

Erich: Just as an aside, it is also easy to forget that we wrote design patterns before there was Java or C#.

Ralph: Some of those languages don't need some of the patterns in Design Patterns because their languages provide alternative ways of solving the problems. Our patterns are for languages between C++ and Smalltalk, which includes just about everything called "object-oriented," but they certainly are not for every programming language. I don't think anybody actually says that programmers in other languages don't need patterns; they just have a different set of patterns.

Erich: Design patterns eventually emerge for any language. Design déjà-vu is language neutral. While these experiences are not always captured as patterns, they do exist. The design principles for Erlang come to mind.

Larry: Where would a person go to learn about patterns for dynamic and functional languages? Who's making good contributions?

Ralph: If by "dynamic" you mean dynamic object-oriented languages like Smalltalk, Ruby or Python, then our patterns are applicable. Functional languages require different patterns, but I don't know who is working on them.

Note: At the end of the interview, Erich says that they tried refactoring the patterns into new categories in 2005. The draft breakdown he provides (accidentally???) takes out Memento, Chain of Responsibility, Bridge, Adapter, and Observer.

As I said above these are just notes in a draft state. Doing a refactoring without test cases is always dangerous...

UPDATE: The Gang of Four have an accompanying article for the interview that they wrote as a group. See A Look Back: Why We Wrote Design Patterns: Elements of Reusable Object-Oriented Software.

Peter Seibel's book Coders at Work is apparently available for purchase, so this is a good time to say a few words about it here.

The book consists of interviews with several illustrious programmers about their personal histories, programming style, likes and dislikes and so on. Among the interviewees are several who are well known in programming language circles and are mentioned regularly on LtU, for example Brendan Eich, Joe Armstrong, Simon Peyton Jones, Peter Norvig, Guy Steele, Dan Ingalls, and Ken Thompson. The interviews go into more detail and depth than I dared hoped for or expected, though as is inevitable you end up annoyed that a question you really wanted answered did not come up.

I am sure LtU readers will want to read these interviews for themselves and revel in the technical miscellanea (I read them on a long flight from the US to Australia...), so I am not going to post a detailed review with spoilers. It would be more fun to hear the questions you guys would have asked had you conducted the interviews (and to know which answers you want to quibble with!) So in lieu of a long and tedious review, here are a few LtU-worthy things that caught my attention in a couple of the interviews that I think will interest LtU members.

For some reason I started by jumping to the interview with Dan Ingalls. It turned out to contain many nice morsels to chew on. Dan emphasizes an attribute that might be called programmability all the way down (he is a Smalltalk guy, so that's not such a surprise, I guess): "You should be able, in a computing environment, to zero in on music and musical synthesis and sound and just understand how the whole thing works. It should be accessible. The same thing with graphics." Not surprisingly, Ingalls admits to having an exploratory programing style (in contrast to Knuth who wrote TeX in a notebook...), which probably influenced the types of language he found himself working on. This seems to be the case for several other interviewees as well. Interestingly, Ingalls recalls being influenced by APL. The interactive environment was part of it, but significantly he also mentions the influence on him of the fact that it is expression oriented and not statement oriented like Fortran.

And oh, Ingalls also opines on the age old question: should programmer education begin with assembly. His answer: No. As you would expect, other interviewees probably feel differently.

The interview with Knuth is also very interesting, as you might expect. Here are a few of the things I picked up on in his interview. From his description, it would seem that Knuth was doing his own style of test driven development, though for some reason this angle is not elaborated on in the interview. While Ingalls ponders how to expose kids (and adults) to programming, and Norvig reflects on the failures of end-user programming, Knuth recites his observation that 2% of people are natural born programmers (my words) since they "really resonate with the machine." Perhaps surprisingly Knuth is here concerned with being attuned to the way the machine "really works," not to algorithmic thinking in a general sense. Perhaps, I wonder, what really unites programmers is a compulsion to program: Knuth admits to having the need to program even before having breakfast.

Knuth has a challenge to programming language designers. He claims that every time a new language comes out it cleans up what's already understood, and then adds something new and experimental. How about "setting our sights lower" and aiming for stability. "It might be a good idea," he says. I am pretty sure some here will argue that we have too much lowering of expectations already...

What really resonated with me, and with the LtU ethos, was Knuth lament about people not going back to the original papers and source materials. He puts it simply and powerfully: "I wish I could... instill in more people the love that I have for reading original sources... I was unable to pass that on to any of my students." LtU always had a history department, and going back to historical papers is something I personally love doing. Maybe Knuth should guest blog on LtU... Really! He talks about having collections of source code, compilers in particular - we want to know more!

Finally, let me note the nice contrasts you find among the interviewees. Naturally, these manifest themselves in differing opinions about C. While Knuth sees the C pointer as one of the great advances in computer science, Fran Allen argues that "C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine."

And if that's not a call to action to all you programming language fanatics, what is?

Disclosure: I was asked to provide a blurb for the cover of the book, and so read the interviews before the book was published. Other than that I had no involvement with the creation of the book, and I have no stake in its success.

Relations of Language and Thought: The View from Sign Language and Deaf Children provides an interesting angle on the Sapir-Whorf hypothesis that we periodically discuss on LtU. A small sample from Google Books is available.

...Hypothesis concerning language and thought...:

• Language equals thought. Perhaps the simplest view of language and thought is that they are essentially the same thing. This position is most frequently ascribed to American behaviorists, and especially to John Watson, who argued that thought is just subvocal speech.
• Language and thought are independent. This view, most often attributed to theorists like Noam Chomsky and Jerry Fodor, suggests that the development of language and the development of cognition are distinct, dependending on different underlying processes and experiences.
• Language determines thought. In the form usually identified with the linguistic determinism and linguistic relativity theories of Sapir and Whorf, this perspective directly entails a correlation between language skill and cognitive skill. One implication of this view is that individuals who have "inferior" (or superlative) language are expected to have "inferior" (or superlative) thought. Implicitly or explicitly, such a perspective has been used as a rationale for an emphasis on spoken language for deaf children by those who have seen sign language as little more than a set of pragmatic gestures.

...The more interesting question... is whether growing up with exposure to a signed language affects cognition in a way different from growing up with a spoken language. Indeed, that is one of the fundamental questions of this volume. While we fully agree... that any strong form of the Sapir-Whorf position appears untenable, it also seems clear that language can affect and guide cognition in a variety of ways. Much of what a child knows about the world, from religion to the habitats of penguins, is acquired through language.

Sign language is an obvious candidate for linguistic study, since the mode is visual as opposed to oral/aural. The summary of one of the authors is telling:

The conclusion that American Sign Language (ASL) is an independent, noncontrived, fully grammatical human language comparable to any spoken language has been supported by over 30 years of research. Recent research has shown that ASL displays principles of organization remarkably like those for spoken languages, at discourse, semantic, syntactic, morphological, and even phonological levels. Furthermore, it is acquired, processed, and even breaks down in ways analogous to those found for spoken languages. The similarities between signed and spoken languages are strong enough to make the differences worth investigating. In the third section of this chapter, I will argue that although there are differences in detail, the similarities are strong enough to conclude that essentially the same language mechanism underlies languages in either modality.

On a programming language level, I can't help but think that sign language offers valuable clues into the nature of visual PLs (though I haven't quite nailed down any specifics). ASL on Wikipedia informs us that signs can be broken down into three categories:

• Transparent: Non-signers can usually correctly guess the meaning
• Translucent: Meaning makes sense to non-signers once it is explained
• Opaque: Meaning cannot be guessed by non-signers

With the majority of signs being opaque. As much as those who design visual languages would like them to be intuitive - falling into the Transparent and Translucent category - I figure you still have to end up using many signs that are only meaningful internally to the language at hand.

On a personal level, I have recently been attempting to delve into ASL. I've almost got the alphabet and numbers down, and have a vocabulary of about 100 additional signs - which probably means that I'm at the proficiency level of somewhere between ankle biter and sesame street. I do find it to be a fascinating language. I noticed when I was looking at the course offerings for college (my son started university this year) that ASL is now offered for foreign language credit (wish it had been offered when I was a student all those years ago).

Just finished reading In the Land of Invented Languages, by Arika Okrent. It makes an accessible read for many topics in language.

Natural languages may be less universal than music and less precise than programming languages, but they are far more versatile, and useful in our everyday lives, than either. Ambiguity, or fuzziness of meaning, is not a flaw of natural language but a feature that gives it flexibility and that, for whatever reason, suits our minds and the way we think. Likewise, the fact that languages depend on arbitrary convention or cultural habit is not a flaw but a feature that allows us to rein in the fuzziness by establishing agreed-upon meanings at different levels of precision. Language needs its "flaws" in order to do the enormous range of things we use it for.

Aside from this passage, the book barely mentions PL's at all. But programming languages are, by definition, invented languages (and, no, Perl does not qualify as natural), I think there are many parallels to be drawn. Most language inventors don't do it for the money - creating PL's is not a way to untold wealth. And there are a thousand invented (and programming) languages, so the chance of success is rather slim (and mostly accidental). The book itself is more an informal narrative that goes between personal experience, to examining the persons behind the languages, and on to a more critical analysis of the languages spotlighted. Although there are over 500 listed languages in the appendix, there is only in depth coverage of a dozen or so. The major periods covered:

• Enlightenment: John Wilkins and his Philosophical Language are the main subject of this period. The 17th century saw the widespread adoption of mathematical conventions, and there was a belief that a language could be designed that removed ambiguity - words would convey meaning exactly as intended. That belief is still a central tenet in much PL design.
• Idealism: Here we have Zamenhoff and Esperanto trying to bring about peace, love and understanding by sharing a common language. A couple of WWs would tell us that such utopian visions were not quite achieved. But Esperanto has been the most successful invented language in terms of usage. Most of the languages of this period were designed to be easier to learn, and were a mixture of languages - rather than striking out in bold semantic/syntactic fashion. Of course, we have PLs that want to borrow features from many different sources and strive to be easy to learn. Then again, efforts to reduce the number of languages usually have the effect of just creating more languages.
• Symbols: Charles Bliss and Blissymbolics with emphasis on non-oral language in this section covering symbol language and sign language. Visual PLs is what I thought of here
• Logic: Brown and Loglan were started as a roundabout thought experiment for Sapir-Whorf. But the only answer it would provide would be: what if, instead of trying to get AI from programming languages, we used something like a programming language for speaking, writing and communicating in the large.
• Esoteric: Klingon and other Conlang's are discussed in this section, with the emphasis on language as art or puzzle. Esoteric PLs are similar in spirit.

Lot's of tangential topics that are fun (Chinese writing, Hebrew, Tolkien, etc) and covers some very colorful characters. Not sure if PL designers are quite so eccentric, though I suspect it's only because we are still early in the game for PL evolution.