Skip to content

Instantly share code, notes, and snippets.

# igalic/mccarthy-paper.rktSecret Last active Dec 3, 2015

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 '()]))
 > (ff '(( a b) c)) >(ff '((a b) c)) > (atom? '((a b) c)) < #f >(ff '(a b)) > (atom? '(a b)) < #f >(ff 'a) > (atom? 'a) < #t <'a 'a >
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.