Clase Substitución CC4101

gistfile1.rkt

#lang plai 

#|
<WAE> ::= <num> 
      |  {+ <WAE> <WAE>}
      |  {- <WAE> <WAE>}
      |  {with {<id> <WAE>} <WAE>}
      |  <id>
|#
(define-type WAE
  [num (n number?)]
  [add (l WAE?) (r WAE?)]
  [sub (l WAE?) (r WAE?)]
  [with (name symbol?) (named-expr WAE?) (body WAE?)]
  [id (name symbol?)])

;; parse :: s-expr -> WAE
(define (parse sexp)
; Tarea personal.
  ...)

#;(test (parse '{with {x {+ 1 2}} {+ x x}})
      (with 'x (add (num 1) (num 2))
            (add (id 'x) (id 'x))))

;; subst :: WAE symbol WAE -> WAE
(define (subst expr sub-id val)
  (type-case WAE expr
    [id (n) (if
             (symbol=? n sub-id)
             val
             expr)]
    [add (l r) (add (subst l sub-id val)
                    (subst r sub-id val))]
    [sub (l r) (sub (subst l sub-id val)
                    (subst r sub-id val))]
    [with (bound-id named-expr bound-body)
          (if
           (symbol=? bound-id sub-id)
           (with bound-id
                 (subst named-expr sub-id val)
                 bound-body)
           (with bound-id 
                 (subst named-expr sub-id val) 
                 (subst bound-body sub-id val)))]
    [else expr]))

;; calc :: WAE -> number
;; evalua la expresion aritmetica dada
(define (calc expr)
  (type-case WAE expr
    [num (n) n]
    [add (l r) (+ (calc l) (calc r))]
    [sub (l r) (- (calc l) (calc r))]
    [id (name) (error "unknown identifier" name)]
    [with (name named-expr body) (calc (subst body name (num (calc named-expr))))]))

(define (run prog)
  (calc (parse prog)))

(test (run 4) 4)
(test (run '{+ 1 {- 2 3}}) 0)

(test (run '{with {x 100}
                  {+ 1 {- 2 3}}}) 0)

(test (run '{with {x {+ 1 2}}
                  {+ x x}}) 6)

(test (run '{with {x 2}
                  {with {y 3}
                        {+ x y}}}) 5)

(test (run '{with {x 2}
                  {with {y x}
                        {+ y y}}}) 4)

(test (run '{with {x 2}
                  {with {x 3}
                        {+ x x}}}) 6)

(test/exn (run 'x) "unknown identifier")
(test/exn (run '{with {x 2}
                      {with {y 3}
                            {+ x z}}}) 
          "unknown identifier")

(test (run '{with {x 5}
                  {with {x x}
                        x}}) 5)