On Scheme

Thoughts on Scheme and teaching Scheme

  • Recent Posts

  • March 2006
    M T W T F S S
        Apr »
  • Archives

  • Categories

  • Blog Stats

    • 14,903 hits
  • Advertisements

Archive for March 25th, 2006

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.


Posted in Exploring Scheme | 7 Comments »