Sunday, August 05, 2012

Historical note: Algol 60 was an early metaprogramming lang.

Some literature browsing this week brought me back to Algo 60, and for some reason, instead of blowing it off as an old dead call-by-name language, I read a bit more this time. Perhaps what caught my eye was a statement by Reynolds that Algo 60 has first-class functions and stack allocation, two features that are difficult to mix in a safe way. So I read chapter 19 of Theories of Programming Languages by Reynolds, which then pointed me to On the Orthogonality of Assignments and Procedures in Algol by Weeks and Felleisen.

It turns out that Algo 60 was an early meta-programming language in that it provided two stages of computation. The first stage was essentially a lambda calculus (pure and functional) whereas the second stage is a simple imperative language. This reminds me of C++, which has a nearly pure functional language in its template system as the first stage and an imperative language in its second stage. Algol 60 is also similar to MetaML in that the type system helps enforce the distinction between the two stages, with expressions and statements of the second stage marked as phrase types, analogous to the code type of MetaML.

With regards to Algo 60's first-class functions and stack allocation, it's no wonder that the combination doesn't cause trouble because they don't exist at the same time in Algo 60: functions live in stage 1 and stack allocation occurs in stage 2.

On the one hand, I'm intrigued by Algo 60's 2-stage design, and think that it could handle a very large number of the programming situations that I care about. On the other hand, my default position regarding language features is that they should be first class, so I find it disturbing that functions are not first-class in Algo 60's second stage (only in it's first stage).


  1. Hi, it seems a pretty interesting characteristic, I know of a expansion of it called MOBULA (Module Building Language) and was created by ICT (International Computers and Tabulators) in 1968 to be run in Simulations in the ICT1900 range of computers.
    I didn't know it had stack allocation, that sounds pretty interesting.
    Thanks for sharing your knowledge.

    1. You're welcome, and thanks for your comment!