On Scheme

Thoughts on Scheme and teaching Scheme

Archive for March 27th, 2006

A Type System For Scheme, Part 3.5

Posted by Peter on March 27, 2006

After doing my research I have decided to take another stab at creating a type system for Scheme, hopefully not as flawed as my last one was. However considerations such as how to define templates/generics for classes and functions are making the process take longer than expected, so until then I have compiled a list of features that were, roughly, the basis of my ratings and which will hopefully be incorporated in my new system. Yes I know not all of my ratings followed this system perfectly, because in some cases I thought there were mitigating circumstances.

One final note I have a bad habit to referring to information known or generated at “compile time”. However in a Lisp/Scheme system you can run and use a program without “compiling” it. So under these circumstances consider compile time to be the process by which the programming environment converts the text of the program into its internal representation. Thus when you enter an expression at the REPL the moment the programming environment begins to deal with it is “compile time”. So for example if your language catches type errors at compile time then entering a statement with type errors at the REPL should result in a notification of these type errors.

2 points – runtime type information and checking
With run-time type information errors result in a controlled termination instead of an ugly crash. Also data can be examined by functions to determine its type.

2 point – compile time optimizations based on type information
The compiler is able to remove type checks and perform other performance optimizations when it knows the type of the data being operated on. For example if you know that a parameter will always be of type list then there is no need to insert instructions to check if it is a cons cell before you call car on it.

1 point – soft typing
Soft typing infers some, or possibly all, type information by working out from known parameter types and return types of primitive operations. This removes most of the need to explicitly declare the type of data.

1 point – type errors caught at compile (read) time
When reading in code the compiler / interpreter will raise an error if a function could be called with data that is not of the appropriate type.

1 point – extendable type system
New types should be able to be defined that are not part of the built in system. For example if the programmer wants to create line objects then they should be able to create a line type and expect the compiler to use this information to optimize and to catch type errors.

1 point – complex types allowed (composed of other types)
Types can be defined that are related to other types. For example the type of a list of number and the type of a list of booleans should not be the same, but they both should be considered variants of the type list.

1 point – results and parameters can be forced into a type
This allows programmers to create their own object systems that make use of the type system. For example if my make-line function returns functions that can be passed messages (are line objects) I need a way to signal to the compiler that this returned value should be considered of type line.

1 point – functions can be overloaded based on type of parameters
When the program is written multiple functions with the same name that are distinguished by having parameters lists of different types can be defined, and when compiled the appropriate call will be made based on the type information available, either through explicit declarations or type inference.

Posted in Exploring Scheme | Leave a Comment »