Lambda the Ultimate

I am about to start a project in the field of partial evaluation and I will be looking into generating compiler generators for DSLs. However, I'm having some trouble coming up with and finding interesting DSLs to use in the project. I would like to ask if anyone knows of some interesting (not necessarily Turing complete) DSLs. I will have to develop quite a bit of software to construct the compiler generator for the DSL, so, I'm looking for languages that preferably have a simple syntax and semantics and/or have readily available parsers / tools written in C.

Thanks in advance!

I've written a a thesis on programming languages for the arts, which I thought some might be interested in here. Here's the abstract:

We consider the artist-programmer, who creates work through its description as source code. The artist-programmer grandstands computer language, giving unique vantage over human-computer interaction in a creative context. We focus on the human in this relationship, noting that humans use an amalgam of language and gesture to express themselves. Accordingly we expose the deep relationship between computer languages and continuous expression, examining how these realms may support one another, and how the artist-programmer may fully engage with both.

Our argument takes us up through layers of representation, starting with symbols, then words, language and notation, to consider the role that these representations may play in human creativity. We form a cross-disciplinary perspective from psychology, computer science, linguistics, human-computer interaction, computational creativity, music technology and the arts.

We develop and demonstrate the potential of this view to inform arts practice, through the practical introduction of software prototypes, artworks, programming languages and improvised performances. In particular, we introduce works which demonstrate the role of perception in symbolic semantics, embed the representation of time in programming language, include visuospatial arrangement in syntax, and embed the activity of programming in the improvisation and experience of art.

You can download the pdf here.

I am curious why it seems there is little or no research on adapting grammars and parsers to support parametric polymorphism. It seems to me that grammars and types are more or less the same thing, and technology related to polymorphic type systems should apply to grammars and parsing as well.

Existing grammar technology has woeful compositional properties compared to type systems. I am currently using Dypgen which allows dynamic extension of a grammar. But first let me backtrack a bit:

Suppose to have an executable recursive descent parser for statements, where the parser accepts a list of statement forms and tries each one until it succeeds. If you put that list in a global variable, it is easy to extend the system by constructing a suitable data structure for parsing a statement at run time, push it onto the statement list and store the resulting list in the global variable.

The use of a global variable here rather than a weak functional technique is mandatory when you consider that some statements may be composed from others, and we want the recursion to extend nested statements to include the new production too.

Now as to Dypgen, it is better because it is purely functional in that after adding a new production for a statement, it rebuilds the parser engine, and so the recursion required to support nested statements works.

BUT .. we are still adding a new production to a statement, which is similar to hacking an Ocaml variant type and adding a new case, then recompiling. It's not the recompilation that concerns me here, but the fact we're forced to modify the old grammar to extend it.

The thing is the *right way(tm)* to do this would seem to be to use open recursion: in Ocaml you can use polymorphic variants with a parameter which is closed to form a concrete type, and for an extension you can add new variants to the open form and then close that. With this technology we have real subtyping: we have a type which is open for modification, and can be trivially closed for use, thus satisfying the open/closed principle.

Why can't we do this for grammars?

There are some real trivial uses for this. Dypgen supports 3 polymorphic operators already, namely * + and ?. But now, suppose I want to define "comma separated list of arbitrary-nonterminal" which in fact I need a lot.

I'm being asked to use a technology so seriously archaic it is worse than Basic or Cobol: it doesn't even have "subroutines". What I need here is actually quite flat: it needs parametric grammars, though not open recursion.

Given the huge amount of research into type systems .. why am I still using Assembler to write my grammars?

Interesting blog post by Crista Lopes. Here is some text from the bottom that struck a chord with me:

