STUDENT NAME: 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall 2004Recitation 10Symbols and QuoteScheme1. Special Forms(a) quote - (quote expr)Returns whatever the reader built for expr.2. Procedures(a) (eq? v1 v2) - returns true if v1 and v 2 are bitwise identical. “Works on” symbols,booleans, and pairs. Doesn’t “work on” numbers and strings.(b) (eqv? v1 v2) - like eq? except it “works on” numbers .(c) (equal? v1 v2) - return true if v1 and v2 print out the same. “Works on” almosteverything.Problems1. Evaluation - give printed value. x is 5.’3’x’’x(quote (3 4))(’+ 3 4)(if ’(= x 0) 7 8)(eq? ’x ’X)STUDENT NAME: 2(eq? (list 1 2) (list 1 2))(equal? (list 1 2) (list 1 2))SetsA set is a collection of unique elements. Attempting to add a second copy of an element to a setwill not change the set. We’ll be working with s ets of symbols.(define (empty- set)(cons ’set nil))(define (set-el ements set)(cdr set))2. Write set-c ontains? which returns #t if the set contains the element.(define (set-co ntains? elem set)3. Write set-a dd which adds an element to a set if the set does not already contain it.(define (set-ad d elem set)Another u seful set p rocedure:(define (set-un ion set1 set2)(fold-right set-ad d set1 (set-elements set2)))Boolean FormulasA boolean formula is a formula containing boolean operations and boolean variables. A booleanvariable is either true or false. and, or, and not are all boolean operations. For the p urposes ofthis problem, and and or will be defin ed to take exactly two inputs.Example formulas:STUDENT NAME: 3a(not b)(or b (not c))(and (not a) (not c))(not (or (not a) c))(and (or a (not b)) (or (not a) c))Some useful procedures:(define (variab le? exp)(symbol? exp))(define (make-v ariable var)var)(define (variab le-name exp)exp)(define (or? exp)(and (pair? exp) (eq? (car exp) ’or)) )(define (make-o r exp1 exp2)(list ’or exp1 exp2))(define (or-fir st exp)(cadr exp))(define (or-sec ond exp)(caddr exp))(define (and? exp)(and (pair? exp) (eq? (car exp) ’and) ))(define (make-a nd exp1 exp2)(list ’and exp1 exp2))(define (and-fi rst exp)(cadr exp))(define (and-se cond exp)(caddr exp))4. Write selectors, constructor, and predicate for not5. Given a formula, we’d like to be able to tell which variables it involves. formula-variablesshould return the set of variables used in the formula.STUDENT NAME: 4(define (formul a-variables exp)(cond ((variabl e? exp)(set-add (variable -name exp) (empty- set)))((not? exp)(formula-variabl es (not-operand exp)))6. Given a formula and a list of variable assignments, decide whether the formula is #t or #f.Assume that you have a procedure (vari able-value bi ndings vname), which takes a listof assignments and a variable name and returns the value assigned to the variable.(define (formul a-value exp bindin
View Full Document
Unlocking...