Lambda the Ultimate

I'm looking for pointers to languages that are considered expressive and usable, yet are defined by simple lexical grammars and parser grammars.

One popular example is Python, which is almost LL(1) in simplicity. LISP is LL(1) and might be considered another example depending on one's views. C++ is, of course, a non-example since it isn't even definable in a context-free grammar.

Given the recent discussion on topics like Nemerle and C# 3.0, Apple: procedural -> OO -> AOP -> advanced procedural, and other AOP type design concerns, it seems to me that a structurally typed, functional, multi-method (maybe plus predicate dispatch) programming language would allow for FP, OOP, and AOP development without requiring language-external solutions or hacks. Nice and CLOS support multi-method, but not really any other languages. Is there a reason that there is no discussion of multi-method programming? Is it simply too complex to reason about? Is it too slow? Or is there something else that I have missed? Thanks.

Lately I've been thinking of garbage collection in terms of being a lazy algorithm. That is, I see a lot potential similarities between lazy evaluation and garbage collection. One of the main benefits of lazy evaluation is the modularity it provides by allowing finer-grained intermingling of programs (the separation of generation from selection). Garbage collection follows this pattern closely by allowing the allocation of memory anywhere, without having to worry about deallocation. Also, the freeing of unused memory is done dynamically on demand, instead of being determined at compile time. Again, similar to the execution path of a lazy program. And lazy evaluation makes it easier to reason about correctness, but harder to reason about efficiency. Much the same could also be said about GC.

I think the unification of the two concepts could inform both areas. I could see a form of strictness analysis performed on our 'lazy' garbage collector which would produce a region inference algorithm or a compile time garbage collection algorithm. And maybe garbage collection research could help in developing better evaluation strategies. Although I have a harder time seeing it, might a generalization of the idea behind generational GC applied to an evaluation strategy lead to something similar to Optimistic or Eager evaluation? (That is, spend more time on executing younger thunks, etc.)

Are there any papers out there which discuss the lazy aspects of garbage collection?

I realize this isn't really a theory question, and I humbly hope the moderators tolerate the thread anyway. However, this crowd probably knows more about FPLs than most, and hopefully this thread will be a useful resource to other people looking to get into an FPL. For my purposes, "productive" includes the following requirements, roughly in order of importance:

• Free - I realize that many FPLs have free implementations, but it would be ideal if the entire toolchain was free, or at least a reasonably significant portion of it; in this case I'm more interested in "free beer" than "free speech"
• Windows implementation - yes, I know Windows is evil, but alternative x86 GUIs just aren't as mature, which leads to the next requirement:
• GUI support - the application I have in mind is a client/server app, and I want the client to have a nice interface; a GUI builder would be best, but a decent GUI API is good enough
• Library support - I don't want a stripped-down language that is mostly useful for solving academic mathematical curiosities; I don't expect a library set as rich as Java or C++, but I want something reasonably rich; if the language supports linking to C/C++ libs, it should do so fairly painlessly
• IDE - the nicer the IDE, the better; an Eclipse plugin would be ideal, but I don't expect anything more fancy than an emacs mode
• OOP - my application will do a lot of modelling, so I suspect that OOP support will be very helpful (though I will make a best attempt to use the language idiomatically)

A rationale along with a given suggestion would be most welcome. Thanks.

REBOL creator Carl Sassenrath addresses this question in his blog. It's basic stuff, but it's interesting to even see the issue come up. REBOL is an interesting and odd language, if you've never seen it. (The answer to the question in the title, BTW, is "no.")

Mentioned on OS News.
The features mentioned in the C# 3.0 preview, if nothing else, will serve to distance the product from Java still further.
Lambda and query expressions...hmmm...

Does anybody have any starting-out references for Category Theory in computer science?

I did a maths degree, and while I came across the odd bit of category theory nobody in the maths faculty taught a course on it. I got the impression it was seen by many as a needlessly abstract way of rephrasing existing algebraic results, which didn't bring many new mathematical insights.

But, since then I see references to it everywhere in connection with logic and theoretical computer science - trying to understand things like monads, domains, denotational semantics, type theory and so forth. The mathematical treatments I've seen have been horribly abstract and lacking in intuition so I thought I'd ask you guys if you know of any references from a slightly different perspective.

Cheers,
Matt

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^)

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!

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.