Lambda the Ultimate

André Pang, Don Stewart, Sean Seefried, and Manuel M. T. Chakravarty. Plugging Haskell In (pdf). Proceedings of the ACM SIGPLAN Workshop on Haskell, 2004, pp. 10-21.

Extension languages enable users to expand the functionality of an application without touching its source code. Commonly, these languages are dynamically typed languages, such as Lisp, Python, or domain-specific languages, which support runtime plugins via dynamic loading of components. We show that Haskell can be comfortably used as a statically typed extension language, and that it can support type-safe dynamic loading of plugins using dynamic types.

Two of the authors also have a more recent paper (pdf) describing applications they've built using hs-plugins.

Given definitions of genetic algorithm and genetic programming, some PLT-inspired observations:

1. As interpreters are a special case of programs, then genetic programming is a special case of genetic algorithms. If this is correct, then some statements from referred articles at least need rewording (e.g., computational complexity).
2. It is (probably) interesting to investigate what are requirements for PLs being used as object language in genetic programming (e.g., set of (more or less) valid programs closed under mutations).
3. Related to the previous one - typing issues.
4. DSL perspective
5. Reflection, staged computation, etc. (bring in the slider).

Am I barking up the fallen tree? Any comments are appreciated.

Unlike the previous approaches, the latest implementation is generic. Shift and control share all the same code, and differ in only one boolean flag. Therefore, it becomes possible to mix different control operators in the same program. Furthermore, the latest implementation is direct rather than emulation (in terms of an object-level shift), therefore, it has the best performance. The code is surprisingly simple, compared with the previous implementation of 'control' by Sitaram and Felleisen, and does not require equality on continuations. All four delimited control operations do indeed reduce to call/cc and one global mutable cell, and hence have a quite simple CPS transform. That has been known since the paper by Chung-chieh Shan (Scheme Workshop, 2004). The current code shows that result more directly.

Oleg's implementation provides all four Friedman-Felleisen delimited control operators: from -F- (similar to cupto) to +F- (aka control) to +F+ (aka shift). The R5RS Scheme code is parameterized by two boolean flags: is-shift and keep-delimiter-upon-effect. All four combinations of the two flags correspond to four delimited control operators.

Over the last couple of months, both my existence and my judgments have been questioned several times on my favorite programming languages waterhole :-)

In the mean time, I was busily working with the SQL, XML, C# and the Visual Basic teams on language integrated query, or as it is now called project LINQ. In particular since early this year I am collaborating with Amanda Silver, Paul Vick, and Rob Copeland and Alan Griver on what has become my programming language of choice Visual Basic.

If you look closely at the new features introduced to C# and Visual Basic in the context of LINQ, you will recognize many familiar concepts that are regularly discussed on LTU ranging from monads, to meta-programming, lambda expressions, XML programming, to the relationship between static and dynamic typing.

The LINQ project consists of a base pattern of query operators (compare to the monad primitives) such as Select (map), SelectMany (concatMap), Where (filter), OrderBy (sort), and GroupBy (groupBy) on top of which Visual Basic and C# define query comprehensions (compare to monad comprehensions) that  facilitate querying objects, relational data and XML. The C# syntax for query comprehensions is similar to FLWOR expressions, while the Visual Basic syntax stays close to SQL including aggregation.

In addition to the language extensions and base operators, LINQ provides two supplementary domain-specific APIs namely DLinq (compare to HaskellDB) for SQL relational data access, and XLinq (compare to HaXml) for XML hierarchical data access. Besides query comprehensions, Visual Basic provides deep XML integration with XML literals and XML late binding on top of XLinq (compare to Haskell Server Pages, XMl, Comega).

Both Visual Basic and C# have added several additional language extensions in support of LINQ, including local type inference (the type of local variable declarations are inferred from their initializers), lambda expressions (with type inference), local functions, anonymous types, object initializers, extension methods (static methods that can be called using instance method syntax), and meta-programming via expression trees (compare to type-based quote and quasi-quote).

Visual Basic adds some further enhancements to leverage the fact that it allows static typing where possible and dynamic typing where necessary in the form of relaxed delegates, improved nullable support, dynamic identifiers (makes writing meta-circular interpreters a breeze) and last but not least dynamic interfaces, or as I like to refer to them strong duck typing (compare to simplified qualified types/type classes).

LINQ general website: http://msdn.microsoft.com/netframework/future/linq/
VB9 specific website: http://msdn.microsoft.com/vbasic/future

G. Kimmell, E. Komp and P. Alexander, "Building Compilers by Combining Algebras," Proceedings of the IEEE Engineering of Computer-Based Systems Symposium and Workshop (ECBS'05), Washington, DC, April 4-7, 2005.

Embedded systems present a wide variety of challenges for developers
of language tools. Verification of correctness, flexibility for adding new
language features, and retargeting new architectures all present significant problems when developing a compiler for embedded systems. In this
paper we present a domain-specific language based on modular monadic
semantics which addresses many of these challenges.

Despite the embedded systems emphasis in the abstract this paper actually presents a fairly general approach to combinator-based compilation. The authors note that their approach should speed the development of compilers, interpreters, and type-checkers, while also making verification easier.

It's probably worth noting here that this is not a paper about parser combinators, but rather presents a flexible, algebra-based approach to generating code from an AST. The authors claim that things like typechecking and optimizations can be accomplished simply by changing the carrier set of the algebra.

Recently, I used delimited continuations to do some "scope herding" in a little language I am implementing. In short, I wrote a pair of combinators enterBlock and bindLocal that use shift and reset (and Reader-monad features) to provide automatic scoping for block-local bindings.

Through the magic of delimited continuations, code like this:

enterBlock $ do
    bindLocal "x" 2
    x <- evalVar "x" 
    bindLocal "y" (x + 1)
    x <- evalVar "x" 
    y <- evalVar "y" 
    return (x + y)

is (in effect) translated into code like this:

local (Map.insert "x" 2) $ do
    x <- evalVar "x" 
    local (Map.insert "y" (x + 1)) $ do
        x <- evalVar "x" 
        y <- evalVar "y" 
        return (x + y)

In the latter form, the scope of each local binding is expressed via the Reader monad's local combinator, which assures me that the binding's effects will not stray outside of the block established by enterBlock, regardless of how the block is exited.

Given the number of recent papers on delimited continuations that have been discussed here on LtU, I was wondering what other nifty uses our readers may have found for them.

Do you have a delimited-continuation trick or story to share? If so, what is it? Please do let us know!

Edd Dumbill has an interview with Autrijus Tang on on Perl and Haskell. It's a much shorter read than the LINQ announcement from Microsoft, so if you only have a few minutes... 8^)