Lambda the Ultimate

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.

Hegarty, M. (1992). Mental animation: Inferring motion from static diagrams of mechanical systems. Journal of Experimental Psychology: Learning, Memory and Cognition, 18(5) 1084-1102

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.

Jill Larkin and Herbert Simon, Why a diagram is (sometimes) worth ten thousand words. Cognitive Science, 1987.

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.

The latest entry has Joe Armstrong discussing Erlang in the ongoing series of interviews with PL designers (The A-Z of Programming Languages). Two related things caught my eye. The first is the obvious truism about language features:

Removing stuff turns out to be painfully difficult. It's really easy to add features to a language, but almost impossibly difficult to remove things. In the early days we would happily add things to the language and remove them if they were a bad idea. Now removing things is almost impossible.

The other thing that I found intriguing was his mention of integrating version control into the language:

We have mechanisms that allow the application software to evolve, but not the language and libraries itself. We need mechanisms for revision control as part of the language itself. But I don't know how to do this. I've been thinking about this for a long time. Instead of having external revision control systems like Git or Subversion I'd like to see revision control and re-factoring built into the language itself with fine-grain mechanism for introspection and version control.

Not sure what he has in mind?

Seems like its been a while since we last grated our linguistic experts. From How Does Our Language Shape The Way We Think? by Lera Boroditsky, the age-old discussion gets reopened:

Such a priori arguments about whether or not language shapes thought have gone in circles for centuries, with some arguing that it's impossible for language to shape thought and others arguing that it's impossible for language not to shape thought. Recently my group and others have figured out ways to empirically test some of the key questions in this ancient debate, with fascinating results.

Being the Programming Languages weblog, issues surrounding languages in general are somewhat tangential. Unlike the linguists, it is generally accepted that programming language syntax and semantics does have a significant effect on design and construction of programs. But like liguistics, one would be hard pressed to isolate the language from the community (culture). My take would be that a large measure of the benefit of looking at new PLs derives from being exposed to differing communities - not just in learning the details of a language.

Wirth, Siekmann, Benzmueller & Autexier. Lectures on Jacques Herbrand as a Logician. SEKI Report SR-2009-01.

Herbrand's work, more than that of any other, provides the intellectual foundations of logic programming. This very readable article discusses Herbrands' contributions to proof theory and the formulation of the idea of a recursive function, and most importantly to PL, his fundamental theorem that yields a semi-decision algorithm for first-order logic and his unification algorithm.

I was just forwarded a message that Peter Landin passed away yesterday.

From: Edmund Robinson
Date: 4 June 2009 09:10:11 GMT+00:00
Subject: Peter Landin

I am very sorry to inform you that Peter Landin died yesterday of natural causes.

For those members who are several generations away from Peter's early contributions, he was one of the major figures in the UK at the time that Computer Science was beginning to establish itself as a discipline. Some of his papers from 40 years ago are essential reading for any serious student of programming languages as still the simplest and clearest exposition of ideas that remain fundamental. The ideas in his papers were truly original and beautiful, but Peter never had a simplistic approach to scientific progress, and would scoff at the idea of individual personal contribution. Some of his own greatest ontribution to the field was as part of a golden nexus of work on programming languages in the UK in the late 60's and early 70's, containing Dana Scott and Christopher Strachey and others as well as Peter. The ideas they developed through their discussions truly lifted the study of programming languages to another level, and are now part of the bedrock of the subject.

Landin was one of the founders of our field, and did a lot of work of lasting value. We've discussed his papers here many times before, even though some of them were written decades ago. He did work that cast a long shadow, or phrased better, did work that illuminated wide vistas.