I have to create a scheme parser and unparser. My teacher is checking this assigment by seeing if (unparse-exp (parse-exp 'expression)) returns expression and parse-exp returns an error when called with bad input. There is no defined format for what is returned from parse-exp just as long uparse can works with it. I can not think of any test cases the fail but the grading program which doesn't show the specific test cases only gives my about half the points. Any ideas? See the some of the assignment details and my code below.
o Allow multiple bodies for lambda, let (including named let), let*, and letrec
expressions. Also allow (lambda x lambda-body …) (note that the x is not in
parentheses) or an improper list of arguments in a lambda expression, such as
(lambda (x y . z) …).
o Add if expressions, with or without the third "else" expression; also add set! expressions.
o Expand the kinds of literals recognized by parse-exp to include strings, quoted lists (proper
and improper), vectors, and the Boolean constants #t and #f. You may want to define a litexp
variant of the expression datatype, and have parse-exp turn each of these cases into a
lit-exp.
o Make parse-exp bulletproof. Add error checking to your parse-exp procedure. It should
"do the right thing" when given any Scheme data as its argument. Error messages should be as
CSSE 304 Assignment 8 Page 3 04/19/10
specific as possible (that will help you tremendously when you write your interpreter in a later
assignment). Call the eopl:error procedure (same syntax as Chez Scheme's error, whose
documentation can be found at http://www.scheme.com/csug/system.html#g2206) ; the first
argument to eopl:error must be 'parse-exp. This will enable the grading program to
process your error message properly, recognizing that the error is generated by your program
rather than by a built-in procedure.
o Modify unparse-exp so it accepts as input any expression object produced by parseexp,
and returns the original concrete syntax expression that produced that parsed expression.
Suggestion: when you modify or add a case to parse-exp, go ahead and make the
corresponding change to unparse-exp and test both.
;the datatype used in parse and unparse
(define-datatype expression expression?
[var-exp
(id symbol?)]
[lambda-exp
(vars (list-of symbol?))
(bodies (list-of expression?))]
[lambda-var-improp-exp
(vars (list-of improperlist?))
(bodies (list-of expression?))]
[lambda-var-sym-exp
(vars symbol?)
(bodies (list-of expression?))]
[set-exp
(id symbol?)
(var expression?)]
[app-exp
(rands (list-of expression?))]
[lit-exp
(id literal?)]
[if-exp
(test expression?)
(true expression?)
(false expression?)]
[if-noelse-exp
(test expression?)
(true expression?)]
[let-exp
(vars (list-of symbol?))
(vals (list-of expression?))
(bodies (list-of expression?))]
[let*-exp
(vars (list-of symbol?))
(vals (list-of expression?))
(bodies (list-of expression?))]
[letrec-exp
(vars (list-of symbol?))
(vals (list-of expression?))
(bodies (list-of expression?))]
[letname-exp
(name symbol?)
(vars (list-of symbol?))
(vals (list-of expression?))
(bodies (list-of expression?))])
;parse
(define parse-exp
(lambda (datum)
(cond
[(symbol? datum) (var-exp datum)]
[(literal? datum) (lit-exp datum)]
[(pair? datum)
(cond
[(eqv? (car datum) 'lambda)
(if (< (length (cdr datum)) 2)
(eopl:error 'parse-exp "Invalid lambda syntax ~s" datum)
(cond
[(list? (cadr datum))
(lambda-exp (cadr datum)
(map parse-exp (cddr datum)))]
[(symbol? (cadr datum))
(lambda-var-sym-exp (cadr datum)
(map parse-exp (cddr datum)))]
[(improperlist? (cadr datum))
(lambda-var-improp-exp (cadr datum)
(map parse-exp (cddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid lambda syntax ~s" datum)]))]
[(eqv? (car datum) 'set!)
(if (= (length (cdr datum)) 2)
(set-exp (cadr datum)
(parse-exp (caddr datum)))
(eopl:error 'parse-exp
"Invalid set! syntax ~s" datum))]
[(eqv? (car datum) 'set)
(eopl:error "Invalid set syntax ~s" datum)]
[(eqv? (car datum) 'if)
(cond
[(= (length (cdr datum)) 3)
(if-exp (parse-exp (cadr datum))
(parse-exp (caddr datum))
(parse-exp (cadddr datum)))]
[(= (length (cdr datum)) 2)
(if-noelse-exp (parse-exp (cadr datum))
(parse-exp (caddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid if syntax ~s" datum)])]
[(and (eqv? (car datum) 'let) (list? (cadr datum)))
(cond
[(< (length (cdr datum)) 2)
(eopl:error 'parse-exp "Invalid let syntax ~s" datum)]
[(and (list-of-lists? (cadr datum))
(andmap lengths-equal-two? (cadr datum)))
(let-exp (firsts (cadr datum))
(map parse-exp (lasts (cadr datum)))
(map parse-exp (cddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid let syntax ~s" datum)])]
[(and (eqv? (car datum) 'let) (symbol? (cadr datum)))
(cond
[(< (length (cdr datum)) 3)
(eopl:error 'parse-exp "Invalid named let syntax ~s" datum)]
[(and (list-of-lists? (caddr datum))
(andmap lengths-equal-two? (caddr datum)))
(letname-exp (cadr datum)
(firsts (caddr datum))
(map parse-exp (lasts (caddr datum)))
(map parse-exp (cdddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid named let syntax ~s" datum)])]
[(eqv? (car datum) 'let*)
(cond
[(< (length (cdr datum)) 2)
(eopl:error 'parse-exp "Invalid let* syntax ~s" datum)]
[(and (list-of-lists? (cadr datum))
(andmap lengths-equal-two? (cadr datum)))
(let*-exp (firsts (cadr datum))
(map parse-exp (lasts (cadr datum)))
(map parse-exp (cddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid let* syntax ~s" datum)])]
[(eqv? (car datum) 'letrec)
(cond
[(< (length (cdr datum)) 2)
(eopl:error "Invalid letrec syntax ~s" datum)]
[(and (list-of-lists? (cadr datum))
(andmap lengths-equal-two? (cadr datum)))
(letrec-exp (firsts (cadr datum))
(map parse-exp (lasts (cadr datum)))
(map parse-exp (cddr datum)))]
[else
(eopl:error 'parse-exp
"Invalid letrec syntax ~s" datum)])]
[(list? datum)
(app-exp (map parse-exp datum))]
[else
(eopl:error 'parse-exp "Invalid syntax ~s" datum)])]
[else (eopl:error 'parse-exp
"Invalid syntax ~s" datum)])))
;unparse
(define unparse-exp
(lambda (exp)
(cases expression exp
[var-exp (id) id]
[lit-exp (id) id]
[lambda-exp (vars bodies)
(append (list 'lambda vars)
(map unparse-exp bodies))]
[lambda-var-sym-exp (vars bodies)
(append (list 'lambda vars)
(map unparse-exp bodies))]
[lambda-var-improp-exp (vars bodies)
(append (list 'lambda vars)
(map unparse-exp bodies))]
[set-exp (id var)
(list id (unparse-exp var))]
[app-exp (rands)
(map unparse-exp rands)]
[if-exp (test true false)
(list 'if (unparse-exp test)
(unparse-exp true)
(unparse-exp false))]
[if-noelse-exp (test true)
(list 'if (unparse-exp test) (unparse-exp true))]
[let-exp (vars vals bodies)
(append (list 'let (combine vars vals))
(map unparse-exp bodies))]
[let*-exp (vars vals bodies)
(append (list 'let* (combine vars vals))
(map unparse-exp bodies))]
[letrec-exp (vars vals bodies)
(append (list 'letrec (combine vars vals))
(map unparse-exp bodies))]
[letname-exp (name vars vals bodies)
(append (list 'let name (combine vars vals))
(map unparse-exp bodies))])))
;The helpers used in parse and unparse
(define list-of
(lambda (pred)
(lambda (val)
(or (null? val)
(and (pair? val)
(pred (car val))
((list-of pred) (cdr val)))))))
;combines 2 lists of the same size
;as a list of list with corresponding elements
(define combine
(lambda (ls1 ls2)
(if (null? ls1)
'()
(append (list (list (car ls1) (car ls2)))
(combine (cdr ls1) (cdr ls2))))))
(define improperlist?
(lambda (x)
(and (pair? x) (not (list? x)))))
(define literal?
(lambda (x)
(or (number? x)
(string? x)
(boolean? x)
(vector? x))))
(define list-of-lists?
(lambda (x)
(and (list? x)
(andmap list? x))))
(define lengths-equal-two?
(lambda (x)
(= (length x) 2)))
(define firsts
(lambda (ls)
(if (null? ls)
'()
(cons (caar ls)
(firsts (cdr ls))))))
(define lasts
(lambda (ls)
(if (null? ls)
'()
(cons (cadar ls)
(lasts (cdr ls))))))