;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname foomble) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; Data Definition

(define-struct lam (para body))
(define-struct app (fun arg))

;; FR is one of:
;;    -- VR
;;    -- (make-lam VR FR)
;;    -- (make-app FR FR)
;; VR is a  Symbol

;; -----------------------------------------------------------------------------
;; dB : FR -> FR 
;; replace variable occurrences with their 'distantc' to the binding lambda (if)

(check-expect (dB 'X) 'X)
(check-expect (dB (make-lam 'X 'X)) (make-lam 'X 'zero))
(check-expect 
 (dB (make-lam 'X (make-app 'X (make-lam 'Y (make-app 'Y 'X)))))
 (make-lam 'X (make-app 'zero (make-lam 'Y (make-app 'zero 'one)))))
(check-expect (dB (make-lam 'X (make-lam 'Y (make-lam 'Z (make-lam 'W 'X)))))
              (make-lam 'X (make-lam 'Y (make-lam 'Z (make-lam 'W 'three)))))



;; by STRUCTURAL DESIGN ON fr, WITH ACCUMULATORS 
(define (dB fr0)
  (local (;; FR [Listof VR] -> FR
          ;; STRUCTURAL DESIGN ON fr, WITH ACCUMULATOR env
          ;; env: parameters encountered on path from fr0 to fr
          (define (dB0 fr env)
            (cond
              [(symbol? fr) (lookup fr env 0)]
              [(lam? fr) (local ((define para (lam-para fr)))
                           (make-lam para (dB0 (lam-body fr) (cons para env))))]
              [(app? fr) 
               (make-app (dB0 (app-fun fr) env) (dB0 (app-arg fr) env))]))
          ;; VR [Listof VR] -> Symbol 
          ;; distance of x to its first occurrence in env as a symbol; else x
          ;; STRUCTURAL DESIGN (env) WITH ACCUMULATOR 
          ;; d: distance of x to env0
          (define (lookup x env d)
            (cond
              [(empty? env) x]
              [else (if (symbol=? (first env) x) 
                        (number->symbol d)
                        (lookup x (rest env) (+ d 1)))]))
          ;; Number -> Symbol
          ;; convert the given number into a symbol (as provided)
          ;; DOMAIN KNOWLEDGE (English)
          (define (number->symbol n)
            (cond
              [(= n 0) 'zero]
              [(= n 1) 'one]
              [(= n 2) 'two]
              [(= n 3) 'three]
                [else 'etc])))          
    (dB0 fr0 '())))