On Scheme

Thoughts on Scheme and teaching Scheme

Archive for March 24th, 2006

A Type System For Scheme, Part 2

Posted by Peter on March 24, 2006

Today I will review three proposals for type systems in Scheme. Two of these are practical solutions and one is an academic paper addressing issues of type inference. Hopefully in the future I will get around to summarizing all the major approaches to adding a type system to Scheme, but Rome wasn’t built in a day, or so they say.

The Typedscm dialect (homepage)
The best part about this type system is that it looks “lispy”, that is it uses parentheses as delimiters, so that when the type extensions are embedded in the code they don’t look out of place. Another highlight is that it has a fully featured way to describe the type of a function. Instead of generics there are type functions. For example, to describe a list containing numbers you write (list-of number) and if you need a predicate to test for this type you write (list-of number?) instead. What I described as free types you can also accomplish with this system, but for more details on that I suggest you visit the documentation for yourself. Finally various syntax extension are introduced to help type inference be conducted properly, which I also won’t go into detail about.

Extra coolness:
If the function returns no value you can designate it as such, and if the function doesn’t return to the caller you can also designate that type of return (most systems would simply designate both as returning nothing).

Currently the type system only supports functions that return a single value, and as you might know I am big into multiple return advocacy. Additionally it is not clear how types from a library function or C extension can be determined since they can’t be inferred from their component operations. More important is that types can’t be forced; at least my reading of the document didn’t show how they could be. Why is this important? Well if you are willing to use their new object system it isn’t a big deal, but most people seem to prefer their own variant systems. To make such a system work you need to specify that the return values of some functions should be considered to be of a certain type. Even though your objects are considered functions they also need to be considered to be their own type, otherwise the compiler would let you pass them to a function via any argument that expected a function, not just ones that are appropriate for the object. Likewise you may want to make the types accepted as parameters to a function more restrictive than the inference allows. Finally this system needs to be able to specify that a type is to be considered a specialization of given other types, so that it will identify as those types, as well as identifying as its own type (this allows your custom object types to “cast” in type properly, i.e. they can be passed to function that expect a class they inherited from).

Overall Rating:
8/10: There are some improvements to be made, but a lot of the foundation has been laid, in a way that is consistent with the look and feel of Scheme. Currently this is my favorite system.

The Bigloo dialect (homepage)
Bigloo is a very nice extension to Scheme, and I definitely want to investigate it further. My only quibble with its implementation is that continuations are discouraged, although they do provide other nice features. However here I am only reviewing its type system so keep that in mind. Bigloo’s type system looks somewhat like mine, you can type parameters and the return value of a function with a ::type syntax after the parameters. The best feature about this type system is probably its simplicity, but it doesn’t rally do much more beyond this basic checking, and it only supports a few types.

The Bigloo type system doesn’t seem to do much if any type inference. Also you can only create your own types by defining Bigloo classes, so implementing your own object system with typing is right out. Additionally Bigloo does not have the resources to specify a list containing a certain type of member, nor anything more complicated to the best of my knowledge. Finally the type information does not affect the compiled performance in any way. Bigloo’s system is designed more as a small addition to standard Scheme than it is a full fledged extension to it.

Overall Rating:
3/10: Well it’s better than no type system. Bigloo has some other very compelling features going for it however, so expect to see some future posts on it from me.

Paper: A Practical Soft Type System for Scheme (pdf)
Like the first typing system mentioned this is a soft type system, meaning that the type of arguments and data are inferred as much as possible from the type of arguments and return values from known primitive functions. Although a little too theoretical for my taste this system does demonstrate how type inference can remove a lot of work at runtime, as well as how it can be accomplished and proven to work.

It’s a 66 page document, sheesh! Anyhow the main disadvantage of the system is that it is not ambitious enough. Well it actually seems like it could remove many run-time checks, but it doesn’t really help the programmer in complicated situations where they need very complex types in order to catch their errors. Basically this system resorts to run-time checking instead of proposing language extensions that could rectify the problem. So while it does provide an interesting basis for a type-inference system it is not really a practical solution.

Overall Rating:
5/10: It has some good ideas, but nothing that solves programmer problems instead of speed problems (i.e. gives the programmer resources to catch conceptual errors, instead of simply optimizing for speed).


Posted in Exploring Scheme | Leave a Comment »