Coding Challenge

Here is a little coding challenge. Learning how to solve this probably won't make you a better programmer (it may make you worse) but it's fun anyway. You are given a file named "helloworld.cxx" that contains the following code.

#include <stdio.h>
#include "muck.h"

int 
main(int argc, char **argv)
{
    printf("%s\n", "Hello World!");
}

You can't edit this file! Your job is to write the "muck.h" header file. When you're done compile "helloworld.cxx" and run it and the output should be "Goodbye!" followed by a newline. Nothing more nothing less. Remember you can only modify "muck.h" and you must compile "helloworld.cxx" unmodified. My solution and it's Makefile.

The Essence of Scheme (part two)

This post is a continuation of part one. You probably want to read that post first. So in my previous post I walked you through a nifty little though experiment on why Scheme is so expressive, and why those pesky ('s and )'s are actually useful. In this post I hope to provide some concrete examples of using Scheme's macros to do interesting things. So lets start with a simple example. The Scheme programming language (R5RS) doesn't have a built in "while" loop. It does have a "do" loop which is kind of like a "for" loop but I don't think it gets used much. Most Schemers use recursion instead. Lets say you're just learning Scheme and recursion hurts your brain and you really really just want to use a "while" loop just this one time and you promise that you'll pay better attention when you CS professor talks about recursion. It turns out it's quite easy to implement a "while" loop as a Scheme macro¹.

;; A while loop
(define-syntax while
  (syntax-rules ()
    [(_ (cnd ...) body ...)
     (letrec ([tmp (lambda () (if (cnd ...) (begin body ... (tmp)) (void)))])
       (tmp))]))

If you want to try it out here is a bit of code that uses the while loop to count from 10 down to 1.

(define count 10)
(while (> count 0)
       (printf "~a\n" count)
       (set! count (- count 1)))

So in 10 lines of code you can define a "while" loop that works just like the "while" loops built into C/C++/Java/Python/Insert_Your_Favorite_Language_Here.

So that doesn't seem to hard. If C didn't have a built in "while" loop you could always create you're own with a C style macro as follows.

#define WHILE(cond) for(;cond;)

Lets try something more difficult. Scheme also doesn't have a C/C++ "#include" directive. So lets write our own.

;; Define include
(define-syntax include
  (lambda (stx)
    (define (read-all port)
      (let ([exp (read port)])
        (if (eof-object? exp)
            '()
            (cons exp
                  (read-all port)))))
    (define read-file
      (lambda (fn ctx)
        (let ([port (open-input-file fn)])
          (begin0
            (datum->syntax ctx (read-all port))
            (close-input-port port)))))
    (syntax-case stx ()
      ((ctx filename)
       (with-syntax ([(exp ...) (read-file (syntax->datum #'filename) #'ctx)])
         #'(begin exp ...))))))

Once you've defined this you can use it as follows.

(include "extern.ss")

Once you've defined the "include" macro any include expression will get evaluated at compile time which opens up the included file reads in the text and injects it into the the source file at the location of the "include" call. Spend a little time thinking about that. A Scheme programmer can write code that gets evaluated at compile time and that code can open, close, and read from files. So if Scheme's macro language allows you to read from files what else can it do? It turns out anything that a Scheme program can do. The above macro can read from files because any old PLT-Scheme program can read from files. A Scheme macro is just a chunk of regular old Scheme code that gets executed at compile time. If your Scheme allows you to open up a TCP/IP socket then you can write a macro to do this at compile time². If your Scheme allows you to rotate images then you can do it at compile time. If your Scheme allows you to play music then you can play music at compile time³. OK so lets look at some more examples.

(define current-catch 
  (make-parameter 
   (lambda (exn) 
     (printf exn) 
     (exit 1))))

(define (throw exn)
  ((current-catch) exn))

(define-syntax try
  (syntax-rules (catch throw)
    [(_ body ... (catch exn cbody ...))
     (let/cc k
       (parameterize ([current-catch (lambda (exn) cbody ... (k (void)))])
         (begin body ...)))]))

This chunk of code allows users to throw and catch exceptions using "try", "catch" and "throw"⁴. Scheme doesn't have a built in exception mechanism, but in 13 lines of code you can write your own. The following code will use the above macro and functions.

(try 
 (printf "Yes\n") 
 (throw "Error\n")
 (printf "No\n")
 (catch exn 
   (printf exn)))

It will print "Yes" followed by "Error" the "No" will not be displayed because of the "Error" exception will be thrown. OK lets look at one more.

(define-syntax define-generator
  (lambda (stx)
    (syntax-case stx ()
      ((_ (name args ...) body ...)
       (with-syntax ([yield (datum->syntax #'name 'yield)])
         #'(define (name args ...)
             (define yield-k #f)
             (define return-k void)
             (define (yield retval)
               (let/cc k
                 (set! yield-k k)
                 (return-k retval)))
             (lambda ()
               (let/cc ret
                 (set! return-k ret)
                 (if yield-k
                     (yield-k '())
                     (begin
                       body ...
                       (set! yield-k (lambda (x) (void)))))))))))))

This allow you to define Python style generators. Here is a simple example that defines a "range" generator that will reuturn 0 he first time it's called and 1 the next.

(define-generator (range init limit)
  (let loop ([i init])
    (yield i)
    (when (< i limit)
      (loop (+ i 1)))))

(define foo (range 0 1))
(foo)
(foo)

I hope these examples give some insight at how expressive and malleable the Scheme programming language is. There is one more issue I'd like to address. If you're a Python programmer you may be thinking to yourself. "Hey Python has loops, exceptions, generators and import which is kind of like #include. If python has these built in then why should I use Scheme?" That is a valid but slightly myopic question. The point of Scheme's macro system is not to create another Python with funnier syntax. The real point is that you the developer can extend and grow the language to meet your needs. You may extend the language by adding features that are found in other programming languages, but you may also add features that don't exist in any language, and that don't have a name, and that may not be generally useful but really make the current program you're working on really really easy to write. In Python, Perl and Java users have the power to create and extend libraries, in Scheme users have the power to create and extend languages⁵. Power to the people!

[1] All examples tested in in PLT-Scheme 4.1.3.
[2] Implementing "http-include" is left as an exercise for the reader.
[3] Playing music at compile time is possible but not recommended by the author.
[4] Anyone want to try implementing exceptions in C?
[5] There is one major downside to learning Scheme. Eventually you'll find yourself writing a program in C/C++/Python/Java and you'll realize that you could solve some problem really elegantly if you could just extend the language just a little bit. Then you'll realize that you can't and you'll spend the next hour wishing you we're never enlightened.