Lambda the Ultimate

A short audio presentation (Avi speaks for less than ten minutes, I guess), about the lessons the Ruby community should learn from Smalltalk. It's mainly about turtles-all-the-way-down, but Self (fast VMs), GemStone (transactional distributed persistence), Seaside (web frameworks) are also mentioned briefly.

Davide Sangiorgi, On the origins of Bisimulation, Coinduction, and Fixed Points.

The origins of bisimulation and bisimilarity are examined, in the three fields where they have been independently discovered: Computer Science, Philosophical Logic (precisely, Modal Logic), Set Theory.

Bisimulation and bisimilarity are coinductive notions, and as such are intimately related to fixed points, in particular greatest fixed points. Therefore also the appearance of coinduction and fixed points are discussed, though in this case only within Computer Science. The paper ends with some historical remarks on the main fixed-point theorems (such as Knaster-Tarski) that underpin the fixed-point theory presented.

There is a wealth of interesting information in this paper. Alas, it is not very easy to read, and the exposition can be improved. So this is not for beginners or outsiders, but if you are familiar with the topic the historical discussion will be of interest.

Solomon Feferman. Gödel, Nagel, minds and machines. Ernest Nagel Lecture, Columbia University, Sept. 27, 2007.

Just fifty years ago, Ernest Nagel and Kurt Goedel became involved in a serious imbroglio about the possible inclusion of Goedel’s original work on incompleteness in the book, Goedel’s Proof, then being written by Nagel with James R. Newman. What led to the conflict were some unprecedented demands that Goedel made over the use of his material and his involvement in the contents of the book - demands that resulted in an explosive reaction on Nagel’s part. In the end the proposal came to naught. But the story is of interest because of what was basically at issue, namely their provocative related but contrasting views on the possible significance of Goedel’s theorems for minds vs. machines in the development of mathematics.

This is not directly PLT related, and more philosophical than what we usually discuss on LtU, but I think it will be of interest to some members of the community.

While the historical details are interesting, I am not sure I agree with the analysis. It would be interesting to here what others make of this.

To make this item slightly more relevant to LtU, let me point out that both the LC and category theory are mentioned (although they are really discussed only in the references).

R6RS has been ratified, with approximately 2/3rds of voters in favour.

Another HOPL-III paper: Statecharts in the Making: A Personal Account by David Harel. This paper reads much different than most of the others, as the author admits to being mostly an accidental PL designer - backing into it from a mathematical perspective.

This paper is a highly personal and subjective account of how the language of statecharts came into being. The main novelty of the language is in being a fully executable visual formalism intended for capturing the behavior of complex real-world systems, and an interesting aspect of its history is that it illustrates the advantages of theoreticians venturing out into the trenches of the real world, "dirtying their hands" and working closely with the system's engineers. The story is told in a way that puts statecharts into perspective and discusses the role of the language in the emergence of broader concepts, such as visual formalisms in general, reactive systems, model-driven development, model executability and code generation.

The Statecharts language arose from the domain of avionics and real-time state modeling. The author's main goal was to turn what were visual doodles into executable models - finite-state-automata. Both UML and Rhapsody use parts of the Statecharts engine. The paper provides a good background for the subject of visual programming languages - a topic that periodically crops up on LtU. I found the emphasis on topology, as opposed to geometry, as the mathematical basis of visual programming to be of interest (though perhaps obvious to those who are more familiar with the subject):

When it comes to visuality, encapsulation and side-by-side adjacency are topological notions, just like edge connectivity, and are therefore worthy companions to edges in hierarchical extensions of graphs. Indeed, I believe that topology should be used first when designing a graphical language and only then one should move on to geometry. Topological features are a lot more fundamental than geometric ones, in that topology is a more basic branch of mathematics than geometry in terms of symmetries and mappings. One thing being inside another is more basic than it being smaller or larger than the other, or than one being a rectangle and the other a circle. Being connected to something is more basic than being green or yellow or being drawn with a thick line or with a thin line. I think the brain understands topological features given visually much better than it grasps geometrical ones. The mind can see easily and immediately whether things are connected or not, whether one thing encompasses another, or intersects it, etc.

Provides a nice refutation for the recent brouhaha of those who think math is irrelevant for process modeling - a solid mathematical foundation is even more critical for languages that concentrate on expression in unique fashions.
(Previous LtU links to HOPL-III papers)

Niklaus Wirth discusses two of his Pascal successor languages in the HOPL-III paper on Modula-2 and Oberon.

