<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
(load  "drscheme-eopl.ss")

;; Abstraktne süntaks

(define-record  lit (datum))
(define-record  varref (var))
(define-record  lambda (formal body))
(define-record  app (rator rand))


;; Konkreetsest süntaksist abstraktsesse ja tagasi

(define parse
  (lambda (datum)
    (cond
      ((number? datum) (make-lit datum))
      ((symbol? datum) (make-varref datum))
      ((pair? datum)
       (if (eq? (car datum) 'lambda)
           (make-lambda (caadr datum) (parse (caddr datum)))
           (make-app (parse (car datum)) (parse (cadr datum)))))
      (else (error "parse: Invalid concrete syntax" datum)))))

(define unparse
  (lambda (exp)
    (variant-case exp
       (lit (datum) datum)
       (varref (var) var)
       (lambda (formal body) 
         (list 'lambda (list formal) (unparse body)))
       (app (rator rand) (list (unparse rator) (unparse rand)))
       (else (error "unparse: Invalid abstract syntax" exp)))))


;; Substitutsioon (substitute e m x) == e[m/x]

(define substitute
  (lambda (e m x)
    (variant-case e
       (lit () e)
       (varref (var) (if (eq? x var) m e))
       (app (rator rand)
          (make-app (substitute rator m x)
                    (substitute rand  m x)))
       (lambda (formal body)
          (cond
            ((eq? x formal) e)
            ((free? formal m)
                (let ((z (gensym)))
                  (make-lambda z 
                     (substitute (substitute body
                                     (make-varref z) formal)
                                 m x))))
            (else (make-lambda formal
                               (substitute body m x)))))
         (else (error "substitute: Invalid abstract syntax" e)))))

(define free?
  (lambda (x expr)
    (variant-case expr
       (lit () #f)
       (varref (var) (eq? x var))
       (app (rator rand)
          (or (free? x rator) (free? x rand)))
       (lambda (formal body)
          (if (eq? x formal)  
              #f
              (free? x body)))
       (else (error "free?: Invalid abstract syntax" expr)))))


;; Ühesammuline beta-reduktsioon
	
(define beta-reduce
  (lambda (rator rand)
    (substitute (lambda->body rator)
                rand 
                (lambda->formal rator))))


;; Aplikatiivses järjekorras väärtustaja

(define app-order-eval
  (lambda (exp)
    (variant-case exp
      (lit (datum) exp)
      (varref (var) exp)
      (lambda (formal body) (make-lambda formal (app-order-eval body)))
      (app (rator rand)
           (let ((rator-val (app-order-eval rator))
                 (rand-val  (app-order-eval rand)))
             (if (lambda? rator-val)
                 (app-order-eval (beta-reduce rator-val rand-val))
                 (make-app rator-val rand-val))))
      (else (error "app-order-eval: not a valid expressions" exp)))))


;; Normaaljärjekorras väärtustaja

(define normal-order-eval
  (lambda (exp)
    (variant-case exp
      (lit (datum) exp)
      (varref (var) exp)
      (lambda (formal body) (make-lambda formal (normal-order-eval body)))
      (app (rator rand)
           (if (lambda? rator)
               (normal-order-eval (beta-reduce rator rand))
               (let ((rator-val (normal-order-eval rator)))
                 (if (lambda? rator-val)
                     (normal-order-eval (beta-reduce rator-val rand))
                     (make-app rator-val 
                                  (normal-order-eval rand))))))
      (else (error "normal-order-eval: not a valid expressions" exp)))))


;; Mõned avaldised testimiseks

(define term1 '((lambda (x) (x (x y)))
                ((lambda (w) w) z)))

(define term2 '((lambda (y) 3)
                ((lambda (x) (x x))
                 (lambda (x) (x x)))))

; (unparse (app-order-eval
;                (parse term1)))
;
; (unparse (normal-order-eval
;                (parse term2)))