Autumn 2004
Nachum Dershowitz

  1. You must write a rewrite program to sort a list of natural numbers from smallest to largest.
    Your program should look like this:
    ;; everything must be in Lisp/Scheme syntax
    ;; numbers are represented in unary:
    ;; 0, (s 0), ... etc.
    ;; lists are
    ;; nil, (cons 0 nil), (cons 0 (cons 0 nil)), etc.
    ;; each rule is a dotted pair
    ;; for example
    ;; sort(x) -> nil
    ;; looks like this
    ;; ((sort x) . nil)
    ;; variables start with u,v,w,x,y, or z
    ;; your program should be in a file and look like this
    (define sort '(
    ;; sort(nil) -> nil
    ((sort nil) . nil)
    ;; more rules here
    ;; for sort and any auxiliary programs
    Put your name and id# at the head of the file with your sorting program
    Mail it to me after testing it with my interpreter.
    To test your solution, run ~nachumd/rewrite/Homework/hw1.scm
    and give it the name of the file with your solution in quotes (e.g. "sort.scm")
    My interpreter is at ~nachumd/rewrite/rewrite.scm (Scheme)
    or ~nachumd/rewrite/Rewriter.txt (Lisp)