On Scheme

Thoughts on Scheme and teaching Scheme

Archive for March, 2006

Graphics Experiment

Posted by Peter on March 29, 2006

I have been playing around with graphics in Dr. Scheme again. You can download my latest experiment from Sourceforge (and run it with the command (main go-for-a-drive)). In this demo you can fly a small spaceship with the a, d, and w keys and quit with q. Unfortunately because I needed to be able to detect multiple keys being held down at once I was forced to modify the graphics library slightly. Simply overwrite the two files in the PLT\collects\graphics directory with the ones provided in the release. Then delete the compiled directory and recompile with the new versions by running the Setup PLT utility in the root PLT folder.

Unfortunately there are still some problems with the graphics library that I can’t simply fix with edits. One is that I want the program to finish automatically when the window is closed (at the moment you have to exit from within the program or manually use the break command, closing the window has no effect). The other problem is flicker when drawing. What I really want to do is draw to a back-buffer and then flip it in all at once.

Thus I am going to attempt to write my own graphics routines using DirectX (obviously for windows only). Although I know how to code in C/C++ and use DirectX already I worry that actually writing the interface between the C code and Scheme will be taxing at best. The problem is that they encourage you to use their own compiler interface, which aids in linking with the Scheme libraries, ect. Unfortunately I may need to compile without their interface, since I will also need to link to the DirectX libraries. If anyone could point me to a better tutorial than the documentation found on the PLT/Dr. Scheme website it would be much appreciated.

Posted in Exploring Scheme | Leave a Comment »


Posted by Peter on March 29, 2006

As you may have already noticed by the new link on the right the Sourceforge companion site was approved. Strangely I never got an email that it was approved it just … appeared. I have uploaded the entire source found in my posts, so feel free to go have fun with it. I released it under the BSD license because that was the least restrictive one I could choose. I was also planning on having everything nice and modularized by now, but unfortunately you can’t set! or fluid-let a variable exported by a module. Thus I had to re-write part of the exception handling code so that throw was never directly set, but could still be used like normal. I did get it working and uploaded (version 2), but I have yet modularized the object code.

Posted in Exploring Scheme | Leave a Comment »

A Type System For Scheme, Part 4

Posted by Peter on March 28, 2006

After researching type systems, and smacking myself for my foolish first attempt, I have come up with a second proposal for a type system that could be added to Scheme, in this case mostly transparently. This system is constructed that type inference will catch compile time type errors as well as result in performance improvements. The constructs described herein are to make the life of the programmer easier, and to allow for the creation of custom types / object systems.

The simple built in types are as follows: number, boolean, string, char, symbol, nil, any

Complex types also exist. Complex types take one or more types as arguments, which may be either simple types or complex types which also have their arguments specified, for example pair-of could be used in the following way: (pair-of number string) or as (pair-of (list-of number) string). The types tor and tand are special in that they both take two or more arguments and that they have special implication for type inference. For example if in the body of a function a variable is used both as a number and as a symbol then it must be of type (tand number symbol). However because the compiler can rule out certain conjunctions as possible this will be rejected as an error. Likewise if a function returns a number on one branch and a symbol on another its return type will be (tor number symbol). This however is not a valid result to pass to a function that expects a value of type symbol as a parameter (although (tand symbol number) would be).
The following complex types are built in:
pair-of, vector-of, list-of, tor, tand, ->

More on type inference:
As you may have already gathered the program performs type inference wherever possible. To make type inference work perfectly a few enhancements are needed. One is that a value should be able to be assigned the special value #<undefined> when it is first declared, either in a define or a let statement. This tells the compiler that its type should be computed from the first time it is set! and not from the declaration. Also there needs to be a type conditional in the form: (tcond variable (type1 statements) (type2 statements) … [(else statements)]). If the else clause is omitted then the compiler will infer that the variable is of type (tor type1 type2 …), if there is an else clause it will infer that it is of type any. Within each clause the variable is treated as if it is the tested type. For example (tcond x (number (+ x 2)) (boolean (not x))) will cause the compiler to infer that x is (tor number boolean), that the return type of this statement is (tor number boolean). Despite these inferences the first clause will compile as if x is of type number and the second as if x is of type boolean. Just as in a standard cond only one clause will be invoked. This tcond also allows us to do away with built in type predicates. For example number? could be written as (define (number? x) (tcond x (number #t) (else #f))). Finally, we can “force” the result of an evaluation with the special form (force type expression). The return type of a force statement is the conjunction (tand) of the given type and the return type of the expression.

Type of functions:
The type of a function is constructed with the -> type, but typedscm does a much better job of explaining it than I could, so just go look at their site. Although I might be tempted to make a few improvements to that part of their system it is simply more efficient to let the experts describe the complex job of typing a function.