This is an account of the development of the languages Modula-2 and Oberon. Together with their ancestors ALGOL 60 and Pascal they form a family called Algol-like languages. Pascal (1970) reflected the ideas of Structured Programming, Modula-2 (1979) added those of modular system design, and Oberon (1988) catered to the object-oriented style. Thus they mirror the essential programming paradigms of the past decades. Here the major language properties are outlined, followed by an account of the respective implementation efforts. The conditions and the environments are elucidated, in which the languages were created. We point out that simplicity of design was the most essential, guiding principle. Clarity of concepts, economy of features, efficiency and reliability of implementations were its consequences.

The main influence on these languages were the Xerox Parc languages of Mesa and Cedar (which were Pascal derivatives). Mesa and Modula-2 explored modules, while Cedar and Oberon were concerned with the entire operating system experience. As Wirth states a couple of times in the paper, his main goal was to teach programming concepts, using language design to further that end, but with an eye for use in non-academic settings. He frowns on the design of modern PLs, with its lack of resource constraints and kitchen-sink approaches - expressing concern that it makes it hard to teach structured programming. He also expresses concern that operating systems are no longer a subject of research, much less integration with PL design.

(Previous LtU links to HOPL-III papers.)

Seeing as we just had a lively discussion of Stroustrup’s HOPL paper, it's more than appropriate to mention another great resource courtesy of Paul McJones: The C++ Historical Sources Archive.

Among the treasures are the source code of the Cfront releases, but there's much more there so go take a peek.

Yet another in the series of draft papers for HOPL-III. This one from Bjarne Stroustrup on Evolving a language in and for the real world: C++ 1991-2006. The paper starts the discussion at the point in time where his 1994 Design and Evolution book ended (which coincides with about the last time I used C++ on a professional basis - meaning I got some insight into what I missed out on for the last dozen years).

The talk outlines the history of the C++ programming language from the early days of its ISO standardization (1991), through the 1998 ISO standard, to the later stages of the C++0x revision of that standard (2007). The emphasis is on the ideals, constraints, programming techniques, and people that shaped the language, rather than the minutiae of language features. Among the major themes are the emergence of generic programming and the STL (the C++ standard library’s algorithms and containers).

Given the period of time covered, generics and the STL are the major highights of the paper. Lots of political discussion (the parts on Sun and Microsoft are mostly obvious, but it's amusing to see Bjarne speak out on the subjects). Much like the Design and Evolution book, this paper is worth a read by anyone interested in PL design, no matter their particular take on C++. Bjarne provides valuable insight on the forces that shape PLs, as well as providing constructive criticism.

Personally I found the discussion on C++0x the most interesting, as it reveals the issues that C++ is trying to overcome as well as the direction the language is headed. I've been tinkering with Boost of late, trying to figure out the FP facilities, but without much luck. Similar to C#3.0 and Java1.7, C++0x is proposing lambdas and a limited form of type inference for variables. But that's a minor addendum, as the paper makes clear that optional GC, concurrency and more thorough libraries are the major aspects to be addressed.

Another draft entry for HOPL-III about the The Development of the Emerald Programming Language by Andrew P. Black, Norman Hutchinson, Eric Jul and Henry M. Levy.

Emerald is an object-based programming language and system designed and implemented in the Department of Computer Science at the University of Washington in the early and mid-1980s. The goal of Emerald was to simplify the construction of distributed applications. This goal was re- flected at every level of the system: its object structure, the programming language design, the compiler implementation, and the run-time support.

This paper describes the origins of the Emerald group, the forces that formed the language, the influences that Emerald has had on subsequent distributed systems and programming languages, and some of Emerald’s more interesting technical innovations.

Worth a read for those interested in PL research topics which are still in play. Emerald explored a number of topics including distributed programming in the presence of failure; Mobile objects; Active objects; structural typing (as opposed to nominal); Static typing in the presence of open programming (shades of the ongoing work in Alice ML); Parametirized types. All of this while having performance as a top priority.

Previous links to HOPL-III papers.

Java was actually designed to have tuples from the start, but they never quite got in. At one point, I tried to add a tuple-like construct as part of JSR-65. We wanted to extend array initializers to full blown expressions. Eventually, that effort got quashed; I didn’t really resist, since the extension was painful, as such things always are in Java. We should have just done straight tuples as a separate construct - but at the time, that was frowned upon too.

Not surprisingly, Gilad thinks that tuples are great.