| blob | 72042ee786b081addb8c261ddafdb73388e8d0c7 |
1 ;; TWENTY CHALLENGES FOR GREAT JUSTICE\r
2 ;; ===================================\r
3 \r
4 ;; by quad\r
5 \r
6 \r
7 \r
8 \r
9 ;; CHALLENGE 1\r
10 \r
11 ;; Define a macro THUNK which will wrap the body of the macro inside a lambda. That\r
12 ;; is, define\r
13 \r
14 ;; (THUNK\r
15 ;; <body>)\r
16 \r
17 ;; so that we get\r
18 \r
19 ;; (lambda () <body>)\r
20 \r
21 \r
22 ;; CHALLENGE 2\r
23 \r
24 ; Quadrescence:\r
25 ; First, tell me why this can't be a function.\r
26 ; Then implement it as a macro. --> A procedure called\r
27 ; SET-IF! such that (set-if! pred sym val) sets the value of SYM to VAL\r
28 ; only if PRED is true. Otherwise, it does nothing.\r
29 ; (or if you want, otherwise, it just gives back NIL)\r
30 \r
31 (define-syntax set-if!\r
32 (syntax-rules ()\r
33 ((_ pred sym val) (if pred\r
34 (set! sym val)))))\r
35 \r
36 (macroexpand '(set-if! #f a 5))\r
37 \r
38 (void)\r
39 \r
40 ;; CHALLENGE 3\r
41 \r
42 ; Quadrescence | qu1j0t3, EXERCISE: Write a version of LETREC which\r
43 ; allows one to use DEFINE syntax.\r
44 ; I think that syntax is more consistent with\r
45 ; general scheme syntax anyway. It's a little baroque\r
46 ; and definitely not "minimal" but neither is being able\r
47 ; to do (define (f x) ...)\r
48 ; when (define f (lambda (x) ...)) works fine\r
49 ; Example:\r
50 ; (define (example x)\r
51 ; (with-definitions\r
52 ; ((define (is-even? x) (zero? (remainder x 2)))\r
53 ; (define rofl "rolling on the floor laughing"))\r
54 ; (if (is-even? x)\r
55 ; (display rofl)\r
56 ; (display ":("))))\r
57 \r
58 (define-syntax with-definitions\r
59 (syntax-rules () ())\r
60 \r
61 (syntax->datum (syntax (foo bar baz)))\r
62 \r
63 \r
64 ;; CHALLENGE 4\r
65 \r
66 ; Qworkescence | Similar in spirit to the counting change problem,\r
67 ; write a function to compute the "partitions of an integer".\r
68 ; A partition of N is some sum of smaller numbers that add to N.\r
69 ; So the partitions of 4 are (4) (3 1) (2 2) (2 1 1) (1 1 1 1)\r
70 \r
71 \r
72 ;; CHALLENGE 5\r
73 \r
74 ; Quadrescence | CHALLENGE: replicate SML's reference type in scheme\r
75 ; | (define a (ref 9))\r
76 ; | (set-ref! a 8)\r
77 ; | (val a)\r
78 ; | ==> 8\r
79 ; | you can use "deref" instead of "val"\r
80 \r
81 \r
82 ;; CHALLENGE 6\r
83 \r
84 ; Quadrescence | CHALLENGE: write bogosort\r
85 \r
86 \r
87 ;; CHALLENGE 7\r
88 \r
89 ; Quadrescence | replicate the behavior of ye olde lisp's SETQ,\r
90 ; which is like SET! but allows several pairs of idents and vals\r
91 ; e.g., (setq x 1 y 2 z 3)\r
92 ; x is set to 1, y to 2, z to 3\r
93 \r
94 \r
95 ;; CHALLENGE 8\r
96 \r
97 ; @Quadrescence | CHALLENGE: Make a macro (define* (f args) body)\r
98 ; which defines f to be memoized: when you call f with\r
99 ; arguments x, it'll save the value of the result\r
100 ; so next time around, it just looks up the result.\r
101 ; Extra credit: Do it without polluting the namespace\r
102 ; (except w/ the function name of course)\r
103 \r
104 \r
105 ;; CHALLENGE 9\r
106 \r
107 ; In challenge #8, you wrote a memoizing\r
108 ; DEFINE macro called DEFINE*. However,\r
109 ; this can be awkward and even inefficient\r
110 ; when we have a COND or CASE. Consider:\r
111 \r
112 ; (define* (fib n)\r
113 ; (cond ((= n 0) 0)\r
114 ; ((= n 1) 1)\r
115 ; (else (+ (fib (- n 1))\r
116 ; (fib (- n 2))))))\r
117 \r
118 ; Each time we compute a yet-uncomputed\r
119 ; fibonacci, we have to check if it's 0\r
120 ; first, then 1, then we can procede to\r
121 ; compute.\r
122 \r
123 ; In this challenge, we want to be allowed\r
124 ; to define constant cases which add to\r
125 ; the hash table immediately. Let's call\r
126 ; this definition procedure DEF.\r
127 \r
128 ; Example:\r
129 \r
130 ; (def fib\r
131 ; (0) => 0\r
132 ; (1) => 1\r
133 ; (n) => (+ (fib (- n 1))\r
134 ; (fib (- n 2))))\r
135 \r
136 ; This will create a function FIB which will\r
137 ; have zero and one memoized, and allow for\r
138 ; the general case. When we do call the general\r
139 ; case for an unmemoized function, we no longer\r
140 ; have to crawl the COND, because there is none.\r
141 ; So we save comparisons each time it's called.\r
142 \r
143 ; For multi-argument functions, it would be illegal to have (4 b c) => ...\r
144 ; for example.\r
145 ; you can safely assume the last case will be the variable case\r
146 \r
147 \r
148 ;; CHALLENGE 10\r
149 \r
150 ; @Quadrescence | qu1j0t3: this one isn't tough, but it's an important\r
151 ; demonstration. Write a macro "with-degrees"\r
152 ; which causes all trig functions (sin cos tan) to use degrees\r
153 ; and not radians. Therefore if there is a\r
154 ; (sin x), it should be changed to (sin (* pi (/ 180) x)),\r
155 ; where pi=3.14159265358979\r
156 ; (with-degrees (+ (sin 30) (sin 90))) should give 1.5\r
157 \r
158 \r
159 ;; CHALLENGE 11\r
160 \r
161 ; Quadrescence | as an exercise, you should implement a C-style FOR loop:\r
162 ; (for ((<var> <init>) <condition> <post-loop-thing>) <body>)\r
163 ; without using DO\r
164 ; and <var>'s scope should be limited to FOR\r
165 ; example: (for ((i 0)\r
166 ; (< i 10)\r
167 ; (set! i (+ 1 i)))\r
168 ; (display i)\r
169 ; (newline))\r
170 ; which would print 0 thru 9\r
171 ; UNLIKE C, i's scope is limited\r
172 ; Quadrescence | Now extend FOR so you can do (for (<VAR> <LST>) ...)\r
173 ; and it will iterate over the list\r
174 ; (this is equivalent to CL's DOLIST macro)\r
175 \r
176 \r
177 ;; CHALLENGE 12\r
178 \r
179 // Quadrescence | write a program which takes a sentence (you can assume no punctuation)\r
180 // and mixes the middle letters of the words randomly, and writes it to stdout\r
181 // based on that classic thing where you can read text even if the middle letters\r
182 // are scrambled, but the first and last remain the same\r
183 \r
184 \r
185 ;; CHALLENGE 13\r
186 \r
187 ; Quad:\r
188 ; I think you should create the macro you suggested. In Common Lisp,\r
189 ; this macro is DESTRUCTURING-BIND. One way it works is like this (schemified):\r
190 ; (define *list* '(1 2 3))\r
191 ; (destructuring-bind (a b c) *list*\r
192 ; (+ a b c))\r
193 ; ===> 6\r
194 \r
195 \r
196 ;; CHALLENGE 14\r
197 \r
198 ; Qworkescence | But the last time I wrote an infix parser was for an\r
199 ; arithmetic expression parser which recognizes\r
200 ; associativity of operands and the natural solution is\r
201 ; from our friend Dijkstra and his beautifully simple\r
202 ; Shunting Yard algorithm\r
203 ; Qworkescence | Exercise: Read about & implement shunting yard\r
204 ; Qworkescence | (in Scheme)\r
205 \r
206 \r
207 ;; CHALLENGE 15\r
208 \r
209 ; Qworkescence | qu1j0t3, easy exercise: write the following functions\r
210 ; in Scheme equivalent to their Common Lisp counterparts:\r
211 ; (CONSTANTLY x) which returns a function which takes\r
212 ; any number of args but always returns x\r
213 \r
214 ; and (COMPLEMENT fn) which takes a boolean function fn\r
215 ; and returns the logical inverse (NOT) of it\r
216 \r
217 ; Qworkescence | CHALLENGE: If COMPLEMENT is the analog of the boolean\r
218 ; function NOT, then write two functions (CONJUNCTION f g)\r
219 ; which returns a function which takes an argument\r
220 ; and checks if both f and g are satisfied.\r
221 \r
222 ; And write (DISJUNCTION f g) which returns a function\r
223 ; which takes an argument and checks if either f or g are\r
224 ; satisfied\r
225 \r
226 ; (clearly CONJUNCTION is the analog of boolean AND,\r
227 ; and DISJUNCTION is the analog of boolean OR)\r
228 ; if you have CONJUNCTION, then you can do stuff like...\r
229 ; (define (divisible-by n)\r
230 ; (lambda (x) (zero? (remainder x n))))\r
231 ; (filter (conjunction (disjunction (divisible-by 3)\r
232 ; (divisible-by 5))\r
233 ; (complement (divisible-by 15)))\r
234 ; some-list)\r
235 ; filter those elements divisible by 3 or 5 and not 15\r
236 \r
237 \r
238 ;; CHALLENGE 16\r
239 \r
240 ; Quadrescence | write (transpose matrix) which transposes.\r
241 ; Quadrescence | If you don't know what transposition is,\r
242 ; every row becomes a column, vice versa\r
243 \r
244 \r
245 ;; CHALLENGE 17\r
246 \r
247 ; qu1j0t3 | Quadrescence: (diagonal? might be a nice scheme challenge..\r
248 ;Quadrescence | first make a function called "square-matrix?" to see\r
249 ; if it's even a matrix\r
250 ; then write diagonal? to determine if the matrix is a diagonal\r
251 ; matrix\r
252 \r
253 \r
254 ;; CHALLENGE 18\r
255 \r
256 ;15:41:53 Quadrescence | FurnaceBoy: Oh, another "small" Scheme challenge:\r
257 ; Given a list of functions L = (f1 f2 ... fn) and a value x, write a\r
258 ; function (appList F x) := ((f1 x) (f2 x) ... (fn x)) ¦\r
259 ; e.g., if L = (sin cos tan), then (appList L 3.14) gives\r
260 ; (0.00159265291648683 -0.99999873172754 -0.00159265493640722)\r
261 \r
262 \r
263 ;; CHALLENGE 19\r
264 \r
265 Furthermore, make (appList* L) return a function such that ((appList* L) x) is\r
266 equivalent to appList in Challenge 18\r
267 \r
268 \r
269 ;; CHALLENGE 20\r
270 \r
271 Write a macro LOCALS which acts sort of like LET, but allows uninitialized values\r
272 (you may initialize them to #f). For example\r
273 \r
274 (locals (a b (c 1) d)\r
275 (set! a 5)\r
276 (+ a c))\r
277 \r
278 returns\r
279 \r
280 6\r
281 \r
282 \r
283 ;; CHALLENGE 21\r
284 \r
285 Write define-curried which defines a curried function. That is,\r
286 (define-curried-function (clog b x) (/ (log x) (log b))), which sets clog to\r
287 (lambda (b)\r
288 (lambda (x)\r
289 (log b x)))\r
290 \r
291 \r
292 ;; CHALLENGE 22\r
293 \r
294 Write (@ f x y z ...) which applies f to x, then the result to y, etc. For\r
295 example, (@ clog 2 5) ==> ((clog 2) 5)\r
296 \r
297 \r
298 ;; CHALLENGE 23\r
299 \r
300 The tangent of a number tan(x) is defined as sin(x)/cos(x). We can\r
301 compute tangent by using the definition, or we can make use of the\r
302 so called "addition formula". The addition formula for tangent is\r
303 \r
304 tan(a) + tan(b)\r
305 tan(a + b) = ----------------- .\r
306 1 - tan(a)*tan(b)\r
307 \r
308 If we wish to compute tan(x), then we can compute tan(x/2 + x/2):\r
309 \r
310 x x tan(x/2) + tan(x/2) 2*tan(x/2)\r
311 tan(- + -) = --------------------- = ---------------- .\r
312 2 2 1 - tan(x/2)*tan(x/2) 1 - (tan(x/2))^2\r
313 \r
314 We also know something about tangent when the argument is small:\r
315 \r
316 tan(x) ~= x when x is very close to 0.\r
317 \r
318 The exercise has two parts:\r
319 \r
320 (1) Write a recursive function TANGENT using the methods above\r
321 to compute the tangent of a number. It is not necessary to\r
322 handle undefined cases (odd multiples of pi/2).\r
323 \r
324 (2) Write an iterative version TANGENT-ITER of (1) which avoids\r
325 tree recursion (uses named-LET or tail-recursive procedures).\r
326 \r
327 \r
328 TEST CASES: Your values need not match these precisely (due to\r
329 floating point error and implementation specifics).\r
330 \r
331 > (tangent-iter 0)\r
332 0\r
333 > (tangent-iter 1.0)\r
334 1.5574066357129577\r
335 > (tangent-iter 2.0)\r
336 -2.1850435345286616\r
337 > (tangent-iter (/ 3.14159 4))\r
338 0.9999983651876447\r