Lambda the Ultimate

A fascinating article by Oleg Kiselyov on delimited continuations:

We demonstrate the conversion of a regular parser to an incremental one in byte-code OCaml. The converted, incremental parser lets us parse from a stream that is only partially known. The parser may report what it can, asking for more input. When more input is supplied, the parsing resumes. The converted parser is not only incremental but also undoable and restartable. If, after ingesting a chunk of input the parser reports a problem, we can `go back' and supply a different piece of input.

The conversion procedure is automatic and largely independent of the parser implementation. The parser should either be written without visible side effects, or else we should have access to its global mutable state. The parser otherwise may be written with no incremental parsing in mind, available to us only in a compiled form. The conversion procedure relies on the inversion of control, accomplished with the help of delimited continuations provided by the delimcc library.

The Fortress blog has a recent post, Why Object-Oriented Languages Need Tail Calls, where Guy Steele argues for the necessity of proper tail call implementations without rehashing two of the classic arguments: state machines and the continuation passing style. It starts by mentioning William Cook's On Understanding Data Abstraction, Revisited:

In this blog post we extend one of his examples in order to make a completely different point: object-oriented programming languages need tail calls correctly implemented, not just as a "trivial and optional" optimization of the use of stack space that could be achieved by using iteration statements, but in order to preserve object-oriented abstractions.

The post also mentions other papers previously discussed on LtU: Automata as Macros, and A Tail-Recursive Machine with Stack Inspection.

Tim Bray shares his conclusions about Clojure.

To get your juices going: He claims "It’s the Best Lisp Ever"! (And that tail call optimization is a red herring.)

I have been contemplating a Clojure department for awhile now, but heck, we may be too far behind the curve by now...

Christopher Kelty's book, Two Bits: The Cultural Significance of Free Software, can be read online, and I think parts of it will interest many here.

It seems that programming languages, while mentioned, do not receive a lot of attention in this work. I would argue that they are a significant factor in the history that is being told, and an important resource for historians (though reading the history from the languages is not a trivial undertaking by any means).

Still, seems like a very good discussion and well worth pursuing.

Edited to add: As Z-Bo mentions in the comments, the website of the book invites people to re-mix it (or "modulate" it). Motivated readers can thus add the relevant PL perspective, if they so wish.

Barry Jay has recently published a book on the Pattern Calculus (which has been discussed before).

The pattern calculus is a new foundation for computation, in which the expressive power of functions and of data structures are combined within pattern-matching functions. The best existing foundations focus on either functions, as in the lambda-calculus, or on data structures, as in Turing machines, or on compromises involving both, as in object-orientation. By contrast, a small typed pattern calculus is able to support all the main programming styles, including functional, imperative, object-oriented and query-based styles, and there is evidence that it can support a language for Web services, able to exploit data structures about which almost nothing is known.

The book covers the operational semantics of both functional and OO features, as well as static and dynamic pattern-matching. Then it covers type systems necessary to deal with all the wild polymorphism thus gained - in rather readable fashion. Then it covers bondi, a programming language based on ML, Java and (lots of!) pattern-matching.

Marc Feeley and Danny Dubé, PICBIT: A Scheme System for the PIC Microcontroller, Fourth Workshop on Scheme and Functional Programming. November 7, 2003.

This paper explains the design of the PICBIT R4RS Scheme system which specifically targets the PIC microcontroller family. The PIC is a popular inexpensive single-chip microcontroller for very compact embedded systems that has a ROM on the chip and a very small RAM. The main challenge is fitting the Scheme heap in only 2 kilobytes of RAM while still allowing useful applications to be run. PICBIT uses a novel compact (24 bit) object representation suited for such an environment and an optimizing compiler and byte-code interpreter that uses RAM frugally. Some experimental measurements are provided to assess the performance of the system.

A very interesting perspective on language implementation, found via @dhess and previous discussion.

Abdulaziz Ghuloum and R. Kent Dybvig, Implicit Phasing for R6RS Libraries, Proc. ICFP 2007.

The forthcoming Revised Report on Scheme differs from previous reports in that the language it describes is structured as a set of libraries. It also provides a syntax for defining new portable libraries. The same library may export both procedure and hygienic macro definitions, which allows procedures and syntax to be freely intermixed, hidden, and exported.

This paper describes the design and implementation of a portable version of R6RS libraries that expands libraries into a core language compatible with existing R5RS implementations. Our implementation is characterized by its use of inference to determine when the bindings of an imported library are needed, e.g., run time or compile time, relieving programmers of the burden of declaring usage requirements explicitly.

R6RS leaves it up to implementations whether import statements need to explicitly state the meta-level into which bindings should be placed. The authors argue for letting the implementation automatically figure out the required meta-levels, and present an implementation-oriented description of how to do so, that they implemented portably. The paper also includes a well-written and detailed introduction to the issues involved, and since they want the community to adopt their solution, they seem to have worked extra hard to produce a convincing paper ;).

(via vieiro)

Mitchel Resnick, John Maloney, Andrés Monroy Hernández, Natalie Rusk, Evelyn Eastmond, Karen Brennan, Amon Millner, Eric Rosenbaum, Jay Silver, Brian Silverman, Yasmin Kafai, Scratch: Programming for All, Communications of the ACM, vol. 52, no. 11, November 2009.

When Moshe Vardi, Editor-in-Chief of CACM, invited us to submit an article about
Scratch, he shared the story of how he learned about Scratch:

A couple of days ago, a colleague of mine (CS faculty) told me how she tried to
get her 10-year-old daughter interested in programming, and the only thing that
appealed to her daughter (hugely) was Scratch.

That’s what we were hoping for when we set out to develop Scratch six years ago. We
wanted to develop an approach to programming that would appeal to people who hadn’t
previously imagined themselves as programmers. We wanted to make it easy for
everyone, of all ages, backgrounds, and interests, to program their own interactive stories,
games, animations, and simulations – and to share their creations with one another.

Scratch is the cover story of the November 2009 issue of CACM. The goal of Scratch is to get kids programming so that they become more fluent in information technology, and develop "computational thinking" skills. Scratch is a graphical language based on a collection of “programming blocks” that children snap together like Lego blocks to create programs. The programs themselves appear to be imperative in nature (at least based on the samples in the CACM article). Programs can be made concurrent by creating multiple stacks of blocks, and the authors claim that their goal is to make concurrent execution as intuitive as parallel execution.

Scratch was previously mentioned on LtU here.

Bytecodes meet Combinators: invokedynamic on the JVM. John Rose. VMIL'09.

The Java Virtual Machine (JVM) has been widely adopted in part because of its classfile format, which is portable, compact, modular, verifiable, and reasonably easy to work with. However, it was designed for just one language—Java—and so when it is used to express programs in other source languages, there are often “pain points” which retard both development and execution. The most salient pain points show up at a familiar place, the method call site.
To generalize method calls on the JVM, the JSR 292 Expert Group has designed a new invokedynamic instruction that provides user-defined call site semantics. In the chosen design, invokedynamic serves as a hinge-point between two coexisting kinds of intermediate language: bytecode containing dynamic call sites, and combinator graphs specifying call targets. A dynamic compiler can traverse both representations simultaneously, producing optimized machine code which is the seamless union of both kinds of input. As a final twist, the user-defined linkage of a call site may change, allowing the code to adapt as the application evolves over time. The result is a system balancing the conciseness of bytecode with the dynamic flexibility of function pointers.

The abstract is pretty vague, but this paper is actually quite interesting, particularly if you're interested in meta-object protocols and if, like me, you don't have the interest or patience to read JSRs. Of course, invokedynamic has been discussed many times over the years. The wheels of Java turn slowly...

Go is a new programming language to come out of google and this thread on Google discouraging python internally for new projects seems more than just coincidence.

Go is an attempt to combine the ease of programming of an interpreted, dynamically typed language with the efficiency and safety of a statically typed, compiled language.

By combining dynamic features, safety, garbage collection and efficiency in a single language and environment, Go claims to remove the reasons why programmers end up building systems using multiple languages. A brief look at Go shows strong C origins with nice support for "goroutines" - essential sequential processes communicating using channels. I don't quite get the "safety" claim of the language since you can take the address of an uninitialized variable in Go. It could qualify as a "C with concurrency" language I think.

Go already has a great set of packages that should make it immediately usable as a pragmatic language. (The terse package names are very reminiscent of Erlang's package structure.) It even has a package for interfacing with Google Native Client (NaCl) for audio/video access.

(minor edits)