- 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)