;; Skeleton code for HW5.
;; Fill in functions as described in assignment description
;; Utility functions
;; Provided
;; You don't need to understand the following function to use it, but
;; if you're curious, the key issue is that Scheme does something
;; funny to commas in quoted lists. E.g.:
;;
;; '(1,2,3) is represented as '(1 (unquote 2) (unquote 3))
;;
;; and
;;
;; (unquote->comma '(1,2,3)) ==> (1 |,| 2 |,| 3)
;;
;; Why the funny business with commas? Look up "quasiquote" in Help.
;; (In fact, you might find it convenient to use quasiquote in your
;; solution, but it is by no means required.)
;;
(define (unquote->comma expr)
(cond [(null? expr) ()]
[(and (pair? (car expr))
(eqv? (caar expr) 'unquote))
(cons '|,|
(cons (cadar expr)
(unquote->comma (cdr expr))))]
[#t (cons (car expr) (unquote->comma (cdr expr)))]))
;; Not provided
(define (union ls1 ls2) '____)
;; Important constants
(define infix-operators '(= < <= > >= + - * /))
(define keyword-symbols '(! if else while return func := unquote))
(define snarfed-functions '(display newline car cdr cons set-car! set-cdr! null? not))
(define reserved-symbols (append infix-operators keyword-symbols snarfed-functions))
;; Provided predicates
;; note that (atom? ()) is true, which is not the scheme definition on "atom". This
;; is meant to test whether an expression is a *DysFun* atom, and for that purpose
;; the empty list appearing in an expression should be treated as such. E.g., as
;; DysFun expressions, "cons(5,10)" and "cons(5,())" are handled pretty much the same way.
(define (atom? x)
(not (pair? x)))
(define (singleton? x)
(and (pair? x)
(null? (cdr x))))
(define (application? x)
(and (list? x)
(= (length x) 2)
(list? (cadr x))))
(define (assign? expr)
(and (list? expr)
(> (length expr) 2)
(symbol? (car expr))
(eqv? (cadr expr) ':=)))
(define (while? expr)
(and (list? expr)
(> (length expr) 2)
(eqv? (car expr) 'while)))
(define (if-else? expr)
(and (list? expr)
(= (length expr) 5)
(eqv? (car expr) 'if)
(eqv? (cadddr expr) 'else)))
(define (if? expr)
(and (list? expr)
(= (length expr) 3)
(eqv? (car expr) 'if)))
;; Warmup function
(define (unbound-vars bound expr) '____)
;; Main functions
(define (dysfun-expr->scheme-expr expr) '____)
(define (dysfun-assign->scheme-set expr) '____)
(define (dysfun-if-else->scheme-if expr) '____)
(define (dysfun-if->scheme-if expr) '____)
(define (dysfun-while->scheme-expr expr) '____)
(define (dysfun-stmt->scheme-expr expr) '____)
(define (dysfun-stmts->scheme-exprs expr) '____)
(define (dysfun-func->scheme-lambda expr) 0)
;; Fibonacci in DysFun
;; Since ; introduces comments in Scheme, statements are
;; terminated with !
(define fib-dysfun '(
func fib (n) {
x := 0 !
y := 1 !
while (n > 1) {
new := x + y !
x := y !
y := new !
n := n - 1 !
} !
return y !
}
))
(define fib-scheme (dysfun-func->scheme-lambda fib-dysfun))
(define fib (eval fib-scheme))