All of these problems should be done without using side effects (i.e. redefining variables or using set!) and without using any explicit Scheme looping constructs (do). Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.
1. Suppose we enter the following definitions at the top-level of a Scheme environment:
(define x 1) (define y 2) (define z 3)
What are the results when you evaluate the following expressions
(let ((x 0)
(z (+ x z)))
(+ x y z))(let ((x 1)
(y (- x 3))
(z (* y 2)))
(+ x y z))
(let* ((x 1)
(y (- x 3))
(z (* y 2)))
(+ x y z))
2. Consider the following definitions:
(define make-scaled
(lambda (scale f)
(lambda (x)
(* scale (f x)))))
(define add-one
(lambda (x)
(+ 1 x)))
(define mystery
(make-scaled 3 add-one))
What is the value of (mystery 4)? Explain how you arrived at your answer.
(For full credit, your answer should explain what happens when (mystery 4)
is evaluated, not just report an answer that you got when you used DrScheme to
evaluate these expressions.)
General hint: Take advantage of map and other higher-order
functions when appropraite.
apply-all that, when given a list of
functions and a number, will produce a list of the values of the functions
when applied to the number. For example,
(apply-all (list sqrt square cube) 4) => (2 16 64))
positive?, we
can
construct an "all are" version of it for testing whether all
elements of the list satisfy the predicate. Define a procedure all-are that does this; that
is, it should be
possible to use it in ways like the following:
((all-are positive?) '(1 2 3 4)) => #t
((all-are even?) '(2 4 5 6 8)) => #f
Scheme does not include classes or modules to directly support encapsulation or abstract data types, but there are common idioms for doing this, using functions to abstract away from the underlying representation of data (which is usually a list).
In this part of the assignment, you will create some functions to manipulate expression trees. Here are some basics about expression trees:
Consider an arithmetic expression, such as one we would write in Scheme as (+ 1 (* 2 (- 3
5))). We can think of this as being a tree-like
structure with numbers at the leaves and operators at the interior nodes.
+
/ \
1 *
/ \
2 -
/ \
3 5
This structure is known as an expression tree.
For this problem, you should assume that the tree is restricted as follows:
Each node in the tree can be represented by a three-element list:
(left-operand
operator right-operand)
Write and test Scheme functions to solve the following problems. You should save all of your function definitions for this part of the assignment in a single source file.
General observation (hint): Binary trees have an elegant, recursive structure. Take advantage of this to structure your code.
(make-expr left-op operator
right-op)
=> (left-op operator right-op)
(operator '(left-op operator right-op)) => operator
(left-op '(left-op operator right-op)) => left-op
(right-op '(left-op operator right-op)) => right-oplist,
cons, car, and cdr. The advantage
of having these functions is that you can write other code in terms of
expressions, operators, and operands, not car, cddadr,
and similar things.
The resulting code should be much easier to read.(preorder expr-tree)
(inorder expr-tree)
(postorder expr-tree)
Test your functions by creating a few trees using nested make-expr function calls and then using these as arguments to the traversal functions.(eval-expr expr-tree)For this (as well as most) assignments, you should turn in your work both electronically over the web and on paper.
Turn in a copy of both of your Scheme source files from parts II and III using this turnin form.
Hand in the following: