aboutsummaryrefslogtreecommitdiff
path: root/lab1/inductive-data-types-lab.ipynb
blob: b2219a1dafe7dea25737bf74abda11ce4a711bbf (plain)
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
{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a105002c-be69-423a-92c4-af05a77af8a2",
   "metadata": {},
   "source": [
    "# Lab: Recursion, Inductive Data Types, and Abstract Syntax Trees\n",
    "\n",
    "<!-- 3 Expressions -->\n",
    "\n",
    "<!-- 4 Binding and Scope -->\n",
    "\n",
    "<!-- 8 Recursion -->\n",
    "\n",
    "<!-- 9 Inductive Data Types -->\n",
    "\n",
    "### Learning Goals\n",
    "\n",
    "The primary learning goals of this assignment are to build intuition for\n",
    "the following:\n",
    "\n",
    "Functional Programming Skills  \n",
    "Representing data structures using algebraic data types.\n",
    "\n",
    "Programming Languages Ideas  \n",
    "Representing programs as abstract syntax.\n",
    "\n",
    "### Instructions\n",
    "\n",
    "A version of project files for this lab resides in the public\n",
    "[pppl-lab1](https://github.com/csci3155/pppl-lab1) repository. Please\n",
    "follow separate instructions to get a private clone of this repository\n",
    "for your work.\n",
    "\n",
    "You will be replacing `???` in the `Lab1.scala` file with solutions to\n",
    "the coding exercises described below. Make sure that you remove the\n",
    "`???` and replace it with the answer.\n",
    "\n",
    "You may add additional tests to the `Lab1Spec.scala` file. In the\n",
    "`Lab1Spec.scala`, there is empty test class `Lab1StudentSpec` that you\n",
    "can use to separate your tests from the given tests in the `Lab1Spec`\n",
    "class. You are also likely to edit `Lab1.worksheet.sc` for any scratch\n",
    "work.\n",
    "\n",
    "Single-file notebooks are convenient when experimenting with small bits\n",
    "of code, but they can become unwieldy when one needs a multiple-file\n",
    "project instead. In this case, we use standard build tools (e.g., `sbt`\n",
    "for Scala), IDEs (e.g., Visual Studio Code with Metals), and source\n",
    "control systems (e.g., `git` with GitHub). While it is almost overkill\n",
    "to use these standard software engineering tools for this lab, we get\n",
    "practice using these tools in the small.\n",
    "\n",
    "If you like, you may use this notebook for experimentation. However,\n",
    "**please make sure your code is in `Lab1.scala`; this notebook will not\n",
    "graded.**\n",
    "\n",
    "## Recursion\n",
    "\n",
    "### Repeat String\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 1**</span> Write a recursive\n",
    "function `repeat`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f7013900",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrepeat\u001b[39m"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repeat(s: String, n: Int): String = {\n",
    "    if (n == 0) \"\"\n",
    "    else s + repeat(s, n - 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54e4328d-f72f-42f8-944e-26e893c9ee2a",
   "metadata": {},
   "source": [
    "where `repeat(s, n)` returns a string with `n` copies of `s`\n",
    "concatenated together. For example, `repeat(\"a\",3)` returns `\"aaa\"`.\n",
    "Implement by this function by direct recursion. Do not use any Scala\n",
    "library methods.\n",
    "\n",
    "### Square Root\n",
    "\n",
    "In this exercise, we will implement the square root function. To do so,\n",
    "we will use Newton’s method (also known as Newton-Raphson).\n",
    "\n",
    "Recall from Calculus that a root of a differentiable function can be\n",
    "iteratively approximated by following tangent lines. More precisely, let\n",
    "$f$ be a differentiable function, and let $x_0$ be an initial guess for\n",
    "a root of $f$. Then, Newton’s method specifies a sequence of\n",
    "approximations $x_0, x_1, \\ldots$ with the following recursive equation:\n",
    "\n",
    "$$\n",
    "x_{n + 1} = x_n - \\frac{f(x_n)}{f'(x_n)}\n",
    "\\;.$$\n",
    "\n",
    "The square root of a real number $c$ for $c > 0$, written $\\sqrt{c}$, is\n",
    "a positive $x$ such that $x^2 = c$. Thus, to compute the square root of\n",
    "a number $c$, we want to find the positive root of the function:\n",
    "$$f(x) = x^2 - c \\;.$$ Thus, the following recursive equation defines a\n",
    "sequence of approximations for $\\sqrt{c}$:\n",
    "$$x_{n + 1} = x_n - \\frac{x_n^2 - c}{2 x_n} \\;.$$\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 2**</span> First, implement a\n",
    "function `sqrtStep`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c539e344",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrtStep\u001b[39m"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sqrtStep(c: Double, xn: Double): Double = {\n",
    "    val n = (xn * xn) - c\n",
    "    val d = 2 * xn\n",
    "    xn - (n / d)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dffe57a-0f30-4de2-b713-67870c807c77",
   "metadata": {},
   "source": [
    "that takes one step of approximation in computing $\\sqrt{c}$ (i.e.,\n",
    "computes $x_{n + 1}$ from $x_n$).\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 3**</span> Next, implement a\n",
    "function `sqrtN`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9bb776bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrtN\u001b[39m"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sqrtN(c: Double, x0: Double, n: Int): Double = {\n",
    "    if (n == 0) x0\n",
    "    else sqrtN(c, sqrtStep(c, x0), n - 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "387179d2-3946-46c8-9c89-888ce27a1933",
   "metadata": {},
   "source": [
    "that computes the $n$th approximation $x_n$ from an initial guess $x_0$.\n",
    "You will want to call `sqrtStep` implemented in the previous part.\n",
    "\n",
    "You need to implement this function using recursion and no mutable\n",
    "variables (i.e., `var`s)—you will want to use a recursive helper\n",
    "function. It is also quite informative to compare your recursive\n",
    "solution with one using a `while` loop.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 4**</span> Now, implement a\n",
    "function `sqrtErr`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5bfde3b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "cmd7.sc:3: value abs is not a member of object almond.display.Math\n",
      "    if (Math.abs((x0 * x0) - c) < epsilon) x0\n",
      "             ^\n",
      "Compilation Failed"
     ]
    }
   ],
   "source": [
    "def sqrtErr(c: Double, x0: Double, epsilon: Double): Double = {\n",
    "    val next = sqrtStep(c, x0)\n",
    "    if (Math.abs((x0 * x0) - c) < epsilon) x0\n",
    "    else sqrtErr(c, next, epsilon)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85e68de9-8cad-4a3f-a34c-b0292ffa3cad",
   "metadata": {},
   "source": [
    "that is very similar to `sqrtN` but instead computes approximations\n",
    "$x_n$ until the approximation error is within $\\varepsilon$ (`epsilon`),\n",
    "that is, $|x_n^2 - c| < \\varepsilon \\;.$ You can use your absolute value\n",
    "function `abs` implemented in a previous part. A wrapper function `sqrt`\n",
    "is given in the template that simply calls `sqrtErr` with a choice of\n",
    "`x0` and `epsilon`.\n",
    "\n",
    "You need to implement this function using recursion, though it is useful\n",
    "to compare your recursive solution to one with a `while` loop.\n",
    "\n",
    "## Data Structures Review: Binary Search Trees\n",
    "\n",
    "In this question, we review implementing operations on binary search\n",
    "trees from Data Structures. Balanced binary search trees are common in\n",
    "standard libraries to implement collections, such as sets or maps. For\n",
    "simplicity, we do not worry about balancing in this question.\n",
    "\n",
    "Trees are important structures in developing interpreters, so this\n",
    "question is also critical practice in implementing tree manipulations.\n",
    "\n",
    "A binary search tree is a binary tree that satisfies an ordering\n",
    "invariant. Let $n$ be any node in a binary search tree whose left child\n",
    "is $l$, data value is $d$, and right child is $r$. The ordering\n",
    "invariant is that all of the data values in the subtree rooted at $l$\n",
    "must be $< d$, and all of the data values in the subtree rooted at $r$\n",
    "must be $\\geq d$. We will represent a binary trees containing integer\n",
    "data using the following Scala `case class`es:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d3700708",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mTree\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mEmpty\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Tree\n",
    "case object Empty extends Tree\n",
    "case class Node(l: Tree, d: Int, r: Tree) extends Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e795398-4da3-46b3-b556-f0bc5852a97d",
   "metadata": {},
   "source": [
    "A `Tree` is either `Empty` or a `Node` with left child `l`, data value\n",
    "`d`, and right child `r`.\n",
    "\n",
    "For this question, we will implement the following four functions.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 5**</span> The function `repOk`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2d4949ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrepOk\u001b[39m"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def repOk(t: Tree): Boolean = {\n",
    "    def check(t: Tree, min: Int, max: Int): Boolean = t match {\n",
    "      case Empty => true\n",
    "      case Node(l, d, r) =>\n",
    "        d >= min && d < max && check(l, min, d) && check(r, d, max)\n",
    "    }\n",
    "    check(t, Int.MinValue, Int.MaxValue)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9902f78c-a33b-4ca0-8ae9-b3033b4426b9",
   "metadata": {},
   "source": [
    "checks that an instance of `Tree` is valid binary search tree. In other\n",
    "words, it checks using a traversal of the tree the ordering invariant\n",
    "described above. This function is useful for testing your\n",
    "implementation.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 6**</span> The function `insert`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "5792d194",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36minsert\u001b[39m"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def insert(t: Tree, n: Int): Tree = t match {\n",
    "    case Empty => Node(Empty, n, Empty)\n",
    "    case Node(l, d, r) =>\n",
    "      if (n < d) Node(insert(l, n), d, r)\n",
    "      else Node(l, d, insert(r, n))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "036345e1-2834-4042-ab05-e89da6ffcd11",
   "metadata": {},
   "source": [
    "inserts an integer into the binary search tree. Observe that the return\n",
    "type of `insert` is a `Tree`. This choice suggests a functional style\n",
    "where we construct and return a new output tree that is the input tree\n",
    "`t` with the additional integer `n` as opposed to destructively updating\n",
    "the input tree.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 7**</span> The function\n",
    "`deleteMin`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "25a13b75",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdeleteMin\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def deleteMin(t: Tree): (Tree, Int) = {\n",
    "    require(t != Empty)\n",
    "    (t: @unchecked) match {\n",
    "      case Node(Empty, d, r) => (r, d)\n",
    "      case Node(l, d, r) =>\n",
    "        val (l1, m) = deleteMin(l)\n",
    "        (Node(l1, d, r), m)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97630bf8-7afd-4dd9-8aa4-3dcb7ff05df8",
   "metadata": {},
   "source": [
    "deletes the smallest data element in the search tree (i.e., the leftmost\n",
    "node). It returns both the updated tree and the data value of the\n",
    "deleted node. This function is intended as a helper function for the\n",
    "`delete` function.\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 8**</span> The function `delete`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6fe5bb5f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mdelete\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def delete(t: Tree, n: Int): Tree = t match {\n",
    "    case Empty => Empty\n",
    "    case Node(l, d, r) if n < d =>\n",
    "      Node(delete(l, n), d, r)\n",
    "    case Node(l, d, r) if n > d =>\n",
    "      Node(l, d, delete(r, n))\n",
    "    case Node(l, d, r) =>\n",
    "      if (l == Empty) r\n",
    "      else if (r == Empty) l\n",
    "      else {\n",
    "        val (r1, min) = deleteMin(r)\n",
    "        Node(l, min, r1)\n",
    "      }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c131559-294b-4894-be21-3ab2cdf996fb",
   "metadata": {},
   "source": [
    "removes the first node with data value equal to `n`. This function is\n",
    "trickier than `insert` because what should be done depends on whether\n",
    "the node to be deleted has children or not. We advise that you take\n",
    "advantage of pattern matching to organize the cases.\n",
    "\n",
    "## Interpreter: JavaScripty Calculator\n",
    "\n",
    "In this question, we consider the arithmetic sub-language of JavaScripty\n",
    "(i.e., a basic calculator). We represent the abstract syntax for this\n",
    "sub-language in Scala using the following inductive data type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "32b17391",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mN\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mUnary\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mBinary\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mUop\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNeg\u001b[39m\n",
       "defined \u001b[32mtrait\u001b[39m \u001b[36mBop\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mMinus\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mTimes\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mDiv\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr                                            // e ::=\n",
    "case class N(n: Double) extends Expr                         //   n\n",
    "case class Unary(uop: Uop, e1: Expr) extends Expr            // | uop e1\n",
    "case class Binary(bop: Bop, e1: Expr, e2: Expr) extends Expr // | e1 bop e2\n",
    "\n",
    "sealed trait Uop              // uop ::=\n",
    "case object Neg extends Uop   //   -\n",
    "\n",
    "sealed trait Bop              // bop ::=\n",
    "case object Plus extends Bop  //   +\n",
    "case object Minus extends Bop // | -\n",
    "case object Times extends Bop // | *\n",
    "case object Div extends Bop   // | /"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f579c467-070f-4902-a445-8a0109a81130",
   "metadata": {},
   "source": [
    "In comments, we give a grammar that connects the abstract syntax with\n",
    "the concrete syntax of the language. We consider grammars in more detail\n",
    "subsequently<span class=\"hidden\">in **?@sec-grammars**</span>. For now,\n",
    "it is fine to ignore the concrete syntax or use your intuition for the\n",
    "connection. ow, given the inductive data type `Expr` defining the\n",
    "abstract syntax:\n",
    "\n",
    "<span class=\"theorem-title\">**Exercise 9**</span> Implement the `eval`\n",
    "function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "054fca87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NaN\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36meval\u001b[39m\n",
       "\u001b[36mexpr1\u001b[39m: \u001b[32mBinary\u001b[39m = \u001b[33mBinary\u001b[39m(bop = Div, e1 = \u001b[33mN\u001b[39m(n = \u001b[32m0.0\u001b[39m), e2 = \u001b[33mN\u001b[39m(n = \u001b[32m0.0\u001b[39m))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def eval(e: Expr): Double = e match {\n",
    "  case N(n) => n\n",
    "  case Unary(Neg, e1) => -eval(e1)\n",
    "  case Binary(Plus, e1, e2) => eval(e1) + eval(e2)\n",
    "  case Binary(Minus, e1, e2) => eval(e1) - eval(e2)\n",
    "  case Binary(Times, e1, e2) => eval(e1) * eval(e2)\n",
    "  case Binary(Div, e1, e2) => eval(e1) / eval(e2)\n",
    "}\n",
    "val expr1 = Binary(Div, N(0.0), N(0.0))\n",
    "println(eval(expr1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03c23117-f6c3-4427-b88a-eb985f06120d",
   "metadata": {},
   "source": [
    "that evaluates the Scala representation of a JavaScripty expression `e`\n",
    "to the Scala double-precision floating point number corresponding to the\n",
    "Scala representation of the JavaScripty *value* of `e`. At this point,\n",
    "you have implemented your first language interpreter!\n",
    "\n",
    "To go in more detail, consider a JavaScripty expression $e$, and imagine\n",
    "$e$ to be concrete syntax. This text is parsed into a JavaScripty AST\n",
    "`e`, that is, a Scala value of type `Expr`. Then, the result of `eval`\n",
    "is a Scala number of type `Double` and should match the interpretation\n",
    "of $e$ as a JavaScript expression. These distinctions can be subtle but\n",
    "learning to distinguish between them will go a long way in making sense\n",
    "of programming languages.\n",
    "\n",
    "To see what a JavaScripty expression $e$ should evaluate to, you may\n",
    "want to run $e$ through a JavaScript interpreter to see what the value\n",
    "should be. For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "931bda9b-2809-4d50-91d6-25b9872deb60",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres13\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m7\u001b[39m"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 + 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ad9e62ed-da7b-4af3-8247-379b7321d3c5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres14\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m0\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 / 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "0f0791e5-834d-4536-8634-4f503740caf6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres15\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m32\u001b[39m"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6 * 4 - 2 + 10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "392df5bb-64b7-4b89-bb92-2dce9ee0e9a8",
   "metadata": {},
   "source": [
    "### Experiment in a Worksheet\n",
    "\n",
    "Scala worksheets provide an interactive interface in the context of a\n",
    "multi-file project. A worksheet is a good place to start for\n",
    "experimenting with an implementation, whether on existing code or code\n",
    "that you are in the process of writing. A scratch worksheet\n",
    "`Lab1.worksheet.sc` is provided for you in the code repository.\n",
    "\n",
    "To test and experiment with your `eval` function, you can write\n",
    "JavaScripty expressions directly in abstract syntax like above. You can\n",
    "also make use of a parser that is provided for you: it reads in a\n",
    "JavaScripty program-as-a-`String` and converts into an abstract syntax\n",
    "tree of type `Expr`.\n",
    "\n",
    "For your convenience, we have also provided in the template `Lab1.scala`\n",
    "file, an overloaded `eval: String => Double` function that calls the\n",
    "provided parser and then delegates to your `eval: Expr => Double`\n",
    "function.\n",
    "\n",
    "### Test-Driven Development and Regression Testing\n",
    "\n",
    "Once you have experimented enough in your worksheet to have some tests,\n",
    "it is useful to save those tests to run over-and-over again as you work\n",
    "on your implementation. The idea behind test-driven development is that\n",
    "we first write a test for what we expect our implementation to do.\n",
    "Initially, we expect our implementation to fail the test, and then we\n",
    "work on our implementation until the test succeeds. IDEs have features\n",
    "to support this workflow. While a test suite can never be exhaustive, we\n",
    "have provided a number of initial tests for you in `Lab1Spec.scala` to\n",
    "partially drive your test-driven development of the functions in this\n",
    "assignment.\n",
    "\n",
    "### Additional Notes\n",
    "\n",
    "While you may not need them in this assignment, the `ast.scala` file\n",
    "also includes some basic helper functions for working with the AST, such\n",
    "as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ec9b583",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValue(e: Expr): Boolean = e match {\n",
    "  case N(_) => true\n",
    "  case _ => false\n",
    "}\n",
    "\n",
    "val e_minus4_2 = N(-4.2)\n",
    "isValue(e_minus4_2)\n",
    "\n",
    "val e_neg_4_2 = Unary(Neg, N(4.2))\n",
    "isValue(e_neg_4_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6705b4d2-c5d5-429c-a1ba-df9a2afb602e",
   "metadata": {},
   "source": [
    "the defines which expressions are values. In this case, literal number\n",
    "expressions `N(` $n$ `)` are values where $n$ is the meta-variable for\n",
    "JavaScripty numbers. We represent JavaScripty numbers in Scala with\n",
    "Scala values of type `Double`.\n",
    "\n",
    "We also define functions to pretty-print, that is, convert abstract\n",
    "syntax to concrete syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "769e512d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prettyNumber(n: Double): String =\n",
    "  if (n.isWhole) \"%.0f\" format n else n.toString\n",
    "\n",
    "def pretty(v: Expr): String = {\n",
    "  require(isValue(v))\n",
    "  (v: @unchecked) match {\n",
    "    case N(n) => prettyNumber(n)\n",
    "  }\n",
    "}\n",
    "\n",
    "pretty(N(4.2))\n",
    "pretty(N(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82aed5b1-4bc6-4683-a890-4728eb767ff1",
   "metadata": {},
   "source": [
    "We only define `pretty` for values, and we do not override the\n",
    "`toString` method so that the abstract syntax can be printed as-is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "222fbd39",
   "metadata": {},
   "outputs": [],
   "source": [
    "e_minus4_2.toString\n",
    "e_neg_4_2.toString"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc7426dc-4ec1-47d3-b116-d3f5da85ed0c",
   "metadata": {},
   "source": [
    "The `@unchecked` annotation tells the Scala compiler that we know the\n",
    "pattern match is non-exhaustive syntactically, so we do not want to be\n",
    "warned about it. However, we see that our definition of `isValue` rules\n",
    "out the potential for a match error at run time (right?).\n",
    "\n",
    "## Submission\n",
    "\n",
    "If you are a University of Colorado Boulder student, we use Gradescope\n",
    "for assignment submission. In summary,\n",
    "\n",
    "-   [ ] Create a private GitHub repository by clicking on a GitHub\n",
    "    Classroom link from the corresponding Canvas assignment entry.\n",
    "-   [ ] Clone your private GitHub repository to your development\n",
    "    environment (using the `<> Code` button on GitHub to get the\n",
    "    repository URL).\n",
    "-   [ ] Work on this lab from your cloned repository. Use Git to save\n",
    "    versions on GitHub (e.g., `git add`, `git commit`, `git push` on the\n",
    "    command line or via VSCode).\n",
    "-   [ ] Submit to the corresponding Gradescope assignment entry for\n",
    "    grading by choosing GitHub as the submission method.\n",
    "\n",
    "You need to have a GitHub identity and must have your full name in your\n",
    "GitHub profile in case we need to associate you with your submissions."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}