Write Yourself a Scheme in 48 Hours

A Haskell Tutorial

By Jonathan Tang

Download in .tar.gz format
Download in .zip format

Contents

  1. Overview
  2. First Steps: Compiling and running
  3. Parsing
    1. A Simple Parser
    2. Whitespace
    3. Literal Numbers and Strings: Return Values
    4. Lists, Dotted Lists, and Quoted Data: Recursive Parsers
  4. Evaluation, Part 1
    1. Displaying Values: Show and Typeclasses
    2. Evaluating Primitive Values: Pattern Matching
    3. Evaluating Primitive Functions: First-class Functions
  5. Intermezzo: Error Checking & Exceptions
  6. Evaluation, Part 2
    1. Additional Primitives: Partial Application
    2. Conditionals: Pattern Matching 2
    3. List Primitives: car, cdr, and cons
    4. Equal? and Weak Typing: Heterogenous Lists
  7. Building a REPL: Basic I/O
  8. Adding Variables and Assignment: Mutable State in Haskell
  9. Defining Scheme Functions: Closures and Environments
  10. Creating IO Primitives: File I/O
  11. Towards a Standard Library: Fold and Unfold
  12. Conclusion & Further Resources

12. Conclusion

You now have a working Scheme interpreter that implements a large chunk of the standard, including functions, lambdas, lexical scoping, symbols, strings, integers, list manipulation, and assignment. You can use it interactively, with a REPL, or in batch mode, running script files. You can write libraries of Scheme functions and either include them in programs or load them into the interactive interpreter. With a little text processing via awk or sed, you can format the output of UNIX commands as parenthesized Lisp lists, read them into a Scheme program, and use this interpreter for shell scripting.

There're still a number of features you could add to this interpreter. Hygienic macros let you perform transformations on the source code before it's executed. They're a very convenient feature for adding new language features, and several standard parts of Scheme (such as let-bindings and additional control flow features) are defined in terms of them. Section 4.3 of R5RS defines the macro system's syntax and semantics, and there is a whole collection of papers on implementation. Basically, you'd want to intersperse a function between readExpr and eval that takes a form and a macro environment, looks for transformer keywords, and then transforms them according to the rules of the pattern language, rewriting variables as necessarily.

Continuations are a way of capturing "the rest of the computation", saving it, and perhaps executing it more than once. Using them, you can implement just about every control flow feature in every major programming language. The easiest way to implement continuations is to transform the program into continuation-passing style, so that eval takes an additional continuation argument and calls it, instead of returning a result. This parameter gets threaded through all recursive calls to eval, but only is only manipulated when evaluating a call to call-with-current-continuation.

Dynamic-wind could be implemented by keeping a stack of functions to execute when leaving the current continuation and storing (inside the continuation data type) a stack of functions to execute when resuming the continuation.

If you're just interested in learning more Haskell, there are a large number of libraries that may help:

This should give you a starting point for further investigations into the language. Happy hacking!

Acknowledgements

Thanks to Ketil Malde, Pete Kazmier, and Brock for sending in questions and suggestions about this tutorial. Additional comments, clarifications, and corrections can be sent to jonathan.d.tang@gmail.com.