Showing how you can build a lambda calculus in 7 lines of Racket (that's the first function)

turing.rkt

#lang racket

;; Demonstration of a turing-complete language
(define (ev e [ρ '()])
  (match e
    [(? symbol? x) (cadr (assoc x ρ))]
    [`(λ (,xs ...) ,es) `(cls ,ρ ,xs ,es)]
    [`(,f ,as ...)
     (match (ev f ρ)
       [`(cls ,cρ ,xs ,es) (ev es (append (map list xs (map (λ (v) (ev v ρ)) as)) cρ ρ))])]))

;; Run like this:
;; (ev '... expression to evaluate ...)
;; (ev '((λ (x) (x x) (λ (y) (y y)))) => loops forever
;; (ev '((λ (x) x) (λ (y) y))) => #<closure y y>

;; Add math to make things a little more interesting
(define (prim-op? s) (assoc s `((+ ,+) (- ,-) (/ ,/) (* ,*))))

(define (ev+ e [ρ '()])
  (match e
    [(? number? x) x]
    [(? symbol? x) (cadr (assoc x ρ))]
    [`(λ (,xs ...) ,es) `(cls ,ρ ,xs ,es)]
    [`(,(? prim-op? op) ,as ...) (apply (cadr (prim-op? op)) (map (λ (v) (ev+ v ρ)) as))]
    [`(,f ,as ...)
     (match (ev+ f ρ)
       [`(cls ,cρ ,xs ,es) (ev+ es (append (map list xs (map (λ (v) (ev+ v ρ)) as)) cρ ρ))])]))

;; (ev+ '((λ (x) (+ x 1)) 1)) => 2