retracing McCarthy's original LISP paper (http://www-formal.stanford.edu/jmc/recursive/node3.html) in Racket

mccarthy-paper.rkt

#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 '()]))

trace

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