Lambda the Ultimate

Bjarne Stroustrup. A rationale for semantically enhanced library languages. LCSD05. October 2005.

This paper presents the rationale for a novel approach to providing expressive, teachable, maintainable, and cost-effective special-purpose languages: A Semantically Enhanced Library Language (a SEL language or a SELL) is a dialect created by supersetting a language using a library and then subsetting the result using a tool that “understands” the syntax and semantics of both the underlying language and the library.

How similar or different this idea really is compared to the facilities found in PLT Scheme and other previous apporaches to this issue?

A Stepper for Scheme Macros. Ryan Culpepper, Matthias Felleisen.

In this paper, we present a macro debugger with full support for modern Scheme macros. To construct the debugger, we have extended the macro expander so that it issues a series of expansion events. A parser turns these event streams into derivations in a natural semantics for macro expansion. From these derivations, the debugger extracts a reduction-sequence (stepping) view of the expansion. A programmer can specify with simple policies which parts of a derivation to omit and which parts to show. Last but not least, the debugger includes a syntax browser that graphically displays the various pieces of information that the expander attaches to syntactic tokens.

Another paper from the Scheme workshop.

Apart from being a nice exercise for macro lovers, a good macro debugger is essential for lowering the barrier to macro programming. Since macro programming is an important technique for building DSELs and for language oriented programming in general, having better macro debugging facilities is a Good Thing.

Abdulaziz Ghuloum (Indiana University), An Incremental Approach to Compiler Construction

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, “better write an interpreter instead.”

The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter.

This paper from the Scheme workshop presents an extended tutorial showing how to implement a compiler from Scheme to x86 assembly language. The compiler is written in Scheme, obviously (something that may confuse students, I might add, so beware).

An important aspect of the presentation of the material is that the compiler is built incrementally, and the product of each step is a working compiler for a growing subset of the language. This is similar to the EOPL approach. In contrast many compiler textbooks and courses follow a different route, in which each phase is dedicated to building a different part of the compiler (i.e., lexer, parser etc.), and thus the student only sees how the parts interconnect, and gets the satisfaction of seeing the compiler work, at the very end of the process.

Supporting material can be found here.

I know this is slightly off topic for LtU, but I see Philip Wadler is collecting material aimed at introducing students and the general public to the discipline of computation, a subject near and dear to my heart.

I will not elaborate my thoughts on this subject here, but I remind people interested in this topic to search the LtU archive (specifically the teaching and learning department) since items related to this goal have appeared here occasionally.

This is also a chance to mention again my suggestion that someone translate Doug Hofstadter's Scientific American columns introducing Scheme to a general audience into Haskell.

As far as I know the LASER Summerschool has not been mentioned on LTU yet.

We have a fine lineup of speakers, including Miguel de Icaza(who gave a great presentation at the Lang .NET symposium), Andreas Zeller whose book on debugging is an instant classic, Mary Poppendieck whose presentations were the highlight of last year's JAOO, Ralf Back who as usual will ensure sound foundations, and of course Bertrand Meyer who needs no introduction!

Registration is open until August 31.

I hope to see many of you in person on Elba.

Via the plt-scheme mailing list:

We are pleased to announce the first public release [beta 7] of ACL2
in DrScheme, a combination of the ACL2 theorem prover system with the
DrScheme programming environment. The objective of this project is
to provide a development environment for ACL2 suitable for novice
users as well as enhancements of ACL2 that are attractive for the
typical undergraduate student (graphics, interactive games, sound).

There's a tutorial with screenshots and some examples on the ACL2 in DrScheme web page.

I'm always happy to see reasoning about programs introduced at the undergraduate level. I wonder what the LtU community would do with a tool like this. What cool things would you teach with a beginner's theorem prover?

This seems to be an introductory ("aimed specifically at non-theoreticians") set of articles on OO type theory. The author is Tony Simons and the articles were all published in the Journal of Object Technology.

1. Perspectives on Type Compatibility (pdf)
2. The Scratch-Built Typechecker (pdf)
3. Object Encodings and Recursion (pdf)
4. Object Types and Subtyping (pdf)
5. Axioms, Assertions and Subtyping (pdf)
6. The Subtyping Inquisition (pdf)
7. A Class is a Family of Types (pdf)
8. Classification and Inheritance (pdf)
9. Inheritance and Self-Reference (pdf)
10. Method Combination and Super-Reference (pdf)
11. Adding Class Types to Object Implementations (pdf)
12. Building the Class Hierarchy (pdf)
13. Template Classes and Genericity (pdf)
14. Modification and Objects like Myself (pdf)
15. Mixins and the Superclass Interface (pdf)
16. Rules of Extension and the Typing of Inheritance (pdf)
17. Multiple Inheritance and the Resolution of Inheritance Conflicts (pdf)
18. Polymorphism Through the Looking Glass (pdf)
19. The Proliferation of Parameters (pdf)
20. The Modular Checking of Classtypes (pdf)

If I've made a mistake above, try A Simons's bibliography or here.

People are discussing this blog post all over, so we might as well mention it here.

The discussion is quite balanced, though you are likely to disagree about the specifics. One issue, discussed here repeatedly, is that code=data doesn't require S-expressions. Lisp expressiveness runs deeper than that.

Our discussion of Spolsky's Java Schools essay is here, by the way.

I have been teaching programming for nearly ten years now, to university students from the first to the fourth year, to both CS majors and non-CS majors (all in technical fields). I have tried to distill results from programming language research into these courses (and wrote a book in the process, CTM). Recently, I had two insights:

1. The best year in which to teach a programming course based on programming concepts is the second year. In the first year, students are not mature enough. In the third and later years, students get conservative. In the second year, they have enough maturity to understand the concepts and enough openness to appreciate them. At UCL, we have been doing this for two years now for all engineering students (more than 300 in Fall 2005) using a first-year course based on Java, and it works remarkably well (better than I expected).

2. Students can be taught programming semantics in the second year. This can succeed if: (1) the semantics requires very little mathematical baggage, just sets and functions, (2) the semantics is factored so it can be taught incrementally, and (3) the semantics is simple and uncluttered so that students can work out a program's execution with paper and pencil. The semantics of CTM is one example that fits these conditions. The students consider the semantics the hardest part of the course. I think it's because they've never been exposed to this kind of formalism, so they are a bit unsettled by it. But I am convinced that students in any technical field should be taught programming language semantics at least once in their careers. It should be as basic as algebra or calculus.

What do you think? I would appreciate hearing your experience and comments. Here are the course notes of the latest version of my course (they are in French; there are English course notes too but they are not as nice for the second year).

Thinking about teaching our undergraduate PL next semester, I've been digging up lots of suddenly interesting readings. The teaching about PL project links to much information, and Wadler's and Felleisen et al.'s critiques of SICP were enlightening as well.

Most recently I stumbled upon Joseph Bergin's writings on teaching, in particular ""The undergraduate language course: what to do?" (SIGPLAN Notices 36(6):20-22, 2001), which describes a taxonomy of course approaches: "historical", "smorgasbord", "interpreter", and "principles". Also relevant is a recent article "In Computer Science, A Growing Gender Gap: Women Shunning a Field Once Seen as Welcoming" by Marcella Bombardieri (Boston Globe 2005-12-18).

(I'm sorry I couldn't find Wadler's and Bergin's articles freely available online.)