#reader(lib"read.ss""wxme")WXME0108 ## #| This file uses the GRacket editor format. Open this file in DrRacket version 5.3.6 or later to read it. Most likely, it was created by saving a program in DrRacket, and it probably contains a program with non-text elements (such as images or comment boxes). http://racket-lang.org/ |# 30 7 #"wxtext\0" 3 1 6 #"wxtab\0" 1 1 8 #"wximage\0" 2 0 8 #"wxmedia\0" 4 1 34 #"(lib \"syntax-browser.ss\" \"mrlib\")\0" 1 0 16 #"drscheme:number\0" 3 0 44 #"(lib \"number-snip.ss\" \"drscheme\" \"private\")\0" 1 0 36 #"(lib \"comment-snip.ss\" \"framework\")\0" 1 0 93 ( #"((lib \"collapsed-snipclass.ss\" \"framework\") (lib \"collapsed-sni" #"pclass-wxme.ss\" \"framework\"))\0" ) 0 0 43 #"(lib \"collapsed-snipclass.ss\" \"framework\")\0" 0 0 19 #"drscheme:sexp-snip\0" 0 0 36 #"(lib \"cache-image-snip.ss\" \"mrlib\")\0" 1 0 68 ( #"((lib \"image-core.ss\" \"mrlib\") (lib \"image-core-wxme.rkt\" \"mr" #"lib\"))\0" ) 1 0 29 #"drscheme:bindings-snipclass%\0" 1 0 88 ( #"((lib \"pict-snip.rkt\" \"drracket\" \"private\") (lib \"pict-snip.r" #"kt\" \"drracket\" \"private\"))\0" ) 0 0 33 #"(lib \"bullet-snip.ss\" \"browser\")\0" 0 0 25 #"(lib \"matrix.ss\" \"htdp\")\0" 1 0 22 #"drscheme:lambda-snip%\0" 1 0 26 #"drracket:spacer-snipclass\0" 0 0 57 #"(lib \"hrule-snip.rkt\" \"macro-debugger\" \"syntax-browser\")\0" 1 0 26 #"drscheme:pict-value-snip%\0" 0 0 45 #"(lib \"image-snipr.ss\" \"slideshow\" \"private\")\0" 1 0 38 #"(lib \"pict-snipclass.ss\" \"slideshow\")\0" 2 0 55 #"(lib \"vertical-separator-snip.ss\" \"stepper\" \"private\")\0" 1 0 18 #"drscheme:xml-snip\0" 1 0 31 #"(lib \"xml-snipclass.ss\" \"xml\")\0" 1 0 21 #"drscheme:scheme-snip\0" 2 0 34 #"(lib \"scheme-snipclass.ss\" \"xml\")\0" 1 0 10 #"text-box%\0" 1 0 32 #"(lib \"text-snipclass.ss\" \"xml\")\0" 1 0 1 6 #"wxloc\0" 0 0 67 0 1 #"\0" 0 75 1 #"\0" 0 12 90 -1 90 -1 3 -1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 255 255 255 1 -1 0 9 #"Standard\0" 0 75 6 #"Menlo\0" 0 20 90 -1 90 -1 3 -1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 255 255 255 1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 -1 -1 2 24 #"framework:default-color\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 15 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 150 0 150 0 0 0 -1 -1 2 15 #"text:ports out\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 150 0 150 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 93 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 15 #"text:ports err\0" 0 -1 1 #"\0" 1.0 0 -1 -1 93 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 175 0 0 0 -1 -1 2 17 #"text:ports value\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 175 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 92 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 34 139 34 0 0 0 -1 -1 2 27 #"Matching Parenthesis Style\0" 0 -1 1 #"\0" 1.0 0 92 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 34 139 34 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 38 38 128 0 0 0 -1 -1 2 37 #"framework:syntax-color:scheme:symbol\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 38 38 128 0 0 0 -1 -1 2 38 #"framework:syntax-color:scheme:keyword\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 38 38 128 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 12 21 194 0 0 0 -1 -1 2 38 #"framework:syntax-color:scheme:comment\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 12 21 194 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 41 128 38 0 0 0 -1 -1 2 37 #"framework:syntax-color:scheme:string\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 41 128 38 0 0 0 -1 -1 2 39 #"framework:syntax-color:scheme:constant\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 41 128 38 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 132 60 36 0 0 0 -1 -1 2 49 #"framework:syntax-color:scheme:hash-colon-keyword\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 132 60 36 0 0 0 -1 -1 2 42 #"framework:syntax-color:scheme:parenthesis\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 132 60 36 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 36 #"framework:syntax-color:scheme:error\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 36 #"framework:syntax-color:scheme:other\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 16 #"Misspelled Text\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 81 112 203 0 0 0 -1 -1 2 38 #"drracket:check-syntax:lexically-bound\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 81 112 203 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 178 34 34 0 0 0 -1 -1 2 28 #"drracket:check-syntax:set!d\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 178 34 34 0 0 0 -1 -1 2 37 #"drracket:check-syntax:unused-require\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 36 #"drracket:check-syntax:free-variable\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 255 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 68 0 203 0 0 0 -1 -1 2 31 #"drracket:check-syntax:imported\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 68 0 203 0 0 0 -1 -1 2 47 #"drracket:check-syntax:my-obligation-style-pref\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 178 34 34 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 116 0 0 0 0 -1 -1 2 50 #"drracket:check-syntax:their-obligation-style-pref\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 0 116 0 0 0 0 -1 -1 2 48 #"drracket:check-syntax:unk-obligation-style-pref\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 139 142 28 0 0 0 -1 -1 2 49 #"drracket:check-syntax:both-obligation-style-pref\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 139 142 28 0 0 0 -1 -1 2 26 #"plt:htdp:test-coverage-on\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 1 0 0 0 0 0 0 255 165 0 0 0 0 -1 -1 2 27 #"plt:htdp:test-coverage-off\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 1 0 0 0 0 0 0 255 165 0 0 0 0 -1 -1 4 1 #"\0" 0 70 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 4 4 #"XML\0" 0 70 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 37 #"plt:module-language:test-coverage-on\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 38 #"plt:module-language:test-coverage-off\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 1 0 0 0 0 0 0 255 165 0 0 0 0 -1 -1 4 1 #"\0" 0 71 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 4 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 1 0 0 0 0 0 0 0 0 1.0 1.0 1.0 0 0 255 0 0 0 -1 -1 4 1 #"\0" 0 71 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 1 0 0 0 0 0 0 0 0 1.0 1.0 1.0 0 0 255 0 0 0 -1 -1 4 1 #"\0" 0 71 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1.0 1.0 1.0 0 100 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 1 1 1 200 0 0 0 0 0 -1 -1 4 1 #"\0" 0 -1 1 #"\0" 1.0 0 92 -1 -1 -1 -1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 255 255 0 -1 -1 0 1 #"\0" 0 75 6 #"Menlo\0" 0.0 21 90 -1 90 -1 3 -1 0 1 0 1 0 0 0.0 0.0 0.0 0.0 0.0 0.0 0 0 0 255 255 255 1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 0 15 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 34 139 34 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 176 48 96 0 0 0 -1 -1 2 1 #"\0" 0 71 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 1 #"\0" 0 71 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 0 100 0 0 0 0 -1 -1 0 1 #"\0" 0 -1 1 #"\0" 0.0 13 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 2 1 #"\0" 0 -1 1 #"\0" 0.0 13 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 1.0 1.0 1.0 1.0 1.0 1.0 0 0 0 0 0 0 -1 -1 0 1 #"\0" 0 75 6 #"Menlo\0" 0.0 14 90 -1 90 -1 3 -1 0 1 0 1 0 0 0.0 0.0 0.0 0.0 0.0 0.0 0 0 0 255 255 255 1 -1 0 1 #"\0" 0 75 9 #"Consolas\0" 0.0 20 90 -1 90 -1 3 -1 0 1 0 1 0 0 0.0 0.0 0.0 0.0 0.0 0.0 0 0 0 255 255 255 1 -1 0 1 #"\0" 0 -1 1 #"\0" 1.0 0 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0.0 0.0 0.0 1.0 1.0 1.0 200 0 0 0 0 0 -1 -1 0 1687 0 27 3 12 #"#lang racket" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 7 #"require" 0 0 23 3 1 #" " 0 0 14 3 24 #"test-engine/racket-tests" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 87 ( #";; Consider the \"fibonnacci sequence\", where each term is the sum " #"of the two preceding:" ) 0 0 23 29 1 #"\n" 0 0 17 3 35 #";; 0,1,1,2,3,5,8,13,21,34,55,..." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 20 #";; Discuss: rabbits." 0 0 23 29 1 #"\n" 0 0 17 3 50 #";; f(n-2) is the #middle-aged rabbits (say, 8)" 0 0 23 29 1 #"\n" 0 0 17 3 37 #";; and f(n-1) is #teenagers (say 13)." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 44 #";; All 8+13 make babies; then after a season" 0 0 23 29 1 #"\n" 0 0 17 3 35 #";; the middle-aged die (8 of them)," 0 0 23 29 1 #"\n" 0 0 17 3 6 #";; the" 0 0 17 3 42 #" teenagers become middle-aged (13 of them)" 0 0 23 29 1 #"\n" 0 0 17 3 6 #";; and" 0 0 17 3 1 #" " 0 0 17 3 3 #"the" 0 0 17 3 1 #" " 0 0 17 3 41 #"newborns become teenagers (8+13 of them)." 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 34 #";; How does sequence go, negative?" 0 0 23 29 1 #"\n" 0 0 17 3 51 #";; How does sequence go, if we use different seeds?" 0 0 23 29 1 #"\n" 0 0 17 3 68 #";; Why does fib(35) take so long? (Start to draw computation tree.)" 0 0 23 29 1 #"\n" 0 0 17 3 66 #";; Does fib(36) take {more,less,exactly} twice as long as fib(35)?" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 70 ( #";; Q: If you have a fib sequence, and you multiply every term by 1" #"7," ) 0 0 23 29 1 #"\n" 0 0 17 3 48 #";; is it still a fib sequence? [Prove it!]" 0 0 23 29 1 #"\n" 0 0 17 3 74 ( #";; Q: If you have two different fib sequences and you add them tog" #"ether," ) 0 0 23 29 1 #"\n" 0 0 17 3 51 #";; do you get a new fib sequence? [Prove it!]" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 71 ( #";; Q: In general, is (fib n) more than twice as big as (fib (- n 1" #"))," ) 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; exactly twice as big, less than twice as big, or 'it varies'" #"?" ) 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; (I'm asking about after we pass the base case -- so for n>1." #")" ) 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #";; A: Clearly, it's less than 2*, but might be something like 1.5-" #"ish times." ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 75 ( #";; Okay: it does seem to be exponential. ..We'll come back to that" #" later." ) 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 11 #";; As code:" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 17 3 11 #"; base case" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 17 3 11 #"; base case" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"2" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"4" 0 0 23 3 2 #") " 0 0 20 3 1 #"3" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 2 #") " 0 0 20 3 2 #"55" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 15 3 4 #"cond" 0 0 23 3 3 #" [(" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #"]" 0 0 23 29 1 #"\n" 0 0 23 3 10 #" [(" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #"]" 0 0 23 29 1 #"\n" 0 0 23 3 9 #" [" 0 0 14 3 4 #"else" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 18 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 6 #")))]))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"2" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"4" 0 0 23 3 2 #") " 0 0 20 3 1 #"3" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 2 #") " 0 0 20 3 2 #"55" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 2 #"#;" 0 0 23 3 1 #"(" 0 0 14 3 8 #"for-each" 0 0 23 3 2 #" (" 0 0 15 3 6 #"lambda" 0 0 23 3 2 #" (" 0 0 14 3 1 #"n" 0 0 23 3 3 #") (" 0 0 14 3 6 #"printf" 0 0 23 3 1 #" " 0 0 19 3 17 #"\"(fib ~v) = ~v~n\"" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-naive" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 4 #")) (" 0 0 14 3 5 #"sleep" 0 0 23 3 1 #" " 0 0 20 3 3 #"0.5" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 9 #" " 0 0 20 3 1 #"'" 0 0 23 3 1 #"(" 0 0 20 3 1 #"0" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 1 #" " 0 0 20 3 2 #"20" 0 0 23 3 1 #" " 0 0 20 3 2 #"22" 0 0 23 3 1 #" " 0 0 20 3 2 #"24" 0 0 23 3 1 #" " 0 0 20 3 2 #"26" 0 0 23 3 1 #" " 0 0 20 3 2 #"28" 0 0 23 3 1 #" " 0 0 20 3 2 #"30" 0 0 23 3 1 #" " 0 0 20 3 2 #"32" 0 0 23 3 1 #" " 0 0 20 3 2 #"34" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 71 ( #";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Memoization: ;;;;;;;;;;;;;;;;;;;" #";;;" ) 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 7 271 4 0 0 0 44 0 17 3 43 #"; Examples of using hash-tables, in racket:" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 8 #"my-table" 0 0 23 3 2 #" (" 0 0 14 3 9 #"make-hash" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 9 #"hash-set!" 0 0 23 3 1 #" " 0 0 14 3 8 #"my-table" 0 0 23 3 1 #" " 0 0 19 3 7 #"\"hello\"" 0 0 23 3 1 #" " 0 0 20 3 2 #"99" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 8 #"hash-ref" 0 0 23 3 1 #" " 0 0 14 3 8 #"my-table" 0 0 23 3 1 #" " 0 0 19 3 7 #"\"hello\"" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 13 #"hash-has-key?" 0 0 23 3 1 #" " 0 0 14 3 8 #"my-table" 0 0 23 3 1 #" " 0 0 19 3 7 #"\"hello\"" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 13 #"hash-has-key?" 0 0 23 3 1 #" " 0 0 14 3 8 #"my-table" 0 0 23 3 1 #" " 0 0 19 3 7 #"\"howdy\"" 0 0 23 3 1 #")" 0 0 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 44 #";;; Use hash tables to memoize (explicitly):" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 11 #"fib-history" 0 0 23 3 2 #" (" 0 0 14 3 9 #"make-hash" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 13 #"hash-has-key?" 0 0 23 3 1 #" " 0 0 14 3 11 #"fib-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 14 3 8 #"hash-ref" 0 0 23 3 1 #" " 0 0 14 3 11 #"fib-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 15 3 3 #"let" 0 0 23 3 3 #" {[" 0 0 14 3 6 #"answer" 0 0 23 3 2 #" (" 0 0 15 3 4 #"cond" 0 0 23 29 1 #"\n" 0 0 23 3 24 #" [(" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #"]" 0 0 23 29 1 #"\n" 0 0 23 3 24 #" [(" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #"]" 0 0 23 29 1 #"\n" 0 0 23 3 23 #" [" 0 0 14 3 4 #"else" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 4 #")) (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 7 #")))])]}" 0 0 23 29 1 #"\n" 0 0 23 3 13 #" (" 0 0 14 3 9 #"hash-set!" 0 0 23 3 1 #" " 0 0 14 3 11 #"fib-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 14 3 6 #"answer" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 12 #" " 0 0 14 3 6 #"answer" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"2" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"4" 0 0 23 3 2 #") " 0 0 20 3 1 #"3" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 2 #") " 0 0 20 3 2 #"55" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 2 #"#;" 0 0 23 3 1 #"(" 0 0 14 3 8 #"for-each" 0 0 23 3 2 #" (" 0 0 15 3 6 #"lambda" 0 0 23 3 2 #" (" 0 0 14 3 1 #"n" 0 0 23 3 3 #") (" 0 0 14 3 6 #"printf" 0 0 23 3 1 #" " 0 0 19 3 1 #"\"" 0 0 19 3 1 #"(" 0 0 19 3 4 #"fib " 0 0 19 3 2 #"~v" 0 0 19 3 9 #") = ~v~n\"" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 2 #" (" 0 0 14 3 8 #"fib-memo" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 4 #")) (" 0 0 14 3 5 #"sleep" 0 0 23 3 1 #" " 0 0 20 3 3 #"0.5" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 12 #" " 0 0 20 3 1 #"'" 0 0 23 3 1 #"(" 0 0 20 3 1 #"0" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 1 #" " 0 0 20 3 2 #"20" 0 0 23 3 1 #" " 0 0 20 3 2 #"30" 0 0 23 3 1 #" " 0 0 20 3 2 #"32" 0 0 23 3 1 #" " 0 0 20 3 2 #"34" 0 0 23 3 1 #" " 0 0 20 3 2 #"36" 0 0 23 3 1 #" " 0 0 20 3 2 #"38" 0 0 23 3 1 #" " 0 0 20 3 2 #"40" 0 0 23 3 1 #" " 0 0 20 3 2 #"50" 0 0 23 3 1 #" " 0 0 20 3 2 #"60" 0 0 23 3 1 #" " 0 0 20 3 3 #"100" 0 0 23 3 1 #" " 0 0 20 3 3 #"200" 0 0 23 3 1 #" " 0 0 20 3 3 #"500" 0 0 23 3 1 #" " 0 0 20 3 4 #"1000" 0 0 23 3 1 #" " 0 0 20 3 4 #"2000" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #";; Can we make a memo-ized version, w/o having to go and re-write ou" #"r original" ) 0 0 23 29 1 #"\n" 0 0 17 3 24 #";; non-memoized version?" 0 0 23 29 1 #"\n" 0 0 17 3 7 #";; Yes!" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 32 #";; Starting w/ regular old fib2," 0 0 23 29 1 #"\n" 0 0 17 3 56 #";; We'll write fib2-memo which tries a lookup and calls " 0 0 17 3 7 #"`fib2` " 0 0 17 3 5 #"when " 0 0 17 3 4 #"the " 0 0 17 3 13 #"lookup fails." 0 0 23 29 1 #"\n" 0 0 17 3 77 ( #";; ...But we don't have a way of going into fib2's code and changing" #" the name" ) 0 0 23 29 1 #"\n" 0 0 17 3 47 #";; of its recursive calls to \"fib2-memo\", Rats!" 0 0 23 29 1 #"\n" 0 0 17 3 77 ( #";; So instead we'll getting this effect through re-binding names. R" #"ead on..." ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 81 ( #";; (a) We'll make a variable `fib2-orig`, bound to (the function kn" #"own as) fib2." ) 0 0 23 29 1 #"\n" 0 0 17 3 53 #";; Note that fib2-orig will make a call to fib2:" 0 0 23 29 1 #"\n" 0 0 17 3 61 #";; fib2-orig ->(recur)-> fib2" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 49 #";; (b) Next, we write a new function fib2-memo: " 0 0 23 29 1 #"\n" 0 0 17 3 45 #";; fib2-memo will be a wrapper function " 0 0 17 3 5 #"which" 0 0 17 3 1 #" " 0 0 17 3 5 #"first" 0 0 17 3 1 #" " 0 0 17 3 18 #"just looks up its " 0 0 23 29 1 #"\n" 0 0 17 3 64 #";; input in a table and returns the stored answer if found;" 0 0 23 29 1 #"\n" 0 0 17 3 63 #";; if the value isn't there then fib2-memo calls fib2-orig" 0 0 23 29 1 #"\n" 0 0 17 3 25 #";; So at this stage:" 0 0 23 29 1 #"\n" 0 0 17 3 21 #";; fib2-memo" 0 0 17 3 1 #" " 0 0 17 3 3 #"-> " 0 0 17 3 6 #"lookup" 0 0 17 3 1 #" " 0 0 17 3 2 #"->" 0 0 17 3 1 #" " 0 0 17 3 9 #"fib2-orig" 0 0 17 3 1 #" " 0 0 17 3 2 #"->" 0 0 17 3 15 #"(recur)-> fib2 " 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; Yeah, this is momentarily pointless since fib2 = fib2-orig)" #"." ) 0 0 23 29 1 #"\n" 0 0 17 3 15 #";; (sigh)" 0 0 17 3 1 #" " 0 0 17 3 2 #"If" 0 0 17 3 1 #" " 0 0 17 3 4 #"only" 0 0 17 3 1 #" " 0 0 17 3 3 #"the" 0 0 17 3 1 #" " 0 0 17 3 9 #"recursive" 0 0 17 3 1 #" " 0 0 17 3 4 #"call" 0 0 17 3 1 #" " 0 0 17 3 2 #"to" 0 0 17 3 1 #" " 0 0 17 3 4 #"fib2" 0 0 17 3 1 #" " 0 0 17 3 8 #"actually" 0 0 17 3 1 #" " 0 0 17 3 20 #"called fib2-memo...." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 63 #";; (c) The final step: re-assign fib2's value to be fib2-memo!" 0 0 23 29 1 #"\n" 0 0 17 3 58 #";; f-memo -> lookup -> f-orig ->(recur)-> f-memo." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 64 #";; That's what we want -- a function which looks up in a table," 0 0 23 29 1 #"\n" 0 0 17 3 83 ( #";; and if not found follows the original code except that we recur " #"back to f-memo!" ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 4 #"fib2" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 1 #"<" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 14 3 1 #"n" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 2 #" (" 0 0 14 3 4 #"fib2" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 4 #")) (" 0 0 14 3 4 #"fib2" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 5 #")))))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 12 #"fib2-history" 0 0 23 3 2 #" (" 0 0 14 3 9 #"make-hash" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 9 #"fib2-orig" 0 0 23 3 1 #" " 0 0 14 3 4 #"fib2" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 13 #"hash-has-key?" 0 0 23 3 1 #" " 0 0 14 3 12 #"fib2-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 14 3 8 #"hash-ref" 0 0 23 3 1 #" " 0 0 14 3 12 #"fib2-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 15 3 3 #"let" 0 0 23 3 3 #" {[" 0 0 14 3 6 #"answer" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-orig" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 3 #")]}" 0 0 23 29 1 #"\n" 0 0 23 3 9 #" (" 0 0 14 3 9 #"hash-set!" 0 0 23 3 1 #" " 0 0 14 3 12 #"fib2-history" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 14 3 6 #"answer" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 8 #" " 0 0 14 3 6 #"answer" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 4 #"set!" 0 0 23 3 1 #" " 0 0 14 3 4 #"fib2" 0 0 23 3 1 #" " 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"2" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"4" 0 0 23 3 2 #") " 0 0 20 3 1 #"3" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-expect" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib2-memo" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 2 #") " 0 0 20 3 2 #"55" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 62 #";; Can we take the above process for fib2, and make a function" 0 0 23 29 1 #"\n" 0 0 17 3 45 #";; where I can *pass in* the function I want?" 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; (memoize! fib2) ; Change the variable `fib2` so it refers to a" #" " ) 0 0 17 3 19 #"memoized version..." 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; (memoize! sqrt) ; Change the variable `sqrt` so it refers to a" #" " ) 0 0 17 3 19 #"memoized version..." 0 0 23 29 1 #"\n" 0 0 17 3 53 #";; We will do this -- but as a macro, not a function." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 46 #";; We *can't* do it as a function; here's why:" 0 0 23 29 1 #"\n" 0 0 17 3 72 ( #";; Recall that step (c) requires set!'ing the name which is used in " #"the " ) 0 0 17 3 15 #"recursive call;" 0 0 23 29 1 #"\n" 0 0 17 3 50 #";; that is `(set! sqrt ...)` or `(set! fib2 ...)`." 0 0 23 29 1 #"\n" 0 0 17 3 24 #";; If we tried to write " 0 0 23 29 1 #"\n" 0 0 17 3 9 #";; (" 0 0 17 3 6 #"define" 0 0 17 3 1 #" " 0 0 17 3 1 #"(" 0 0 17 3 8 #"memoize!" 0 0 17 3 1 #" " 0 0 17 3 4 #"f_id" 0 0 17 3 1 #")" 0 0 17 3 1 #" " 0 0 17 3 3 #"..." 0 0 17 3 1 #" " 0 0 17 3 1 #"(" 0 0 17 3 4 #"set!" 0 0 17 3 11 #" f_id ...))" 0 0 23 29 1 #"\n" 0 0 17 3 71 ( #";; then we'll be re-assigning our parameter, and not the identifier " #"tht" ) 0 0 23 29 1 #"\n" 0 0 17 3 31 #";; memoize! had been called on." 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; In fact, that identifier will never be given to a function -- jus" #"t" ) 0 0 23 29 1 #"\n" 0 0 17 3 47 #";; the value that the identifier had stood for." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #";; This is exactly the sort of problem macros are made to get around" #"!" ) 0 0 23 29 1 #"\n" 0 0 17 3 64 #";; \"define-syntax-rule\" means it's not a function; it's a macro." 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 18 #"define-syntax-rule" 0 0 23 3 2 #" (" 0 0 14 3 8 #"memoize!" 0 0 23 3 1 #" " 0 0 14 3 4 #"f_id" 0 0 23 3 3 #") " 0 0 17 3 34 #"; f_id *must* be an identifier.[1]" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 15 3 4 #"let*" 0 0 23 3 3 #" {[" 0 0 14 3 4 #"memo" 0 0 23 3 2 #" (" 0 0 14 3 9 #"make-hash" 0 0 23 3 2 #")]" 0 0 23 29 1 #"\n" 0 0 23 3 10 #" [" 0 0 14 3 6 #"f-orig" 0 0 23 3 1 #" " 0 0 14 3 4 #"f_id" 0 0 23 3 3 #"] " 0 0 17 3 51 #"; Remember the code which contains recursive calls " 0 0 17 3 7 #"to f_id" 0 0 23 29 1 #"\n" 0 0 23 3 10 #" [" 0 0 14 3 6 #"f-memo" 0 0 23 3 2 #" (" 0 0 15 3 6 #"lambda" 0 0 23 3 2 #" (" 0 0 14 3 4 #"args" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 20 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 13 #"hash-has-key?" 0 0 23 3 1 #" " 0 0 14 3 4 #"memo" 0 0 23 3 1 #" " 0 0 14 3 4 #"args" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 24 #" (" 0 0 14 3 8 #"hash-ref" 0 0 23 3 1 #" " 0 0 14 3 4 #"memo" 0 0 23 3 1 #" " 0 0 14 3 4 #"args" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 24 #" (" 0 0 15 3 5 #"begin" 0 0 23 3 2 #" (" 0 0 14 3 9 #"hash-set!" 0 0 23 3 1 #" " 0 0 14 3 4 #"memo" 0 0 23 3 1 #" " 0 0 14 3 4 #"args" 0 0 23 3 2 #" (" 0 0 14 3 6 #"f-orig" 0 0 23 3 1 #" " 0 0 14 3 4 #"args" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 31 #" (" 0 0 14 3 8 #"hash-ref" 0 0 23 3 1 #" " 0 0 14 3 4 #"memo" 0 0 23 3 1 #" " 0 0 14 3 4 #"args" 0 0 23 3 5 #"))))]" 0 0 23 29 1 #"\n" 0 0 23 3 10 #" }" 0 0 23 29 1 #"\n" 0 0 23 3 5 #" (" 0 0 14 3 4 #"set!" 0 0 23 3 1 #" " 0 0 14 3 4 #"f_id" 0 0 23 3 1 #" " 0 0 14 3 6 #"f-memo" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 76 ( #";; When somebody calls, say, `(memoize! sqrt)`, the parameter `f_id`" #" doesn't" ) 0 0 23 29 1 #"\n" 0 0 17 3 70 ( #";; hold the sqrt function (like it would if memoize! were a function" #");" ) 0 0 23 29 1 #"\n" 0 0 17 3 62 #";; instead since memoize! is a macro, `f_id` holds *syntax* --" 0 0 23 29 1 #"\n" 0 0 17 3 30 #";; -- the *identifier* `sqrt`." 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #";; The macro goes on to build/return a new *expression* (a let* in t" #"his case);" ) 0 0 23 29 1 #"\n" 0 0 17 3 64 #";; wherever we mention `f_id` it will really be substituted with" 0 0 23 29 1 #"\n" 0 0 17 3 25 #";; the identifier `sqrt`." 0 0 23 29 1 #"\n" 0 0 17 3 71 ( #";; Once we've constructed this new let* involving the identifier `sq" #"rt`" ) 0 0 23 29 1 #"\n" 0 0 17 3 73 ( #";; then it will get evaluated (which will end in \"...(set! sqrt f-m" #"emo)\"." ) 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 2 #"#;" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 1 #"<" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 14 3 1 #"n" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 4 #")) (" 0 0 14 3 3 #"fib" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 5 #")))))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 8 #"memoize!" 0 0 23 3 1 #" " 0 0 14 3 3 #"fib" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 17 3 1 #"#" 0 0 17 3 1 #"|" 0 0 17 29 1 #"\n" 0 0 17 3 58 #"; N.B. check-expects for `fib` are already at top of file." 0 0 17 29 1 #"\n" 0 0 17 3 1 #"(" 0 0 17 3 4 #"time" 0 0 17 3 2 #" (" 0 0 17 3 3 #"fib" 0 0 17 3 1 #" " 0 0 17 3 4 #"1500" 0 0 17 3 2 #"))" 0 0 17 29 1 #"\n" 0 0 17 3 1 #"(" 0 0 17 3 4 #"time" 0 0 17 3 2 #" (" 0 0 17 3 3 #"fib" 0 0 17 3 1 #" " 0 0 17 3 5 #"50000" 0 0 17 3 2 #"))" 0 0 17 29 1 #"\n" 0 0 17 3 1 #"(" 0 0 17 3 4 #"time" 0 0 17 3 2 #" (" 0 0 17 3 3 #"fib" 0 0 17 3 1 #" " 0 0 17 3 5 #"50000" 0 0 17 3 2 #"))" 0 0 17 29 1 #"\n" 0 0 17 3 2 #"|#" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 62 #"; [1] We could stand to have the macro do some error-checking," 0 0 23 29 1 #"\n" 0 0 17 3 80 ( #"; to make sure people don't call (memoize! 2) or (memoize! (first (l" #"ist sqrt)))." ) 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #"; (I mean, if somebody passes in something that's not an identifier" #"," ) 0 0 23 29 1 #"\n" 0 0 17 3 60 #"; it will generate an error in the \"(set! f_id ...)\" line," 0 0 23 29 1 #"\n" 0 0 17 3 65 #"; but that error message will just confuse somebody who is just" 0 0 23 29 1 #"\n" 0 0 17 3 52 #"; using the macro and has no idea what it's doing." 0 0 23 29 1 #"\n" 0 0 17 3 67 #"; So we'd like the chance to do our own error-checking and giving" 0 0 23 29 1 #"\n" 0 0 17 3 34 #"; more detailed error messages.)" 0 0 23 29 1 #"\n" 0 0 17 3 55 #"; But this'd requires doing some computing *before* the" 0 0 23 29 1 #"\n" 0 0 17 3 45 #"; macro even assembles the expression-result." 0 0 23 29 1 #"\n" 0 0 17 3 72 ( #"; We can't do that with `define-syntax-rule`; see instead `syntax-ru" #"les`" ) 0 0 23 29 1 #"\n" 0 0 17 3 49 #"; (or maybe syntax-case ?) ... Just so you know." 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 32 #";;===== A fib-specific solution:" 0 0 23 29 1 #"\n" 0 0 17 3 39 #";; Ask a mathematician to look at fib." 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #";; We earlier decided that fib seems to grow exponential (but less " #"than 2^n)." ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #";; GUESS: ***IF*** we could write (fib n) = k^n, what value of k w" #"ould work?" ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 59 #";; Well, since (fib n) = (+ (fib (- n 1)) (fib (- n 2)))" 0 0 23 29 1 #"\n" 0 0 17 3 43 #";; combine that with (fib n) = k^n to get:" 0 0 23 29 1 #"\n" 0 0 17 3 55 #";; k^n = k^(n-1) + k^(n-2) -- want to solve for k." 0 0 23 29 1 #"\n" 0 0 17 3 50 #";; k^n = k^2 * k^(n-2) = k*k^(n-2) + 1*k^(n-2)" 0 0 23 29 1 #"\n" 0 0 17 3 17 #";; k^2 = k + 1" 0 0 23 29 1 #"\n" 0 0 17 3 51 #";; .... k = alpha (~1.6), or k=alphaBar (~0.5)." 0 0 23 29 1 #"\n" 0 0 17 3 84 ( #";; (Keep in mind, we're being all" #" hypothetical -- we started with \"***IF***...\"...)" ) 0 0 23 29 1 #"\n" 0 0 17 3 55 #";; But if we try (fib n) = alpha^n it doesn't work." 0 0 23 29 1 #"\n" 0 0 17 3 32 #";; Likewise with alphaBar^n." 0 0 23 29 1 #"\n" 0 0 17 3 70 ( #";; ... except both of those do seem to give *other* fib sequence" #"s." ) 0 0 23 29 1 #"\n" 0 0 17 3 88 ( #";; Can we take a linear combination of those two, to get our exact " #"fib sequence 0,1,..?" ) 0 0 23 29 1 #"\n" 0 0 17 3 55 #";; Well, let's try (fib n) = A*alpha^n + B*alphabar^n." 0 0 23 29 1 #"\n" 0 0 17 3 40 #";; (fib 0) = 0, so that gives us A+B=0." 0 0 23 29 1 #"\n" 0 0 17 3 84 ( #";; (fib 1) = 1, so that gives us A*alpha + B*alphaBar=1 => A=1/sq" #"rt(5), and B=-A." ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 83 ( #";; Except remember that this is all hypothetical -- we started with" #" \"***IF***...\"." ) 0 0 23 29 1 #"\n" 0 0 17 3 86 ( #";; But induction, to the rescue! We can show that (fib n) = A*alph" #"a^n - A*alphaBar^n" ) 0 0 23 29 1 #"\n" 0 0 17 3 83 ( #";; (A nice save by induction -- it gives us no clue how to come up " #"with a formula," ) 0 0 23 29 1 #"\n" 0 0 17 3 68 ( #";; but once we have a candidate it can confirm it for all n \\in N." #")" ) 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 40 #";; Note how this result is a bit weird:" 0 0 23 29 1 #"\n" 0 0 17 3 73 ( #";; We add two irrationals together, and they happen to exactly ca" #"ncel." ) 0 0 23 29 1 #"\n" 0 0 17 3 91 ( #";; Moreover: alphaBar ~ 0.5, so alphaBar^n is negligible (just th" #"e tiny irrational bit)." ) 0 0 23 29 1 #"\n" 0 0 17 3 34 #";; SO: (fib n) = (round alpha^n)." 0 0 23 29 1 #"\n" 0 0 17 3 80 ( #";; (This even happens to work for n=0,n=1, before alphaBar^n gets " #"ultra-tiny.)" ) 0 0 23 29 1 #"\n" 0 0 17 3 6 #";; " 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";;" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 5 #"alpha" 0 0 23 3 2 #" (" 0 0 14 3 1 #"/" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #" (" 0 0 14 3 4 #"sqrt" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 3 #")) " 0 0 20 3 1 #"2" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 8 #"alphaBar" 0 0 23 3 2 #" (" 0 0 14 3 1 #"/" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #" (" 0 0 14 3 4 #"sqrt" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 3 #")) " 0 0 20 3 1 #"2" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 1 #"A" 0 0 23 3 2 #" (" 0 0 14 3 1 #"/" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #" (" 0 0 14 3 4 #"sqrt" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 2 #" " 0 0 17 3 2 #"#;" 0 0 23 3 1 #"(" 0 0 14 3 1 #"+" 0 0 23 3 2 #" (" 0 0 14 3 1 #"*" 0 0 23 3 1 #" " 0 0 14 3 1 #"A" 0 0 23 3 2 #" (" 0 0 14 3 4 #"expt" 0 0 23 3 1 #" " 0 0 14 3 5 #"alpha" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 4 #")) (" 0 0 14 3 1 #"*" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 1 #"A" 0 0 23 3 3 #") (" 0 0 14 3 4 #"expt" 0 0 23 3 1 #" " 0 0 14 3 8 #"alphaBar" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 5 #"round" 0 0 23 3 2 #" (" 0 0 14 3 1 #"*" 0 0 23 3 1 #" " 0 0 14 3 1 #"A" 0 0 23 3 2 #" (" 0 0 14 3 4 #"expt" 0 0 23 3 1 #" " 0 0 14 3 5 #"alpha" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 4 #"))))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #") " 0 0 20 3 1 #"0" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"1" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 2 #") " 0 0 20 3 1 #"1" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"2" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"4" 0 0 23 3 2 #") " 0 0 20 3 1 #"3" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 1 #"5" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 12 #"check-within" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 20 3 2 #"10" 0 0 23 3 2 #") " 0 0 20 3 2 #"55" 0 0 23 3 1 #" " 0 0 20 3 5 #"1e-12" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 41 #";; Is this solution really constant-time?" 0 0 23 29 1 #"\n" 0 0 17 3 37 #";; How many digits of alpha are kept?" 0 0 23 29 1 #"\n" 0 0 17 3 44 #";; How does floating-point error accumulate?" 0 0 23 29 1 #"\n" 0 0 17 3 46 #";; We can compare fib-const vs (memoized) fib:" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 2 #" (" 0 0 14 3 11 #"fib-compare" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 3 #"fca" 0 0 23 3 2 #" (" 0 0 14 3 9 #"fib-const" 0 0 23 3 1 #" " 0 0 14 3 1 #"n" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 15 3 6 #"define" 0 0 23 3 1 #" " 0 0 14 3 3 #"fma" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 7 #" " 0 0 14 3 1 #"n" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 2 #" " 0 0 20 3 1 #"`" 0 0 23 3 2 #"((" 0 0 14 3 2 #"n:" 0 0 23 3 5 #" " 0 0 27 3 1 #"," 0 0 14 3 1 #"n" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 5 #" (" 0 0 14 3 6 #"fib-n:" 0 0 23 3 1 #" " 0 0 27 3 1 #"," 0 0 14 3 3 #"fma" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 4 #" " 0 0 27 3 2 #",@" 0 0 23 3 1 #"(" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 3 #"fma" 0 0 23 3 1 #" " 0 0 14 3 3 #"fca" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 6 #" " 0 0 20 3 1 #"`" 0 0 23 3 2 #"()" 0 0 23 29 1 #"\n" 0 0 23 3 6 #" " 0 0 20 3 1 #"`" 0 0 23 3 2 #"((" 0 0 14 3 7 #"approx:" 0 0 23 3 3 #" " 0 0 27 3 1 #"," 0 0 14 3 3 #"fca" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 9 #" (" 0 0 14 3 5 #"diff:" 0 0 23 3 5 #" " 0 0 27 3 1 #"," 0 0 23 3 1 #"(" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 3 #"fma" 0 0 23 3 1 #" " 0 0 14 3 3 #"fca" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 9 #" (" 0 0 14 3 9 #"rel-diff:" 0 0 23 3 1 #" " 0 0 27 3 1 #"," 0 0 23 3 1 #"(" 0 0 14 3 1 #"/" 0 0 23 3 2 #" (" 0 0 14 3 3 #"abs" 0 0 23 3 2 #" (" 0 0 14 3 1 #"-" 0 0 23 3 1 #" " 0 0 14 3 3 #"fma" 0 0 23 3 1 #" " 0 0 14 3 3 #"fca" 0 0 23 3 3 #")) " 0 0 14 3 3 #"fma" 0 0 23 3 6 #"))))))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 2 #";(" 0 0 17 3 3 #"map" 0 0 17 3 12 #" fib-compare" 0 0 17 3 1 #" " 0 0 17 3 1 #"(" 0 0 17 3 4 #"list" 0 0 17 3 1 #" " 0 0 17 3 2 #"20" 0 0 17 3 1 #" " 0 0 17 3 2 #"30" 0 0 17 3 1 #" " 0 0 17 3 2 #"40" 0 0 17 3 1 #" " 0 0 17 3 31 #"50 60 70 75 100 500 1400 1500))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 4 #"test" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 18 #";-----------------" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 7 289 25 0 0 0 47 0 17 3 25 #"; First, a quick feature:" 0 0 23 29 1 #"\n" 0 0 17 3 43 #"; Scheme's \"quote\" suppresses evaluation --" 0 0 23 29 1 #"\n" 0 0 17 3 71 ( #"; \"just return this thing exactly, without looking up its meaning\"" #". [2]" ) 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 5 #"quote" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #"))" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 5 #"quote" 0 0 23 3 1 #" " 0 0 14 3 1 #"y" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 17 3 79 ( #"; Note that \"quote\" isn't a function -- it can't be, because expre" #"ssions passed" ) 0 0 23 29 1 #"\n" 0 0 17 3 64 #"; to a function get evaluated *before* the function even starts." 0 0 23 29 1 #"\n" 0 0 17 3 73 ( #"; We say that quote is a \"special form\". It's kinda a silly speci" #"al form" ) 0 0 23 29 1 #"\n" 0 0 17 3 49 #"; that does nothing (except suppress evaluation)." 0 0 23 29 1 #"\n" 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 0 17 3 55 #"; Btw, \"quote\" is often abbreviated as a tick-mark ('):" 0 0 23 29 1 #"\n" 0 0 20 3 1 #"'" 0 0 23 3 1 #"(" 0 0 14 3 1 #"+" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 20 3 1 #"'" 0 0 14 3 1 #"y" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 35 #"; Suppose we want to report errors." 0 0 23 29 1 #"\n" 0 0 17 3 45 #"; Why doesn't it work, as a regular function?" 0 0 23 29 1 #"\n" 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 7 457 25 0 0 0 75 0 23 3 1 #"(" 0 0 15 3 6 #"define" 0 0 23 3 3 #" (" 0 0 14 3 9 #"my-tester" 0 0 23 3 1 #" " 0 0 14 3 1 #"e" 0 0 23 3 1 #" " 0 0 14 3 1 #"r" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 1 #"=" 0 0 23 3 1 #" " 0 0 14 3 1 #"e" 0 0 23 3 1 #" " 0 0 14 3 1 #"r" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 14 3 6 #"printf" 0 0 23 3 1 #" " 0 0 19 3 14 #"\"Test passed.\"" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 14 3 6 #"printf" 0 0 23 3 1 #" " 0 0 19 3 33 #"\"Test failed: ~v = ~v, not ~v.~n\"" 0 0 23 3 2 #" (" 0 0 14 3 5 #"quote" 0 0 23 3 1 #" " 0 0 14 3 1 #"e" 0 0 23 3 2 #") " 0 0 14 3 1 #"e" 0 0 23 3 1 #" " 0 0 14 3 1 #"r" 0 0 23 3 3 #")))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 9 #"my-tester" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"5" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 9 #"my-tester" 0 0 23 3 2 #" (" 0 0 14 3 1 #"+" 0 0 23 3 1 #" " 0 0 20 3 1 #"2" 0 0 23 3 1 #" " 0 0 20 3 1 #"3" 0 0 23 3 2 #") " 0 0 20 3 1 #"4" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 9 #"my-tester" 0 0 23 3 2 #" (" 0 0 14 3 4 #"sqrt" 0 0 23 3 1 #" " 0 0 20 3 2 #"25" 0 0 23 3 2 #") " 0 0 20 3 1 #"4" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 0 17 3 57 #"; We want a *macro* -- that is, we want to have my-tester" 0 0 23 29 1 #"\n" 0 0 17 3 73 ( #"; be given raw, unevaluated syntax (like `(+ 2 3)`), and build new s" #"yntax" ) 0 0 23 29 1 #"\n" 0 0 17 3 63 #"; out of that (like `(if (= (+ 2 3) 5) ... (quote (+ 2 3)...) )" 0 0 23 29 1 #"\n" 0 0 17 3 48 #"; and then we'll run that newly-produced syntax." 0 0 23 29 1 #"\n" 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 0 17 3 67 #"; You can think of a macro as something which takes in a parse-tree" 0 0 23 29 1 #"\n" 0 0 17 3 31 #"; and returns a new parse tree." 0 0 23 29 1 #"\n" 0 0 17 3 56 #"; Go back and change 'define' with 'define-syntax-rule'." 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 38 #"; Other things macros can be used for:" 0 0 23 29 1 #"\n" 0 0 17 3 59 #"; - you want (in Java) to be able to say \"gettable int x;\"," 0 0 23 29 1 #"\n" 0 0 17 3 47 #"; and have the field and getter auto-created." 0 0 23 29 1 #"\n" 0 0 17 3 38 #"; - you want to have a 'swap' feature," 0 0 23 29 1 #"\n" 0 0 17 3 32 #"; or general call-by-reference" 0 0 23 29 1 #"\n" 0 0 17 3 63 #"; docs.racket-lang.org/guide/pattern-macros.html?q=syntax-rule" 0 0 23 29 1 #"\n" 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 0 17 3 68 #"; - you want to define your own little-language for non-programmers," 0 0 23 29 1 #"\n" 0 0 17 3 55 #"; and auto-transform your language into running code." 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 59 #"; [2] \"Quotation means suppressing the standard meaning\" is" 0 0 23 29 1 #"\n" 0 0 17 3 59 #"; actually what quoting can sometimes mean in English, too:" 0 0 23 29 1 #"\n" 0 0 17 3 13 #"; Consider" 0 0 23 29 1 #"\n" 0 0 17 3 37 #"; My favorite band is garbage." 0 0 23 29 1 #"\n" 0 0 17 3 39 #"; My favorite band is \"garbage\"." 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #"; In the quoted version, we suppress associating the name with it" #"s meaning." ) 0 0 23 29 1 #"\n" 0 0 17 3 15 #"; Similarly:" 0 0 23 29 1 #"\n" 0 0 17 3 76 ( #"; \"Love\" is a four-letter word. (An obvious, unimportant s" #"tatement.)" ) 0 0 23 29 1 #"\n" 0 0 17 3 13 #"; Love" 0 0 17 3 1 #" " 0 0 17 3 43 #"is a four-letter word. (A cynical view.)" 0 0 23 29 1 #"\n" 0 0 17 3 1 #";" 0 0 23 29 1 #"\n" 0 0 17 3 69 ( #"; This evolves to be: use quotes when introducing a technical term" #"," ) 0 0 23 29 1 #"\n" 0 0 17 3 66 #"; to stress that you're replacing/ignoring any previous meeting:" 0 0 23 29 1 #"\n" 0 0 17 3 75 ( #"; Between me and the stage was a pillar; I was in its sonic \"" #"shadow\"." ) 0 0 23 29 1 #"\n" 0 0 17 3 49 #"; This has further evolved to be sarcastically:" 0 0 23 29 1 #"\n" 0 0 17 3 87 ( #"; He calls that purse a backpack? Ha, I bet he keeps lipstick" #" in his \"backpack\"." ) 0 0 23 29 1 #"\n" 0 0 17 3 54 #"; Well, time for another \"productivity\" meeting." 0 0 23 29 1 #"\n" 0 0 17 3 72 ( #"; They are sarcastically recognizing how somebody is *trying* to u" #"se a" ) 0 0 23 29 1 #"\n" 0 0 17 3 78 ( #"; a term technically, in a way which is actually opposite its true" #" meaning. " ) 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 18 #";project-euler.net" 0 0 17 3 14 #", problem #25:" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 14 3 9 #"for/first" 0 0 23 3 3 #" {[" 0 0 14 3 1 #"i" 0 0 23 3 2 #" (" 0 0 14 3 11 #"in-naturals" 0 0 23 3 2 #")]" 0 0 23 29 1 #"\n" 0 0 23 3 12 #" " 0 0 22 3 6 #"#:when" 0 0 23 3 2 #" (" 0 0 14 3 2 #">=" 0 0 23 3 2 #" (" 0 0 14 3 13 #"string-length" 0 0 23 3 2 #" (" 0 0 14 3 14 #"number->string" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 14 3 1 #"i" 0 0 23 3 4 #"))) " 0 0 20 3 4 #"1000" 0 0 23 3 2 #")}" 0 0 23 29 1 #"\n" 0 0 23 3 2 #" " 0 0 14 3 1 #"i" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0 17 3 54 #"; the above for/first is equivalent to this named-let:" 0 0 23 29 1 #"\n" 0 0 23 3 1 #"(" 0 0 15 3 3 #"let" 0 0 23 3 1 #" " 0 0 14 3 4 #"loop" 0 0 23 3 3 #" {[" 0 0 14 3 1 #"i" 0 0 23 3 1 #" " 0 0 20 3 1 #"0" 0 0 23 3 2 #"]}" 0 0 23 29 1 #"\n" 0 0 23 3 3 #" (" 0 0 14 3 2 #"if" 0 0 23 3 2 #" (" 0 0 14 3 2 #">=" 0 0 23 3 2 #" (" 0 0 14 3 13 #"string-length" 0 0 23 3 2 #" (" 0 0 14 3 14 #"number->string" 0 0 23 3 2 #" (" 0 0 14 3 3 #"fib" 0 0 23 3 1 #" " 0 0 14 3 1 #"i" 0 0 23 3 4 #"))) " 0 0 20 3 4 #"1000" 0 0 23 3 1 #")" 0 0 23 29 1 #"\n" 0 0 23 3 6 #" " 0 0 14 3 1 #"i" 0 0 23 29 1 #"\n" 0 0 23 3 7 #" (" 0 0 14 3 4 #"loop" 0 0 23 3 2 #" (" 0 0 14 3 4 #"add1" 0 0 23 3 1 #" " 0 0 14 3 1 #"i" 0 0 23 3 4 #"))))" 0 0 23 29 1 #"\n" 0 0 23 29 1 #"\n" 0 0