Com S 342 --- Principles of Programming Languages
HOMEWORK 3: STATIC PROPERTIES OF VARIABLES
(File $Date: 2001/10/25 16:36:41 $)
Due: problems 1-2,4-9 at beginning of class, October 23, 2001;
problems 10-11,14 at beginning of class, October 25, 2001;
problems 17-19 at beginning of class, October 30, 2001.
In this homework, you will review a bit about type checking and
currying, learn more about recursion over grammars,
and learn important programming language concepts relating to static
properties of variables. In terms of learning about recursion, we aim
to ensure that you don't think that all recursions are recursions over
flat lists. To that end you will work with variants of the lambda
calculus, and you should be sure to use the type checker.
Also, don't use the parse-... procedures in your own code,
but use the other helpers.
Please remember the tips given in class for working these kinds of
problems. In the past, students have made life harder for themselves
by making the problems harder than they are. The way they made things
harder was by not following the relevant grammar for the problem,
which led to confusion because they mixed recursion over a grammar
with recursion over a list, and several extra cases that didn't need to be
handled. Please don't make that mistake. That is, don't code for
examples which are not in the relevant language's grammar.
We provide a parser for the relevant grammar, which we apply to the test
cases to do the relevant error checking. Hence, you don't have to
worry about the error checking. As we discussed in class,
think about the following questions/tips for full recursion
(which should be your default in this homework):
(1) Are there examples needed? Write out related simpler examples.
(2) What is the type?
(3) What is the input grammar? Use an outline that matches it.
(4) Use only one kind of recursion per procedure.
(5) Recurse for each helping procedure.
Don't hesitate to use helping procedures, especially for lists.
For coding problems, code is to be written in Scheme, using the exact
procedure names specified in the problem descriptions. For coding
problems starting with problem 2, we suggest that, for practice for
tests, that you first write out by hand a solution to the problem, and
only then type in your solution to the computer. However, you should
hand in just a printout of the code, and an unedited transcript of
testing.
See the directory $PUB/homework/hw3 for test data for each coding
problem. (You can use the procedure test-hw3 to run our tests, as
described in homework 1.)
The section headings below give the readings related to the problems.
(Please read them!)
CLASSROOM DISCUSSIONS
ESSENTIALS OF PROGRAMMING LANGUAGES, Section 2.1
STRUCTURE AND INTERPRETATION OF PROGRAMMING LANGUAGES, Section 2.1
1. (5 points) [static vs. dynamic type checking]
In the previous homework, many students had the experience that
they could get programs involving the types sym-exp and s-lists to
work but had some difficulty with the type checker. What does this
tell you about the relative advantages and disadvantages of static
vs. dynamic type checking? Briefly explain.
2. (10 points) [type checking and abstraction]
Consider the difference between the program code in
$PUB/lib/subst.scm and the textbook's code on pages 19-20, which is
found in $PUB/lib/1.scm.
(a) Briefly summarize the difference between the outputs from the
following, which executes the book's subst procedure on some
tests using sym-exp-cooked.scm in the untyped interpreter for
Scheme, scheme342 (or scm342) ...
> (load-from-lib "1.scm") ; the book's code
> (load-from-lib "sym-exp-cooked.scm")
> (subst 'a 'b (parse-s-list '((b c) (b () d))))
> (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d))))
> (s-list?
(subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d)))))
... and the following which executes the same tests but using
the code in $PUB/lib/subst.scm and sym-exp-cooked.scm.
> (load-from-lib "subst.scm")
> (load-from-lib "sym-exp-cooked.scm")
> (subst 'a 'b (parse-s-list '((b c) (b () d))))
> (subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d))))
> (s-list?
(subst 'hmm 'symbol (parse-s-list '((symbol c) (symbol () d)))))
Be sure to summarize the differences, not just to describe both outputs.
Hint: you may want to look at the code of the two procedures
subst-in-symbol-expression and subst-sym-exp in these two files.
(b) What does the experiment above tell you about the utility and
the need to treat data abstractly through interfaces?
A TYPE NOTATION FOR SCHEME
(http://www.cs.iastate.edu/~cs342/docs/typedscm_toc.html)
3. (5 points; extra credit)
The current version of the type checker (which you can run by
using scheme342typed), gives the following error for file 1.scm
(among others):
1.scm: lines 45 to 49: Expected type of variable and definition differ
Variable: subst-in-symbol-expression
Type from deftype or uses : (forall (t)
(-> ((list-of t) (list-of t) t) t))
Type of defining expression: (forall (t)
(-> ((list-of t) (list-of t) (list-of t))
(list-of t)))
This type error report is a confusion on the part of the
type checker, since the code actually doesn't encounter an error at
run-time. It is caused by the outermost if-expression in
subst-in-symbol-expression in $PUB/lib/1.scm. Can you explain why
the type checker gives this type error but isn't confused by the
code in $PUB/lib/subst.scm?
STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTION 1.3
(http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3)
4. (5 points) [average3-c]
Define a curried version of the following procedure,
call it average3-c, and write the deftype for it as well.
(deftype average3 (-> (number number number) number))
(define average3
(lambda (a b c)
(/ (+ a b c) 3)))
Use the type checked interpreter, in scheme342typed, to do your
testing for this problem. After loading (and thus type checking
your code), test your code by executing the following.
(test-hw3 "average3-c")
Remember, for this and all of the following coding problems, you
must hand in both a printout of your code file and a transcript showing
testing using our test data. Be sure to include statements at the
top of your code file identifying yourself, as described in
previous homeworks.
5. (5 points) [average-9-42]
Using your solution from problem 4, define a procedure,
(deftype average-9-42 (-> (number) number))
that takes a number, c, and returns the average
of 9, 42, and c. For example,
(average-9-42 0) ==> 17
(average-9-42 3) ==> 18
Use the type checked interpreter, in scheme342typed, to do your
testing for this problem. After loading (and thus type checking
your code), test your code by executing the following.
Test your code by executing the following.
(test-hw3 "average-9-42")
Important: your solution must use average3-c from the previous
problem. You will get zero points if your solution's code does not
depend on average3-c.
STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTIONS 1.1.6
(http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.6)
REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME
CODE EXAMPLES PAGE
(http://www.cs.iastate.edu/~cs342/docs/code-examples.html#SyntacticAbstraction)
6. (10 points) [occurs-twice using "and" and "or"]
Write the procedure occurs-twice? from homework 1, problem 5 without
using #t and #f, but using "and" and "or".
Hand in a printout of your code and a transcript of testing that
includes our test cases, which you can execute using:
(test-hw3 "occurs-twice")
Use of the type checker is optional for this problem, although it
should work fine and may be helpful to you.
7. (10 points) [vector-index with letrec]
Write the procedure, vector-index, from homework 2 problem 17
using "letrec" and tail recursion.
Do not use Scheme's procedures vector->list or list->vector.
You can run our the tests using
(test-hw2 "vector-index")
Use of the type checker is optional for this problem, although it
should work fine and may be helpful to you.
8. (5 points) [example of syntactic sugar]
Give an example of a statement or expression in C++ that is a
syntactic sugar. Explain by a simple example how to desugar this
statement or expression.
ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.3.1
In addition to the section of the book named above,
please also read the file $PUB/lib/lambda-1+quote-exp-examples.scm
closely, which illustrates by example the grammar and helping procedures
for this set of problems. See also $PUB/lib/lambda-1+quote-exp-examples.tst
for test cases for those examples. Pay particular attention to the
subst-var-exps example, as that illustrates the most general case.
The language lambda-1+quote-exp, used in the first three problems
below, is defined by the following grammar. (In this language,
quotation for symbols means the same thing as in Scheme.)
The grammar comments enclosed in quotes to the right of the grammar
tell you information about the name of the production and the names of
its "fields". For example, the first production is named "var-exp"
and has one field named "id". These names determine the names of the
helping procedures. For example, as indicated next to the first
production, there is a predicate named var-exp?, a constructor
var-exp, and an observer var-exp->id.
::=
"var-exp (id)"
| (quote ) "quote-exp (symbol)"
| ( lambda ( ) ) "lambda-exp (id body)"
| ( ) "app-exp (rator rand)"
We have provided you with helping procedures in the following file.
$PUB/lib/lambda-1+quote-exp.scm
These are designed to work with our type checker,
so you should use the type-checked interpreter for these problems.
9. (10 points total) [lambda-helpers]
Load the file lambda-1+quote-exp.scm from the library by typing:
(load-from-lib "lambda-1+quote-exp.scm")
a. (5 points) Without using parse-lambda-1+quote-exp, make a transcript that
shows how you use the other helping procedures defined in
lambda-1+quote-exp.scm, to build the following expressions:
(If you use "define" to bind them to names, that will help in part b.)
x
(x (quote y))
(f x)
(lambda (x) (f x))
((lambda (x) (f x)) (quote x))
All of these should have the type lambda-1+quote-exp.
b. (5 points) Using the helping procedures in lambda-1+quote-exp.scm, and
names you defined in part (a), make a transcript that shows an
expression that returns the var-exp x from each of the 5
expressions in part a.
10. For this problem, a ``lambda calculus expression'',
means an in the language lambda-1+quote-exp.
a. (15 points) [free-vars]
Write a procedure, free-vars, with type given by
(deftype free-vars (-> (lambda-1+quote-exp) (set-of symbol)))
that takes a lambda calculus expression, expr, and returns the set of the
symbols that occur free in expr. (See the book for the definition of
``occurs free.'')
To work with sets, you should use your set-ops.scm file from
homework 2. (If you didn't get problem 7 of homework 2 working,
email us for a working solution.)
Your code should satisfy the following equations between sets,
(where set is as in homework 2, that is, (set 'x 'y) means
the set containing the symbols x and y).
(free-vars (parse-lambda-1+quote-exp 'x)) = (set 'x)
(free-vars (parse-lambda-1+quote-exp 'z)) = (set 'z)
(free-vars (parse-lambda-1+quote-exp '(quote z))) = the-empty-set
(free-vars (parse-lambda-1+quote-exp '(x (x y)))) = (set 'x 'y)
(free-vars (parse-lambda-1+quote-exp '(x (f (quote y))))) = (set 'x 'f)
(free-vars (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = (set 'y)
(free-vars (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y))))))
= (set 'x 'y)
(free-vars (parse-lambda-1+quote-exp '((lambda (y) y) (lambda (x) (y x)))))
= (set 'y)
To receive full credit your procedure must follow the lambda-1+quote-exp
grammar and it must type check.
In particular it should only be called recursively with arguments
that are in the above grammar (n.b., empty lists are not in the grammar).
If your code passes the type checker, this will be assured.
You should use the helping procedures in the file
$PUB/lib/lambda-1+quote-exp.scm to make sure the type checker can
do its job. To do this, put
(load-quietly-from-lib "lambda-1+quote-exp.scm")
at the top of your file.
Warning: do not try to flatten the lambda calculus expressions into a list,
since that will make your solution wrong! (See the last example above.)
For this and all succeeding problems, we suggest that you write out a
solution by hand first, and then type in your code to the computer.
Please try testing your code by hand first,
so you are in control of the testing process. After you debug this way,
then try using our test cases by typing.
(test-hw3 "free-vars")
Remember, for this and all of the following coding problems, you
must hand in: a printout of your code and a transcript showing
testing using our test data.
Note: when Scheme prints (quote x), it prints it as 'x; you can also type
(quote y) in as 'y in test cases if you wish. But watch out:
as ''y ==> (quote y) which prints as 'y, but 'y ==> y.
b. (5 points) [free?]
Write a procedure, free?, with type,
(deftype free? (-> (symbol lambda-1+quote-exp) boolean))
that takes a symbol, s, and a lambda calculus expression, expr,
and returns #t just when s occurs free in expr.
Your code should satisfy the following equations.
(free? 'x (var-exp 'x)) = #t
(free? 'x (quote-exp 'x)) = #f
(free? 'z (parse-lambda-1+quote-exp 'y)) = #f
(free? 'x (parse-lambda-1+quote-exp '(x (x y)))) = #t
(free? 'y (parse-lambda-1+quote-exp '(x (x y)))) = #t
(free? 'y (parse-lambda-1+quote-exp '(x (x (quote y))))) = #f
(free? 'a (parse-lambda-1+quote-exp '(x (x y)))) = #f
(free? 'x (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #f
(free? 'y (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #t
(free? 'x (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = #t
After doing your own testing, you can use our tests by typing:
(test-hw3 "free")
11. For this problem, a lambda calculus expression
means an in the language lambda-1+quote-exp.
a. (15 points) [bound-vars]
Write a procedure, bound-vars, with type
(deftype bound-vars (-> (lambda-1+quote-exp) (set-of symbol)))
that takes a lambda calculus expression, expr, and returns the set of the
symbols that occur bound in expr. (See the book for the definition of
``occurs bound.'')
Again, use your set-ops.scm file, as in the previous problem to work
with sets. And use the file $PUB/lib/lambda-1+quote-exp.scm for helping
functions that work with the type checker. (Hint: use free-vars too!)
See problem 1 for more information.
(bound-vars (parse-lambda-1+quote-exp 'x)) = the-empty-set
(bound-vars (parse-lambda-1+quote-exp '(quote z))) = the-empty-set
(bound-vars (parse-lambda-1+quote-exp '(x (x y)))) = the-empty-set
(bound-vars (parse-lambda-1+quote-exp '(lambda (x) (x (x y)))))
= (set 'x)
(bound-vars (parse-lambda-1+quote-exp '(lambda (y) x)))
= the-empty-set
(bound-vars (parse-lambda-1+quote-exp '(lambda (y) (quote y))))
= the-empty-set
(bound-vars (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y))))))
= (set 'x)
To receive full credit your procedure must follow the grammar
for lambda-1+quote-exp and it must type check.
It will have little chance of being correct if you don't!
After doing your own testing, you can use our tests by typing:
(test-hw3 "bound-vars")
b. (5 points) [bound?]
Write a procedure, bound?, with type
(deftype bound? (-> (symbol lambda-1+quote-exp) boolean))
that takes a symbol, s, and a lambda calculus expression, expr,
and returns #t just when s occurs bound in expr.
Your code should satisfy the following equations.
(bound? 'x (parse-lambda-1+quote-exp 'x)) = #f
(bound? 'z (parse-lambda-1+quote-exp 'y)) = #f
(bound? 'x (parse-lambda-1+quote-exp '(x (x y)))) = #f
(bound? 'y (parse-lambda-1+quote-exp '(x (x y)))) = #f
(bound? 'a (parse-lambda-1+quote-exp '(x (x y)))) = #f
(bound? 'x (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #t
(bound? 'y (parse-lambda-1+quote-exp '(lambda (x) (x (x y))))) = #f
(bound? 'x (parse-lambda-1+quote-exp '(x (lambda (x) (x (x y)))))) = #t
For testing this problem, you can use
(test-hw3 "bound")
12. (10 points, extra credit)
Do exercise 1.20 on p. 31 in the text.
13. (suggested practice)
Do exercise 1.21 on p. 31 in the text.
14. (40 points) [free-vars and bound-vars for lambda+if-exp]
The language lambda+if-exp, used in this problem, is defined by the
following grammar. The grammar comments enclosed in quotes to the
right of the grammar tell you information about the name of the
production and the names of its "fields".
::=
"var-exp (id)"
| (quote ) "quote-exp (symbol)"
| ( lambda ( {}* ) ) "lambda-exp (ids body)"
| ( if "if-exp (test-exp
true-exp
) false-exp)"
| ( {}* ) "app-exp (rator rands)"
For this problem, you should write two procedures that compute the sets
of free and bound variables for the above grammar:
a. (deftype free-vars (-> (lambda+if-exp) (set-of symbol)))
b. (deftype bound-vars (-> (lambda+if-exp) (set-of symbol)))
Use the file $PUB/lib/lambda+if-exp.scm for helping procedures
for this grammar that work with the type checker.
See the file $PUB/lib/lambda+if-exp-examples.scm
for examples using these, and $PUB/lib/lambda+if-exp-examples.tst
for test cases for the examples.
Again, use your set-ops.scm file, to work with sets.
To receive full credit, your code for free-vars and bound-vars must
type check and follow the grammar. Beware that our test cases may
not ensure that your code is perfect: you must be sure to recurse
in every place the grammar recurses yourself.
For testing this problem, you can use
(test-hw3 "free-vars-lambda+if-exp")
(test-hw3 "bound-vars-lambda+if-exp")
15. (100 points, extra credit) [inheritance]
Isn't it a pain to have to duplicate code when changing your free-vars
to work on a different grammar? As an object-oriented programmer
this will look to you like a job for inheritance, especially if you
remember that a procedure in Scheme is like an object in an OO
language. To make things clearer, rename the procedures in the
above problem to be free-vars-lambda+if-exp and bound-vars-lambda+if-exp.
Now, you might try, for example, having free-vars-lambda+if-exp call
free-vars on the lambda-1+quote grammar to do part of its work; but
you'll find that the recursions in free-vars point to free-vars
instead of free-vars-lambda+if-exp.
However, the problem with the recursion can be solved by thinking of it
as a changing part. If you do that, then the next step is obvious:
abstract it! So you'd write free-vars as follows.
(deftype free-vars-gen
(forall (T)
(-> ((-> (T) (set-of symbol))) (-> (T) (set-of symbol)))))
(define free-vars-gen
(lambda (recur)
(lambda (exp)
... code for free-vars, except that recur replaces free-vars ...)))
Use this idea to write free-vars and free-vars-lambda+if-exp so that
you can reuse the code you've written (in this new style)
without editing it to make extended versions.
(Note: this is essentially the semantics of inheritance in OO programs!
It looks harder than it is. Just try it...)
ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.3.2
16. (suggested practice) [scoping]
Do exercises 1.27 and 1.28 on pp. 34-35 in the text.
17. (5 points) [lexical address idea]
Do exercise 1.29 on p. 36 in the text. (This can be handwritten.)
18. (5 points) [lexical address idea]
Do exercise 1.30 on p. 36 in the text. (This can be handwritten.)
19. (45 points) [lexical-address]
(This is similar to, but different than, exercise 1.31 on p. 37 in
the text. We treat free variables differentyl and in addition treat quoted
data.) Write the procedure, lexical-address, whose type is given by
(deftype lexical-address (-> (lambda+if-exp) lexical-addr-exp))
where lambda+if-exp is the type of s specified by the grammar
in $PUB/lib/lambda+if-exp.scm, and lexical-addr-exp is the type of data
defined by the following grammar:
::=
"la:var-exp (lexical-addr)"
| (quote ) "la:quote-exp (symbol)"
| ( lambda ( {}* ) "la:lambda-exp (ids
) body)"
| ( if "la:if-exp (test-exp
true-exp
) false-exp)"
| ( "la:app-exp (rator
{}* ) rands)"
::= ( : )
Helpers for this grammar are found in the file
$PUB/lib/lexical-addr-exp.scm which loads helpers for the
grammar in $PUB/lib/lexical-addr.scm. Note that the
helpers for lexical-addr-exp all have "la:" prefixed to their
names, so that you can distinguish them from the helpers for lambda+if-exp.
For example:
(lexical-address (parse-lambda+if-exp 'car)) ==> (car : 0 0)
(lexical-address (parse-lambda+if-exp 't)) ==> (t : 0 0)
(lexical-address (parse-lambda+if-exp '(car ls)))
==> ((car : 0 0) (ls : 0 1)) ;; see note (*) below
(lexical-address (parse-lambda+if-exp '(if t (car ls) ls)))
==> (if (t : 0 0) ((car : 0 1) (ls : 0 2)) (ls : 0 2))
(lexical-address (parse-lambda+if-exp '(lambda (car ls) (car ls))))
==> (lambda (car ls) ((car : 0 0) (ls : 0 1)))
(lexical-address (parse-lambda+if-exp '(lambda (ls car) (car ls))))
==> (lambda (ls car) ((car : 0 1) (ls : 0 0)))
(lexical-address (parse-lambda+if-exp '(lambda (ls car) (ls))))
==> (lambda (ls car) ((ls : 0 0)))
(lexical-address (parse-lambda+if-exp
'(lambda (x) (if p (f x g) (f y h)))))
==> (lambda (x) (if (p : 1 0) ;; see note (*) below
((f : 1 2) (x : 0 0) (g : 1 1))
((f : 1 2) (y : 1 3) (h : 1 4))))
(lexical-address (parse-lambda+if-exp '(x
(lambda (z f)
(x z f
(lambda (q r)
(x z f q r))))
(lambda (f z)
(x z f
(lambda (r q)
(x z f q r)))))))
==> ((x : 0 0)
(lambda (z f)
((x: 1 0) (z : 0 0) (f : 0 1)
(lambda (q r)
((x : 2 0) (z : 1 0) (f : 1 1)
(q : 0 0) (r : 0 1)))))
(lambda (f z)
((x: 1 0) (z : 0 1) (f : 0 0)
(lambda (r q)
((x : 2 0) (z : 1 1) (f : 1 0)
(q : 0 1) (r : 0 0))))))
(*) Note that, for an expression with free variables, the position number
of the lexical address of free variables is left up to your implementation.
That is any assignment of position numbers to free variables is okay,
as long as they are all different. For example,
both of the following are correct:
(lexical-address (parse-lambda+if-exp '(car ls))
==> ((car : 0 0) (ls : 0 1))
(lexical-address (parse-lambda+if-exp '(car ls))
==> ((car : 0 1) (ls : 0 0))
It is important to plan your solution carefully, as this problem
always gives some students trouble. Think about the tips for
writing recursions over grammars carefully. Which one is the input
grammar? As an additional aid, start by copying the file
$PUB/homework/hw3/lexical-address.scm to your directory, which
is a file of hints, and contains an basic outline of the code you
can use.
Full credit will only be given for solutions that type check
and follow the grammar.
For testing this problem, you can use
(test-hw3 "lexical-address")
When you print your code, you can remove all (or most) of the hints
in the comments we gave you in lexical-address.scm. This will help
save some paper. Be sure to put your name in the file.
20. (60 points, extra credit) [un-lexical-address]
Do exercise 1.32 on p. 37 in the text.