In order to do experimental design research AND be scientifically honest at the same time, one needs to let go of claims altogether. In that dreadful part of a topic proposal where the committee asks the student “what are your claims?” the student should probably answer “none of interest.” In experimental design research, one can have hopes or expectations about the effects of the system, and those must be clearly articulated, but very few certainties will likely come out of such type of work. And that’s ok! It’s very important to be honest. For example, it’s not ok to claim “my language produces bug-free programs” and then defend this with a deductive argument based on unproven assumptions; but it’s ok to state “I expect that my language produces programs with fewer bugs [but I don't have data to prove it].” TB-L’s proposal was really good at being honest.

We've talked a little about programming language design research before.

Lang.NEXT, a cross-industry conference on programming language design and implementation, was held on Apr 2-4, 2012. The focus of the event is sharing mutual inspiration and novel ideas in programming language design and implementation in both industry and academia.

List of speakers:

Martin Odersky (keynote, Scala)
Walter Bright (D)
Peter Alvaro (Bloom)
Andrei Alexandrescu (D)
Stefan Karpinski (Julia)
Jeff Bezanson (Julia)
Kunle Olukotun (Scala, Pervasive Parllelism)
John Cook (R)
Andy Moran (Haskell)
Robert Griesemer (Go)
Gilad Bracha (Dart)
Kim Bruce (Grace)
Andrew Black (Grace)
Jeroen Frijters (IKVM.NET)
Herb Sutter (C++11)
Andy Gordon (Machine Learning)
Luke Hoban (ES 6)
Dustin Campbell (Roslyn)
Mads Torgersen (C# Async)
Donna Malayeri (F# 3.0)
Martyn Lovell (WinRT)

All session videos (or all-1, perhaps) will be available here: http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012. Currently live sessions (and keynote) are:

Keynote - Martin Odersky: Reflection and Compilers -> http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012/Reflection-and-Compilers

John Rose: Java 8 -> http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012/Java-8

Jeroen Frijters: IKVM.NET: Building a Java VM on the .NET Framework -> http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012/IKVM-NET-Building-a-Java-VM-on-the-NET-Framework

Andrew Black and Kim Bruce: Teaching with Grace -> http://channel9.msdn.com/Events/Lang-NEXT/Lang-NEXT-2012/Teaching-with-Grace

I'm trying to get a handle on core technology for an application that's going to involve massive numbers of entities - where the entities want to have characteristics that draw from both the object and actor models.

Think of something like massive numbers of stored email messages, where each message is addressable, can respond to events, and in some cases can initiate events - for example, on receiving an email message, a reader can fill in a form, and have that update every copy of the message spread across dozens (or hundreds, or thousands) of mailboxes/folders distributed across the Internet. Or where an email message, stored in some folder, can wake up and send a reminder.

One sort of wants to blend characteristics of:
- messages (small, static, easy to store huge numbers, easy to move around)
- objects (data and methods bound together, inheritance, ...)
- actors (massive concurrency, active)

The topic has come up before, in discussions of active objects, reactive objects, concurrent objects, etc. - I'm wondering what the current state of the art and practice look like.

I'm thinking that Erlang might be nice operating environment for such a beast, but wonder at what point one hits limits in the numbers of actors floating around. I'm also wondering what other environments might blend these characteristics.

I am thinking about a design for a new programming language, and I can't decide whether to include first-class functions.

I understand (I think) how they work and when they might be used, but I can't think of any programming problem where the solution requires them. Can anyone give such an example?

Thanks, Mark.

Bret Victor's talk has been making a huge splash on the net and we might as well talk about it here. The first part of the talk basically describes a lot of live programming ideas, some of which we have explored before but have never demoed quite as well as he has. Note that his demo is completely on cherry picked scenarios, there isn't a general system behind his work. Here are the interesting parts I'm recalling from memory:

• The first part simply discusses live editing of a discrete program that creates a static image, which simply means you re-execute the program after each edit and observe its new output in real time. Easy enough to do in any language, as long as the program is small enough to execute quickly, edits effects on execution will appear seamless.
• The second part deals with a stateful game, where he demonstrates time travel and projection to explore how changes in the code effect the result. Much more interesting, though I think for the demo he is just recording the input streaming and replaying the game (which is just one scene) with the recorded input each time time travel occurs backward (wit projection you just fiddle screen clearing).
• Observing the effects of programming a quicksort function in real time by specifying sample input. Very similar to Flogo II's live text concept, but loop variable values are encoded as nice tables.
• Finally, Bret does a custom animation through macro recording and by going back in time and recording other movements. The composite of all the recordings that occur in overlapping time segments then becomes the final animation.

A new blog entry has beed created with continues the description of Modern Eiffel's proof engine.

This blog entry focuses on the introduction of negation and it's axioms into the class BOOLEAN and presents a rich set of proofs.

This entry completes the use of the proof engine for propositional calculus. The next entries will focus more on real calculations using inductive data types.

Twitter has become a hotbed for PLT humor.

Currently known accounts are:

• PLT Borat
• PLT HULK
• popltarts
• Smug Lisp Borat
• PLT Zizek
• PLT Alain de Botton
• PLT Molyneux
• PLT Ryan Gosling (new!)

If you know of any others let us know in the comments. Or create one your own! It's fun. :-)