6.001 Tutorial 5 NotesGerald Dalley7–8 Mar 2005Reminders• Problem set due Tuesday• Project 2 due Friday• Grading– Quiz 1 = 12.5% of final grade– Project 1 ≈ 6% of final gradequoteThe quote special form just returns exactly the ar-gument it was given – whatever the reader built.Give a box-and-pointer diagram (as appropriate)for the results of evaluating each expression:(quote 1)1(quote (1 2 3))1 2 3You can also use the sugared form of quote,’:’1’1 ⇔ (quote 1) ⇔ 1’(1 2 3)’(1 2 3) ⇔ (quote (1 2 3)) ⇔1 2 3SymbolsSymbols are another data type in Scheme. Theyare similar to strings but they are interned. WhenScheme sees a symbol, it checks to see if it has everseen a symbol with the same character string before.If it has not, it creates a new symbol. If it has, itreturns a pointer to the symbol it created last timeit saw the character string.Because of this, any two symbols of the same namerefer to the same object. Unlike strings, we can com-pare two symbols for equality in constant time, bychecking if they point to the same object.We use symbols for many purposes:• Tagged data – see Tuesday’s lecture• Deferring evaluation – we’ll see this later in theterm.• Giving names to values – (define a b) asso-ciates the value of b with the symbol a.For each question, give the value and type of eachexpression. Assume they are evaluated in the givenorder.’33, number’xx, symbol’’x(quote x), s ymbol(quote (3 4))(3 4), list(’+ 3 4)error, the + symbol is not an operator.(if ’(= x 0) 7 8)7, number, the list (= x 0) is not #f, so truebranchEqualityWe’ve talked about =, used to compare numbers forequality. We now have eq? and equal?.1(eq? a b) is the simplest test. It checks whethera and b are the same object (for C program-mers, whether a and b are the same pointer). Itworks for booleans and symbols, but not for numbers!(eq? #t #t)#t(eq? ’foo ’foo)#t(eq? ’foo ’FOO)#t(eq? (list 1 2 3) (list 1 2 3))#f(equal? a b) checks whether a and b print out thesame and works for almost everything.(equal? #t #t)#t(equal (list 1 2 3) (list 1 2 3))#tWhat do these do?(eq? ’x ’X)#t, boolean, case insensitivity(eq? (list 1 2) (list 1 2))#f, boolean, list builds a new list each time(equal? (list 1 2) (list 1 2))#t, boolean the two lists print the sameIn general, you should use = for numbers, eq? forsymbols, and equals? for lists. Assuming we haveevaluated the following:(define lst ’(1 2 3))fill in the table below with #t, #f, e (for error), oru (for unspecified) if we assume that the actual textwritten in the a and b columns was copied and pastedinto the given expressions:(= (eq? (equal?a b a b) a b) a b)1 1 #t u #t3456789 3456789 #t u #t#f #f e #t #t"123" "123" e u #t’a ’a e #t #tlst lst e #t #tlst ’(1 2 3) e #f #t’(1 2 3) ’(1 2 3) e #f #tcar car e #t #tSee http://sicp.csail.mit.edu/Spring-2005/manuals/scheme-7.5.5/doc/scheme 4.html for acomplete description of the equality tests with manymore examples.Symbolic Boolean ExpressionManipulationA boolean formula is a formula containing booleanoperations and boolean variables. A boolean variableis either true or false. and, or, and not are allboolean operations. For the purposes of this problem,and and or will be defined to take exactly two inputs.Example formulas:a(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))Assume that we have the following abstractions de-fined for boolean expressions:• (variable? exp) → booleanIndicates whether the given boolean expressionis a simple variable.• (make-variable sym) → expConverts a symbol into a expression. The re-turned expression is a variable.• (variable-name exp) → symObtains the symbol associated with an expres -sion. Assumes exp is a variable.• (not? exp) → booleanPredicate for not expressions.• (make-not exp) → expConstructor for not expressions. exp should bean expression. It becomes the subexpression forthe new not expression.• (not-operand exp) → expReturns the subexpression of a not expression.• (or? exp) → booleanPredicate for or expressions.• (make-or exp1 exp2) → expConstructor for or expressions. exp1 and exp2should be expressions. They become the twosubexpressions for the new or expression.• (or-first exp) → expReturns the first subexpression of an or expres-sion.• (or-second exp) → expReturns the second subexpression of an or ex-pression.• (and? exp) → booleanPredicate for and expressions.• (make-and exp1 exp2) → expConstructor for and expressions. exp1 and exp2should be expressions. They become the twosubexpressions for the new and expression.• (and-first exp) → expReturns the first subexpression of an and expres-sion.• (and-second exp) → expReturns the second sub express ion of an and ex-pression.For those who are curious, a simple implementationof these methods are given in this week’s tutorial so-lutions.; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; D e f i n i t i o n s f o r Dr . Scheme; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; Semi− standard f u n c t i o n s and v a l u e s( d e f i n e n i l ’ ( ) )( d e f i n e ( f o l d − r i g h t op i n i t l s t )( i f ( n u l l ? l s t )i n i t( op ( c a r l s t )( f o l d − r i g h t op i n i t ( cd r l s t ) ) ) ) )( d e f i n e ( f i l t e r pred l s t )(cond ( ( n u l l ? l s t ) n i l )( ( pred ( c ar l s t ) )( cons ( c ar l s t )( f i l t e r pred ( cdr l s t ) ) ) )( e l s e ( f i l t e r pred ( cd r l s t ) ) ) ) ); ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;; ; Error ch ec k i n g h e l p e r s; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;( d e f i n e ( assert t es t − v a l pred )( i f ( pred t es t − v a l )#t( error ”ASSERT FAILED: ”t …
View Full Document
Unlocking...