What inspired typed-case-lambda?

Jun 23, 2009 at 1:03 AM

What inspired typed-case-lambda?

Coordinator
Jun 23, 2009 at 6:40 AM
Edited Jun 23, 2009 at 6:42 AM

Hi Grant

typed-case-lambda (and typed-lambda) is part of my ongoing research and experimentation for version 2 of IronScheme.

The basic idea is to create a fully typed scheme as the underlying implementation for IronScheme.

Currently a lambda generates .NET code similar to:

object Foo(object x, object y)
{
return Builtins.Add(x, y);
}

So how does typed work?

(typed-lambda (x y)
((Int32 Int32) Int32) ; signature
($fx+ x y)) ; unsafe version

This will generate:

int Foo(int x, int y) 
{
return x + y;
}

Obviously, this wont be valid for all cases as required by Scheme. But case-lambda (and lambda) is describable in terms of typed-case-lambda.

Example:

(typed-lambda (x y)
((Object Object) Object)
(fx+ x y))

will generate an untyped construct.

So why do I want to do this?

Boxing and unboxing, as well as liberal type checking (excluded from samples), slows down IronScheme. Further more, neither of the aforementioned are necessary in a completed typed scenario. While a single typed-lambda will probably slow down IronScheme, the combination of a few greatly improves performance.

Obviously, this needs to be as transparent to the end user as possible, thus I will need to apply some type inference to fill in the missing pieces (type information) so the user can still just use plain old lambda.

So why haven't I done this earlier?

Not all problems are solved (and I don't even know if they will be solvable), most notably, space leaks due to type conversion in tail positions. I also still need to decide what kind of level of 'typeness' I will be using. F# for example utilizes generics quite well, and I am tempted to do the same (but oh the complexity!).

It's all still a bit overwhelming to me, and I am still trying to visualize the entire process. But I will get there  :)

Cheers

leppie

 

Jun 23, 2009 at 7:31 PM

Interesting. Thanks for the overview.

On the PLT list there was a discussion about building Scheme on top of Typed Scheme:

http://groups.google.com/group/plt-scheme/browse_thread/thread/3181030c67b61df9/dbcf3848260dd523?lnk=gst&q=time+machine

Jun 23, 2009 at 7:31 PM

BTW; your post would be a great blog post.