Delta, Lambda, Pi (the fraternity of calculi)
We recently had an internal presentation covering a variety of fundamental theories of computation that underly several important programming languages. Here are a few papers that might help explain those theories in more depth (if not the actual interpreters we developed):
- Foundational Calculi for Programming Languages
- Introduction to Lambda Calculus
- Making [Erlang] (Joe Armstrong’s PhD thesis)
The “foundational calculi” paper introduces both the lambda and pi calculus. It explains Church numerals, booleans, and data structures purely in terms of lambda expressions. It’s written by Benjamin Pierce, whose book Types and Programming Languages is one of the holy books of programming language theory.
Joe Armstrong’s thesis is especially interesting for this little insight into the politics of software development at large companies:
In February 1998 Erlang was banned for new product development within Ericsson—the main reason for the ban was that Ericsson wanted to be a consumer of software technologies rather than a producer.
They reversed this position a short time later, much to the relief of their bottom line. This case especially highlights the central role that niche programming languages (formalized industry jargon) play in realizing the dreams of businesses.
June 28th, 2007 at 6:31 pm
Niche Programming Languages? Is that another way of saying DSL (Domain Specific Language)? Or do you see DSLs as something completely different?
June 28th, 2007 at 7:48 pm
I think that any company that can create a programming language that embodies the very essence of their business has created a huge competitive advantage for themselves. Of course this is very hard to do and does have some downside risk. Erlang comes very close to this ideal for the telecom industry although it clearly errs on the side of being a general programming language. Such efforts should be rewarded.
June 28th, 2007 at 8:18 pm
Doug, it’s just another way of saying DSL (maybe with more emphasis on the D than the L).
Sal, good point — it can be very easy to implement a compiler/interpreter for a new language, but a very complex and difficult decision for a business to seriously invest in it. If there’s money on the line it had better have indexes.
July 20th, 2007 at 11:12 pm
great papers. the second one was an easier read. but the last one was way too long to print.