Lambda the Ultimate

With the recent popularity of the comparison between PLs and Religions (reddit, slashdot), I thought it'd be mildly amusing to see what other comparisons were out there on the intarweb.

Here's the list for the meme that I collected of If Programming Languages were ...

• Religions
• Cars
• Boats
• Women
• Girlfriends
• Subcultures
• Mixed Drinks
• Music
• Rock Bands
• Art
• Languages
• Christmas Songs

Probably others that I missed. (Note: There's probably material in here to offend all). (Personally, I think the obvious missing comparison is If Programming Languages Were Tools. I nominate Assembler as the Stick, being the most primitive).

For those who like their PL History presented in avante guard beat poetry, a video of Steele & Gabriel's 50 in 50 speech at JAOO is made to order. Or as the link says:

A fun, artistic and enlightning presentation full of interesting facts - and who better to do it than Richard P. Gabriel and Guy L. Steele (the great Quux). Nothing more to say than the rallying cry; More cowbell!

Passing aside the Stephen Wright comic delivery of the two speakers, there are a lot of interesting thoughts, though very few are dwelled on. I think the most interesting things were the languages that they chose as expositions for the major ideas that they covered. Here's the ones that I picked out (though I ended up with only 49):

Do Loops	Fortran (Pascal,APL)	Guarded Commands	Algol-68
Array Origin	C, Fortan, Pascal, APL	Extensible Language	PPL
Domain Specific Language	APT	Structured Programming	BLISS, INTERCAL
Text vs. Environment	Algol-60, Lisp, Smalltalk	Language as Educational Tool	Logo
Stack Machines	Befunge (SECD Machine, Forth)	Formal Dynamic Semantics	SECD
Data Parallelism	APL	Enumerated Types	Pascal
Coercion	PL/I (Fortran-V)	Backtracking and Theorem Proving	Conniver (Prolog)
Hierarchical Records	COBOL	Argument Handling	Common Lisp, Ada, Python (VB, C#, Suneido, PL/pgSQ)
Pointers & Lists	IPL-V	Coding in Natural Language	Perligata (COBOL, Hypercard)
Parsing	Yacc (LR1, Recursive Descent)	Computational Drama	Shakespeare
Linked Records	AED	Reasoning	Prolog
Mathematical Syntax	MADCAP, MIRFAC, Kleerer-May System	Type Declarators	C
Line Numbers	Basic (Focal, APL)	Data Abstraction	CLU, Alphard
Visual Languages	Piet	Dynamic vs. Lexical Scoping	Scheme
Pattern Matching & Replacement	COMIT, SNOBOL	Knowledge Representation	KRL (Conniver, Microplanner)
Branding	Ada (COMIT, SNOBOL, TRAC)	Stream Processing	Lucid
Dynamic Languages	AMBIT/L	Generic Functions	Common Lisp
Program as Data	Lisp	Reflection	3-Lisp
Macro Processor	TRAC, ML/I, Limp, M4	Metacircular Interpreters	Lisp
Call By Name vs. Call By Value	C, Algol-60	Functional Programming	KRC
Dangling Else	Algol-60	Control Parallelism	Occam
Formal Static Semantics	Algol-68	Domain Specific Languages	HQ9+, MUMBLE
Algebraic Formula Manipulation	Formac (Macsyma, Mathematica)	Build Languages	Make, Ant, Rake (JCL)
Message Passing	Smalltalk (C++, C#, Java, Flavors, Common Loops, CLOS, Scheme, Dylan, Simula, Self)	Scripting	Perl
Objects	Simula (Smalltalk, C++, Java)

Courtesy of my shiny new commute, I have been listing to various podcasts, including Software Engineering Radio. A while back, they had an interview with Dan Grossman on his OOPSLA 2007 paper, which I have not seen discussed here.

The Transactional Memory / Garbage Collection Analogy is an essay comparing transactional memory with garbage collection based on the analogy:

Transactional memory (TM) is to shared-memory concurrency
as
garbage collection (GC) is to memory management.

Grossman presents the analogy as a word-for-word transliteration of a discussion of each of the technologies. (Hence the "fun" category.)

(As an aside, Grossman does not address message-passing, but says, "Assuming that shared memory is one model we will continue to use for the foreseeable future, it is worth improving," which is probably a correct assumption.)

One point that he does make is that

[This essay] will lead us to the balanced and obvious-once-you-say-it conclusion that transactions make it easy to define critical sections (which is a huge help in writing and maintaining shared-memory programs) but provide no help in identifying where a critical section should begin or end (which remains an enormous challenge).

The one serious weakness of the analogy, to me, is that GC does not require (much) programmer input to work, while TM does.

Although some parts of the analogy are strained, there are some interesting correspondences.

As a follow up to the previous post, check out how Chung-chieh Shan applied regions to a seemingly unrelated problem. His post begins by explaining how automatic (numerical) partial differentiation can be implemented, and goes on to show how to use regions to avoid mixing-up the variables being differentiated.

Just a quick reminder -- the 2008 ICFP Programming Contest starts tomorrow.

Maker Faire was fun, but you can read all about it on numerous web sites and blogs. While I enjoyed the Coke + Mentos demonstration like everyone else, some things caught my eye in particular and may also amuse LtU readers.

Talking to the guys demoing the CNC machines I discovered G Code which turns out to be the main machine languages used to control the CNC machines. It was cool to meet people who actually wrote their own software to emit or/consume G codes (the styrofoam CNC machine was way cool).

I also enjoyed The Art of Motion Control sculpture, since the text said "Path designs using custom LISP routines running within AutoCAD." I think that was the only one explicitly mentioning Lisp. At least, that was the only one I saw...

Any cool language references I missed?

Conrad Barski has posted a sneak peak from his upcoming Lisp textbook/comic: Land of Lisp.

The first slides may seem unrelated, but boy does the message sting when you reach the ending...

FPers will be quick to note, of course, that this being April Fools' Day the whole thing is a joke and we can all go back to Haskell...

You can get soup in a can. You can get bread in a can. Now the long wait is over! You can finally get Lambda Calculus in a can...Project LambdaCan takes [the Lambda Calculus] and implements it on a microcontroller better suited to the most mundane of tasks, like running a vending machine or microwave oven. And it sticks the microcontroller in a can that you can connect to your PC using a USB cable.

For those that are both language geeks and hardware geeks...

A Dialogue on Infinity, between a mathematician and a philosopher. Alexandre Borovik and David Corfield.

A new blog... From the first post:

The project concentrates on one of the principal purposes of the Exploring the Infinite Program:

To understand the nature of and the role played by conceptualizations of infinity in mathematics.

It will be shaped as a dialogue between a mathematician (AB) and a philosopher (DC) and will address one of the central paradoxes of mathematics:

why are most uses of infinity in mathematics restricted to the recycling of a small number of “canonical” and ubiquitous structures?

...To put the study of infinity on a firm basis, we first have to discuss the issue of the identity and “sameness” of mathematical objects: infinity of what?

This is pretty far out for LtU, but I suspect it will interest some more philosophically inclined readers. They will look at a number of disciplines, including computer science.

(I feel like maybe even "Theory" is not theoretical for this. Therefore I am also calling it "Fun".)

While Anton was waxing about Church & Turing, I figured that Occam's Razor would be the type of proof one would postulate when giving the nod to Lambda Calculus over Universal Turing Machines. This leads inexorably to the question of what is the smallest (as measured in binary bits) Turing Machine that can possibly be constructed. John Tromp provides an answer to this question in his always fun Lambda Calculus and Combinatory Logic Playground:

Pictured you can see the 210 bit binary lambda calculus self-interpreter, and the 272 bit binary combinatory logic self-interpreter. Both are explained in detail in my latest paper available in PostScript and PDF. This design of a minimalistic universal computer was motivated by my desire to come up with a concrete definition of Kolmogorov Complexity, which studies randomness of individual objects. All ideas in the paper have been implemented in the the wonderfully elegant Haskell language, which is basically pure typed lambda calculus with lots of syntactic sugar on top.

Interestingly, the version based on the Lambda Calculus is smaller than the one on Combinators. A statement I found of interest in the paper about PL's:

Although information content may seem to be highly dependent on choice of programming language, the notion is actually invariant up to an additive constant.

Not sure if that statement means that PL research is ultimately doomed. :-)