View on GitHub

CS374

Principles of Programming Languages

CS374: Principles of Programming Languages - The Interpreter (100 Points)

Purpose, Task, and Criteria

Purpose: To read a small working interpreter written in Flex and Bison, and to change its evaluator, scanner, and grammar, so that you can see how the pieces of a language fit together.

Task: Build and run a given Scheme interpreter, answer three questions about how it works, and make three targeted changes to it: a new primitive, a new shorthand in the scanner and grammar, and a new special form.

Criteria: I grade this on accurate answers about how the interpreter works, and on three changes that work without breaking the provided programs. The rubric below breaks this down in full.

Assignment Goals

The goals of this assignment are:

To explain how a scanner, a grammar, and an evaluator work together in a small interpreter
To add a primitive function to an interpreter
To add syntax through the scanner and the grammar
To add a special form, and to explain why it cannot be a function

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

In this assignment you read a small working interpreter and change it. You get a Scheme written in Flex, Bison, and C, about 300 lines in all, and you add to it in three small steps. Everything is in the starter kit, and nothing depends on any earlier assignment.

Before You Start

You need flex, bison, gcc, and make. On Ubuntu, sudo apt install flex bison gcc make installs them. Make a folder named cs374-interpreter, and copy the starter kit into it.

Part 1: Build It, Run It, and Read It

You write: notes.md. You run: make, from inside your folder.

Build it and run the two provided programs. make runs bison -d parser.y, flex scanner.l, and gcc, so you only have to run it again after a change. The interpreter reads a program from standard input, and it prints the value of each expression at the top level:

make
./scheme < programs/basics.scm
./scheme < programs/functions.scm

You should see.
7
9
(a b c)
2
120
7
(4 5 6)

From Calculator to Scheme builds this same evaluator in Python, and C for Flex and Bison covers the C it is written in: structs, ->, switch, and the table of functions.

Read these three files in this order, because each change below touches a different one:

scanner.l turns characters into tokens: numbers, symbols, #t, #f, and parentheses.
parser.y turns tokens into Scheme data. A list in the source becomes a linked list of Values, built with cons in the items rule. Scheme code and Scheme data are the same thing, so the parser needs no other structure. The program rule evaluates each item as soon as it is read.
scheme.c holds the evaluator. In eval, a number evaluates to itself and a symbol is looked up. A list is either a special form, which decides for itself what to evaluate, or a call, which evaluates everything and then applies the function. lookup walks a linked list of scopes, and a call makes a new scope whose parent is the scope where the function was created. That parent link is why adder in functions.scm works.

Do this. Answer these in notes.md. The answers are short, and each one points you at a part of the code.

Trace (+ 1 (* 2 3)) through eval. Which case handles the outer list, in what order are its parts evaluated, and what does apply receive?
Why is if a special form in eval, when + is a primitive? What would go wrong with (if (= n 0) 1 (fact (- n 1))) if if were a primitive?
In functions.scm, add3 is called after adder has already returned. How does lookup still find a? Name the two scopes on the chain.

Part 2: Add a Primitive, `max`

A primitive is a function written in C, and the table of functions shows the pattern on another example. It receives its evaluated arguments as a list, and first(a) and second(a) read them. So adding one takes two lines in scheme.c: a function next to prim_add, and a row in the PRIMITIVES table. Write prim_max, which returns the larger argument, and add its row under the name max.

make && printf '(max 3 7)\n(max (+ 5 5) 7)\n' | ./scheme

You should see. 7, then 10. The arguments are evaluated before your function runs, which is why (+ 5 5) arrives as 10.

Part 3: Add a Shorthand, `'`

Scheme programmers write 'x for (quote x), and Step 5: Quote explains what quote does. The evaluator already handles quote, so this change lives only in the scanner and the grammar.

In scanner.l, the last rule catches a stray ' as an error, and it is the only character that rule can still reach. Replace that rule with one that returns the character:
```
"'"     { return '\''; }
```

In parser.y, add a rule to datum that builds the same list the long form would build:

| '\'' datum   { /* TODO: $$ is the list (quote <datum>), built with cons, make_symbol, and nil */ }

make && printf "'(a b c)\n(car '(1 2))\n" | ./scheme

You should see. (a b c), then 1.

Part 4: Add a Special Form, `cond`

Step 4: If shows why if is a special form, and cond has to be one for the same reason: a call would evaluate every clause, and cond must evaluate only the one it chooses. It looks like this:

(cond (test1 expr1) (test2 expr2) ...)

Add it to eval in scheme.c, next to if. Here is the algorithm, and x->cdr is the list of clauses:

for each clause c in x->cdr:
    if is_true(eval(first(c), env)):
        return eval(second(c), env)
report an error, with die, that no clause matched

make && printf '(define sign (lambda (n) (cond ((< n 0) -1) ((= n 0) 0) (#t 1))))\n(sign -5)\n(sign 0)\n(sign 9)\n' | ./scheme

You should see. -1, 0, and 1. Then run the two provided programs again, and confirm their output has not changed.

Deliverables

Submit a ZIP of your cs374-interpreter folder, with the build products removed (make clean), containing notes.md and the interpreter with your three changes.

Self-Check Before You Submit

make clean && make shows no warnings.
max, ', and cond work.
Both provided programs give the same output as before your changes.

Reflection Prompts

Each change touched a different file. How did you decide where each one belonged?
' needed no change to eval. What does that tell you about the difference between syntax and meaning?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file.

If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague.

In your README, please include answers to the following questions:

Describe what you did, how you did it, what challenges you encountered, and how you solved them.
Please answer any questions found throughout the narrative of this assignment.
If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).
Please describe any use of outside resources you may have engaged in the completion of this assignment, including the use of generative Artificial Intelligence.

Assignment Rubric

Description	Pre-Emerging (< 50%)	Beginning (50%)	Progressing (85%)	Proficient (100%)
Reading the Interpreter (Goal 1) (25%)	The interpreter was not built, or the questions are not answered	One question is answered accurately	Two questions are answered accurately, or all three with a mistake in the trace	The trace of an evaluation is accurate, the answer says why `if` is a special form, and the answer follows the scope chain for `adder` through the parent link
A New Primitive (Goal 2) (25%)	No primitive is added	The function is written, but it is not in the table or does not run	The primitive runs but returns a wrong value in some case	`max` returns the larger of its two evaluated arguments, and it is added with one function and one table row
A New Shorthand (Goal 3) (25%)	The shorthand is not added	The scanner or the grammar is changed, but not both	The shorthand works on a symbol or a list but not both, or the build reports warnings	`'x` reads as the list `(quote x)` for any datum, and the build has no conflict or scanner warnings
A New Special Form (Goal 4) (25%)	The form is not added	The form is added but evaluates every clause, or it crashes	The form chooses correctly, but a case with no matching clause is not reported	`cond` evaluates tests in order and only the chosen expression, reports an error when no clause matches, and the provided programs give the same output as before

Please refer to the Style Guide for code quality examples and guidelines.