Write the result of evaluating the following scheme expressions. Assume the statements are executed in the order presented. If the result is an error, explain why it is an error.
| Expression | Result |
|---|---|
(+ 1 (* 3 2 (- 2 3) ) (cond ((= 1 2) 3) (else 2))) |
-3 |
(define x 3) |
The results depend on the implementation of scheme you are using, but most print x |
(define (y 2)) |
This is an error because the function y has no body. If the expression was (define (y 2) 2) it would also be an error because all function parameters must be variable names, not values. |
(define (z) (w 2)) |
The results depend on the implementation of scheme you are using, but most print z. Notice that the function body is not evaluated by the interperter. We are allowed to refer to the function w in the body of z, even if w is not yet defined. When we call z w must be defined. |
(define (w z) (+ z z 1)) |
The results depend on the implementation of scheme you are using, but most print z. Notice how the local definition of the variable z overrides the definition of the function z in the global environment. |
(z) |
5 |
((z)) |
This is an error. The result of evaluating (z) is 5. The number five is not a function, but we are telling the interpereter to evaluate it as a function, this is clearly an error. |
(and (= 3 2) (/ 1 0)) |
The result is #f. and is a special form, it stops executing its arguments and returns #f after discovering one of its arguements is false. |
(cond ((= (w x) 7) #t) ((= x 3) #f) (else #f)) |
The result is #t. Notice that cond is a special form and that it evaluates its tests in order and stops evaluating them after the first one that is true. |
Translate the following scheme expressions into infix expressions.
| Scheme Code | Infix Expression |
|---|---|
(cond ((= (w x) 7) #t) ((= x 3) #f) (else #f)) |
If w(x) = 7, then #t else if x = 3, then #f else #f |
(- (+ (* 3 2) 7 2) (/ 8 2) (+ 2 3)) |
3 * 2 + 7 + 2 - 8 / 2 - (2 + 3) |
Translate the following infix expressions into scheme expressions.
| Infix Expression | Scheme Expression |
|---|---|
12 * 4 / 2 - (5 - 6 * -2 ) + 1 |
(- (/ (* 12 4) 2) (+ (- 5 (* 6 -2)) 1)) |
x + 1 + 3 * y = 5 |
(= (+ x 1 (* 3 y)) 5) |
Evaluate the following expression step by step using applicative order evaluation.
(w (w 1))
(w (w 1)) (w 3) 7
Now evaluate the expression using normal order evaluation.
(w (w 1)) (w (+ 1 1 1)) (+ (+ 1 1 1) (+ 1 1 1) 1) (+ 3 (+ 1 1 1) 1) (+ 3 3 1) 7
Is the result the same for both normal and applicative order evaluation, why or why not?
The result is the same for both normal and applicative order evaluation, but the process of evaluation is different. Exercise 1.5 in the book is a case where the result is different. o
Jane loves doing the crossword puzzle every morning. To help her do the crossword her daughter has compiled a list of commonly used words. This list is stored as a scheme list in the variable dictionary. The list is not ordered in any way. If the list had only the words cat, rat, and mouse in it, typing dictionary at the scheme prompt would produce (mouse cat rat). Jane's daughter has enlisted your help in writing a procedure to help her mother do the crossword puzzle. The procedure is called find-words and it takes three arguments: the length of the desired words, a position, and a list of consecutive letters known at the position. Word positions are numbered starting from one. find-words returns a list of all the words in the list of words that match, and returns the empty list if no words match. Fill in the definition of find-words. Feel free to write helper procedures. Example usage is presented below.
> dictionary (mouse cat rat)
> (find-words 3 2 (sentence 'a)) (cat rat) ;; (rat cat) is also acceptable output.
> (find-words 5 5 (sentence't)) ()
The source file for the solution is here
;; the list of words
(define dictionary (sentence 'mouse 'cat 'rat))
;; the procedure to help Jane solve her crossword puzzle
(define (find-words word-length start-position letters)
;; the helper function length-filter takes a sentence (list)
;; of words an returns a list of words of length word-length
(define (length-filter words)
(cond ((null? words) nil)
((= (count (first words)) word-length)
(sentence (first words)
(length-filter (bf words))))
(else (length-filter (bf words)))))
;; the helper function letter-filter takes a position, a letter and a
;; sentence (list) of words and returns a list of words who have the
;; letter at the position. This function assumes that all the words
;; are long enough
(define (letter-filter position letter words)
;; the helper function letter-at takes a word and a position
;; and returns a one character word that is the letter at the
;; desired postion. This function assumes that all the words
;; are enough
(define (letter-at wrd position)
(if (= position 1)
(first wrd)
(letter-at (bf wrd) (- position 1))))
(cond ((null? words) nil)
((equal? (letter-at (first words) position) letter)
(sentence (first words)
(letter-filter position letter (bf words))))
(else (letter-filter position letter (bf words)))))
;; the helper function letter-reducer takes a list of letters,
;; a position, and a senctence (list) of words and returns a
;; list of words that have the letter sequence starting at position
;; with the letters in the list of letters
(define (letter-reducer letters position words)
(cond ((null? words) words)
((null? letters) words)
(else (letter-reducer (bf letters)
(+ position 1)
(letter-filter position
(first letters)
words)))))
(letter-reducer letters
start-position
(length-filter dictionary)))
Copyright 1999 Paul Twohey. All rights reserved.