Lambda the Ultimate

I'm building a new programming language called Felix:

http://felix.sf.net

Much of the design in influenced by Ocaml, but Felix generates C++ and is intended to provide seamless integration with C/C++ datatypes and architectures.

I'm working towards SWIG'ing wrappers for major libraries (GTK for example) and beginning the process of bootstrapping. Checkout the tutorial to get some idea what it looks like.

A chance now to do more than discusss pros and cons of existing languages .. help design one!

What features should a new programming language have? What do you like -- and hate -- about the languages you use?

So, I suppose, if you're going to create a new language, don't make it a retread of many old languaegs, and if (well, OK, when) you screw things up (we all do) at least make new stupid mistakes, rather than recreating the old stupid mistakes. :)

After an initial calibration period the runtime system would tailor the evaluation strategy to maximise speed (eg by increasing strictness) while keeping memory use within some boundary. If memory use becomes dangerously high then the strategy would shift to one that lowered memory use.

You might use sub-threads to implement the additional strict evaluation so that "bottom" can be detected and deferred.

As far as I can see, this is impossible in general and, while it might be possible in practice in some cases, the runtime cost is too high. On the other hand, I had a frustrating evening yesterday trying to persuade Haskell to do what I wanted... ;o)

I only bother to bring anything up at all because felix looks so great otherwise, especially the macros and type manipulations.

I also would miss operator overloading. It looks silly, but it makes things like Blitz++ useable.

Operator overloading like in Cecil would be fantastic, as would that in Kiev.

I can't recall which of those let you define your own character sequences as operators, but both allow customized precedence. Big win!

P.S. For more language ideas as written up by the pros, check out http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/ especially the extensions to the language.

I think overloading in general is a big win. C++ has function overloading, limited type overloading (with partial template specialization). Felix has value overloading with unions.

Dynamic dispatch and multi-methods are valuable.

Constructors and destructors are great tools, and C#'s set and get methods are great extensions, but maybe too much fluff.

Either compile-time type (and pointer and integer) manipulation (like C++) or real macros (lisp/scheme) is essential. It looks like you have parts of both, which is great.

