Lambda the Ultimate

Clojure was mentioned here before and the Boston Lisp talks from Rich Hickey are amazing: Part 1 and Part 2. Just the idea of imutable vectors, sets and maps as additional first class data structures with different kind of parentheses already makes it the best lisp for functional programming ever.

What formalisms are available for specification of visual (i.e., graphical, two-dimensional, diagrammatic) programming languages? Which of these, if any, are popular?
If readers feel that few are popular because visual languages are of limited use, do these readers refute the premise that visual syntax is a superset of character sequence syntax?

The Computer World series is continuing with Anders Hejlsberg on C#. Of particular interest is his discussion of F#:

Q:What do you think of functional programming in general?

I think that functional programming is an incredibly interesting paradigm for us to look at, and certainly if you look at C# 3.0, functional programming has been a primary inspiration there, in all that we’ve done with LINQ and all of the primitive language features that it breaks down to. I think the time has finally come for functional programming to enter the mainstream. But, mainstream is different from taking over the world.

I definitely think that there is a space for functional programming today, and F# is unique in being the first industrial strength functional programming language with an industrial strength tooling language behind it, and an industrial strength platform underneath it. The thing that’s really unique about F# compared to all of the other functional programming languages is that it really offers first class support for object oriented programming as well, and first class interoperability with the .NET framework. Anything we have in the .NET framework is as easy to use from F# as it is from C# as it is from VB – it does not feel forced.

A lot of functional programming languages have lived in their own little world, and they’ve been pure and mathematical and so forth, but you couldn’t get to the big library that’s out there. If you look at languages today, they live and die by whether they have good framework support, as the frameworks are so big and so huge and so rich that you just cannot afford to ignore them anymore. And that’s why you’re seeing so many languages being built on top of .NET or on top of Java as opposed to being built in their own little worlds.

And what he sees as the importance of the entire software ecosystem to programming.

It's common for Scheme programers to develop object systems based on closures. An object's methods are closures whose free variables comprise the object's instance variables. The object itself is represented by a method lookup function. See for example Ken Dickey's "Scheming with Objects".

Have any programming languages been based on closures as the fundamental building block?

I'm trying to find some interesting abstract machines that support lazy graph reduction. Haskell implementations seem to prefer the Spineless Tagless G-Machine (GHC, NHC, YHC), and the G-Machine (Hugs). I've heard that Clean is based on the ABC Machine, but I can't really find any literature on it. I've also seen the machines that SP Jones mentions in his "Implementing functional languages, a tutorial", which IIRC includes: Template Instantiation, the G-Machine, and the Three Instruction Machine (TIM).

I have a couple of questions about this:

1) Are there any other interesting machines out there?
2) Where can I find some information on the ABC machine?
3) Why do Haskell implementers love STG so much?

EDIT: Spineless Tagless G-Machine, not Stackless...

What is a programming language? The common definition generally only includes the syntax and semantics of, for lack of a better description, the “text” of a program. For instance, we think of languages as defining how variables are declared, how loops are specified, functions defined, if certain mechanisms like continuations or closures are first-class (or close to it), etc.

This definition fails to capture how the languages are really used, though. Just because a handy library is written in C++ doesn’t mean it will integrate nicely into my present C++ program. The reason is that it is the APIs that are the real language - not the obscure rules that define what a loop looks like or which characters are allowed in a variable name.

I realize this is a (potentially mis-informed) blog post (from my own blog, no less), but I'm not familiar enough with the research to know if this phenomenon has been widely studied or not. (And if so, where I can read more about it.)

In my experience, the integration of multiple libraries with different styles is one of the primary reasons large programs often devolve into an incomprehensible mess over time. It's not the only reason, of course, but I think it contributes - especially when some programmers on the team are more familiar with one library vs. another, etc.

What could be done in the context of a programming language to mitigate this? Or, what has been done? It doesn't seem like the mainstream languages are very good at keeping this problem at bay. (Or is it perhaps not a problem for anyone but me?)

Whilst thinking on the subject of language design, specifically lowish-level (C++ level), I came up against the seeming brick wall of function pointers. Now, whilst function declarations can be modified to allow for such niceties as closures, coroutines and multiple return values, function pointers, it seems, can never be harnessed for the power of good. The reason for this seems to be the way that functions are declared in C-type languages, i.e. completely differently from data and, I might add, rightly so. I much prefer:

int doIt(int a)
CODE

or even something along the lines of:

int,int iHandle:swapInt(int a, int b)
CODE

as a more elaborate coroutine with a multiple returns and a handle to its own instance, compared to more object based delcarations:


(int)function(int) doIt = new (int)function(int)
CODE

(note: this is just an example in a sugarless but statically typed language, I'm sure there are nicer ways of having OOP function declaration)
which, in any case also brings up the question of integrating return types into the declaration (hint: Pascal is also very ugly)
However, even for the modest simple function, the C function pointer of

int(*fp)(int);


is just completely whack compared to the rest of the data declarations.

int a;
char c;
int(*fp)(int);

(spot the odd one out)

So my question is this, has anyone encountered a statically-typed function/funcpointer declaration system that is at all elegant?

-DNQ

Old question, still difficult. I am in the process of moving from a compiler which compiles the source code to an AST representation in C and then runs a trampolining interpreter on top of it, towards full-blown C compilation.

I am puzzled whether to do the CPS transform or not (major code expansion, seems like a large performance hit? Or am I using the wrong transform?). I can also go ANF but actually, I am not too sure how to compile the ANF representation efficiently.

And actually, is there any _real_ difference between CPS and ANF? Seems to me that the CPS transform just makes the return pointer explicit in the lambda representation.

Any thoughts?

As BitC moves towards a more human-compatible (sorry lispers!) surface syntax, we're considering mixfix parsing. Since it really applies only in the expression sub-grammar, it seems like a shame not to be able to use Bison (or something similar) for the rest of the grammar.

As near as I can tell, the only way to implement this is to have Bison simply accumulate a token sequence for expressions without trying to deal with precedence at all, and then apply a rewriter on the resulting AST to apply operator precedence rules dynamically.

Hmm. A kludge may be possible with mid-production actions and GLR parsing.

Is there a known solution to this, or am I just barking up trees?

I feel incredibly silly posting this, but I could use some pointers.

There seem to be two schools of function specification: one in which all function types are expressed as T1 -> T2, and the other in which function types are expressed as T1 x T2 x ... Tn -> Tout. The difference here is that the second makes function arity part of the type.

In BitC, we initially chose the N-ary functions because I was slow figuring out how to make C's void type come out right. Later, we retained it because I thought that arity checking was important. That is, given a function:

(define (f x y) ...)

it seemed like a good thing to be able to notice that:

(f 1 2 3)

was a malformed call because the number of arguments do not agree. The alternative was to define application to occur by pair consing (similar to Scheme style, but with using an unboxed construction):

(f 1 2 3) =>
(f (1, 2, 3))

My concern about this is that type checking doesn't accomplish arity checking in the case where the type of the last parameter to the function is parametric. That is, if we get a function f whose type is something like:

(int32, float, 'a) -> bool

then you'll get to pass as many arguments as you want.

The N-ary function thing is now getting in our way, and I would like to switch to something like the pair-consed view. There seem to be three resolutions:

• Conclude that losing the arity check when the last parameter is polymorphic is survivable.
• Check arity as a separate syntactic matter that is independent from type.
• Ask how other people have dealt with this.

So: how do other polymorphic languages handle this?