Project list

If you are thinking about hacking one of these projects, you would probably do well to take a look at a couple of existing Underground systems first:

Scsh projects

Scsh is a new Unix shell that is embedded inside Scheme. It provides a high-level Scheme notation for invoking and composing Unix programs. Instead of writing
    	delatex essay.tex | spell | sort | enscript -2r
you write
        (run (| (delatex essay.tex)
                (enscript -2r)))
Unlike traditional shells, scsh has more than a high-level notation; it also provides complete low-level access to the Unix kernel, and the programming power of a full, R5RS-compliant Scheme. Scsh runs on just about every Unix system around. It has gone through multiple releases, and is available on the Net.

Some scsh-based projects one could do:

Interactive command-line shell with job-control
Develop a csh- or sh-like notation for interactive use. This would involve learning how to use lexer and parser generator tools, Scheme macro systems, and other sophisticated Scheme hacking techniques. We have a design for this, but no time to implement it.

Emacs-based interactive shell with job-control
Port the emacs editor edwin from MIT Scheme to Scheme 48, and use it as the front-end for a screen-oriented shell. Directory listings would appear in windows, with common shell commands defined in Scheme and bound to emacs commands. Complex commands would be entered in Scheme form. Roll this together with a Scheme-based X windows manager, and you'd have a pretty amazing complete GUI...

Expect is a system for scripting interactive tasks in Unix. All the pieces are available in scsh for constructing a powerful, Scheme-based tool to automate similar tasks: job-control, regular-expression matching, pseudo-terminals, and signal handlers. A couple of macros and a few support routines is all you would need to build this system.

Scsh's process notation makes it easy to develop a Scheme-based variant of the make(1) program for dependency-directed recompilation. A B.S. thesis or Master's thesis level project would investigate more sophisticated alternatives to make's dependency-directed system.

Graphics projects

Functional Postscript
PostScript is the industry-standard description language for marking devices such as laser-printers. PostScript, in fact, is a complete programming language. When you send a PostScript file to a printer, you are really sending a complete program to be executed by the printer. As the printer executes your PostScript program, it builds up images on the page and prints them out.

PostScript is a simple language. It has a base set of imaging operators (such as "fill in this outline with ink" or "rotate this image by an angle"). These basic operators are composed and applied by programs written in the forth programming language.

Functional PostScript is a UROP-designed graphics language that takes PostScript's base imaging operators, and embeds them in a Scheme engine instead of a forth engine. A "picture description" is a small (or not so small) Scheme program; executing the program causes the picture to be rendered.

The resulting language is something fairly similar to the "picture" language used in Structure and Interpretation of Computer Programming and the 6.001 course for building Escher-like pictures, but with the extremely powerful PostScript primitives at the base. For example, you can use any PostScript font to render text.

The result is a system that provides device-independent, resolution-independent graphics support from Scheme. A full description of the system can be obtained on the Web, complete with sources. (Take a look; it's an elegant system.)

The current implementation produces output by rendering the picture to a stream of straight-line PostScript text, which can then be shipped off to any PostScript printer, or viewed from Ghostview or other previewer program.

We'd like to have a back-end that renders directly to the screen. This could be done by linking FPS's Scheme with the free Ghostscript C library of PostScript primitives to render to X. Then we'd have a high-level, device-indendent graphics system for doing interactive screen graphics.

X interfaces

Networking projects

Web agents
Suppose World-Wide Web servers had Scheme interpreters linked in with their executables. Then small Scheme programs could transfer themselves across the network from server to server to carry out tasks for their masters, perhaps coming back to a home machine to report on their results in the end. Scheme is a good choice for such a language because Scheme implementations are "safe" -- it is easy to guarantee that an arbitrary Scheme program received by a server can't damage the server or compromise its security. With proper cryptographic authentication, an agent can access or commit the user's resources: buy movie tickets, check his bank account, and so forth.

Internet protocols
Want to learn about Internet protocols? Scsh provides access to the Internet through Unix's socket interface. Several Internet protocols have been implemented with it, such as http for Web service, and smtp for email. It would be very nice to have the telnet and ftp protocols available as a software library.

Apache plug-in for scripting
Package scsh up as a plug-in for the Apache web server, for implementing server extensions in scsh.

Documentation tools

It would be pleasant to have a word-processing system that could be extended in Scheme, and have multiple back-ends, such as HTML, SGML, LaTeX, and emacs info. The markup processor is one such design. It was designed and implemented by grad students at MIT and Carnegie Mellon. Two PhD dissertations have been written using it, rendered both into LaTeX and HTML. However, the system needs further work.

A member of the Underground who works in the document-layout industry is interested in Scheme-based tools for markup, and is willing to advise a student who wants to develop these kinds of tools. We would want to make these tools available to the various documentation projects that exist for free software such as Linux.

Systems projects

The Scheme Underground uses a new Scheme implementation, Scheme 48 (source code available on the Net), that has many nice properties:

Scheme 48 is being used as an implementation platform by several research projects in the AI Lab. We are using it because it is elegant, comprehensible, efficient, easy to modify, and portable. This also means that any systems developed on top of Scheme 48 are easily exported outside MIT onto the Internet.

There are many projects possible for hacking Scheme48 for students who would like to get "under the hood" and learn what the internals of a new-tech Scheme implementation are like. Here is an assortment of projects that would provide real improvement to the system:

Dynamically-linked libraries
Dynamically linked libraries are modules of procedures and data (Scheme heaps, in fact) that are brought into a process' memory from the file system the first time an element of the module is referenced by the program. Hacking the Scheme 48 virtual machine to map in libraries shared-text read-only would allow multiple Scheme 48 programs to run in very small amounts of memory.

Advanced garbage-collection algorithms
Scheme 48 does not currently use generational garbage collection.

Mobile Scheme machines
We have embedded the Scheme 48 byte-code interpreter and static heap into the small ROM of a portable computer that can run off of batteries. We plan to use these systems for mobile robots and wearable computers.

Multithreading scsh
This is a challenging project. Scsh is currently built on top of an old release of Scheme 48 (0.36) that does not provide support for multi-threading. Porting scsh to a newer, multi-threaded release of Scheme 48 would require really digging into the internals of both systems, to preserve scsh's full Unix interface in the face of multi-threading.

This would pay off for many other systems that could then be written using thread-based concurrency, such as graphics interfaces.

Better C interface
Linking C libraries into scsh is difficult, and an important determinant of what one can do with the system. We could use a better system.
Database interfaces
If would be very useful for scsh to have interfaces to dbm or standard SQL-based rdbm's. For example, it would enable many kinds of interesting Web services to be provided using scsh's networking package.