Midterm

#lang typed-scheme

#|
The grammar:
  <FLANG> ::= <num>
            | { + <FLANG> <FLANG> }
            | { - <FLANG> <FLANG> }
            | { * <FLANG> <FLANG> }
            | { / <FLANG> <FLANG> }
            | { with { <id> <FLANG> } <FLANG> }
            | <id>
            | { fun { <id> } <FLANG> }
            | { call <FLANG> <FLANG> }

Evaluation rules:

  subst:
    N[v/x]                = N
    {+ E1 E2}[v/x]        = {+ E1[v/x] E2[v/x]}
    {- E1 E2}[v/x]        = {- E1[v/x] E2[v/x]}
    {* E1 E2}[v/x]        = {* E1[v/x] E2[v/x]}
    {/ E1 E2}[v/x]        = {/ E1[v/x] E2[v/x]}
    y[v/x]                = y
    x[v/x]                = v
    {with {y E1} E2}[v/x] = {with {y E1[v/x]} E2[v/x]} ; if y =/= x
    {with {x E1} E2}[v/x] = {with {x E1[v/x]} E2}
    {call E1 E2}[v/x]     = {call E1[v/x] E2[v/x]}
    {fun {y} E}[v/x]      = {fun {y} E[v/x]}           ; if y =/= x
    {fun {x} E}[v/x]      = {fun {x} E}

  eval:
    eval(N)            = N
    eval({+ E1 E2})    = eval(E1) + eval(E2)  \ if both E1 and E2
    eval({- E1 E2})    = eval(E1) - eval(E2)   \ evaluate to numbers
    eval({* E1 E2})    = eval(E1) * eval(E2)   / otherwise error!
    eval({/ E1 E2})    = eval(E1) / eval(E2)  /
    eval(id)           = error!
    eval({with {x E1} E2}) = eval(E2[eval(E1)/x])
    eval(FUN)          = FUN ; assuming FUN is a function expression
    eval({call E1 E2}) = eval(Ef[eval(E2)/x])  if eval(E1)={fun {x} Ef}
                       = error!                otherwise
|#

(define-type FLANG
  [Num  (n Number)]
  [Add  (lhs FLANG) (rhs FLANG)]
  [Sub  (lhs FLANG) (rhs FLANG)]
  [Mul  (lhs FLANG) (rhs FLANG)]
  [Div  (lhs FLANG) (rhs FLANG)]
  [Id   (name Symbol)]
  [With (name Symbol) (named FLANG) (body FLANG)]
  [Fun  (name Symbol) (body FLANG)]
  [Call (fun-expr FLANG) (arg-expr FLANG)])

(: parse-sexpr : (Sexpr -> FLANG))
;; to convert s-expressions into FLANGs
(define (parse-sexpr sexpr)
  [...])

(: parse : (String -> FLANG))
;; parses a string containing an FLANG expression to a FLANG AST
(define (parse str)
  [...])

(: subst : (FLANG Symbol FLANG -> FLANG))
;; substitutes the second argument with the third argument in the
;; first argument, as per the rules of substitution; the resulting
;; expression contains no free instances of the second argument
(define (subst expr from to)
  (cases expr
    [(Num n) expr]
    [(Add l r) (Add (subst l from to) (subst r from to))]
    [(Sub l r) (Sub (subst l from to) (subst r from to))]
    [(Mul l r) (Mul (subst l from to) (subst r from to))]
    [(Div l r) (Div (subst l from to) (subst r from to))]
    [(Id name) (if (eq? name from) to expr)]
    [(With bound-id named-expr bound-body)
     (With bound-id
           (subst named-expr from to)
           (if (eq? bound-id from)
             bound-body
             (subst bound-body from to)))]
    [(Call l r) (Call (subst l from to) (subst r from to))]
    [(Fun bound-id bound-body)
     (if (eq? bound-id from)
       expr
       (Fun bound-id (subst bound-body from to)))]))

(: arith-op : ((Number Number -> Number) FLANG FLANG -> FLANG))
;; gets a Scheme numeric binary operator, and uses it within an FLANG
;; `Num' wrapper
(define (arith-op op expr1 expr2)
  (define: (Num->number [e : FLANG]) : Number
    (cases e
      [(Num n) n]
      [else (error 'arith-op "expects a number, got: ~s" e)]))
  (Num (op (Num->number expr1) (Num->number expr2))))

(: eval : (FLANG -> FLANG))
;; evaluates FLANG expressions by reducing them to *expressions*
(define (eval expr)
  (cases expr
    [(Num n) expr]
    [(Add l r) (arith-op + (eval l) (eval r))]
    [(Sub l r) (arith-op - (eval l) (eval r))]
    [(Mul l r) (arith-op * (eval l) (eval r))]
    [(Div l r) (arith-op / (eval l) (eval r))]
    [(With bound-id named-expr bound-body)
     (eval (subst bound-body
                  bound-id
                  (eval named-expr)))]
    [(Id name) (error 'eval "free identifier: ~s" name)]
    [(Fun bound-id bound-body) expr]
    [(Call fun-expr arg-expr)
     (let ([fval (eval fun-expr)])
       (cases fval
         [(Fun bound-id bound-body)
          (eval (subst bound-body
                       bound-id
                       (eval arg-expr)))]
         [else (error 'eval "`call' expects a function, got: ~s"
                            fval)]))]))

(: run : (String -> Number))
;; evaluate a FLANG program contained in a string
(define (run str)
  (let ([result (eval (parse str))])
    (cases result
      [(Num n) n]
      [else (error 'run
                   "evaluation returned a non-number: ~s" result)])))