Skip to content

Instantly share code, notes, and snippets.

@igalic
Last active December 3, 2015 14:26
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
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
>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment