CS 3520/6520: Programming Languages

Ideas behind the design and implementation of programming languages. Syntactic description; scope and lifetime of variables; runtime stack organization; parsing and abstract syntax; semantic issues; type systems; programming paradigms; interpreters and compilers.

Goal and Objectives

This course cover concepts of programming languages generally and functional languages in particular, including functions, continuations, syntactic sugar, and type systems. These concepts are explained primarily though a sequence of interpreters and type checkers.

At the end of this course, students will be able to:

• employ a recipe for functional programming: data, examples, template (including natural recursions), implementation, and tests
• use and implement lexical scope, closures, records, objects, and classes
• encode language constructs using constructs that are more primitive, especially lambda-calculus terms
• represent continuations and state explicitly, instead of relying on host-language implementations
• use and implement different evaluation orders: eager and lazy
• explain type soundness and implement sound type checkers for functional and object-oriented languages that include subtyping and parametric polymorphism

Materials for this course:

Programming Languages: Application and Interpretation, Second EditionLinks to an external site., Shriram Krishnamurthi (PDFLinks to an external site.)
DrRacket: https://download.racket-lang.org

Syllabus

CTIHB 109 MW 11:50-1:10 (livestreamed and recorded via Zoom)

Instructors

Co-Instructors:
Ben Greenman <blg@cs.utah.edu> MEB 3252
Matthew Flatt <mflatt@cs.utah.edu> MEB 3256
<help-cs3520@lists.utah.edu>

Teaching Assistant:
 Alec Mills <help-cs3520@lists.utah.edu>

Required Materials

Materials for this course:

• Programming Languages: Application and Interpretation, Second Edition, Shriram Krishnamurthi (PDF)
• DrRacket: https://download.racket-lang.org

Communication

Preferred Contact Methods

The easiest way to contact your instructor directly is to use the    Inbox, located in the far left Canvas menu.
You can also contact your instructor in the following ways:

• help-cs3520@lists.utah.edu
• blg@cs.utah.edu
• mflatt@cs.utah.edu

Asking for Help

When asking a question in a place where it makes sense to show your code (i.e., in a direct message to the instructor or a TA):

• Do include the full source of your program as an attachment.
• Do point the instructor/TA to a particular part of the program (e.g., by line number) where you have a question or where you think there’s a problem.
• Don’t send just a fragment of your code. The instructor/TA probably needs more context. Also, If you don’t understand why a fragment of code has problems, then maybe you’re looking at the wrong fragment.
• Don’t include just a screen shot of the program text. Sometimes, the instructor/TA needs to try running your program to see what happens, and screenshots don’t compile. A screen shot is useful sometimes, but in that case, include both program text and a screen image.
• Don’t copy and paste the text into your mail message, because mail transport mangles text. Provide a program as an attachment.

Evaluation

Your performance in this course will be evaluated by:

• Homework assignments (55%)
• Two midterm exams (15% each)
• Final programming assignment (10%)
• Video-lecture quizzes (5%)

Course Policies

Submitting Assignments

All assignments must be submitted via the “Handin” button in DrRacket. Install the uu-cs3520 package and restart DrRacket to get the “Handin” button. See DrRacket and the Handin Button for more information. You can check your handin status and get feedback from the Handin status server.
Each set of lecture videos has an associated quiz on Canvas. Quizzes are due before the corresponding class meeting.

Late Assignments

Late quizzes are not accepted. Homework submissions will be accepted up to 48 hours after the deadline. For each student, up to two late homework submissons (each up to 48 hours late) will be accepted without penalty. After a student’s first two late submissions, a late submission within 24 hours of the deadline will be penalized 25%. A submission more than 24 hours late but less than 48 hours late will be penalized 50%.

Large Language Models

The use of large language models (LLMs) such as ChatGPT is permitted on homework assignments. An LLM’s contribution to your homework submission must be acknowledged in a comment. Students should take care to use LLMs in a way that fosters their own learning — perhaps, for example, relying on ChatGPT as a way of understanding existing code rather than having it change code or write new code for you. The course staff will not provide technical or financial support to help students use LLMs. Do not rely on LLMs to answer course-related questions (grading, due dates, etc.); ask the course staff instead. The use of LLMs, program interpreters, or remote resources is not permitted during in-class midterm exams.

Some general disclaimers: LLMs may output text that is grossly incorrect, subtly incorrect, or otherwise misleading. LLM companies may track the queries you submit. LLMs may have, in the aggregate, a large cost to the environment that companies do not (or, cannot) fully account for.

Grading

Grading for this course

Each quiz associated with a set of lecture videos is worth a number of points corresponding to the number of questions on the quiz, where each correct answer is worth 1 point. The intent is that you take the quiz after/during watching the videos. At the end of the semester, any cumulative quiz grade of 60% or more is rounded up to 100%. Consequently, you should not be unduly concerned about missed quiz questions, even though there are no retakes, as long as you are following the videos and answering most questions correctly.

Homework is graded on the following scale: check+ = 100% for perfect or nearly perfect work, check = 80% for somewhat flawed but acceptable work, check- = 50% for seriously flawed work, 0 = 0% for missing or completely unacceptable work, and check++ = 110% for perfect work plus extra credit (when specifically offered). All homework assignments are weighted equally.

Exams are graded on a scale of 0 to 100 points.

A final assignment will be similar to a homework assignment, but larger, and the handin process will include a 1-page report. The final assignment serves much the same role as a final exam.

Accommodations

Disclaimer

Accommodations will be considered on an individual basis and may require documentation.

Please contact your instructor and/or teaching assistant as soon as possible (preferably shortly before the semester begins) to request accommodations of any kind.

Extreme personal circumstances

Please contact your instructor as soon as possible if an extreme personal circumstance
(hospitalization, death of a close relative, natural disaster, etc.) is interfering with your ability to
complete your work.

Religious Practice

To request an accommodation for religious practices, contact your instructor at the beginning of the semester.

Active Duty Military

If you are student on active duty with the military and experience issues that prevent you from participating in the course because of deployment or service responsibilities, contact your instructor as soon as possible to discuss appropriate accommodations.

Disability Access

All written information in this course can be made available in an alternative format with prior notification to the Center for Disability Services (CDS). CDS will work with you and the instructor to make arrangements for accommodations. Prior notice is appreciated. To read the full accommodations policy for the University of Utah, please see Section Q of the Instruction & Evaluation regulations.

If you will need accommodations in this class, contact:

Center for Disability Services
  801-581-5020
  disability.utah.edu
  162 Union Building
    200 S. Central Campus Dr.
     Salt Lake City, UT 84112

Changes to the Syllabus

This syllabus is not a contract. It is meant to serve as an outline and guide for your course. Please note that your instructor may modify it to accommodate the needs of your class.
You will be notified of any changes to the Syllabus.

Lectures

• Lecture 0
• Lecture 1
• Lecture 2
  • Lecture 2b
• Lecture 3
• Lecture 4
• Lecture 5
  • Lecture 5b
• Lecture 6
• Lecture 7
• Practice Midterm

Homework Assignments

HW0

Difficulty: ★☆☆☆

Part 0 — Create Handin Account

After installing the uu-cs3520 package as described in DrRacket and the Handin Button, select the Manage CS 3520 Handin… menu item from DrRacket’s File menu. Change to the New User panel, and pick a username and password. (Use your real name and real Utah student ID, so that we can connect your homework submissions with you.)

You will have to install uu-cs3520 for DrRacket on each different filesystem that you use to get a Handin button. However, after creating a handin account once from any machine, you can use DrRacket’s Handin button on any other machine.

Use #lang shplait at the start of your program, so that it’s implemented in the Plait language.

Part 1 — Implement to_the_3rd

Define the function to_the_3rd, which takes a number and raises it to the 3rd power.

Your program should include check forms to check to_the_3rd on a few inputs.

Example use: to_the_3rd(17) should produce 4913.

Part 2 — Implement to_the_42nd

Define the function to_the_42nd (in the same program), which takes a number and raises it to the 42nd power.

It’s probably a good idea to use functions like to_the_3rd to build up to to_the_42nd.

Your program should include check forms to check to_the_42nd on a few inputs.

Example use: to_the_42nd(17) should produce 4773695331839566234818968439734627784374274207965089.

Part 3 — Implement plural

Define plural, which takes a string and returns a string. If the given string ends in “y”, the result should be the same as the input but with the “y” replaced by “ies”. Otherwise, the result should be the same as the given string with “s” added to the end.

Your program should include check forms to check plural on a few inputs.

Example uses: plural("baby") should produce "babies", while plural("fish") should produce "fishs".

See the documentation for Shplait to find functions that you need to work with strings.

Part 4 — Implement electricity-usage

Use the following type definition (add it to your program):

  type Light
  | bulb(watts :: Int,
         technology :: Symbol)
  | candle(inches :: Int)

Implement the function electricity_usage, which takes a Light and produces the number of watthours of electricity that the light uses in 24 hours. Your function will need to use match.

As always, include relevant check forms.

Example uses: electricity_usage(bulb(100, #'halogen)) should produce 2400, while electricity_usage(candle(10)) should produce 0.

Part 5 — Implement use-for-one-hour

Implement the function use_for_one_hour, which takes a Light and produces another Light that represents the given light source after it is used for another hour. Assume that a candle burns one inch per hour (unless it is already gone), and assume that a light bulb is the same after one hour of use.

Example uses: use_for_one_hour(bulb(100, #'halogen)) should produce bulb(100, #'halogen), while use_for_one_hour(candle(10)) should produce candle(9).

Part 6 — Handin

Click the Handin button in DrRacket to submit your homework. The Handin button submits whatever is in DrRacket’s definitions area, so click Handin after you have defined to_the_3rd, to_the_42nd, plural, electricity_usage, and use_for_one_hour, all in the same program.

The handin process will check that you have defined the right names. It will also run some tests on your programs. If tests fail, then your handin will not be accepted—but you can override that by clicking Submit even if server reports problems. That checkbox won’t override very basic problems, however, such as not using #lang shplait or submitting a program that doesn’t compile.

You can double-check that handin was successful by visiting the Handin status server. Log in with the account that you created for handin. You can check whether a submission has been uploaded, you can check the time of the upload, and you can download your submission. Solutions and grades for your assignments will appear later in that same place.

Solution

  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

#lang shplait

// Part 1
fun to_the_3rd(n :: Int):
  n * n * n

check: to_the_3rd(0)
       ~is 0
check: to_the_3rd(2)
       ~is 8
check: to_the_3rd(17)
       ~is 4913
check: to_the_3rd(-4)
       ~is -64
       
// Part 2
fun to_the_15th(n :: Int): // (n^3)^3 * n^3 * n^3 = n^15
  to_the_3rd(to_the_3rd(n)) * to_the_3rd(n) * to_the_3rd(n)

fun to_the_27th(n :: Int): // ((n^3)^3)^3 = n^27
  to_the_3rd(
    to_the_3rd(
      to_the_3rd(n)
    )
  ) 

fun to_the_42nd(n :: Int): // n^27 * n^15 = n^42
  to_the_27th(n) * to_the_15th(n)

       
check: to_the_15th(0)
       ~is 0
check: to_the_15th(2)
       ~is 32768
check: to_the_15th(17)
       ~is 2862423051509815793
check: to_the_15th(-3)
       ~is -14348907
       
check: to_the_27th(2)
       ~is 134217728
check: to_the_27th(7)
       ~is 65712362363534280139543
check: to_the_27th(-6)
       ~is -1023490369077469249536
       
check: to_the_42nd(0)
       ~is 0
check: to_the_42nd(1)
       ~is 1
check: to_the_42nd(17)
       ~is 4773695331839566234818968439734627784374274207965089
check: to_the_42nd(2)
       ~is 4398046511104
check: to_the_42nd(-5)
       ~is 227373675443232059478759765625
       

// Part 3
fun plural(str :: String):
  cond
  | string_length(str) == 0: "s" // I thought this should be empty string, but the submission test fails.
  | string_get(str, string_length(str)-1) == #{#\y}: substring(str, 0, string_length(str)-1) +& "ies"
  | ~else: str +& "s"


check: plural("baby")
       ~is "babies"
check: plural("fish")
       ~is "fishs"
check: plural("")
       ~is "s"

// Part 4
type Light
| bulb(watts :: Int,
       technology :: Symbol)
| candle(inches :: Int)


fun electricity_usage(l :: Light):
  match l:
  | bulb(w, t): w * 24
  | candle(i): 0


check: electricity_usage(bulb(100, #'halogen))
       ~is 2400
check: electricity_usage(bulb(0, #'free_energy))
       ~is 0
check: electricity_usage(bulb(-30, #'somehow_this_bulb_produces_energy))
       ~is -720
check: electricity_usage(candle(10))
       ~is 0


// Part 5

fun use_for_one_hour(l :: Light):
  match l:
  | bulb(w,t): l
  | candle(i):
      if i > 0
      | candle(i-1)
      | candle(0)

check: use_for_one_hour(bulb(100, #'halogen))
       ~is bulb(100, #'halogen)
check: use_for_one_hour(candle(10))
       ~is candle(9)
check: use_for_one_hour(candle(0))
       ~is candle(0)

HW1

Difficulty: ★★☆☆

The following Tree datatype implements a binary tree with a number in each node and leaf:

  type Tree
  | leaf(val :: Int)
  | node(val :: Int,
         left :: Tree,
         right :: Tree)

Part 1 — Sum

Implement a sum function that takes a tree and returns the sum of the numbers in the tree.

Example:
sum(node(5, leaf(6), leaf(7))) should produce 18.

Part 2 — Negate

Implement the function negate, which takes a tree and returns a tree that has the same shape, but with all the numbers negated.

Example:
negate(node(5, leaf(6), leaf(7))) should produce node(-5, leaf(-6), leaf(-7)).

Part 3 — Contains

Implement the function contains, which takes a tree and a number and returns #true if the number is in the tree, #false otherwise.

Example:
contains(node(5, leaf(6), leaf(7)), 6) should produce #true.

Part 4 — Big Leaves?

Implement the function has_big_leaves, which takes a tree and returns #true if every leaf is bigger than the sum of numbers in the path of nodes from the root that reaches the leaf.

Examples:
has_big_leaves(node(5, leaf(6), leaf(7))) should produce #true, while has_big_leaves(node(5, node(2, leaf(8), leaf(6)), leaf(7))) should produce #false (since 6 is smaller than 5 plus 2).

The has_big_leaves function should be a thin wrapper on another function, perhaps has_bigger_leaves, that accumulates a sum of node values.

A tree that is just a leaf has no nodes between the leaf and the root, which means that the path from the root corresponds to an empty sequence of numbers. Conventionally, the sum of an empty sequence of numbers is defined to be 0, because it’s convenient and consistent; that’s the intent here, too.

Part 5 — Positive Trees

Implement the function positive_trees, which takes a list of trees and returns #true if every member of the list is a positive tree, where a positive tree is one whose numbers sum to a positive value.

Hint 1: This function takes a list, not a tree, so don’t try to use the template for a tree function.
Hint 2: Use your sum function as a helper.
Hint 3: positive_trees([]) should produce #true, because there’s no tree in the empty list whose numbers sum to 0 or less.

More examples:

  check: positive_trees(cons(leaf(6), []))
         ~is #true

  check: positive_trees(cons(leaf(-6), []))
         ~is #false

  check: positive_trees(cons(node(1, leaf(6), leaf(-6)), []))
         ~is #true

  check: positive_trees(cons(node(1, leaf(6), leaf(-6)),
                             (cons(node(0, leaf(0), leaf(1)), []))))
         ~is #true

  check: positive_trees(cons(node(-1, leaf(6), leaf(-6)),
                             cons(node(0, leaf(0), leaf(1)), [])))
         ~is #false

Part 6 — Optional challenge: Flatten

CS 3520 and CS 6520 students are welcome to complete the exercise, but it does not count for extra credit.

Implement the function flatten, which takes a tree and returns a list that has all numbers in the tree’s nodes and leaves. The numbers should be ordered to match an inorder traversal of the tree, and a number that appears multiple times in the tree should appear the same number of times in the list.

Your function should run in time proportional to the size of the tree, which rules out making a list of the tree numbers using append on recursive calls. You may find it helpful to recur on a right subtree before a left subtree.

Hint: Does the function take a list or a tree? Which template should you use?

Submit

Submissions in this class are directly supported by the programming environment, DrRacket. Submit your work using the handin button in DrRacket.

Solution

  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

#lang shplait

type Tree
| leaf(val :: Int)
| node(val :: Int,
       left :: Tree,
       right :: Tree)

// Part 1

fun sum(t :: Tree):
  match t
  | leaf(v): v
  | node(v, l, r): v + sum(l) + sum(r)

check: sum(node(5, leaf(6), leaf(7)))
       ~is 18
check: sum(leaf(-10))
       ~is -10
check: sum(node(5, leaf(2), node(4, leaf(6), leaf(8))))
       ~is 5+2+4+6+8

// Part 2

fun negate(t :: Tree):
  match t
  | leaf(v): leaf(-v)
  | node(v, l, r): node(-v, negate(l), negate(r))

check: negate(node(5, leaf(6), leaf(7)))
       ~is node(-5, leaf(-6), leaf(-7))
check: negate(leaf(-10))
       ~is leaf(10)
check: negate(node(5, leaf(2), node(4, leaf(6), leaf(8))))
       ~is node(-5, leaf(-2), node(-4, leaf(-6), leaf(-8)))


// Part 3

fun contains(t :: Tree, n :: Int):
  match t
  | leaf(v): v == n
  | node(v, l, r): v == n || contains(l, n) || contains(r, n)


check: contains(node(5, leaf(6), leaf(7)), 6)
       ~is #true
check: contains(node(5, leaf(2), node(4, leaf(6), leaf(8))), 8)
       ~is #true
check: contains(node(5, leaf(2), node(4, leaf(6), leaf(8))), 3)
       ~is #false
check: contains(leaf(1), 2)
       ~is #false


// Part 4

fun has_bigger_leaves(t :: Tree, total :: Int):
  match t
  | leaf(v): v > total
  | node(v, l, r): has_bigger_leaves(l, total + v) && has_bigger_leaves(r, total + v)
  
fun has_big_leaves(t :: Tree):
  has_bigger_leaves(t, 0)


check: has_bigger_leaves(leaf(10), 9)
       ~is #true
check: has_bigger_leaves(leaf(10), 11)
       ~is #false
check: has_bigger_leaves(leaf(10), 10)
       ~is #false
check: has_bigger_leaves(node(5, node(2, leaf(8), leaf(6)), leaf(7)), 0)
       ~is #false
check: has_bigger_leaves(node(5, leaf(6), leaf(7)), 0)
       ~is #true


check: has_big_leaves(node(5, leaf(6), leaf(7)))
       ~is #true
check: has_big_leaves(node(5, node(2, leaf(8), leaf(6)), leaf(7)))
       ~is #false
check: has_big_leaves(leaf(5))
       ~is #true


// Part 5

fun positive_trees(ts :: Listof(Tree)):
  match ts
  | []: #true
  | cons(t, rest_t): sum(t) > 0 && positive_trees(rest_t)

check: positive_trees(cons(leaf(6),
                           []))
       ~is #true

check: positive_trees(cons(leaf(-6),
                           []))
       ~is #false

check: positive_trees(cons(node(1, leaf(6), leaf(-6)),
                           []))
       ~is #true

check: positive_trees(cons(node(1, leaf(6), leaf(-6)),
                           (cons(node(0, leaf(0), leaf(1)),
                                 []))))
       ~is #true

check: positive_trees(cons(node(-1, leaf(6), leaf(-6)),
                           cons(node(0, leaf(0), leaf(1)),
                                [])))
       ~is #false


// Part 6: Optional

fun flatten(t :: Tree):
  match t
  | node(v, l, r): append(append(flatten(l), cons(v, [])), flatten(r))
  | leaf(v): cons(v, [])

check: flatten(leaf(0))
       ~is [0]
check: flatten(node(5, node(2, leaf(8), leaf(6)), leaf(7)))
       ~is [8, 2, 6, 5, 7]
check: flatten(node(6, node(4, node(2, leaf(1), leaf(3)), leaf(5)), node(8, leaf(7), node(10, leaf(9), leaf(11)))))
       ~is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

HW2

Difficulty: ★★★☆

Part 1 — Maximum

Start with the interpreter with functions, and add a max operator that takes two numbers and returns the larger of them. The syntax for max should be similar to a function call.

Since you must change the Exp datatype, and since different people may change it in different ways, you must update the parse function, which accepts a syntax object and produces an Exp value.

Examples:

  check: interp(parse('max(1, 2)'),
                [])
         ~is 2
  check: interp(parse('max(4+5, 2+3)'),
                [])
         ~is 9

Part 2 — Functions that Accept Multiple Arguments

Extend the interpreter to support multiple or zero arguments to a function, and multiple or zero arguments in a function call.

For example,

fun area(w, h): w * h

defines a function that takes two arguments, while

fun five(): 5

defines a function that takes zero arguments. Similarly,

area(3, 4)

calls the function area with two arguments, while

five()

calls the function five with zero arguments.

At run-time, a new error is now possible: function application with the wrong number of arguments. Your interp function should detect the mismatch and report an error that includes the words “wrong arity”.

To support functions with multiple arguments, you’ll have to change fd and appE and all tests that use them. When you update the parse function, note that match supports ... in a pattern to indicate zero or more repetitions of the preceding pattern, and so do templates, and syntax_to_list recognizes []-shaped syntax. So '$sym($arg, ...)' matches any number of arguments, and syntax_to_list('[$arg, ...]') converts the arguments into a list of syntax objects.

Beware of putting the multi-argument application pattern too early in parse, since that pattern is likely to match other forms. In addition, you’ll need to update the parse_fundef function that takes one quoted fun form and produces a FunDef value.

Preserve the starting behavior that an argument expression is always evaluated before it is passed to a function. That is, only numbers should be substituted into a function body for a function call.

Examples:

  check: interp(parse('f(1, 2)'),
                [parse_fundef('fun f(x, y): x + y')])
         ~is 3
  check: interp(parse('f() + f()'),
                [parse_fundef('fun f(): 5')])
         ~is 10
  check: interp(parse('f(2, 3)'),
                [parse_fundef('fun f(x, y): y + x + x')])
         ~is 7
  check: interp(parse('f(1)'),
                [parse_fundef('fun f(x, y): x+y')])
         ~raises "wrong arity"

Remember that Shplait provides map, which takes a function and a list, and applies the function to each element in the list, returning a list of results. For example, if ars is a list of syntax objects to parse, map(parse, ars) produces a list of Exps by parsing each S-expression.

But also remember that map doesn’t work for everything. Sometimes, when you have a list to process (or maybe two lists in parallel), then you need to write a new function using the template for lists.

If you get stuck here, then see HW 2 Hint (but you should try this part before you look at the hint).

Part 3 — Function Argument Checking (CS 6520)

This exercise is required only for CS 6520 students. CS 3520 students are welcome to complete the exercise, but it does not count for extra credit.

A function is ill-defined if two of its argument names are the same. To prevent this problem, update your parse_fundef function to detect this problem and report a “bad syntax” error.

For example, parse_fundef('fun f(x, x): x') must report a “bad syntax” error, while parse_fundef('fun f(x, y): x') should produce a FunDef value.

Solution

  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

#lang shplait

type Exp
| intE(n :: Int)
| idE(s :: Symbol)
| plusE(l :: Exp,
        r :: Exp)
| multE(l :: Exp,
        r :: Exp)
| appE(s :: Symbol,
       args :: Listof(Exp))
| maxE(l :: Exp,
       r :: Exp)

type FunDef
| fd(name :: Symbol,
     args :: Listof(Symbol),
     body :: Exp)

// An EXP is either
// - 'NUMBER'
// - 'SYMBOL'
// - 'EXP + EXP'
// - 'EXP * EXP'
// - 'SYMBOL(EXP)'
// - '(EXP)'

fun parse(s :: Syntax) :: Exp:
  cond
  | syntax_is_integer(s):
      intE(syntax_to_integer(s))
  | syntax_is_symbol(s):
      idE(syntax_to_symbol(s))
  | ~else:
      match s
      | '$left + $right':
          plusE(parse(left),
                parse(right))
      | '$left * $right':
          multE(parse(left),
                parse(right))
      | 'max($left, $right)':
          maxE(parse(left),
               parse(right))
      | '$sym($arg, ...)':
          appE(syntax_to_symbol(sym),
               map(parse, syntax_to_list('[$arg, ...]')))
      | '($e)':
          parse(e)
      | ~else:
          error(#'parse, "invalid input: " +& s)

fun parse_fundef(s :: Syntax) :: FunDef:
  match s
  | 'fun $name($arg, ...): $body':
      fd(syntax_to_symbol(name),
         check_unique(map(syntax_to_symbol,
                          syntax_to_list('[$arg, ...]'))),
         parse(body))
  | ~else:
      error(#'parse, "invalid input: " +& s)

module test:
  check: parse('2')
         ~is intE(2)
  check: parse('2 + 1')
         ~is plusE(intE(2), intE (1))
  check: parse('3 * 4')
         ~is multE(intE(3), intE(4))
  check: parse('3 * 4 + 8')
         ~is plusE(multE(intE(3), intE(4)),
                   intE(8))
  check: parse('max(1, 9)')
         ~is maxE(intE(1), intE(9))
  check: parse('double(9)')
         ~is appE(#'double, [intE(9)])
  check: parse('1 + double(9)')
         ~is plusE(intE(1),
                   appE(#'double, [intE(9)]))
  check: parse('3 * (4 + 8)')
         ~is multE(intE(3),
                   plusE(intE(4), intE(8)))
  check: parse('1 2')
         ~raises "invalid input"

  check: parse_fundef('fun double(x): x + x')
         ~is fd(#'double, [#'x], plusE(idE(#'x), idE(#'x)))
  check: parse_fundef('fun f: 1')
         ~raises "invalid input"

  def double_def = parse_fundef('fun double(x): x + x')
  def quadruple_def = parse_fundef('fun quadruple(x): double(double(x))')

// check_unique ----------------------------------------
fun check_unique(syms :: Listof(Symbol)):
  match syms
  | []: []
  | cons(sym, rst_syms):
      if member(sym, rst_syms)
      | error(#'parse, "bad syntax, duplicate argument: " +& sym)
      | cons(sym, check_unique(rst_syms))

module test:
  check: check_unique([])
         ~is []
  check: check_unique([#'a, #'b, #'c])
         ~is [#'a, #'b, #'c]
  check: check_unique([#'a, #'b, #'b])
         ~raises "bad syntax"
  check: check_unique([#'a, #'b, #'a])
         ~raises "bad syntax"

// interp ----------------------------------------
fun interp(a :: Exp, defs :: Listof(FunDef)) :: Int:
  match a
  | intE(n): n
  | idE(s): error(#'interp, "free variable: " +& s)
  | plusE(l, r): interp(l, defs) + interp(r, defs)
  | multE(l, r): interp(l, defs) * interp(r, defs)
  | appE(s, args):
      block:
        def a_def = get_fundef(s, defs)
        if length(fd.args(a_def)) == length(args)
        | interp(substs(map(fun (arg): intE(interp(arg, defs)),
                            args),
                        fd.args(a_def),
                        fd.body(a_def)),
                 defs)
        | error(#'interp, "wrong arity")
  | maxE(l, r): max(interp(l, defs), interp(r, defs))
        
module test:
  check: interp(parse('2'), [])
         ~is 2
  check: interp(parse('x'), [])
         ~raises "free variable"
  check: interp(parse('2 + 1'), [])
         ~is 3
  check: interp(parse('2 * 1'), [])
         ~is 2
  check: interp(parse('(2 * 3) + (5 + 8)'), [])
         ~is 19
  check: interp(parse('max(2 * 3, 4 * 2)'), [])
         ~is 8
  check: interp(parse('double(8)'),
                [double_def])
         ~is 16
  check: interp(parse('quadruple(8)'),
                [double_def, quadruple_def])
         ~is 32
  check: interp(parse('quadruple(8, 9)'),
                [double_def, quadruple_def])
         ~raises "wrong arity"

// get_fundef ----------------------------------------
fun get_fundef(s :: Symbol, defs :: Listof(FunDef)) :: FunDef:
  match defs
  | []: error(#'get_fundef, "undefined function: " +& s)
  | cons(a_def, rst_defs):
      if s == fd.name(a_def)
      | a_def
      | get_fundef(s, rst_defs)

module test:
  check: get_fundef(#'double, [double_def])
         ~is double_def
  check: get_fundef(#'double, [double_def, quadruple_def])
         ~is double_def
  check: get_fundef(#'double, [quadruple_def, double_def])
         ~is double_def
  check: get_fundef(#'quadruple, [quadruple_def, double_def])
         ~is quadruple_def
  check: get_fundef(#'double, [])
         ~raises "undefined function"

// subst ----------------------------------------
fun subst(what :: Exp, for :: Symbol, in :: Exp):
  match in
  | intE(n): in
  | idE(s): (if for == s | what | in)
  | plusE(l, r): plusE(subst(what, for, l),
                       subst(what, for, r))
  | multE(l, r): multE(subst(what, for, l),
                       subst(what, for, r))
  | appE(s, args): appE(s, map(fun (arg):
                                 subst(what, for, arg),
                               args))
  | maxE(l, r): maxE(subst(what, for, l),
                     subst(what, for, r))

module test:  
  check: subst(parse('8'), #'x, parse('9'))
         ~is parse('9')
  check: subst(parse('8'), #'x, parse('x'))
         ~is parse('8')
  check: subst(parse('8'), #'x, parse('y'))
         ~is idE(#'y)
  check: subst(parse('8'), #'x, parse('x + y'))
         ~is plusE(parse('8'), idE(#'y))
  check: subst(parse('8'), #'x, parse('y * x'))
         ~is multE(idE(#'y), parse('8'))
  check: subst(parse('8'), #'x, parse('double(x)'))
         ~is parse('double(8)')
  check: subst(parse('8'), #'x, parse('max(x, y)'))
         ~is parse('max(8, y)')

// subst ----------------------------------------
fun substs(whats :: Listof(Exp), fors :: Listof(Symbol), in :: Exp):
  match whats
  | []: in
  | cons(what, rst_whats):
      subst(what,
            first(fors),
            substs(rst_whats,
                   rest(fors),
                   in))

module test:
  check: substs([], [], intE(0))
         ~is intE(0)
  check: substs([parse('8'), parse('9')], [#'x, #'y], parse('x + y'))
         ~is parse('8 + 9')

HW3

Difficulty: ★★☆☆

Part 1 — Booleans

Start with the interpreter with function values, and extend the implementation to support boolean literals, an equality test, and a conditional form:

  <Exp> = ....
        | #true
        | #false
        | <Exp> == <Exp>
        | if <Exp> | <Exp> | <Exp>

The == operator should only work on number values, and if should only work when the value of the first subexpression is a boolean. Report a “not a number” error if a subexpression of == produces a non-number value, and report a “not a boolean” error when the first subexpression of if does not produce a boolean. The if form should evaluate its second subexpression only when the first subexpression’s value is true, and it should evaluate its third subexpression only when the first subexpression’s value is false. The precedence of == should be lower than +, and if should have the lowest precedence like let.

Note that you not only need to extend Exp with new kinds of expressions, you will also need to add booleans to Value.

For example,

#true should produce a true value, while

if #true
| 1 + 2
| 5

should produce 3, and

if 1
| 2
| 3

should report a “not a boolean” error.

As usual, update parse to support the extended language.

More examples:

  check: interp(parse('1 + 2 == 3'),
                mt_env)
         ~is interp(parse('#true'),
                    mt_env)
  check: interp(parse('if 2 == 1 + 1 
                       | 7 
                       | 8'),
                mt_env)
         ~is interp(parse('7'),
                    mt_env)
  check: interp(parse('if #false 
                       | 1 + (fun (x): x) 
                       | 9'),
                mt_env)
         ~is interp(parse('9'),
                    mt_env)
  check: interp(parse('if #true 
                       | 10 
                       | 1 + (fun (x): x)'),
                mt_env)
         ~is interp(parse('10'),
                    mt_env)
  check: interp(parse('if 1 | 2 | 3'),
                mt_env)
         ~raises "not a boolean"

Part 2 — Hiding Variables

Add an unlet form (lowest precedence) that hides the nearest visible binding (if any) of a specified variable, but lets other bindings through. For example,

let x = 1:
  unlet x:
    x

should raise a “free variable” exception, but

let x = 1:
  let x = 2:
    unlet x:
      x

should produce 1. If there’s no visible binding of a variable around an unlet of the variable, the unlet does not hide anything (but it’s not an error).

As before, you must update the parse function.

Examples:

  check: interp(parse('let x = 1:
                         unlet x:
                           x'),
                mt_env)
         ~raises "free variable"
  check: interp(parse('let x = 1:
                         x + (unlet x:
                                1)'),
                mt_env)
         ~is interp(parse('2'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                            x + (unlet x:
                                   x)'),
                mt_env)
         ~is interp(parse('3'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                           let z = 3:
                              x + (unlet x:
                                     x + z)'),
                mt_env)
         ~is interp(parse('6'), mt_env)
  check: interp(parse('let f = (fun (z):
                                  let z = 8:
                                    unlet z:
                                      z):
                         f(2)'),
                mt_env)
         ~is interp(parse('2'), mt_env)

Part 3 — Thunks

A thunk is like a function of zero arguments, whose purpose is to delay a computation. Extend your interpreter with a delay form that creates a thunk, and a force form that causes a thunk’s expression to be evaluated:

  <Exp> = ....
        | delay: <Exp>
        | force(<Exp>)

A thunk is a new kind of value, like a number, function, or boolean. For parsing, delay has lowest precedence. The force form has a precedence like function calls, but it should be preferred by the parser over a function-call form, so it can be matched just before a function-call form in parse.

Examples:

delay: 1 + (fun (x): x)

produces a thunk value without complaining that a function is not a number, while

force(delay: 1 + (fun (x): x))

triggers a “not a number” error. As another example,

let ok = (delay: 1 + 2):
  let bad = (delay: 1 + #false):
    force(ok)

produces 3, while

let ok = (delay: 1 + 2):
  let bad = (delay: 1 + #false):
    force(bad)

triggers a “not a number” error.

More examples:

  check: interp(parse('force(1)'),
                mt_env)
         ~raises "not a thunk"
  check: interp(parse('force(if 8 == 8 | (delay: 7) | (delay: 9))'),
                mt_env)
         ~is interp(parse('7'),
                    mt_env)
  check: interp(parse('let d = (let y = 8:
                                  delay: y + 7):
                         let y = 9:
                           force(d)'),
                mt_env)
         ~is interp(parse('15'),
                    mt_env)

Note: In some languages, delay creates a promise. A promise is like a thunk, but when a promise is forced multiple times, the result from the first time is remembered and returned all the other times, so that the expression in a promise is evaluated at most once. We’re not concerned with that facet of delay and force, for now.

Solution

  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

#lang shplait

type Value
| intV(n :: Int)
| closV(arg :: Symbol,
        body :: Exp,
        env :: Env)
| boolV(v :: Boolean)
// We need to remember what was in the environment when thunk was defined.
// This is so that later defined variables will not override free variables inside thunk
// So each thunk will have it's own saved snapshot of environment
| thunkV(v :: Exp, env :: Env) 

type Exp
| boolE(v :: Boolean)
| compE(l :: Exp,
        r :: Exp)
| intE(n :: Int)
| idE(s :: Symbol)
| plusE(l :: Exp,
        r :: Exp)
| multE(l :: Exp,
        r :: Exp)
| letE(n :: Symbol,
       rhs :: Exp,
       body :: Exp)
| unletE(n :: Symbol,
         body :: Exp)
| funE(n :: Symbol,
       body :: Exp)
| appE(fn :: Exp,
       arg :: Exp)
| ifE(condition :: Exp,
      trueE :: Exp,
      falseE :: Exp)
| delayE(body :: Exp)
| forceE(body :: Exp)

type Binding
| bind(name :: Symbol,
       val :: Value)

type Env = Listof(Binding)

def mt_env = []
def extend_env = cons
fun remove_env(name :: Symbol, env :: Env):: Env:
  match env
  | []: []
  | cons(b, b_rest): if bind.name(b) == name:
                     | b_rest
                     | cons(b, remove_env(name, b_rest))
  

// parse ----------------------------------------
fun parse(s :: Syntax) :: Exp:
  cond
  | syntax_is_integer(s):
      intE(syntax_to_integer(s))
  | s == '#true':
      boolE(#true)
  | s == '#false':
      boolE(#false)
  | syntax_is_symbol(s):
      idE(syntax_to_symbol(s))
  | ~else:
      match s
      | 'delay: $body':
          delayE(parse(body))
      | 'force($body)':
          forceE(parse(body))
      | 'let $name = $rhs:
           $body':
          letE(syntax_to_symbol(name),
               parse(rhs),
               parse(body))
      | 'unlet $name:
           $body':
          unletE(syntax_to_symbol(name),
                 parse(body))
      | 'if $condition | $left | $right':
          ifE(parse(condition), parse(left), parse(right))
      | '$left == $right':
          compE(parse(left),
                parse(right))
      | '$left + $right':
          plusE(parse(left),
                parse(right))
      | '$left * $right':
          multE(parse(left),
                parse(right))
      | 'fun ($id): $body':
          funE(syntax_to_symbol(id),
               parse(body))
      | '$fn($arg)':
          appE(parse(fn),
               parse(arg))
      | '($e)':
          parse(e)
      | ~else:
          error(#'parse, "invalid input: " +& s)

module test:
  check: parse('2')
         ~is intE(2)
  check: parse('x')
         ~is idE(#'x)
  check: parse('2 + 1')
         ~is plusE(intE(2), intE (1))
  check: parse('3 * 4')
         ~is multE(intE(3), intE(4))
  check: parse('3 * 4 + 8')
         ~is plusE(multE(intE(3), intE(4)),
                   intE(8))
  check: parse('fun (x): 9')
         ~is funE(#'x, intE(9))
  check: parse('double(9)')
         ~is appE(idE(#'double), intE(9))
  check: parse('1 + double(9)')
         ~is plusE(intE(1),
                   appE(idE(#'double), intE(9)))
  check: parse('3 * (4 + 8)')
         ~is multE(intE(3),
                   plusE(intE(4), intE(8)))
  check: parse('let x = 1 + 2:
                  y')
         ~is letE(#'x,
                  plusE(intE(1), intE(2)),
                  idE(#'y))
  check: parse('1 2')
         ~raises "invalid input"

  check: parse('if 2 == 1 + 1
                | 7
                | 8')
         ~is ifE(compE(intE(2),plusE(intE(1),intE(1))), intE(7), intE(8))

// interp ----------------------------------------
fun interp(a :: Exp, env :: Env) :: Value:
  match a
  | intE(n): intV(n)
  | boolE(v): boolV(v)
  | compE(l, r): bool_equal(interp(l, env), interp(r, env))
  | idE(s): lookup(s, env)
  | plusE(l, r): num_plus(interp(l, env), interp(r, env))
  | multE(l, r): num_mult(interp(l, env), interp(r, env))
  | letE(n, rhs, body):
      def rhs_v = interp(rhs, env)
      interp(body,
             extend_env(bind(n, rhs_v),
                        env))
  | unletE(n, body):
      interp(body,
             remove_env(n, env))
  | funE(n, body): closV(n, body, env)
  | ifE(condition, l, r):
      match interp(condition, env)
      | boolV(v): if v:
                  | interp(l, env)
                  | interp(r, env)
      | ~else: error(#'interp, "not a boolean")
          
  | appE(fn, arg):
      match interp(fn, env)
      | closV(n, body, c_env):
          interp(body,
                 extend_env(bind(n, interp(arg, env)),
                            c_env))
      | ~else: error(#'interp, "not a function")
  | forceE(body):
      match interp(body, env)
      | thunkV(e, thunk_env): interp(e, thunk_env)
      | ~else: error(#'interp, "not a thunk")
  | delayE(body):
      thunkV(body, env)
      
      

module test:
  check: interp(parse('2'), mt_env)
         ~is intV(2)
  check: interp(parse('x'), mt_env)
         ~raises "free variable"
  check: interp(parse('x'),
                extend_env(bind(#'x, intV(9)), mt_env))
         ~is intV(9)
  check: interp(parse('2 + 1'), mt_env)
         ~is intV(3)
  check: interp(parse('2 * 1'), mt_env)
         ~is intV(2)
  check: interp(parse('(2 * 3) + (5 + 8)'), mt_env)
         ~is intV(19)
  check: interp(parse('fun (x): x + x'),
                mt_env)
         ~is closV(#'x, plusE(idE(#'x), idE(#'x)), mt_env)
  check: interp(parse('let x = 5: x + x'),
                mt_env)
         ~is intV(10)
  check: interp(parse('let x = 5:
                         let x = x + 1:
                           x + x'),
                mt_env)
         ~is intV(12)
  check: interp(parse('let x = 5:
                         let y = 6:
                           x'),
                mt_env)
         ~is intV(5)
  check: interp(parse('(fun (x): x + x)(8)'),
                mt_env)
         ~is intV(16)
  check: interp(parse('1(2)'), mt_env)
         ~raises "not a function"
  check: interp(parse('1 + (fun (x): x)'), mt_env)
         ~raises "not a number"
  check: interp(parse('let bad = (fun (x): x + y):
                         let y = 5:
                           bad(2)'),
                mt_env)
         ~raises "free variable"

  #//
  time:
    interp(parse('let x2 = (fun (n): n + n):
                    let x4 = (fun (n): x2(x2(n))):
                      let x16 = (fun (n): x4(x4(n))):
                        let x256 = (fun (n): x16(x16(n))):
                          let x65536 = (fun (n): x256(x256(n))):
                            x65536(1)'),
           mt_env)    
               
// num_plus and num_mult ----------------------------------------
fun num_op(op :: (Int, Int) -> Int, l :: Value, r :: Value) :: Value:
  cond
  | l is_a intV && r is_a intV:
      intV(op(intV.n(l), intV.n(r)))
  | ~else:
      error(#'interp, "not a number")
fun num_plus(l :: Value, r :: Value) :: Value:
  num_op(fun (a, b): a+b, l, r)
fun num_mult(l :: Value, r :: Value) :: Value:
  num_op(fun (a, b): a*b, l, r)

fun bool_op(op :: (Int, Int) -> Boolean, l :: Value, r :: Value) :: Value:
  cond
  | l is_a intV && r is_a intV:
      boolV(op(intV.n(l), intV.n(r)))
  | ~else:
      error(#'interp, "not a number")
fun bool_equal(l :: Value, r :: Value) :: Value:
  bool_op(fun (a, b): a == b, l, r)

module test:
  check: num_plus(intV(1), intV(2))
         ~is intV(3)
  check: num_mult(intV(3), intV(2))
         ~is intV(6)
  
// lookup ----------------------------------------
fun lookup(n :: Symbol, env :: Env) :: Value:
  match env
  | []: error(#'lookup, "free variable")
  | cons(b, rst_env):
      cond
      | n == bind.name(b):
          bind.val(b)
      | ~else:
          lookup(n, rst_env)

module test:
  check: lookup(#'x, mt_env)
         ~raises "free variable"
  check: lookup(#'x, extend_env(bind(#'x, intV(8)), mt_env))
         ~is intV(8)
  check: lookup(#'x, extend_env(bind(#'x, intV(9)),
                                extend_env(bind(#'x, intV(8)),
                                           mt_env)))
         ~is intV(9)
  check: lookup(#'y, extend_env(bind(#'x, intV(9)),
                                extend_env(bind(#'y, intV(8)),
                                           mt_env)))
         ~is intV(8)

  check: interp(parse('x + 3'),       
                extend_env(bind(#'x, intV(2)),
                           mt_env))
         ~is intV(5)


// Part 1
module test:
  check: interp(parse('1 + 2 == 3'),
                mt_env)
         ~is interp(parse('#true'),
                    mt_env)
  check: interp(parse('if 2 == 1 + 1 
                       | 7 
                       | 8'),
                mt_env)
         ~is interp(parse('7'),
                    mt_env)
  check: interp(parse('if #false 
                       | 1 + (fun (x): x) 
                       | 9'),
                mt_env)
         ~is interp(parse('9'),
                    mt_env)
  check: interp(parse('if #true
                       | 10 
                       | 1 + (fun (x): x)'),
                mt_env)
         ~is interp(parse('10'),
                    mt_env)
  check: interp(parse('if 1 | 2 | 3'),
                mt_env)
         ~raises "not a boolean"
  check: interp(parse('if #true == 5 | 6 | 7'),
                mt_env)
         ~raises "not a number"
  check: interp(parse('if (5 == 6) == 5 | 6 | 7'),
                mt_env)
         ~raises "not a number"

// Part 2
module test:
  check: interp(parse('let x = 1:
                         unlet x:
                           x'),
                mt_env)
         ~raises "free variable"
  check: interp(parse('let x = 1:
                         x + (unlet x:
                                1)'),
                mt_env)
         ~is interp(parse('2'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                            x + (unlet x:
                                   x)'),
                mt_env)
         ~is interp(parse('3'), mt_env)
  check: interp(parse('let x = 1:
                         let x = 2:
                           let z = 3:
                              x + (unlet x:
                                     x + z)'),
                mt_env)
         ~is interp(parse('6'), mt_env)
  check: interp(parse('let f = (fun (z):
                                  let z = 8:
                                    unlet z:
                                      z):
                         f(2)'),
                mt_env)
         ~is interp(parse('2'), mt_env)
  check: interp(parse('unlet x:
                         x'), mt_env)
         ~raises "free variable"

// Part 3
module test:
  check: interp(parse('force(1)'), mt_env)
         ~raises "not a thunk"
  check: interp(parse('force(if 8 == 8 | (delay: 7) | (delay: 9))'), mt_env)
         ~is interp(parse('7'), mt_env)
  check: interp(parse('let d = (let y = 8:
                                  delay: y + 7):
                         let y = 9:
                           force(d)'),
                mt_env)
         ~is interp(parse('15'),
                    mt_env)
  // Got some of these from discord
  check: interp(parse('let add = (fun (y): delay: x+y):
                         let x = 5:
                           force(add(5) + 10)'), mt_env)
         ~raises "not a number"
  check: interp(parse('let d = (let y = 1:
                                  delay: x + y + 2):
                         let x = 3:
                           force(d)'), mt_env)
         ~raises "free variable"
  check: interp(parse('delay: 1 + (fun (x): x)'), mt_env)
         ~is thunkV(plusE(intE(1), funE(#'x, idE(#'x))), mt_env)
  check: interp(parse('let add = (fun (y): delay: x+y):
                         let x = 5:
                           force(add(5) + 10)'), mt_env)
         ~raises "not a number"
  check: interp(parse('let x = (if 0 == 1 | 1 | 2):
                         3'), mt_env)
         ~is interp(parse('3'), mt_env)
  check: interp(parse('let x = (if 0 | 1 | 2):
                         3'), mt_env)
         ~raises "not a boolean"

HW4

Difficulty: ★★★★

Part 1 — Improving Assignment

Start with store_reslet.rhm. In the starting program, the representation of the store grows every time that a box’s content is modified with set_box. Change the implementation of set_box so that the old value of the box is dropped (i.e., replaced with the new value) instead of merely hidden by the outside-in search order of fetch.

Example:

check: interp(parse('let b = box(1):
                         begin:
                           set_box(b, 2)
                           unbox(b)'),
                mt_env,
                mt_store)
         ~is res(intV(2),
                 override_store(cell(1, intV(2)),
                                mt_store))

Part 2 — Sequences

Generalize begin to allow one or more sub-expressions, instead of exactly two sub-expressions.

  <Exp> = ....
        | begin:
            <Exp>
            <Exp>
            ...

Example:

check: interp(parse('let b = box(1):
                         begin:
                           set_box(b, 2 + unbox(b))
                           set_box(b, 3 + unbox(b))
                           set_box(b, 4 + unbox(b))
                           unbox(b)'),
                mt_env,
                mt_store)
         ~is res(intV(10),
                 override_store(cell(1, intV(10)),
                                mt_store))

A note on pattern matching: To match a begin form with one or more expressions, each on its own line, you can use this Shplait pattern:

   'begin:
     $exp0
     $exp
     ...'

After matching that pattern, exp0 stands for one line/group, and exp is a sequence of additional lines/groups. Although the exp repetition is created from separate lines, the repetition doesn’t have to be used in a template as different lines. You can use syntax_to_list('[$exp0, $exp, ...]') to put the matches together in a list syntax object and convert it to a list of syntax objects.

A tip on dealing with nonempty lists: As you know, a list has two cases: [] and cons(<item>, <list>). A nonempty_list has two different cases: it is always a cons pair and its rest may or may not be empty. A match cannot easily follow the shape of nonempty lists (it needs a case for [] and a nested match), so we recommend cond instead, which can check for the first nonempty-list case with the test is_empty(rest(nonempty_list)).

Part 3 — Records

Extend the interpreter to support the construction of records with named fields, to support field selection from a record (as in record.rhm):

  <Exp> = ....
        | {<Sym> : <Exp>, ...}
        | <Exp> . <Sym>

Adding records means that the language now has four kinds of values: numbers, functions, boxes, and records. At run-time, an error may occur because a record is misused as a number or function, a number or function is supplied to ., or a record supplied to . does not have the named field, and so on. Your error message for the last case should include the words “no such field”, but beyond that constraint, you can make up your own error messages.

Expressions within a {} form should be evaluated when the {} form itself is evaluated, and in the order that the expressions appear in the {} form. For example,

let b = box(0):
    let r  = { a: unbox(b) }:
      begin:
        set_box(b, 1)
        r.a

should produce 0, not 1, because unbox(b) is evaluated when the {} expression is evaluated, not when the . expression is evaluated.

Note that you will not be able to use map to interp field values, since a store must be carried from one field’s evaluation to the next. Instead, interping the field value will be more like interping a sequence of expressions for begin.

You can assume (without checking) that all field names in a {} form are distinct.

For homework purposes, we don’t want to nail down the representation of a record value, because there are many choices. The examples below therefore use interp_expr, which you must define as a wrapper on interp that takes just an Exp and produces just a syntax object: a syntax number if interp produces any number, the syntax object 'function' if interp produces a closure, the syntax object 'box' if interp produces a box, or the syntax object 'record' if interp produces a record value.

Examples:

check: interp_expr(parse('1 + 4'))
         ~is '5'
check: interp_expr(parse('{ a: 10, b: 1 + 2 }'))
         ~is 'record'
check: interp_expr(parse('{ a: 10, b: 1 + 2 }.b'))
         ~is '1'
check: interp_expr(parse('{ a: 10 }.b'))
         ~raises "no such field"
check: interp_expr(parse('{ r : { z: 0 } }.r'))
         ~is 'record'
check: interp_expr(parse('{ r : { z: 0 } }.r.z'))
         ~is '0'
check: interp_expr(parse('let b = box(0):
                              let r  = { a: unbox(b) }:
                                begin:
                                  set_box(b, 1)
                                  r.a'))
         ~is '0'

Part 4 — Mutating Records (extra credit for CS 3520; required for CS 6520)

This exercise is required for CS 6520 students, but it counts as extra credit for CS 3520 students.

Add an assignment form that modifies the value of a record field imperatively (as opposed to functional update):

  <Exp> = ....
        | <Exp> . <Sym> := <Exp>

Evaluation of a {} expression allocates a location for each of its fields. A . expression without := accesses from the record produced by the sub-expression the value in the location of the field named by the identifier. A . with := form changes the value in the location for a field; the value of the sub-expression after := determines the field’s new value, and that value is also the result of the assignment expression.

Note: Making record fields mutable has the same effect as forcing every field of a record to be a Moe box, where the box contains the proper value of the field. Internal to the interpreter implementation, you could use Moe boxes in your implementation of mutable records, or you could use addresses more directly. You should not use Shplait boxes at all.

Examples:

check: interp_expr(parse('let r = { x: 1 }:
                          r.x'))
         ~is '1'

check: interp_expr(parse('let r = { x: 1 }:
                          begin:
                            r.x := 5
                            r.x'))
         ~is '5'

check: interp_expr(parse('let r = { x: 1 }:
                          let get_r = (fun (d): r):
                            begin:
                              (get_r(0)).x := 6
                              (get_r(0)).x'))
         ~is '6'

check: interp_expr(parse('let g = (fun (r): r.a:
                          let s = (fun (r): fun (v): r.b := v:
                            let r1 = { a: 0, b: 2 }:
                              let r2 = { a: 3, b: 4 }:
                                r1.b + (begin:
                                         s(r1)(g(r2))
                                         (begin:
                                           s(r2)(g(r1))
                                           r1.b) + r2.b)'))
         ~is '5'

Solution