Scheme&Basics&> (butfirst '(help!)) () ![The!butf irst!o f!a!* se n ten c e* !containing!one!word!is!all!but!that!word ,!i.e.,!the!em pty !sen tence.!!(BUTFIRST !'HE LP !)!with ou t!th e!inn er!pa ren the ses!w o uld !be!bu tfirst!of!a!w o rd,!and!would!! return!ELP!,!the!most!common!wrong!answer.!!The!second!most!common!wrong!answer,!although!we!didn't!take!off!for!it,!was!'()!JJ!that!is,!the!correct!answer!with!a!quote!in!front.!!If!you!are!r e ad in g !'()!in!progra m s!as!if!it!we re!the !name!of!the!empty!se nte nc e,!then !you !do n't!un d erstan d !quo ting .]!!!! > ((if 3 * +) 4 5) 20 ![Since!3!is!true ,!th e!v alu e!o f!t h e!in n e r!p a ren t h es ize d !expression!is!the!multiplication!function.]!!!! > (let ((+ -))(+ 8 2)) 6 [Names !of !primitives!are!just!ordinary!variables!that!happen!to!have!a!prede fined !valu e,!but!that!can!be!overridden!by!a!local!binding.!!Notice!that!that!isn't!true!about!nam e s!of!special!forms;!you!can't!say!(LET!((DEFINE!+))!)!etc.]!!&> (let ((+ -)(- +))(- 8 2)) 10 ![Names !of !primitives!are!just!o rd ina ry !va riab les !that!happen!to!have !a!pre de fined !valu e,!but!that!can!be!overridden!by!a!local!bind in g .!!N o tic e!t h at !tha t!isn't!true!ab o ut!na m es!o f!special!forms;!you!can't!say!(LET!((DEFINE!+))!...)!etc.!Since!all!the!bindings!in!a!LET!are!done!at!once,!not!in!sequence,!the!local!value!for!the !name!"J"!is!the!*original*!meaning!of!+,!not!the!local!meaning.]!!!! > ((lambda (z) (- z z)) (random 10)) 0 ![Some!p e op le !said !"0 !if!ap p licative!order,!some!random!value!if!normal!orde r."!!Tha t's!true,!bu t!the!point!of!the!question!was!to!see!if!you!know!what!Scheme!does!]!&&&&&&&&&&&&&Applicative&vs.&Normal&Order&If!an!expression!produces!an!error,!just!say!"error":!if!it!returns!a!procedure,!just!say!"procedure."!!Given!the!following!definitions:!!(define (marco x) 'done) (define (polo) (polo)) !(a)!What!will!be!the!result!of!the!expression!(marco (polo))!!!!!!!in!normal!order?!!!!!!!!!!!done!!!!!!!.!!!!!!!in!applicative!order?!!!!!!!!!!Error!!!!!!.!!(b)!What!will!be!the!result!of!the!expression!(marco polo)!!!!!!!in!normal!order?!!!!!!!!!!!done!!!!!!!.!!!!!!!in!applicative!order?!!!!!!!!!!!done!!!!!!!&Iterative&vs&Recursive&!Is!the!following!procedure!iterative!or!recursive:!!(define (foo sent) (define (foo-helper sent prev) (cond ((empty? (bf sent)) (* (first sent) prev)) (else (se (* (first sent) prev) (foo-helper (bf sent) (first sent)))))) (foo-helper sent 1)) !If!recursive,!rewrite!as!iterative.!If!iterative,!rewrite!as!recursive.!!!This!is!recursive.!The!iterative!version!looks!like:! (define (foo sent) (define (foo-iter sent prev so-far) (cond ((empty? sent) so-far) (else (foo-iter (bf sent) (first sent) (se so-far (* (first sent) prev))))) (foo-iter sent 1 '())) !&Boxes&and&Pointers&!Draw!the!box!and!pointer!diagrams!for!the!following!expressions!!>(list (append (list 1 2) (cons 3 (cons 4 '( )))) (cons 5 6)) +---+---+ +---+---+ ->| | -|---->| | / | +-|-+---+ +-|-+---+ | | | V | +---+---+ +---+---+ | | 5 | -|-->| 6 | / | | +---+---+ +---+---+ V +---+---+ +---+---+ +---+---+ +---+---+ | 1 | -|-->| 2 | -|-->| 3 | -|--> | 4 | / | +---+---+ +---+---+ +---+---+ +---+---+ >(cons (cons 1 '( )) (list 2 (list 3))) ! +---+---+ +---+---+ +---+---+ ->| | -|----->| 2 | -|-->| | / | +-|-+---+ +---+---+ +-|-+---+ | | V V +---+---+ +---+---+ | 1 | / | | 3 | / | !!! +---+---+ +---+---+ ! (define x (list (list 1 2 3) (list 5) (cons 6 7))) (define y (map cdr x)) !! +---+---+ +---+---+ +---+---+ ->| | -|-->| / | -|-->| 7 | / | +-|-+---+ +---+---+ +---+---+ V +---+---+ +---+---+ | 2 | -|-->| 3 | / | +---+---+ +---+---+ &&&Orders&of&Growth&!1.!!(define (garply n) (if (< n 2) n (garply (garply (- n 1))))) !Solution:&&garply!is!a!procedure!that!takes!linear!O(n)!time.!When!garp ly !is !ca lle d !w ith !a !positive!number!as!argument,!garply!will!call!itself!with!progressively!smaller!arg u ments,!and!so!(garply!n)!will!yield !(garply!(garply!(ga rply!(g arp ly...(garp ly !1))...))))!in!n!time.!(garply!1)!takes!constant!time!to!evaluate!and!returns!1,!and!so!each!containing!procedure!call!will!receive!1!as!argument!and!return!1.!The!chain!collapses!to!the!value!1,!and!since!there!are!n!procedu re!calls!in!the !cha in,!eac h!of!w h ich!takes!constant!time!to!evaluate,!garply!takes!2n !tota l!time,!or!O(n)!time,!to!evaluate.!!!2.!(Define (garply n) (if (< n 2) n (+ (foo n) (garply (- n 1))))) !Assuming!foo!is!defined!somewhere,!please!circle!TRUE!or!FALSE.!and!in!one!sentence!explain!your!choice.!!True!or!False:!We!have!enough!information!to!determine!the!order!of!growth!of!garply.!!True!or!False:!NO!matter!how!foo!is!defined,!garply!will!always!have!an!order!of!growth!greater!than!or!equal!to!THETA(n)!!True!or!False:!garply!has!an!order!of!growth!in!Theta(n^2)!if!foo!is!defined!as!follows:!!(define (foo n) (if (< n 100) 121 (+ (* n 100) (foo (- n 1)))) !Solutions:!False,!True,!True!!&&&&&&&&&Data&Abstraction&!Time!for!some!math!!We're!going!to!use!Scheme!to!represent!polynomials!of!arbitrary!degree.!We!are!going!to!represent!a!polynomial!as!a!list,!where!the!first!element!in!the!list!is!the!coefficient!of!the!zeroth!order!term,!the!second!element!in!the!list!is!the!coefficient!of!the!first!order!term,!etc.!For!example,!the!polynomial!7!–!2x!+!3x^3!would!be!represented!as!the!list!(7!J2!0!3).!!!Assume!that!we!already!have!the!constructor!makeJpolynomial!defined!as!follows:!!(define!(makeJpoly!ls)!ls).!This!seems!a!little!silly!but!bear!with!us!for!now.!!!Write!the!following!utility!procedures:!!1. getJn,!which!takes!a!polynomial!and!a!number!n!as!argument!and!returns!the!coefficient!of!its!nth!term!(ex:!(getJn!(makeJpoly!'(7!J2!0!3))!1)!returns!J2).!2. degree,!which!takes!a!polynomial!as!argument!and!returns!its!degree!(ex:!(degree!(makeJpoly!'(7!J2!0!3)))!returns!3).!!(define (get-n poly n) (if (= n 0) (car poly) (get-n (cdr poly) (- n 1)))) (define (degree poly) (- (length poly) 1))
View Full Document
Unlocking...