#lang pl 04 #| BNF for the ALGAE language: ::= | { + ... } | { * ... } | { - ... } | { / ... } | { with { } } | |# ;; ALGAE abstract syntax trees (define-type ALGAE [Num Number] [Add (Listof ALGAE)] [Mul (Listof ALGAE)] [Sub ALGAE (Listof ALGAE)] [Div ALGAE (Listof ALGAE)] [Id Symbol] [With Symbol ALGAE ALGAE]) (: parse-sexpr : Sexpr -> ALGAE) ;; parses s-expressions into ALGAEs (define (parse-sexpr sexpr) ;; utility for parsing a list of expressions (: parse-sexprs : (Listof Sexpr) -> (Listof ALGAE)) (define (parse-sexprs sexprs) (map parse-sexpr sexprs)) (match sexpr [(number: n) (Num n)] [(symbol: name) (Id name)] [(cons 'with more) (match sexpr [(list 'with (list (symbol: name) named) body) (With name (parse-sexpr named) (parse-sexpr body))] [else (error 'parse-sexpr "bad `with' syntax in ~s" sexpr)])] [(list '+ args ...) (Add (parse-sexprs args))] [(list '* args ...) (Mul (parse-sexprs args))] [(list '- fst args ...) (Sub (parse-sexpr fst) (parse-sexprs args))] [(list '/ fst args ...) (Div (parse-sexpr fst) (parse-sexprs args))] [else (error 'parse-sexpr "bad syntax in ~s" sexpr)])) (: parse : String -> ALGAE) ;; parses a string containing an ALGAE expression to an ALGAE AST (define (parse str) (parse-sexpr (string->sexpr str))) #| Formal specs for `subst': (`N' is a , `E1', `E2' are s, `x' is some , `y' is a *different* ) N[v/x] = N {+ E ...}[v/x] = {+ E[v/x] ...} {* E ...}[v/x] = {* E[v/x] ...} {- E1 E ...}[v/x] = {- E1[v/x] E[v/x] ...} {/ E1 E ...}[v/x] = {/ E1[v/x] E[v/x] ...} y[v/x] = y x[v/x] = v {with {y E1} E2}[v/x] = {with {y E1[v/x]} E2[v/x]} {with {x E1} E2}[v/x] = {with {x E1[v/x]} E2} |# (: subst : ALGAE Symbol ALGAE -> ALGAE) ;; 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) ;; convenient helper -- no need to specify `from' and `to' (: subst* : ALGAE -> ALGAE) (define (subst* x) (subst x from to)) ;; helper to substitute lists (: substs* : (Listof ALGAE) -> (Listof ALGAE)) (define (substs* exprs) (map subst* exprs)) (cases expr [(Num n) expr] [(Add args) (Add (substs* args))] [(Mul args) (Mul (substs* args))] [(Sub fst args) (Sub (subst* fst) (substs* args))] [(Div fst args) (Div (subst* fst) (substs* args))] [(Id name) (if (eq? name from) to expr)] [(With bound-id named-expr bound-body) (With bound-id (subst* named-expr) (if (eq? bound-id from) bound-body (subst* bound-body)))])) #| Formal specs for `eval': eval(N) = N eval({+ E ...}) = evalN(E) + ... eval({* E ...}) = evalN(E) * ... eval({- E}) = -evalN(E) eval({/ E}) = 1/evalN(E) eval({- E1 E ...}) = evalN(E1) - (evalN(E) + ...) eval({/ E1 E ...}) = evalN(E1) / (evalN(E) * ...) eval(id) = error! eval({with {x E1} E2}) = eval(E2[eval(E1)/x]) evalN(E) = eval(E) if it is a number, error otherwise |# (: eval-number : ALGAE -> Number) ;; helper for `eval': verifies that the result is a number (define (eval-number expr) (let ([result (eval expr)]) (if (number? result) result (error 'eval-number "need a number when evaluating ~s, but got ~s" expr result)))) (: value->algae : (U Number) -> ALGAE) ;; converts a value to an ALGAE value (so it can be used with `subst') (define (value->algae val) (cond [(number? val) (Num val)] ;; Note: a `cond' doesn't make much sense now, but it will when ;; we extend the language with booleans. Also, since we use ;; Typed Racket, the type checker makes sure that this function ;; is never called with something that is not in its type, so ;; there's no need for an `else' branch like ;; [else (error 'value->algae "unexpected value: ~s" val)] ;; (Strictly speaking, there's no need for the last predicate ;; (which is the only one here until you extend this), but it's ;; left in for clarity.) #|... more code should be here ...|#)) (: eval : ALGAE -> (U Number)) ;; evaluates ALGAE expressions by reducing them to numbers (define (eval expr) (cases expr [(Num n) n] [(Add args) (+ (eval-number (first args)) (eval-number (second args)))] [(Mul args) (* (eval-number (first args)) (eval-number (second args)))] [(Sub fst args) (- (eval-number fst) (eval-number (first args)))] [(Div fst args) (/ (eval-number fst) (eval-number (first args)))] [(With bound-id named-expr bound-body) (eval (subst bound-body bound-id ;; see the above `value->algae' helper (value->algae (eval named-expr))))] [(Id name) (error 'eval "free identifier: ~s" name)])) (: run : String -> (U Number)) ;; evaluate an ALGAE program contained in a string (define (run str) (eval (parse str))) ;; tests (for simple expressions) (test (run "5") => 5) (test (run "{+ 5 5}") => 10) (test (run "{with {x {+ 5 5}} {+ x x}}") => 20) (test (run "{with {x 5} {+ x x}}") => 10) (test (run "{with {x {+ 5 5}} {with {y {- x 3}} {+ y y}}}") => 14) (test (run "{with {x 5} {with {y {- x 3}} {+ y y}}}") => 4) (test (run "{with {x 5} {+ x {with {x 3} 10}}}") => 15) (test (run "{with {x 5} {+ x {with {x 3} x}}}") => 8) (test (run "{with {x 5} {+ x {with {y 3} x}}}") => 10) (test (run "{with {x 5} {with {y x} y}}") => 5) (test (run "{with {x 5} {with {x x} x}}") => 5)