retracing McCarthy's original LISP paper (http://www-formal.stanford.edu/jmc/recursive/node3.html) in Racket
#lang racket | |
; use trace-define, to effortlessly McCarthy's trace | |
(require racket/trace) | |
; we simplify the definition of atom? to | |
(trace-define (atom? x) | |
(not (pair? x))) | |
; 1. ff[x] | |
; The value of ff[x] is the first atomic symbol of the | |
; S-expression x with the parentheses ignored. Thus | |
(trace-define (ff x) | |
(if (atom? x) | |
x | |
; rather than `car`, we use `first` here | |
; because i can actually remember what `first` means ;) | |
(ff (first x)))) | |
; 2. subst[x ; y ; z] | |
; This function gives the result of substituting the | |
; S-expression x for all occurrences of the atomic | |
; symbol y in the S-expression z. It is defined by | |
(trace-define (subst x y z) | |
(if (atom? z) | |
(if (eq? z y) | |
x | |
z) | |
(cons (subst x y (first z)) (subst x y (rest z))))) | |
; 3. equal [x; y] | |
; This is a predicate that has the value T if x and y are | |
; the same S-expression, and has the value F otherwise. We have | |
(trace-define (equal? x y) | |
(cond | |
[(and (atom? x) (atom? y)) (eq? x y)] | |
[(nand (atom? x) (atom? y)) (and (equal? (first x) (first y)) (equal? (rest x) (rest y)))] | |
[else false])) | |
; n.b.: among is the first of functions that McCarthey defines | |
; which racket doesn't cover yet (null, append, pair? cadr, caddr, etc..) | |
; 2. among [x;y]. This predicate is true if the S-expression | |
; x occurs among the elements of the list y. We have | |
(trace-define (among? x y) | |
(and (not (null? y)) | |
(or (equal? x (first y)) (among? x (rest y))))) | |
; 3. pair [x;y]. This function gives the list of pairs of | |
; corresponding elements of the lists x and y. We have | |
(trace-define (pair x y) | |
(cond | |
[(nand (null? x) (null? y)) (cons (list (first x) (first y)) (pair (rest x) (rest y)))] | |
[else '()])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment