Lambda the Ultimate

We've seen the Santa Claus problem before, but that was a few Xmas's ago.

Jingle Bells: Solving the Santa Claus Problem in Polyphonic C#

O'Reilly has an article, Introducing Comega, which covers some of the basic features of Cω: streams, "choice" and "nullable" types, anonymous structs and syntax support for XPath and relational query constructs.

I begin to see the point of language integration for XML processing, although the thought of using XML for general data storage and management still gives me the shivers...

Non-determinism in functional languages. Sondergaard and Sestoft. The Computer Journal, Volume 35, Issue 5, pp. 514-523. 1992

The introduction of a non-deterministic operator in even an very simple functional programming language gives rise to a plethora of semantic questions. These questions are not only concerned with the choice operator itself. A surprisingly large number of different parameter passing mechanisms are made possible by the introduction of bounded non-determinism. The diversity of semantic possibilities is examined systematically...

A very useful paper if you are interested in this sort of thing. Thinking of non-determinism helps calrify muddled thinking about properties such as referential transparency.

The version I found online, alas, is a set of tiff image files, one for each page...

• Formula Engine Rewrite is an amusing story of how real software gets developed. In this case, a language processor inside Lotus Notes. VM hacking and the like...

• Waterstone's fires 11-year-employee for blogging. I wouldn't normally link to such an item, but since we all tend to buy books, and I am a great fan of bookstores, allow me to suggest our UK readers boycott Waterstones's.

Page 4 of the lecture notes from Mitch Wand's first Principles of Programming Languages lecture:

When looking at a language, we will always ask four questions. As we proceed through the course, we will ask these questions in more and more sophisticated ways; I’ll show some of these subquestions now, even though we haven’t yet covered enough to understand what they mean:

1. What are the values in the language?
   • What are the values manipulated by the language, and what operations on those values are represented in the language?
   • What are the expressed and denoted values in the language?
   • What are the types in the language?
2. What are the scoping rules of the language?
   • How are variables bound? How are they used?
   • What variables are in scope where?
3. What are the effects in the language?
   • Are there side-effects in the language?
   • Can execution of programs have effects in the world?
   • Can execution of programs have effects on other programs?
   • Can execution of a program fail to terminate?
   • Are there non-local control effects in the language?
4. What are the static properties of the language?
   • What can we predict about the behavior of a program without knowing the run-time values?
   • How can we analyze a program to predict this behavior?

What do you consider the fundamental properties of a programming language?

Stanford technical report number 26 by George E. Forsythe, 1965.

I consider computer science to be the art and science of exploiting automatic digital computers, and of creating the technology necessary to understand their use. It deals with such related problems as the design of better machines using known components, the design and implementation of adequate software systems for communication between man and machine, and the design and analysis of methods of representing information by abstract symbols and of processes for manipulating these symbols. Computer science must also concern itself with such theoretical subjects supporting this technology as information theory, the logic of the finitely constructable, numerical mathematical analysis, and the psychology of problem solving. Naturally, these theoretical subjects are shared by computer science with such disciplines as philosophy, mathematics, and psychology.

So I think it's really important that we approach metaprogramming with caution. I think Guido has been right to resist macros. Not because they are necessarily wrong, but because we haven't yet figured out how to do them right. And maybe we never will, maybe source code simply isn't the right level for abstractions. I think it's good that Python doesn't do tail-call elimination; it seems like a nice feature, but in subtle ways it makes the language harder. And I think continuations could lead to bad things. There are wrong paths on the road to higher-level programming. (Though in some ways I also feel the opposite: tell us not to shoot ourselves in the foot, and expect us to listen, don't assume we'll abuse every feature that exists; there's always a tension in these design choices.)

This deserves more attention than I can give it right now, but I am sure others here will want to comment.

Simon Peyton Jones book on the Implementation of Functional Programming Languages, circa 1987, is available online.

This book is about implementing functional programming languages using lazy graph reduction, and it divides itnto three parts.



The first part describes how to translate a high-level functional language into an intermediate language, called lambda calculus, including detailed coverage of pattern-matching and type checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as super-combinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance...

via the Haskell mailing lists. I've seen lots of references to this work, as it was one of the seminal works in the development of the Haskell programming language. But I can't find where it was directly discussed on LtU before.

If you feel like nominating us, or voting for us - go ahead...

JoCaml

The JoCaml system is an experimental extension of the Objective-Caml language with the distributed join-calculus programming model. This model includes high-level communication and synchronising channels,mobile agents, failure detection and automatic memory management. JoCaml enables programmers to rapidly develop distributed large-scale applications, using both Objective-Caml ease of programmation and extended libraries, and the join-calculus distributed and concurrent features.

Mentioned on LtU before, but never in a separate story.

Could become Erlang-killer, if were not stopped for some reason.

Definitely worth trying, if only for ideas on how to bring powerful concurrency/distribution to a mature language.