/
scheme.html
1072 lines (865 loc) · 39.9 KB
/
scheme.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html>
<head>
<link href="css/assignments.css" rel="stylesheet" type="text/css">
<title>../../Proj/Scheme</title>
</head>
<body>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Project 04: Scheme</title>
</head>
<body>
<h2>Project 4: A Scheme Interpreter</h2>
<blockquote>
<center>
<img src="money_tree.png" />
</center>
<center>
<cite>Eval calls apply,<br />
which just calls eval again!<br />
When does it all end?</cite>
</center>
</blockquote>
<h3>Introduction</h3>
<p>In this project, you will develop an interpreter for a subset of the
Scheme language. As you proceed, think about the issues that arise in the
design of a programming language; many quirks of languages are the byproduct
of implementation decisions in interpreters and compilers. </p>
<p>You will also implement some small programs in Scheme, including the
<code>count_change</code> function that we studied in lecture. Scheme is a simple but
powerful functional language. You should find that much of what you have learned about
Python transfers cleanly to Scheme as well as to other programming languages. To learn
more about Scheme, you can read the original <a href=
"http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_start">Structure
and Interpretation of Computer Programs</a> online for free. Examples from
chapters 1 and 2 are included as test cases for this project. Language
features from Chapters 3, 4, and 5 are not part of this project, but of
course you are welcome to extend your interpreter to implement more of the
language. Since we only include a subset of the language, your interpreter
will not match exactly the behavior of other interpreters such as STk.</p>
<p>The project concludes with an open-ended graphics contest that challenges you to
produce recursive images in only a few lines of Scheme. As an example of what you might
create, the picture above abstractly depicts all the ways of making change for $0.50
using U.S. currency. All flowers appear at the end of a branch with length 50. Small
angles in a branch indicate an additional coin, while large angles indicate a new
currency denomination. In the contest, you too will have the chance to unleash your
inner recursive artist.</p>
<p>This project includes several files, but all of your changes will be made to the
first three: <code><a href="scheme.py.html">scheme.py</a></code>, <code><a href="scheme_reader.py.html">scheme_reader.py</a></code>, and
<code><a href="tests.scm">tests.scm</a></code>. You can download all of the
project code as a <a href="scheme.zip">zip archive</a>.</p>
<table cellpadding="10">
<tr>
<td><code><a href="scheme.py.html">scheme.py</a></code></td>
<td>The Scheme evaluator</td>
</tr>
<tr>
<td><code><a href="scheme_reader.py.html">scheme_reader.py</a></code></td>
<td>The Scheme parser</td>
</tr>
<tr>
<td><code><a href="tests.scm">tests.scm</a></code></td>
<td>A collection of test cases written in Scheme that are designed
to test your Scheme interpreter. You will implement some Scheme
procedures yourself. </td>
</tr>
<tr>
<td><code><a href="scheme_tokens.py.html">scheme_tokens.py</a></code></td>
<td>A tokenizer for scheme</td>
</tr>
<tr>
<td><code><a href="scheme_primitives.py.html">scheme_primitives.py</a></code></td>
<td>Primitive Scheme procedures</td>
</tr>
<tr>
<td><code><a href="scheme_test.py.html">scheme_test.py</a></code></td>
<td>A testing framework for Scheme</td>
</tr>
<tr>
<td><code><a href="ucb.py.html">ucb.py</a></code></td>
<td>Utility functions for 61A</td>
</tr>
</table>
<h3>Logistics</h3>
<p>This is a two-part project. As in the previous project, you'll work in a
team of two people, person A and person B. All questions are labeled
sequentially, but some are designated for certain people by a prefix of their
letter (A or B). Both partners should understand the solutions to all
questions.</p>
<p>In the first part, you will develop the interpreter in stages:</p>
<ul>
<li>Reading Scheme expressions</li>
<li>Primitive procedure calls</li>
<li>Symbol evaluation and definition</li>
<li>Lambda expressions and procedure definition</li>
<li>Calling user-defined procedures</li>
<li>Evaluation of various special forms</li>
</ul>
<p>In the second part, you will implement Scheme procedures that are similar
to some exercises that you previously completed in Python.</p>
<p>There are 27 possible correctness points and 3 composition points. The
composition score in this project will evaluate the clarity of your code
<i>and</i> your ability to write tests that verify the behavior of your
interpreter. </p>
<h3>The Scheme Language</h3>
<p>Before you begin working on the project, review what you have learned in lecture
about the Scheme language in <a href=
"http://inst.eecs.berkeley.edu/~cs61a-tz/book/chapters/interpretation.html#functional-programming">Chapter
3.5</a> of the course lecture notes.
<p><b>Read-Eval-Print.</b> Run interactively, the interpreter reads Scheme
expressions, evaluates them, and prints the results. The interpreter uses
<code>scm></code> as the prompt.</p>
<pre>
scm> 2
2
scm> (((lambda (f) (lambda (x) (f f x)))
(lambda (f k) (if (zero? k) 1 (* k (f f (- k 1)))))) 5)
120
</pre>
<p>The starter code for your Scheme interpreter in <code><a href="scheme.py.html">scheme.py</a></code>
can successfully evaluate the first expression above, since it consists of a
single literal numeral. The second (a computation of 5 factorial) will not
work just yet.</p>
<p><b>Load.</b> Our <code>load</code> function differs from standard Scheme
in that we use a symbol for the file name. For example,</p>
<pre>
scm> (load 'tests)
</pre>
<p><b>Symbols.</b> Unlike some implementations of Scheme, in this project
numbers and boolean values cannot be used as symbols. Symbols may not be
capitalized.
<p><b>Turtle Graphics.</b> In addition to standard Scheme procedures, we
include procedure calls to the Python <code>turtle</code> package. Read its
<a href=
"http://docs.python.org/py3k/library/turtle.html">documentation</a>.</p>
<p><u>Note</u>: The <code>turtle</code> Python module may not
be installed by default on your personal computer. However, the
<code>turtle</code> module is installed on the instructional machines.
So, if you wish to create turtle graphics for this project (i.e. for
the contest), then you'll either need to setup <code>turtle</code> on
your personal computer, or test on your class account. </p>
<h3>Testing</h3>
<p>The tests for this project are largely taken from the Scheme
textbook that 61A used for many years. Examples from relevant
chapters (and a few more examples to test various corner cases)
appear in <code><a href="tests.scm">tests.scm</a></code>.</p>
<p>You can also compare the output of your interpreter to the expected output
by running <code><a href="scheme_test.py.html">scheme_test.py</a></code>.</p>
<pre>
python3 scheme_test.py
</pre>
<p>The <code><a href="tests.scm">tests.scm</a></code> file contains Scheme
expressions interspersed with comments in the form:
<pre>
(+ 1 2)
; expect 3
(/ 1 0)
; expect Error
</pre>
<p> Above, <code><a href="scheme_test.py.html">scheme_test.py</a></code> will evaluate <code>(+ 1 2)</code>
using your code in <code><a href="scheme.py.html">scheme.py</a></code>, then output a test failure
if <code>3</code> is not returned. The second example tests for an error
(but not the specific error message). The <code>scheme_test</code> script
collects these expected outputs and compares them with the actual output from
the program, counting and reporting mismatches.
<p>Only a small subset of tests are designated to run by default because
<code>tests.scm</code> contains an <code>(exit)</code> call near the
beginning, which halts testing. As you complete more of the project, you
should move or remove this call. <i>Note that your interpreter doesn't know
how to exit until Problems 3 and 4 are completed.</i>
<p><b>Important</b>: As you proceed in the project, add new tests to the top
of <code>tests.scm</code> to verify the behavior of your implementation.
<p>Finally, as always, you can run the doctests for the project using:
<pre>
python3 -m doctest scheme.py scheme_reader.py
</pre>
<p>Don't forget to use the <code>trace</code> decorator from the
<code>ucb</code> module to follow the path of execution in your
interpreter.</p>
<p>As you develop your Scheme interpreter, you may find that Python raises
various uncaught exceptions when evaluating Scheme expressions. As a result,
your Scheme interpreter will crash. Some of these may be the results of bugs
in your program, and some may be useful indications of errors in user
programs. The former should be fixed (of course!) and the latter should be
caught and changed into <code>SchemeError</code> exceptions, which are caught
and printed as error messages by the Scheme read-eval-print loop we've
written for you. Python exceptions that "leak out" to the user in raw form
are errors in your interpreter (tracebacks are for implementors, not
civilians).</p>
<h3>Running Your Scheme Interpreter</h3>
<p> To run your Scheme interpreter in an interactive mode, type:
<pre>
python3 scheme.py
</pre>
Alternately, you can tell your Scheme interpreter to evaluate the
lines of an input file by passing the file name as an argument to
<code><a href="scheme.py.html">scheme.py</a></code>:
<pre>
python3 scheme.py tests.scm
</pre>
Currently, your Scheme interpreter can handle a few simple expressions, such
as:
<pre>
scm> 1
1
scm> 42
42
scm> #t
True
</pre>
To exit the Scheme interpreter, issue either <code>Ctrl-c</code> or
<code>Ctrl-d</code> or evaluate the <code>exit</code> procedure:
<pre>
scm> (exit)
</pre>
<h3>The Reader</h3>
<p>The function <code>scheme_read</code> in <code><a href="scheme_reader.py.html">scheme_reader.py</a></code>
parses a <code>Buffer</code> (<code><a href="buffer.py.html">buffer.py</a></code>) instance that returns
valid Scheme tokens on invocations of <code>current</code> and
<code>pop</code> methods. It returns the next full Scheme expression in the
<code>src</code> buffer, using an internal representation as follows:
<table border="1" align="center">
<tr>
<th> Scheme Data Type</th>
<th> Our Internal Representation </th>
</tr>
<tr>
<td> Numbers </td>
<td> Python's built-in <code>int</code> and <code>float</code> data types.
</td>
</tr>
<tr>
<td> Symbols </td>
<td> Python's built-in <code>string</code> data type. </td>
</tr>
<tr>
<td> Booleans (<code>#t</code>, <code>#f</code>)</td>
<td> Python's built-in <code>True</code>, <code>False</code>
values. </td>
</tr>
<tr>
<td> Pairs </td>
<td> The <code>Pair</code> class, defined in the
<code><a href="scheme_reader.py.html">scheme_reader.py</a></code> file. </td>
</tr>
<tr>
<td> nil </td>
<td> The <code>nil</code> object, defined in the
<code><a href="scheme_reader.py.html">scheme_reader.py</a></code> file. </td>
</tr>
</table>
<p><b>Problem 1</b> (1 pt). Complete the <code>scheme_read</code> function in
<code><a href="scheme_reader.py.html">scheme_reader.py</a></code> by adding support for quotation.
<ul>
<li> If the next token in <code>src</code> is the string
<code>"nil"</code>, return the <code>nil</code> object. (provided)
<li> If the next token is not a delimiter, then it is an atom. Return it.
(provided)
<li> If the current token refers to the beginning of a <b>quote</b> (such
as <code>'bagel</code>), then treat the quoted symbol as the special form
<code>(quote bagel)</code>.
<li> If the current token is a left parenthesis <code>"("</code>, return
the result of <code>read_tail</code>. (provided)
</ul>
<p><b>Problem 2</b> (2 pt). Complete the <code>read_tail</code> function in
<code><a href="scheme_reader.py.html">scheme_reader.py</a></code> by adding support for dotted lists. A dotted
list in Scheme is not necessarily a well-formed list, but instead has an
arbitrary <code>second</code> attribute that may be any Scheme value.
<p>The <code>read_tail</code> function expects to read the rest of a list or
dotted list, assuming the open parenthesis has already been popped by
<code>scheme_read</code>.
<p>Consider the case of calling <code>scheme_read</code> on input "<code>(1 2
. 3)</code>". The <code>read_tail</code> function will be called on the
suffix "<code>1 2 . 3)</code>", which is</p>
<ul>
<li>the pair consisting of the Scheme value <code>1</code> and the value of the tail
"<code>2 . 3)</code>", which is
<ul>
<li>the pair consisting of the Scheme value <code>2</code> and the Scheme value
<code>3</code>.</li>
</ul>
</li>
</ul>
Thus, <code>read_tail</code> would return <code>Pair(1, Pair(2, 3))</code>.
<p><i>Hint:</i> In order to verify that only one element follows a dot, after
encountering a <code>'.'</code>, read one additional expression and then
check to see that a closing parenthesis follows.
<p>To verify that your solutions to Problem 1 and 2 work correctly, run the
doctests for <code><a href="scheme_reader.py.html">scheme_reader.py</a></code> and test your parser interactively
by running,
<pre>
# python3 scheme_reader.py
read> 42
42
read> '(1 2 3)
(quote (1 2 3))
read> nil
()
read> '()
(quote ())
read> (1 (2 3) (4 (5)))
(1 (2 3) (4 (5)))
read> (1 (9 8) . 7)
(1 (9 8) . 7)
read> (hi there . (cs . (student)))
(hi there cs student)
</pre>
<h3>The Evaluator</h3>
<p><b>All further changes to the interpreter will be made in
<code><a href="scheme.py.html">scheme.py</a></code>. For each question, add a few tests to the top of
<code>tests.scm</code> to verify the behavior of your implementation.</b>
<p><a
href="http://inst.eecs.berkeley.edu/~cs61a-tz/book/chapters/interpretation.html#interpreters-for-languages-with-abstraction">Chapter
3.7</a> of the course lecture notes describes the structure of the Scheme
evaluator. In the implementation given to you, the <code>scheme_eval</code>
function is complete, but few of the functions or methods it uses are
implemented. In fact, the evaluator can only evaluate self-evaluating
expressions: numbers, booleans, and <code>nil</code>.
<p><b>Problem 3</b> (2 pt). Implement <code>apply_primitive</code>, which is
called by <code>scheme_apply</code> for <code>PrimitiveProcedures</code>.
Primitive procedures are applied by calling a corresponding Python function
that implements the procedure.
<p> Scheme primitive procedures are represented as instances of the
<code>PrimitiveProcedure</code> class, defined in
<code><a href="scheme_primitives.py.html">scheme_primitives.py</a></code>. A <code>PrimitiveProcedure</code> has two
instance attributes:
<ul>
<li> <code>self.fn</code> is the <emph>Python</emph> function that
implements the primitive Scheme procedure.
<li> <code>self.use_env</code> is a boolean flag that indicates whether or
not this primitive procedure will expect the current environment to be
passed in as the last argument. The environment is required, for instance,
to implement the primitive <code>eval</code> procedure.</li>
</ul>
<p>To see a list of all Scheme primitive procedures used in the project, look
in the <code><a href="scheme_primitives.py.html">scheme_primitives.py</a></code> file. Any function decorated with
<code>@primitive</code> will be added to the globally-defined
<code>_PRIMITIVES</code> list. </p>
<p>The <code>apply_primitive</code> function takes a
<code>PrimitiveProcedure</code> instance, a Scheme list of argument values,
and the current environment. Your implementation should:
<ul>
<li> Convert the Scheme list to a Python list of arguments.
<li> If the <code>procedure.use_env</code> is <code>True</code>, then
add the current environment <code>env</code> as the last argument.
<li> Call <code>procedure.fn</code> on those arguments (<i>hint</i>: use *
notation).
<li> If calling the function results in a <code>TypeError</code> exception
being thrown, then raise a <code>SchemeError</code> instead.</li>
</ul>
<p>The doctest for <code>apply_primitive</code> should now pass. However,
your Scheme interpreter will still not be able to apply primitive
procedures, because your Scheme interpreter still doesn't know
how to look up the values for the primitive procedure symbols (such as
<code>+</code>, <code>*</code>, and <code>car</code>).
<p><b>Problem 4</b> (2 pt) Implement the <code>lookup</code> method of the
<code>Frame</code> class. It takes a symbol (Python string) and returns the
value bound to that name in the first frame of the environment in which it is
found. A <code>Frame</code> represents an environment via two instance
attributes:
<ul>
<li> <code>self.bindings</code> is a dictionary that maps Scheme symbols
(represented as Python strings) to Scheme values.
<li> <code>self.parent</code> is the parent <code>Frame</code>
instance. The parent of the Global Frame is <code>None</code>.
</ul>
Your <code>lookup</code> implementation should,
<ul>
<li> Return the value of a symbol in <code>self.bindings</code> if it exists.
<li> Otherwise, <code>lookup</code> that symbol in the parent if it exists.
<li> Otherwise, raise a <code>SchemeError</code>.
</ul>
<p>After you complete this problem, you should be able to evaluate primitive
procedure calls, giving you the functionality of the Calculator language and
more.</p>
<pre>
scm> +
#[primitive]
scm> (+ 1 2)
3
scm> (* 3 4 (- 5 2) 1)
36
scm> (odd? 31)
True
</pre>
<p><b>Problem A5</b> (1 pt). There are two missing parts in the method
<code>do_define_form</code>, which handles the <code>(define ...)</code>
special forms. Implement just the first part, which binds names to values
but does not create new procedures. <code>do_define_form</code> should return
the name after performing the binding.</p>
<pre>
scm> (define tau (* 2 3.1415926))
tau
</pre>
<p>You should now be able to give names to values and evaluate symbols to
those values.
<pre>
scm> (define x 15)
x
scm> (define y (* 2 x))
y
scm> y
30
scm> (+ y (* y 2) 1)
91
scm> (define x 20)
x
scm> x
20
</pre>
<p><b>Problem B6</b> (1 pt). Implement the <code>do_quote_form</code>
function, which evaluates the <code>quote</code> special form. Once you have
done so, you can evaluate quoted expressions.</p>
<pre>
scm> 'hello
hello
scm> '(1 . 2)
(1 . 2)
scm> '(1 (2 three . (4 . 5)))
(1 (2 three 4 . 5))
scm> (car '(a b))
a
scm> (eval (cons 'car '('(1 2))))
1
</pre>
<p> At this point in the project, your Scheme interpreter should be
be able to support the following features:
<ul>
<li> Evaluate atoms, which include numbers, booleans, nil, and symbols,</li>
<li> Evaluate the <code>quote</code> special form,</li>
<li> Evaluate lists,</li>
<li> Define symbols, and</li>
<li> Call primitive procedures, such as <code>(+ (- 4 2) 5)</code> </li>
</ul>
<h3> User-Defined Procedures </h3>
<p>In our interpreter, user-defined procedures will
be represented as instances of the <code>LambdaProcedure</code> class,
defined in <code><a href="scheme.py.html">scheme.py</a></code>. A <code>LambdaProcedure</code>
instance has three instance attributes:
<ul>
<li> <code>self.formals</code> is a Scheme list of the formal
parameters (symbols) that name the arguments of the procedure.
<li> <code>self.body</code> is a single Scheme expression; the body of the
procedure.
<li> <code>self.env</code> is the environment in which the procedure was
defined. </li>
</ul>
<p><b>Problem 7</b> (2 pt). Implement the <code>begin</code> special form,
which has a list of one or more sub-expressions that are each evaluated in
order. The value of the final sub-expression is the value of the
<code>begin</code> expression.
<pre>
scm> (begin (+ 2 3) (+ 5 6))
11
scm> (begin (display 3) (newline) (+ 2 3))
3
5
</pre>
<p> <u>Note</u>: When <code>scheme_eval</code> evaluates one of
the conditional constructs (<code>if</code>, <code>and</code>,
<code>or</code>, <code>cond</code>, <code>begin</code>,
<code>case</code>), notice that it calls <code>scheme_eval</code>
on the <b>return value</b> of the relevant <code>do_FORM</code>
procedures (<code>do_begin_form</code>, <code>do_cond_form</code>, etc.).
Take care that your Scheme interpreter doesn't inadvertantly call
<code>scheme_eval</code> on the same value twice, or else you might
get the following invalid behavior:
<pre>
scm> (begin 30 'hello)
Error: unknown identifier: hello
</pre>
<p><b>Problem 8</b> (2 pt). Implement the <code>do_lambda_form</code> method,
which creates <code>LambdaProcedure</code> values by evaluating
<code>lambda</code> expressions. While you cannot call a user-defined
procedure yet, you can verify that you have read the procedure correctly by
evaluating a lambda expression.
<pre>
scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))
</pre>
In Scheme, it is legal to have function bodies with more than one expression:
<pre>
STk> ((lambda (y) 42 (* y 2)) 5)
10
</pre>
In order to implement this feature, your
<code>do_lambda_form</code> should detect when the body of a lambda
expression contains multiple expressions. If so, then
<code>do_lambda_form</code> should place the expressions
inside of a <code>(begin ...)</code> expression, and use that
<code>begin</code> expression as the body:
<pre>
scm> (lambda (y) 42 (* y 2))
(lambda (y) (begin 42 (* y 2)))
</pre>
<p><b>Problem A9</b> (1 pt). Currently, your Scheme interpreter is
able to define user-defined procedures in the following manner:
<pre>
scm> (define f (lambda (x) (* x 2)))
f
</pre>
However, we'd like to be able to use the shorthand form of defining
procedures:
<pre>
scm> (define (f x) (* x 2))
f
</pre>
<p>Modify the <code>do_define_form</code> function so that it correctly
handles the shorthand procedure definition form above. Make sure that it can
handle multi-expression bodies. <i>Hint</i>: construct a <code>lambda</code>
expression and evaluate it with <code>do_lambda_form</code>.
<p>Once you have completed this problem, you should find that defined
procedures evaluate to lambda procedures.
<pre>
scm> (define (square x) (* x x))
square
scm> square
(lambda (x) (* x x))
</pre>
<p><b>Problem 10</b> (2 pt). Implement the <code>make_call_frame</code> method of
the <code>Frame</code> class. It should do 2 things:
<ul>
<li> Creating a new Frame, the parent of which is <code>self</code> (done for you). </li>
<li> Binding formal parameters to their associated argument values. </li>
</ul>
<p>
Make sure the number of arguments <code>make_call_frame</code> recieves is the same as the number of formal parameters it recieves.
</p>
<!--
<p>Don't forget the cases where the formal parameter list contains a trailing "varargs"
entry, as in:
<pre>
(define (format port form . args) ...)
</pre>
Which means that every (in this example) every argument passed to format after form
will be stuffed into a scheme list which the symbol <code>args</code> is bound to.
One unifying way to handle this case along with the simple lists-of-symbols is to
consider the formals list as a kind of <i>pattern</i> that is matched against the list
of argument values. That is, the formals list <i>matches</i> the argument list if you
treat each symbol in the formals list as a <i>pattern variable</i> or <i>wildcard</i>
that matches any expression. Thus, the list of values <code>(1 2 3)</code> has the
internal structure
<pre>
Pair(<i>number</i>, Pair(<i>number</i>, Pair(<i>number</i>, NULL)))
</pre>
while the formals list <code>(a . b)</code> has the structure
<pre>
Pair(<i>symbol a</i>, <i>symbol b</i>)
</pre>
These have the same form if we match symbol <code>a</code> to the number 1 and
symbol <code>b</code> to <code>Pair(<i>number</i>, Pair(<i>number</i>, NULL))</code>
Likewise, the ordinary formals list <code>(a b c)</code> has the structure
<pre>
Pair(<i>symbol a</i>, Pair(<i>symbol b</i>, Pair(<i>symbol c</i>, NULL)))
</pre>
so it matches the argument list, too.
-->
<p><b>Problem B11</b> (1 pt). Implement the <code>check_formals</code>
function to raise an error whenever the Scheme list of formal parameters
passed to it is invalid. Raise a <code>SchemeError</code> if the list of
<code>formals</code> is not a well-formed list of symbols or if any symbol is
repeated. (Hint: Look inside of <code><a href="scheme_primitives.py.html">scheme_primitives.py</a></code> for a function that tells you something is a scheme symbol. )
</p>
<!--
<p>
In particular, make sure that it supports the following argument
syntax:
<pre>
scm> (lambda (x y z) (+ x y z))
scm> (lambda (x . nums) (* x (reduce + nums)))
scm> (lambda nums (reduce * nums))
</pre>
Make sure that your interpreter rejects the following. Where
your interpeter rejects the following is not important (i.e. in
<tt>scheme_read</tt> or <tt>check_formals</tt>),
as long as you are correctly raising some <tt>SchemeError</tt>. It is
an error for your interpreter to raise a Python exception.
<pre>
scm> (lambda (x (y) z) (* x y z))
scm> (define (fn x 2) (+ x 2))
</pre>
</p>
-->
<p><b>Problem 12</b> (2 pt). Implement <code>scheme_apply</code> to correctly
apply user-defined <code>LambdaProcedure</code> instances. (The case of
<code>MuProcedures</code> is handled later in the project). It should:
<ul>
<li> Create a new <code>Frame</code>, with all formal parameters
bound to their argument values.
<li> Evaluate the body of <code>procedure</code> in the environment
represented by this new frame.
<li> Return the value of calling <code>procedure</code>.
</ul>
<p>After you complete <code>scheme_apply</code>, user-defined functions (and
lambda functions) should work in your Scheme interpreter. Now is an
excellent time to revisit the tests in <code>tests.scm</code> and ensure that
you pass the ones that involve definition (Sections 1.1.2 and 1.1.4). You
should also add additional tests of your own to verify that your interpreter
is behaving as you expect.
<h3>Special Forms</h3>
<p>The basic Scheme logical special forms are <code>if</code>,
<code>and</code>, <code>or</code>, and <code>cond</code>. These expressions
are special because not all of their sub-expressions may be evaluated.
<p>In Scheme, only <code>#f</code> (also known as <code>false</code> or
<code>False</code>) is a false value. All other values are true values. You
can test whether a value is a true value or a false value using the provided
Python functions <code>scheme_true</code> and <code>scheme_false</code>,
defined in <code><a href="scheme_primitives.py.html">scheme_primitives.py</a></code>.
<p><b>Problem A13</b> (1 pt). Implement <code>do_if_form</code> so that
<code>if</code> expressions are evaluated correctly. This function should
return either the second (consequent) or third (alternative) expression of
the <code>if</code> expression, depending on the value of the first
(predicate) expression.
<pre>
scm> (if (= 4 2) true false)
False
scm> (if (= 4 4) (* 1 2) (+ 3 4))
2
</pre>
<p>It is legal to pass in just two expressions to the <code>if</code> special
form. In this case, you should return the second expression if the first
expression evaluates to a true value. Otherwise, return the special
<code>okay</code> value, which represents an undefined value.
<pre>
scm> (if (= 4 2) true)
okay
</pre>
<p><b>Problem B14</b> (2 pt). Implement <code>do_and_form</code> and
<code>do_or_form</code> so that <code>and</code> and <code>or</code>
expressions are evaluated correctly.
<p>The logical forms <code>and</code> and <code>or</code> are <i>short-
circuiting</i>. For <code>and</code>, your interpreter should evaluate each
sub-expression from left to right, and if any of these evaluates to
<code>False</code>, then <code>False</code> is returned. If all but the last
sub-expressions evaluate to true values, return the last sub-expression from
<code>do_and_form</code>.</p>
<p>For <code>or</code>, evaluate each sub-expression from left to right. If any
evaluates to a true value, then <code>quote</code> that value and return it.
These return values must be quoted because they are evaluated in
<code>scheme_eval</code>. If all but the last sub-expression evaluate to
false, return the last sub-expression from <code>do_or_form</code> without
quoting it.</p>
<pre>
scm> (and)
True
scm> (or)
False
scm> (and 4 5 6)
6 ; all operands are true values
scm> (or 5 2 1)
5 ; 5 is a true value
scm> (and #t #f 42 (/ 1 0))
False ; short-circuiting behavior of and
scm> (or 4 #t (/ 1 0))
4 ; short-circuiting behavior of or
</pre>
<p><b>Problem A15</b> (1 pt). Implement <code>do_cond_form</code> so that it
returns the first result sub-expression corresponding to a true predicate (or
else). Your implementation should match the following examples and the
additional tests in <code>tests.scm</code>.
<pre>
scm> (cond ((= 4 3) 'nope)
((= 4 4) 'hi)
(else 'wait))
hi
scm> (cond ((= 4 3) 'wat)
((= 4 4))
(else 'hm))
True
scm> (cond ((= 4 4) 'here 42)
(else 'wat 0))
42
</pre>
For the last example, where the body of a <code>cond</code> has multiple
expressions, you might find it helpful to replace <code>cond</code>-bodies
with multiple expression bodies into a single <code>begin</code> expression,
i.e., the following two expressions are equivalent.
<pre>
(cond ((= 4 4) 'here 42))
(cond ((= 4 4) (begin 'here 42)))
</pre>
<p>The value of a <code>cond</code> is undefined if there are no true
predicates and no <code>else</code>. In such a case, <code>do_cond_form</code>
should return <code>okay</code>.</p>
<p><b>Problem A16</b> (2 pt). The <code>let</code> special form introduces local
variables, giving them their initial values. For example,</p>
<pre>
scm> (define x 'hi)
x
scm> (define y 'bye)
y
scm> (let ((x 42)
(y (* 5 10)))
(list x y))
(42 50)
scm> (list x y)
(hi bye)
</pre>
Implement
the <code>do_let_form</code> method to have this effect and test it, by
adding test cases to <code>tests.scm</code>. Make sure your <code>let</code>
correctly handles multi-expression bodies:
<pre>
scm> (let ((x 42)) x 1 2)
2
</pre>
<p> The let special form is equivalent to creating and then calling a lambda
procedure. That is, the following two expressions are equivalent:
<pre>
(let ((x 42) (y 16)) (+ x y))
((lambda (x y) (+ x y)) 42 16)
</pre>
Thus, a <code>let</code> form implicitly creates a new
<code>Frame</code> (containing the <code>let</code> bindings)
which extends the current environment and evaluates the body of the
<code>let</code> with respect to this new <code>Frame</code>. This is
very much exactly like a user-defined function call. Note that, in your
project code, you don't have to actually create a
<code>LambdaProcedure</code> and call it. Instead, you can
create a new <code>Frame</code>, add the necessary bindings, and
evaluate the expressions of the <code>let</code> body with respect to
the new <code>Frame</code>.</p>
<p>The bindings created by a <code>let</code> are not able to refer back to
previously-declared bindings from the same <code>let</code>.
<p><b>Problem B17</b> (2 pt). Implement <code>do_mu_form</code> to evaluate
the <code>mu</code> special form, a non-standard Scheme expression type. A
<code>mu</code> expression is similar to a <code>lambda</code> expression,
but evaluates to a <code>MuProcedure</code> instance that is dynamically
scoped. The <code>MuProcedure</code> class has been provided for you.
<p>Additionally, complete <code>scheme_apply</code> to call
<code>MuProcedure</code> procedures using dynamic scoping. Calling a
<code>LambdaProcedure</code> uses lexical scoping: the parent of the new call
frame is the environment in which the procedure was defined. Calling a
<code>MuProcedure</code> created by a <code>mu</code> expression uses dynamic
scoping: the parent of the new call frame is the environment in which the
call expression was evaluated. As a result, a <code>MuProcedure</code> does
not need to store an environment as an instance attribute. It can refer to
names in the environment from which it was called.
<pre>
scm> (define f (mu (x) (+ x y)))
f
scm> (define g (lambda (x y) (f (+ x x))))
g
scm> (g 3 7)
13
</pre>
<p>Your Scheme interpreter implementation is now complete. You should have
been adding tests to <code>tests.scm</code> as you did each problem. These
tests will be evaluated as part of your composition score for the project.
Make sure that your project works as expected.
<h3>Part 3: Write Some Scheme</h3>
<p>Not only is your Scheme interpreter itself a tree-recursive program, but it is
flexible enough to evaluate <i>other</i> recursive programs. Implement the following
procedures in Scheme at the bottom of <code><a
href="tests.scm">tests.scm</a></code>.</p>
<p><b>Problem 18</b> (2 pt). Implement the <code>merge</code> procedure, which
takes in a comparator and two sorted list arguments and combines them into one
sorted list. A <emph>comparator</emph> is a function that compares two values.
For example:
<pre>
scm> (merge < '(1 4 6) '(2 5 8))
(1 2 4 5 6 8)
scm> (merge > '(6 4 1) '(8 5 2))
(8 6 5 4 2 1)
</pre>
<p><b>Problem A19</b> (2 pt). Implement the <code>count-change</code> procedure, which
counts all of the ways to make change for a <code>total</code> amount, using coins with
various denominations (<code>denoms</code>), but never uses more than
<code>max-coins</code> in total. The procedure definition line is provided
in <code>tests.scm</code>, along with a list of U.S. denominations.</p>
<p><b>Problem B20</b> (2 pt) Implement the <code>count-partitions</code> procedure,
which counts all the ways to partition a positive integer <code>total</code> using only
pieces less than or equal to another positive integer <code>max-value</code>. The
number <code>5</code> has 5 partitions using pieces up to a <code>max-value</code> of
<code>3</code>:</p>
<pre>
3, 2 (two pieces)
3, 1, 1 (three pieces)
2, 2, 1 (three pieces)
2, 1, 1, 1 (four pieces)
1, 1, 1, 1, 1 (five pieces)
</pre>
<p><b>Problem 21</b> (2 pt). Implement the <code>list-partitions</code> procedure,
which lists all of the ways to partition a positive integer <code>total</code> into at
most <code>max-pieces</code> pieces that are all less than or equal to a positive
integer <code>max-value</code>. <i>Hint</i>: Define a helper function to construct
partitions.</p>
<p><b>Problem 22</b> (0 pt). Implement the <code>hax</code> procedure that
draws the following recursive illustration when passed two arguments, a side
length <code>d</code> and recursive depth <code>k</code>. The example below
is drawn from <code>(hax 200 4)</code>.
<div>
<img alt="hax.png" src="hax.png" />
</div>
<p>To see how this illustration is constructed, consider this annotated
version that gives the relative lengths of lines of the component shapes in
the figure.
<div>
<img alt="h1.png" src="h1.png" />
</div>
<h3>Extra Credit</h3>
<p><b>Problem 23</b> (2 pt). Complete the function
<code>scheme_optimized_eval</code>
in <code><a href="scheme.py.html">scheme.py</a></code>. This alternative to <code>scheme_eval</code> is
properly tail recursive. That is, the interpreter will allow an unbounded
number of active <a href=http://en.wikipedia.org/wiki/Tail_call>tail
calls</a> in constant space.
<p>Instead of recursively calling <code>scheme_eval</code> for tail calls and
logical special forms, and <code>let</code>, replace the current
<code>expr</code> and <code>env</code> with different expressions and