Lambda the Ultimate

I'm pleased to announce that we are planning a celebration for Mitch Wand's 60th birthday!

From the MitchFest home page:

Northeastern University is hosting a special Symposium in celebration of Dr. Mitchell Wand's 60th birthday and honoring his pioneering work in the field of programming languages. For over 30 years Mitch has made important contributions to many areas of programming languages, including semantics, continuations, type theory, hygienic macros, compiler correctness, static analysis and formal verification.

After receiving his PhD from MIT in 1973, Mitch taught at Indiana University where he and colleague Daniel P. Friedman wrote the first edition of their seminal text, Essentials of Programming Languages. Described by a reviewer as "so influential that the initials EOPL are a widely understood shorthand," the text is now in its third edition from MIT Press. Mitch joined the faculty of Northeastern University in 1985 and has been a leader in the College of Computer and Information Science. In 2007, Mitch was inducted as a Fellow of the Association for Computing Machinery.

Please join us at Northeastern on August 23rd and 24th as we celebrate this personal milestone and pay tribute to a great computer scientist, researcher, teacher and colleague, Dr. Mitchell (Mitch) Wand.

LtU regulars will recall that we've discussed DanFest 2004 here before, as well as the talk videos.

MitchFest is open to the public and coordinated with Scheme Workshop 2009, which will be at MIT on August 22nd (the same weekend). More event information, including registration, is available on the MitchFest home page. Following the Symposium, we will be publishing a special edition of HOSC as a Festschrift in honor of Mitch.

We will post a schedule on the web site soon, but for now you can view the preliminary list of papers in the Call for Participation.

Update: added link to HOSC.

...a domain specific language for simulating football. ... We have used Soccer-Fun in teaching during the past four years. We have also experience in using Soccer-Fun for pupils in secondary education. ... It engages students to problem solving with functional programming because it allows them to compete at several disciplines: the best performing football team can become champion of a tournament; the best written code can be awarded with a prize; students can be judged on the algorithms used. This enables every student to participate and perform at her favourite skill. ... It can be implemented in any functional programming language that supports some kind of windowing toolkit.

Teaching Functional Programming with Soccer-Fun (pdf)

Ross Anderson and Roger Needham, 1995. Programming Satan’s Computer. In J. van Leeuwen, editor, Computer Science Today, LNCS 1000, pages 426-440.

Cryptographic protocols are used in distributed systems to identify users and authenticate transactions. They may involve the exchange of about 2–5 messages, and one might think that a program of this size would be fairly easy to get right. However, this is absolutely not the case: bugs are routinely found in well known protocols, and years after they were first published. The problem is the presence of a hostile opponent, who can alter messages at will. In effect, our task is to program a computer which gives answers which are subtly and maliciously wrong at the most inconvenient possible moment. This is a fascinating problem; and we hope that the lessons learned from programming Satan’s computer may be helpful in tackling the more common problem of programming Murphy’s.

Incidentally, the first edition of Anderson's book, Security Engineering, Wiley, 2001, is available for download.

Michel Ingham, Robert Ragno, and Brian Williams, A Reactive Model-based Programming Language for Robotic Space Explorers, Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics and Automation in Space, Montreal, Canada, June 2001.

Model-based autonomous agents have emerged recently as vital technologies in the development of highly autonomous reactive systems, particularly in the aerospace domain. These agents utilize many automated reasoning capabilities, but are complicated to use because of the variety of languages employed for each capability. To address this problem, we introduce model-based programming, a novel approach to designing embedded software systems. In particular, we introduce the Reactive Model-based Programming Language (RMPL), which provides a framework for constraint-based modeling, as well as a suite of reactive programming constructs. To convey the expressiveness of RMPL, we show how it captures the main features of synchronous programming languages and advanced robotic execution languages.