Types can be declared as follows:
(define-type type-name known-type)
A type declaration in this way is often used as an abbreviation for a complex type such as (define-type vec-list (list-of (vector-of number)))
A second way to define types is:
(define-type (type-name related-types …) known-type)
These type declarations can also be self referential. For example if you wanted to define a generic binary tree type you would do so as follows (define-type (binary-tree-of X) (pair-of (tor X (binary-tree-of X)) (tor X (binary-tree-of X)))).
Finally if you must you can “extend” an old type with the following:
(define-extended-type (type-name related-types …) extended-types …)
If tested, for example with a tcond, or when the compiler is determining if the arguments to a function call are of a valid type, the extended type can be considered as one of the types it is extended from, however the types it is extended from will not be considered the derived type for the purposes of these computations.

Although I haven’t thought of a clean syntax for it yet obviously imported functions from compiled code (for example a C library) will need to have their type declared at the time they are imported for the purpose of type inference.

One final issue to address is how to create generic functions, and thus by extension generic classes. Obviously generics must be implemented as a macro (since types are not first class objects). One way to define a generic might be (define-generic name (unbound-types …) body). For example a function might be written as (define-generic my-function (A B) (lambda (x) (tcond x (A …) (B …))))). When you wanted to call such a function you would write ((my-function number boolean) params …), and if you wanted to get the function itself (for example to pass it as a value) you would write (my-function number boolean). The system might work as follows underneath: The generic name itself is defined as a macro. When that macro is invoked it looks up the type parameters in a hash table, if that combination is already known it returns a reference to the needed function. If it is not known it compiles a new top-level function, substituting the types given as parameters for the unbound types, and then saves that result in its look-up hash.

Overall Rating:
9/10: This proposal does a lot of things, but there are some areas it still doesn’t address. For example I couldn’t think of a clean way of doing overloading by parameter type. Likewise I was unable to devise a way to make types first class objects and still be able to conduct type inference properly

Posted in Exploring Scheme | 2 Comments »

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 »

Java is Bad for Students

Posted by Peter on March 26, 2006

I’ll be back with more on type systems tomorrow, hopefully, but today I want to state my objections to Java being used to teach students computer science, especially in college. Joel on Software also wrote a piece on Java schools, and his conclusion was that Java was too easy for students, that it did too much for them and thus never forced them to learn the concepts. I think this is true in terms of the number of libraries built in, for example students never really need to know how to create a linked list, however in terms of the language itself I think that Java is just the opposite, it is too complex.

Not everyone begins programming at the college level knowing about variables and classes and functions, and because of this many promising students are turned away from programming. To create even a simple hello world program in Java you need to be able to import from a library, create a class, create a function in that class, and write a complicated prototype for the main function. On the other hand in C, for example, you just need to write a very simple main function and use printf. Most teachers simply tell students to simply copy the boiler plate code, which is fine, but to do anything in Java you need to use objects, so there is a lot of code students need to copy and paste. In even the simplest programs you are using System.out to print your results and to manipulate text you need Strings, both of which require the student to use objects and method calls before they are ready to. This alone adds more and more complexity that the students are just told to ignore, or to copy and paste without it being explained to them. Even using Strings can lead to confusing problems as students wonder why String s = new String() is possible but int i = new int() isn’t. Eventually some students are able to make sense of this, but for many weeks, before objects are introduced students are engaging in a copy-paste mentality for the majority of their work.

This copy-paste mentality makes the program seem much more confusing than it really is. By the time students are introduced to objects and the difference between a reference and a value most of them are thoroughly lost. Besides, how do you explain a reference to students who don’t know that data has addresses in memory, much less what a pointer is? The answer is that you just do some hand-waving, and students learn enough that they don’t make too many mistakes, and also have no idea what it really is. Because of this the bar has to be greatly lowered on introductory programming courses, and in subsequent courses, as students enter into the system without a real understanding of what the program is doing, but only with a handful of tricks that seem to make things work.

The benefits of beginning with C/C++/ect is that in these languages it is possible to write complete programs with only a very small portion of the language. Also it is possible to explain more complex features in terms of simpler ones, for example a struct can be explained in terms of an array with named slots. Also students who understand one of these languages have a much easier time understanding assembly language, and thus what the machine is actually doing when their programs run, which in turn leads to fewer bugs and faster programs. Scheme and Lisp also have the advantage that complete programs (at the REPL) can be run with only a small portion of the language. Basically all you need to do is explain define and function calls and you are ready to go. Admittedly Scheme and Lisp don’t give students an understanding of the low level operation of the computer, however they make up for this by making it easy to teach about complex algorithms, functional programming, and data structures. For example students can be taught about binary trees using only lists, without any need for complicated structures or objects.

Unfortunately Java, which is easy to learn for programmers who have already mastered the fundamentals of programming, has been adopted in the majority of colleges, probably because of the obsession with giving their students “practical” skills. Thus this generation of programmers is coming out of college barely able to code.

Symptoms of Java Education:
-Every bug is approached with the debugger or with print statements
-Programs are never optimized
-Difficulty learning new languages
-Difficulty leaning new styles of programming

Posted in Teaching Scheme | Leave a Comment »