Lambda the Ultimate

O’Reilly author chromatic has a string of blog posts describing his maintainable language. Possibly interesting even while it might be an Avril joke? (Didn't notice this posted on LTU yet.)

Lee, E.A., "The Problem With Threads", IEEE Computer, vol. 36, no. 5, May 2006, pp. 33-42, available online as U.C. Berkeley EECS Department Technical Report UCB/EECS-2006-1

For concurrent programming to become mainstream, we must discard threads as a programming model. Nondeterminism should be judiciously and carefully introduced where needed, and it should be explicit in programs.

Many of the points about concurrency raised in this article will be familiar to LtU readers, particularly those who have any familiarity with CTM, but the article does provide a good summary of the issues. Beyond that, what I found interesting (especially from a PLT perspective) is Lee's contention that the emphasis on developing general-purpose languages that support concurrency is misplaced. Lee believes that a better approach is to develop what he calls "coordination languages", which focus on arranging sequential components written in conventional languages into some concurrent configuration (I suppose that piping in a Unix shell could be considered a limited coordination language). Quoting from the article:

"Coordination languages do introduce new syntax, but that syntax serves purposes that are orthogonal to those of established programming languages. Whereas a general-purpose concurrent language like Erlang or Ada has to include syntax for mundane operations such as arithmetic expressions, a coordination language need not specify anything more than coordination. Given this, the syntax can be noticeably distinct."

It's not immediately obvious to me that there's anything preventing a "coordination language" from being a well-defined subset of some more general language. Lee's key point seems to involve making coordination constructs syntactically distinct (e.g. block diagrams vs. text). Which, of course, raises some interesting questions about whether other important facets of a language (such as the language of type declarations) should also have strongly syntactically-distinct representations, and just how homogeneous (Lisp anyone?) the syntax of a language should be...

Ruby and python have been mentioned many times on LtU, but I would like the opinnion of gurus here. Which language is more interesting for those who have deeper knowledge of programming language theory?

I'm not so concerned with speed of respective VMs, the community around these languages, even their syntax, etc. I'm iterested in the languages (and their APIs I suppose).

For example, for practical programming, are ruby's continuations significantly better than python's co-routines (2.5)? How do 'lambda' functions in each language compare?

Is one language closer to 'functional' programming than another? Is one language better than another for building logic programming or constraint logic programming constructs? Is one language better than another for building the kind of functionality found in concurrent languages (erlang, Oz)?

Those following my posts, may know that I am recently enamored with stack-based functional languages (like Joy). I have posted the powerpoint slides from a proposed talk about the Cat Programming Language at http://www.cdiggins.com/cat.ppt.

Here is the proposal which accompanies the presentation:

Cat Programming Language: A Functional Optimization Framework for the MSIL

Abstract

Cat is a stack-based pure functional language, inspired by the Joy programming language, which targets the Microsoft Intermediate Language (MSIL). Cat, like Joy, differs from mainstream functional languages in that it is based on the composition of functions rather than the application of functions. This design makes algebraic manipulation of programs trivial, and thus facilitates optimization.

This goal of the presentation (http://www.cdiggins.com/cat.ppt ) is to introduce the semantics and syntax of Cat, demonstrate rewriting rules for high-level functional optimizations, and show preliminary performance results for a simple IL Code generator written in C#.

Summary of Language

The Cat language is a pure functional language, inspired by Joy, which in turn is inspired by Forth and FP. All constructs in Cat (atomic programs, user defined programs, operators, literals, lists) behave as functions which takes a single stack as input and returns a new stack. In Cat the concatenation of two functions (e.g. [f g]) has the effect of composition of both functions (e.g. g(f(x))). All new user defined functions are defined as lists of functions. Cat not only has no variable declaration, there are no argument declarations. Cat also lends itself to the higher order functional programming: the lambda operation in Cat is the list construction operator "[...]" and currying can be achieved used basic operations such as "cons".

Results of Research

The primary result of the work done with Cat is the observation that high-level functional optimizations can be very easily expressed and applied. Consider the examples:

f map g map => [f g] map
[f] map x [g] fold => x [[f' f] g] fold 
[f] filter x [g] fold => x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold => x [f g [h] [pop] if] fold 

These optimizations are very important, but are extremely hard to apply once a langauge has been reduced to an assembly, or pseudo-assembly, form.

The thesis of this work is that by first compiling a language to a stack-based functional language such as Cat, before targeting a lower level target such as MSIL, better performance can be achieved.

Hi,

Is it possible/plausible to have a Java/C++ like language in which you can write code like:

void aFunction(nonnull Object o) ....

Something s = new Something();
aFunction(s);

and then have the type system prove that o can never be null? This feels simple but I wonder if it ends up becoming dependent types, arbitrary theorem proving or some other suitably scary thing. Being able to add simple, small increases in type safety to a program written in a non-functional language would be quite nice to have!

I also wonder if this sort of thing could be implemented using C++ smart pointers.

"A preview of LINQ, code name for a set of extensions to the .NET Framework that encompass language-integrated data query, set, and transform operations."

First, thanks all to those responded to my post awhile ago. I picked a few brains and got some help, sorry if I didn't get a chance to write back to you.

So I am trying to make a very simple list oriented language (well more like preprocessor ala m4), I think there is a very "natural" solution (something that basically writes itself) to what I am looking for, but I was wondering if I could get some (more) help fleshing out the idea. Basically, I would just want to define list assignment, functions and function application over lists that is very \n delimiter oriented, with the default interpolation behaviour to take cross-products. This would be pseudo example, the idea being that the syntax would be very lightweight over a normal text file...

denotes output

As->{
1
2
3
4
5
}

Bs->{
6
7
8
9
}

AsBs

>16
27
38
49
5

x-> is some number

6x

>6 is some number

6{1,2,3,4}

>61
62
63
64

level1a->{
A
AA
}

level1b->{
B
BB
}

level2->{
level1a level1a
level1a level1b
}

level2

>A A
A AA
AA A
AA AA
A B
A BB
AA B
AA BB

I am not sure exactly how well I've thought this out, but it gives you an idea...it's basically just subsitition with and emphasis on cross products that sacrifices some flexibility for simplicity by imposing things like new line delimiters. I would just need to be able to define lists function and apply them appropriately.

I can kinda see that by imposing newlines, I could swallow things one line at a time, but I keep thinking in terms of encoding an FSM with a bunch of "if" statements...

Should this be a peice of cake using something like recdescent? I would be cool if this was just basically something like a syntax modified perl, so that I could define functions with all the normal goodies.

Many thanks for any advice.

Hi i'm looking for literature and/or research on/in programming language design, implementation, etc, etc specifically in the domain of numerical analysis and scientific computing in general.

There seems to be a lack or slow down in development of array functional languages. From what i've investigated/researched already constraint-based programming is very well suited to numerical analysis problems and i can find alot of literature in that department.

I'm kind of curious of the possibility of a new language that is an array functional language which is purely functional, supports constraint-based programming, light-weight dependently typed type system, some kind of effects system in the type system for controlled, localized side-effects.

I know you probably think i'm crazy but i'm just curious :-)

I notice in stack based languages certain symmetric programs reduce to no-ops:

f1 = [swap swap] = []
f2 = [dup pop] = []
f3 = [cons uncons] = [] 
f4 = [dup swap cons uncons swap pop] = [dup swap swap pop] = [dup pop] = []

So how much of this is blindingly obvious to the research community? It seems that this must be much harder to detect in non stack based languages.

Cyclone is a type-safe dialect of C that incorporates a number of features from functional languages, including parametric polymorphism (ML-style, not C++), datatypes, and pattern matching. It also includes a number of features necessary to make C safe, such as fat pointers, tagged unions, and region-based memory management.

We've just put out a new release (1.0) and a new web site: http://cyclone.thelanguage.org