Reactive programming has been discussed on LtU quite a bit in the past. Functional reactive programming, in particular, has got a lot of attention. But I don't think we've covered reactive model-based programming before. This is an interesting approach that combines constraint-based modeling with reactive programming, and compiles programs down to hierarchical constraint automata for execution. Whereas reactive languages like Esterel focus on manipulating signals, RMPL works by manipulating (potentially hidden) system states.

Given that Unix won, I think it's interesting that dynamic languages make very little use of the dynamic linking and loading infrastructure provided by modern free Unixes such as Linux and the BSDs.

Most dynamic PLs opt to implement "dynamism" (i.e. redefining stuff, loading code at runtime) with application-specific data structures (e.g. Lisp: red-black trees for uniquifying symbols, function pointers and indirect function calls), and they do so solely at runtime (mostly using interpreters and JITs, although Scheme, one of the most advanced dynamic languages, is increasingly illuminating the possibilities of static, independent compilation of dynamic programs).

(Metaprogramming at runtime is perilous, as it is easy to mix up phase distinctions, something we can expect newer dynamic programming languages to discover in a decade (of course we don't know which decade.))

Link-time is mostly ignored. And yet, under Linux with its heavy use of shared objects, one cannot even start a single program without invoking the dynamic linker.

But some people, even some computer programmers, don't know how linkers work and what they do. Basically, a modern linking file format, such as ELF, is a declarative way to construct the memory image of a running process, with lots of features for dynamic customization of the image construction process (ELF even contains a customization hook called "program interpreter" in every executable!).

Likewise, modern compilers and runtime systems such as GNU C contain sophisticated features aimed squarely at dynamic languages: weak symbols for runtime redefinability (used by libc's malloc and in the Linux kernel, for example), computed gotos, nested functions, and increasingly, GC. And there is evidence that dynamic compilation and linking of C snippets is accepted and used in modern systems software.

I have collected some links to these topics, and would be interested to hear of languages and systems that you know that exploit them.

• Linkers and Loaders. A very well-written book with broad coverage of the topics discussed, that is available for free.
• The Linux Program Library HOWTO talks about dynamic loading under Linux.
• Executable and Linkable Format (ELF) specification, 60 pages of highly compressed information in best Bell Labs style.
• ELF and ABI Standards. These specifications describe the actual layouts of things such as stack frames and ELF data structures for different CPUs.
• Shared library call redirection via ELF PLT infection. This article shows a technique that could be used to implement a REPL and other important dynamic language features solely through link-time operations.
• ELF: From The Programmer's Perspective: "Combined with appropriate tools, programmers can use ELF to control the flow of execution at run time."
• How to Write Shared Libraries, an in-depth look by glibc's Ulrich Drepper (thanks, kkourt).
• Series of articles on linkers by Ian Lance Taylor, the author of the gold linker.

(Updates: added 3 ELF links; added Drepper; added Taylor)

Fully-parameterized, first-class modules with hygienic macros, dissertation by Martin Gasbichler, 2006.

It is possible to define a formal semantics for configuration, elaboration, linking, and evaluation of fully-parameterized first-class modules with hygienic macros, independent compilation, and code sharing. This dissertation defines such a semantics making use of explicit substitution to formalize hygienic expansion and linking. In the module system, interfaces define the static semantics of modules and include the definitions of exported macros. This enables full parameterization and independent compilation of modules even in the presence of macros. Thus modules are truly exchangeable components of the program. The basis for the module system is an operational semantics for hygienic macro expansion - computational macros as well as rewriting-based macros. The macro semantics provides deep insight into the nature of hygienic macro expansion through the use of explicit substitutions instead of conventional renaming techniques. The semantics also includes the formal description of Macro Scheme, the meta-language used for evaluating computational macros.

A very readable, interesting, and useful work.

Roy, Peter van (2009). Programming Paradigms for Dummies: What Every Programmer Should Know. In G. Assayag and A. Gerzso (eds.) New Computational Paradigms for Computer Music, IRCAM/Delatour, France.

This chapter gives an introduction to all the main programming paradigms, their underlying concepts, and the relationships between them. We give a broad view to help programmers choose the right concepts they need to solve the problems at hand. We give a taxonomy of almost 30 useful programming paradigms and how they are related. Most of them differ only in one or a few concepts, but this can make a world of difference in programming. We explain briefly how programming paradigms influence language design, and we show two sweet spots: dual-paradigm languages and a definitive language. We introduce the main concepts of programming languages: records, closures, independence (concurrency), and named state. We explain the main principles of data abstraction and how it lets us organize large programs. Finally, we conclude by focusing on concurrency, which is widely considered the hardest concept to program with. We present four little-known but important paradigms that greatly simplify concurrent programming with respect to mainstream languages: declarative concurrency (both eager and lazy), functional reactive programming, discrete synchronous programming, and constraint programming. These paradigms have no race conditions and can be used in cases where no other paradigm works. We explain why for multi-core processors and we give several examples from computer music, which often uses these paradigms.

I have not found this paper in the LTU archives, but I though it is likely of interest to this community. Of course, the author is well know here (e.g., his book Concepts, Techniques, and Models of Computer Programming). I like the bird's eye view of this paper.

Mixins, a very interesting post from Slava Pestov's Factor blog.

Factor's object system allows the following operations without forcing unnecessary coupling:

* Defining new operations over existing types
* Defining existing operations over new types
* Importing existing mixin method suites into new types
* Importing new method suites into existing types
* Defining new operations in existing mixin method suites
* Defining new mixin method suites which implement existing operations

That's pretty much what I want from an object-functional language.

Reaction-time and eye-fixation data are analyzed to investigate how people infer the kinematics of simple mechanical systems (pulley systems) from diagrams showing their static configuration. It is proposed that this mental animation process involves decomposing the representation of a pulley system into smaller units corresponding to the machine components and animating these components in a sequence corresponding to the causal sequence of events in the machine's operation. Although it is possible for people to make inferences against the chain of causality in the machine, these inferences are more difficult, and people have a preference for inferences in the direction of causality. The mental animation process reflects both capacity limitations and limitations of mechanical knowledge.

Following the theme of yesterday's post this is another non-PL research paper that explores cognitive factors that might be relevant to programming language design.

The research in the paper nicely illustrates how different accounts of the cognitive processes involved in reasoning about the behavior of a mechanical system or model can be compared experimentally. The results suggest the types of inferences that are involved in mental animation of the type requested from the subjects, and how they are orchestrated.

The first section of the paper provides the general framework, and explains the notion of mental animation. A discussion of the generality of the results can be found at the end of the paper.

Those who find my last two posts too far removed from PL issues need not worry; I am not going to post more research of this type soon. Those who are intrigued by this research will be happy to know that a lot more is available where this came from.

The advantages of diagrams, in our view, are computational. That is diagrams can be better representations not because they contain more information, but because the indexing of this information can support extremely useful and efficient computational processes. But this means that diagrams are useful only to those who know the appropriate computational processes for taking advantage of them. Furthermore, a problem solver often also needs the knowledge of how to construct a "good" diagram that lets him take advantage of the virtues we have discussed. In short, the ideas we have presented, not only provide an explanation of why diagrams can be so useful, but also provide a framework for further study of the knowledge required for effective diagram use.

While this paper is not about programming languages, it describes research that may be relevant to the discussion of visual programming languages versus textual languages as well as other language design decisions. Seeing as human factors were recently mentioned, and that it seems to be cognitive-week here on LtU, I thought this paper might be of interest.

While I am sure this paper can be discussed from many angles, I'll only mention two. 1. While this paper is old, I still find it remarkable how old fashioned it seems. I am not sure exactly what causes it to feel this way; probably something in the writing style. 2. While I haven't searched the literature, I don't recall seeing research on programming languages that uses the framework suggested by this paper even though Simon's work was, of course, well known to computer scientists in general, and PL researchers in particular.