A Meta-object protocol for staticly typed languages (like Aldor's) makes certain previosly impossible tasks possible.

In summary, I'm looking for

1. Lots and lots of overloading - value, function (including multi-methods and dynamic dispatch), type, operator, construction, destruction, allocation . . .

2. Compile time manipulation - types, identifiers

3. First class meta- and sub- - objects, functions

4. Cases - pattern matching, partial specialization of generic functions/types

5. Inheritance - object, meta-object, function (see beta's INNER)

Sorry for the long and rambling response. Great job so far. I'm compiling O'Caml just to give Felix a go.

EDIT: you also might want to check out merd at http://merd.net/

To Daniel Yokomiso..

Referential-transparency -- Felix has a purely functional subsystem. At least, it's purely functional provided any primitive functions imported from C don't have side effects :-)

The downside of this is that the procedural system can be clumbsy to use for example:

var result:bool; do_something(&result);

is pretty ugly compared to

var result = do_something();

I'd be interested in ideas on syntax to fix this.

Daniel Yokomiso>Dislike: subclassing as a subtyping mechanism

No worries here: Felix doesn't have any classes yet :-) Nor is there any subtyping of alegbraic types yet. As an Ocaml fan .. I'll probably follow the model used there, where subtyping is signature based.

Dislike>"primitive" numeric types as basic types

Heh! Felix doesn't have ANY primitive types. Not even bool. All your primitives have to be defined in C/C++ and imported into Felix at present (Felix has no classes).

Of course, bool exists in Felix, but it is NOT a primitive type. Here is the definition from the standard library:

typedef bool = 2;

Its just an alias for the type 2. The notation 2 is just sugar for the type 1 + 1, where 1 is just a sugar for the type of (), the empty tuple.

Unlike most other languages, Felix has an anonymous (non-generative) sum type. Bool has two values written:

case 1 of 2 case 2 of 2

It's a bit clumbsy but you can write:

typedef number = int + long + float;

(case 2 of number) 1.2

The anonymous type constructor (case 2 of number) is the second injection function into the sum type number.

Daniel Yokomiso> wants: "unbounded (modulo memory) precision integers" [as primitives]

Sure, but not built in! There is a wrapper in the works for GNU GMP. It's just a library module ..

Daniel Yokomiso> wants higher order statements, functions, modules..

Felix has higher order functions and procedures. Modules are like in Ocaml at present: only first order. It isn't clear how to make them higher order (dynamically bindable), at least without very strong run time type information to describe the types of the module, especially as values are not boxed in Felix.

On higher order object combinators: there is no real system for handling stateful objects as yet. I am looking at how Charity does this. There is a lot of new theory on stateful (coinductive) programming, based on dualising known theory for functional (inductive) programming. The name is woeful .. Bisimulation .. Argggg.. anyhow, I do plan some kind of symmetrical support for stateful data structures like streams.

"perceived necessity/desirability of bootstrapping. Stick with O'Caml for implementation"

There are two strong reasons for bootrapping Felix.

(1) It proves the language is strong enough to bootstrap itself. (and also is a good regression test :-)

(2) Felix will have an adaptable syntax. To do this, one needs to be able to extend the compiler with code generated by Felix (for example, extend the parser).

One could do this by calling

system("ocaml stuff"); module = dlopen("stuff"); new_function = dlsym(module,"new_function");

except for one problem .. Ocaml cannot generate shared libraries. Unless the Ocaml team fixes that problem, it becomes difficult to extend the compiler at run time .. which I consider essential in the long run. [it is possible embed the bytcode interpreter .. of course there is still the hassle of interfacing data structures across the boundary .. two garbage collectors .. and a licencing problem]

There are numerous related problems where the code used to generate things at compile time cannot be used at run time, because the former is Ocaml and the latter must be (reducible to) C.

For example: there is a statement in Felix:

regmatch "string" with | "abc" => ... | "def" -> .. endmatch

which works by building a finite state automata at compile time. This requires the regular expressions be constants. To make it dynamic, I have to rewrite the finite state automaton generator code in C++ so I can invoke it at run time...

This problem goes away if the compiler is written in C/C++/Felix. [I've been hassling the Ocaml team for shared library generation, but no go yet .. the native code compiler generates non-relocatable code .. ]

I'm sure I will. (Already screwed up the design/implementation of part of the module system .. :-)

"Oh, ghod, not another variant on X"

Yeah. Well, Felix is a bit like that, and partly deliberately. The syntax is *deliberately* meant to look a bit C++ like, so C++ programmers will feel a bit comfortable.

The integration of functional and imperative features is the traditional Algol model (lvalues, variables, statements, expressions). Partly for user familiarity, and partly because *I* am familiar with it :-)

"and they made the same damn mistakes"

Well, the way to avoid that is to ask for help. HELP!! [Design reviews needed regularly .. ]

The best Felix can do at the moment is constant folding :-)

As to adaptive code generation .. that is *really* hard. One could use a neural net for parameter tuning, and perhaps choice of implementation strategies in an interpreter with JIT compiler, but Felix generates traditional binaries.

"I use C++, and I like nested classes (which I notice are missing in felix). How would you write a vector without a first-class vector::iterator?"

Err.. look again. Felix has no nested classes .. because it has no classes :-)

Yeah, it has a struct like C, which is mainly a generative version of a tuple type (but the fields are mutable). It can't support methods (at least not yet).

At the moment, the way you write a first class vector would be .. write it in C++, then import it as a primitive into Felix .. the easiest way is something like:

header 'include <vector>'; type vector[T] = "std::vector[?1]"; type iterator[T] = "typename std::vector[?1]::iterator"; fun begin[T] (v:vector[T]):iterator[T]) = "v.begin()"; ...

which is pretty easy (except std::vector doesn't know about the Felix garbage collector :-)

"I also would miss operator overloading."

Why? Felix has overloading. You can even overload functors :-) At the moment:

fun add: int * int -> int = "$1 + $2"; fun add: float * float -> float = "$1 + $2";

print (1 + 2); print (1.0 + 2.9);

