On Scheme

Thoughts on Scheme and teaching Scheme

A Type System For Scheme, Part 3

Posted by Peter on March 25, 2006

Common Lisp
Allow me to briefly describe how Common Lisp goes beyond Scheme types: In Common Lisp when a new variable is introduced that variable can be declared to be one of the known types. Then when code is compiled where the variable is visible run-time checks can be eliminated for better performance. Additionally the result of any evaluation can be likewise declared to be of a fixed type. This system allows Common Lisp users to explicitly type only when they feel they need the increased performance.

However despite the benefits it brings to performance this system can be unwieldy in terms of making the code much longer than necessary, for example if you want to type three parameters you will need to retype them all over again in the(declare (type parameter) (type parameter) …) statement. More importantly, and the central fault of this system, is that despite having such declarations no compile time checking is done for validity of calls, at least none that I could determine. Unfortunately since this typing feature is only used when performance is absolutely necessary it doesn’t have the most extensive documentation (which is why my unedited post, as shown by the comments, made a mistake concerning it).

Overall Rating:
4/10: Remember this is a rating of the type system, not of Common Lisp. Unfortunately this system like soft-typing systems is solving speed problems instead of conceptual ones, i.e. it isn’t catching programmer mistakes such as passing parameters in the wrong order.

Oaklisp Dialect (pdf)
The Oaklisp system attempts to improve Scheme by turning it into an object oriented system. Thus a call such as (a b …) is not passing the parameters b … to the function a but is instead passing the message a and the parameters to object b. By inheriting all objects from fundamental classes that provide type information, as well as allowing the types themselves to be first class objects a great deal of type manipulation and type inspection can be done within the program.

A personal criticism I have of systems such as this is that if you want to program in Smalltalk you should just program in Smalltalk. With that out of the way Oaklisp does improve upon the basic type system of Scheme marginally, because first class types do have their uses on occasion. However the same basic situation regarding types exists in standard Scheme as it does in Oaklisp, there is no compile-time checking, and type errors are only caught at the place where they occur, not at the point where the function is called.

Overall Rating:
2/10: Although providing more type information is useful it doesn’t really solve the problems that arise due to Scheme’s lack of a type system. For the curious this is also the rating I would give Scheme’s standard type system.

Type Classes (pdf)
Type classes are somewhat complicated matter so I am just going to cover their simplest implications here: they give you resources which you can both overload functions based on the type of their parameters (vs. the number of their parameters), and you can conveniently overload multiple functions at the same time (for example it makes sense to overload the numerical operations at the same time). The foremost advantage to this system is that type errors will be caught immediately when the function is called, since there will be no appropriate dispatch, rather than somewhere inside the function.

Obviously this isn’t a compile time system, so the complaints I have already mentioned with purely run-time systems still stand. Also there is no performance benefit to this method, and in the current implementation there is actually a tiny performance penalty.

Overall Rating:
3/10: I am rating this system so low because it is really only one part of a possible fix. I do think type classes are interesting, and possibly deserve to be included in the main body of Scheme, especially since you can always choose not to use them.

C/C++/Java/ect Type System
Admittedly there is no current Scheme implementation, that I know of, which uses such a system. It would however be possible to design one, as my own suggestion shows. The advantage to such a system is that the vast majority of type errors are caught at compile time. Thus performance can be likewise increased, with run-time checks only existing when one type is “cast” to another.

The most onerous disadvantage of such a system is all the excess code that is generated, by which I mean that every parameter and every return value must be typed, even if type inference could have figured it out. Another disadvantage that such systems have is their problems handling complex types. Just recently in Java, and much longer ago in C++, the idea of generics were introduced, which indicates a type that can be related in some fixed way to one or more other types, for example a list of numbers might be list<number>. However such systems still can’t handle more complex types, such as a list of numbers or characters, or a list of numbers or (lists of numbers or (lists of … ect)).

Overall Rating:
2.5/10: Although this system is slightly better than a run-time only system for catching programmer errors and performing optimizations its benefits are reduced by the restrictions on how types can be defined and the needless amount of work that must be done typing every variable, parameter, return, ect. In such a system a little type-inference could go a long way.


7 Responses to “A Type System For Scheme, Part 3”

  1. Zach Beane said

    (defun foo (bar baz quux) (declare (fixnum bar baz quux)) …) ; is perfectly valid

  2. Peter said

    Sure if they are all the same type, which is not that often in my experiance, but you are right in that it saves some effort. However even with this method you were forced to re-enter all the variable names. Under type inference however you wouldn’t have to do any of this declaring, and under a systme like Bigloo the types could be declared in the parameters list. Either of these options is superior.

  3. Zach Beane said

    for example if you want to type three parameters you will need three (declare type …) statements.

    That’s also not true. The following is perfectly valid.

    (defun foo (bar baz) (declare (fixnum bar) (character baz)) …)

    If you wish to criticize something as inelegant or inferior, please at least characterize its shortcomings accurately.

  4. Peter said

    The problem is not how many times you are writing declare, but the fact that you have to re-enter all the parameter names. Obviously even if multiple declares were required this could be macro-ed away. However the syntax is not my main criticism with the Common Lisp way of doing things, it is that this information is not used to identify bad function calls at compile time, to quote myself it is “solving speed problems instead of conceptual ones”.

  5. Zach Beane said

    The problem is not how many times you are writing declare…

    That is indeed not a problem, but you call it a problem in the article.

  6. Peter said

    I see your point and yes my original post is in error concerning the Common Lisp syntax, I will edit my post to both be more accurate and to be clearer in that this minor quibble is not the real shortcomings of the system.

  7. inglorion said

    It’s worth pointing out that, although the Common Lisp specification does not require implementations to do compile-time type checking (in fact, implementations are allowed to completely ignore all declarations, except ‘special), many implementations do perform compile-time type checks. Better yet, many implementations also perform type inference (and I’ve seen such type inference yield faster code and catch more errors than code I had manually annotated).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: