Representing Abstract Syntax with Records

 (define-datatype expression expression?

    (var-exp

      (id symbol?))

    (lambda-exp

      (id symbol?)

      (body expression?))

    (app-exp

       (rator expression?)

     (rand expression?)))

Parse: Concrete to Abstract Syntax

(define parse-expression

  (lambda (datum)

    (cond

      ((symbol? datum) (var-exp datum))

      ((pair? datum)

       (if (eqv? (car datum) 'lambda)

         (lambda-exp (caadr datum)

           (parse-expression (caddr datum)))

         (app-exp

           (parse-expression (car datum))

           (parse-expression (cadr datum)))

       )

      )

      (else (eopl:error 'parse-expression

              "Invalid concrete syntax ~s" datum))

)))

Example (Petite Scheme)

 

(current-directory

     “I:\\tkprasad\\cs784\\EOPL-CODE\\interps")

> (load "chez-init.scm")

> (load "2-2-2.scm")

> (parse-expression 'x)

(var-exp x)

> (parse-expression '(lambda (x) (f x)))

(lambda-exp x (app-exp (var-exp f) (var-exp x)))

> (parse-expression 45)

Error reported by parse-expression:

Invalid concrete syntax 45

debug>e

>(unparse-expression

      '(lambda-exp x (app-exp                    

                       (var-exp f) (var-exp x))))

(lambda (x) (f x))

Unparse: Abstract to Concrete Syntax

 

(define unparse-expression

  (lambda (exp)

    (cases expression exp

      (var-exp (id) id)

      (lambda-exp (id body)

        (list 'lambda (list id)

          (unparse-expression body)) )

      (app-exp (rator rand)

        (list (unparse-expression rator)

              (unparse-expression rand)) )

)))

 Role of Induction and Recursion

•Define data structures (infinite values) by induction.

•Seed elements.

•Closure operations.

•Define functions (operations) by recursion.

•Boundary/Basis case.

•Composite/Recursive case.

•Prove properties using structural induction.

•Basis case.

•Inductive step.

Representing Environment  

 Alternative 1

(define empty-env

  (lambda () '()))

(define extend-env

  (lambda (syms vals env)

    (cons (list syms vals) env) ))

(define apply-env

  (lambda (env sym)

    (if (null? env)

      (eopl:error 'apply-env "No binding for ~s" sym)

      (let ((syms (car (car env)))

            (vals (cadr (car env)))

            (env (cdr env)))

        (let ((pos (rib-find-position sym syms)))

          (if (number? pos)

            (list-ref vals pos)

            (apply-env env sym)))))

))

Alternative 2

(define empty-env

  (lambda ()

    (lambda (sym)

      (eopl:error 'apply-env "No binding for ~s" sym)) )

)

(define extend-env

  (lambda (syms vals env)

    (lambda (sym)

      (let ((pos (list-find-position sym syms)))

        (if (number? pos)

          (list-ref vals pos)

          (apply-env env sym)))) )

)

(define apply-env

  (lambda (env sym)

    (env sym) )

)

 

Alternative 3

(define-datatype environment environment?

  (empty-env-record)            

  (extended-env-record

    (syms (list-of symbol?))

    (vals (list-of scheme-value?))

    (env environment?)))

(define scheme-value? (lambda (v) #t))

 

(define empty-env

  (lambda ()

    (empty-env-record) ))

(define extend-env

  (lambda (syms vals env)

    (extended-env-record syms vals env)))

(define apply-env

  (lambda (env sym)

    (cases environment env

      (empty-env-record ()

        (eopl:error 'apply-env "No binding for ~s" sym))

      (extended-env-record (syms vals env)

        (let ((pos (list-find-position sym syms)))

          (if (number? pos)

            (list-ref vals pos)

            (apply-env env sym)))) )

))

 Scheme Queue

(define create-queue

  (lambda ()

    (let ((q-in '())  (q-out '()))

      (letrec

        ((reset-queue

           (lambda ()

             (set! q-in '()) (set! q-out '())) )

         (empty-queue?

           (lambda ()

             (and (null? q-in) (null? q-out))) )

         (enqueue

           (lambda (x)

             (set! q-in (cons x q-in))) )

         (dequeue

           (lambda ()

             (if (empty-queue?)

               (eopl:error 'dequeue "Not on an empty queue")

               (begin

                 (if (null? q-out)

                   (begin

                     (set! q-out (reverse q-in)) (set! q-in '())))

                   (let ((ans (car q-out)))

                     (set! q-out (cdr q-out))

                     ans))))) )

        (vector reset-queue empty-queue? enqueue dequeue))

)))