Lambda the Ultimate

It seems that Oslo is going to get a lot of press soon, and I don't think we have discussed it yet, nor am I sure I really understand what it's all about...

We have been following Microsoft's DSL and modeling project on and off for a couple of years, and Oslo seems to be another step on this road. The buzz seems to be about visual development, a textual DSL, and development by non-developers (which is probably not the same as end-user programming).

eWeek has a short discussion of The Origins of Microsoft's Oslo Software Modeling Platform. If you have links to more informative resources, or insights to share, please do.

Phil Windley has has a new startup, and he is documenting some of aspects of their design process (business and technical) on his blog. For us the nice part is that he is building a DSL. Here is an explanation why building a DSL makes sense (not that we need one, over here, but still a nice analysis). And here is a discussion of high order perl and parsing.

I wouldn't normally think a library is LtU material, but since this one lives at the intersection of embedded DSLs, process calculi, and a spotlight language, I think it fits: Communicating Scala Objects, Bernard Sufrin, Communicating Process Architectures 2008.

In this paper we introduce the core features of CSO (Communicating Scala Objects) – a notationally convenient embedding of the essence of occam in a modern, generically typed, object-oriented programming language that is compiled to Java Virtual Machine (JVM) code.

If you would like to play with it, the library can be downloaded here.

This paper reports the results of a qualitative field study of the scholarly writing, collaboration, information management, and long-term archiving practices of researchers in five related subdisciplines. The study focuses on the kinds of artifacts the researchers create in the process of writing a paper, how they exchange and store materials over the short term, how they handle references and bibliographic resources, and the strategies they use to guarantee the long term safety of their scholarly materials.

Not directly programming language related, but two things makes this paper relevant. First, many of the tools involved, especially those that really enhance productivity are language-based, or include DSLs (e.g., Latex, Bibtex, R (+Sweave) etc.). Second, many of us write papers, and as language geeks we surely crave great tools...

So, what is you ideal tool chest when it comes to doing and publishing research? And what do you actually use everyday?

A command-line, textual, and probably linguistic, interface to the browser.

I am not sure how complex they are planning of making this, nor how it meshes with visions of the future of web browsing, but it's worth keeping an eye on.

I spent some time thinking about site-specific scripting, and had some discussions with students about building a site-specific DSL compiled to Greasemonkey scripts, but alas nothing came of it. It would be interesting to see whether Ubiquity command lines could be integrated into scripts, and how extensible the vocabulary is going to be, and on what level (i.e., site by site, via plugins etc.) Clearly also related to the often discussed topic of "end-user programming".

Things always seem to slow down as we approach this time of year, so I'll post a OOPSLA 2007 video interview of Guy Steele on Programming Languages that I stumbled upon. Covers a range of topics that are of interest to the current and future state of PLs. Nothing too technically deep, but tidbits of interest scattered throughout the interview (especially on DSLs).

(see also prior LtU discussion Guy Steele on Language Design).

(Maybe others have seen this before but I really like the interface that is provided for the video. The list of questions are clickable links which move you to that place in the interview where the question was asked. I hope this catches on for all technical video interviews.)

Functional Netlists, Sungwoo Park, Jinha Kim, Hyeonseung Im. ICFP 2008.

In efforts to overcome the complexity of the syntax and the lack of formal semantics of conventional hardware description languages, a number of functional hardware description languages have been developed. Like conventional hardware description languages, however, functional hardware description languages eventually convert all source programs into netlists, which describe wire connections in hardware circuits at the lowest level and conceal all high-level descriptions written into source programs.

We develop a variant of the lambda calculus, called l-lambda (linear lambda), which may serve as a high-level substitute for netlists. In order to support higher-order functions, l-lambda uses a linear type system which enforces the linear use of variables of function type. The translation of l-lambda into structural descriptions of hardware circuits is sound and complete in the sense that it maps expressions only to realizable hardware circuits and that every realizable hardware circuit has a corresponding expression in l-lambda. To illustrate the use of l-lambda as a high-level substitute for netlists, we design a simple hardware description language that extends l with polymorphism, and use it to implement a Fast Fourier Transform circuit.

Given the recent discussion about hardware synthesis languages, the appearance of this paper seems timely. The use of linear types is perhaps unsurprising from a technical point of view, but it's surprising when you consider how frequently and in how many different contexts they appear.

Also, one thing I don't understand: there's apparently a difference between a "hardware description language" and a "hardware synthesis language". If anyone could explain what the difference means, I'd appreciate it. :)

TileStack is an attempt to resurrect HyperCard and bring it to the web.

Running online there are going to be limitations about which stacks can be ported, which may reduce the usefulness and impact of this project, but maybe a standalone version will come later.

The system compiles Speak (the TileStack version of HyperTalk) to Javascript. If the result is not obfuscated, something I haven't verified, it may be possible to augment the output from TileStack with additional capabilities not supported or not yet implemented.

From the compatibility angle it is interesting to note that they renamed the language and seem to imply they are going to extend it beyond HyperTalk, without giving any specific guarantee about future compatibility. I'd suggest releasing the compiler that's as close to full HyperTalk compatibility as a separate product (or even, if they can bring themselves to do it, releasing it as open source).

Map-reduce-merge: simplified relational data processing on large clusters (freely-accessible slides). Hung-chih Yang, Ali Dasdan, Ruey-Lung Hsiao, D. Stott Parker. 2007 ACM SIGMOD conference.

Map-Reduce is a programming model that enables easy development of scalable parallel applications to process a vast amount of data on large clusters of commodity machines. Through a simple interface with two functions, map and reduce, this model facilitates parallel implementation of many real-world tasks such as data processing jobs for search engines and machine learning.

However,this model does not directly support processing multiple related heterogeneous datasets. While processing relational data is a common need, this limitation causes difficulties and/or inefficiency when Map-Reduce is applied on relational operations like joins.

We improve Map-Reduce into a new model called Map-Reduce-Merge. It adds to Map-Reduce a Merge phase that can efficiently merge data already partitioned and sorted (or hashed) by map and reduce modules. We also demonstrate that this new model can express relational algebra operators as well as implement several join algorithms.

They seem to add a third phase – merge: ((k1, [v1]), (k2, [v2])) → (k3, [v3]) – which combines the outputs of two separate, parallel MapReduce tasks.

This makes it possible to do things like joins and build cartesian products.

John Resig (of jQuery fame) has ported the Processing visualization language to JavaScript.

The examples are remarkable, check them out (but check the browser issues John discusses).

John has a little confession:

The first portion of the project was writing a parser to dynamically convert code written in the Processing language, to JavaScript. This involves a lot of gnarly regular expressions chewing up the code, spitting it out in a format that the browser understands.

It works "fairly well" (in that it's able to handle anything that the processing.org web site throws at it) but I'm sure its total scope is limited (until a proper parser is involved). I felt bad about tackling this using regular expressions until I found out that the original Processing code base did it in the same manner (they now use a real parser, naturally).

Actually that's quite cool in itself (even if angels weep at this parsing code, I think we on LtU shouldn't cast the first stone). DSLs should be easily built and played with. Cleaning up the implementation comes later, if at all.

Purists may not only object to the regular expression parsing, but also to the central line of code which ties things together, namely: eval(parse(code, p)). But then, DSL lovers are not the sort of people to object to eval...

In the old days of LtU we regularly posted links to cool small interpreters that people could play with. Some of the more amusing ones were javascript based, and the page contained a REPL form (Luke, I am talking to you!). It is a shame we don't post more stuff like this, in between the more highbrow discussions...