'operator+' is spell 'add' in Felix at the moment (though I might change that to __add__ like Python, or perhaps 'op +' like C++ but shorter)

Ocaml allows arbitrary special symbol sequences as user defined operators. At present, Felix doesn't. One reason for bootstrapping is to allow the client to extend the lexer and parser -- its not really enough to just have new operator symbols, nor enough to just have user defined precedences. You really need to integrate the symbol in to the grammar properly..

One would like 'user defined domain specific sublanguages' and that is one of the goals. One of the key targets for this is SQL. I plan to add an SQL like subset directly into the language .. and then try to eliminate it with a library component.

"P.S. For more language ideas as written up by the pros, check out.."

This is the C++ committee papers, I know .. I've been a member of the C++ committee for over 10 years. They're anything but pros I'm afraid. Indeed, one reason for building Felix is the inability of the committee to grasp even elementary ideas accepted by theoreticians.

"Dynamic dispatch and multi-methods are valuable."

No classes yet. There is, however, a rudimentary dynamic mechamism for making objects from function closures.

[An object is just a factory function that returns a struct of some function nested in it, these functions are bound to the factory function's stack frame which may be considered the private data ..]

"you also might want to check out merd at http://merd.net/"

I'm looking .. probably steal some of your ideas. I'm seeking some ways to do fairly dynamic object like handling. The reason is: static classes are quite weak (class based OO sucks). People in strongly typed environments often resort to 'mini-interpreters' to solve this problem (eg like 'printf()') -- not only throwing away static typing, but having to reinvent the wheel all over again.

C++ provides limited RTTI to help, but it isn't enough. A much stronger dynamic construction tool kit is required.

D'oh. When you use a hammer all day long, not only does everything look like a nail, but screwdrivers just look like strange hammers.

"'I also would miss operator overloading.'

Why? Felix has overloading. You can even overload functors :-) At the moment:"

So, can I overload operators for my own structs?

http://felix.sourceforge.net/flx_1.0.4/tut/doc/en_flx_tutorial_0005.html

Doesn't really indicate I could.

I would miss it for the simplicity and readability of writing A+B for two sparse matrices, for instance.

[snipped discussion of difficulty of user-defined operators and precedences]

Yeah, it doesn't sound easy to implement. 8-)

"They're anything but pros I'm afraid. Indeed, one reason for building Felix is the inability of the committee to grasp even elementary ideas accepted by theoreticians."

D'oh. That's a shame. Nonetheless, I'm excited about typeof, decl, and the new auto semantics.

Maybe you could shed light on why there isn't a nested function proposal. Or maybe I should pony up the cash for D&E.

"'you also might want to check out merd at http://merd.net/'

I'm looking .. probably steal some of your ideas."

Oh, not mine, just an exciting project I found.

"I'm seeking some ways to do fairly dynamic object like handling. The reason is: static classes are quite weak (class based OO sucks). People in strongly typed environments often resort to 'mini-interpreters' to solve this problem (eg like 'printf()') -- not only throwing away static typing, but having to reinvent the wheel all over again."

[Goes over my head] The only OO I've ever used is class-based. I've read about prototype-based OO and dynamic classes like in CLOS, but I don't understand what you just wrote above.

"C++ provides limited RTTI to help, but it isn't enough. A much stronger dynamic construction tool kit is required."

Could you elaborate?

says:

"Felix allows procedures and functions to be overloaded, as does C++."

Consider:

// Define a struct for complex numbers struct complex { x: float; float y:float; };

// define a routine to add them up fun add (a: complex, b: complex): complex { return complex(a.x + b.x, a.y + b.y); }

// make 2 complex numbers: // note componentwise constructor used

val a = complex(1.0,2.0); val b = complex(3.0, 4.0);

// use the overloaded function 'add' by name as a global:

val c = add(a,b);

// use it with OO syntactic sugar

val c = a.add(b);

// use the corresponding operator

val d = a + b;

Note: I will be adding classes and methods and stuff to Felix, but not yet.

'Felix has a very powerful OO subsystem. Its called "C++"'

[Its just a huge pain to write classes in C++ and then have to provide bindings for all the methods ..]

(haskell cafe has had quite a few good threads recently)