2 A2: Primitives and Conditionals
In a forgotten corner of an old electronics lab, an outdated hardware processor sat, long unused and gathering dust. Once a cutting-edge piece of technology, it had now become a relic of the past. The processor, though old, was still functional — its circuits quietly capable, but it had a very limited range of operations. It could only handle 8-bit signed integers, and it was restricted to performing basic integer and boolean operations.
Despite these limitations, the processor had one remarkable strength: it excelled at handling programs with many branches, quickly jumping between different paths in a program. But to use it effectively, a new programming language was needed—one that could work within its constraints and take advantage of its unique ability to handle complex branching efficiently. The challenge was clear: how could a programmer write code that would unlock the full potential of this old processor?
The goal of this assignment is to extend the Con language to support these features. We will call this language Con+. This will require you to change the language in a similar fashion as we have been doing in class.
You are given a zip file on Canvas hw2.rkt with a starter code for the assignment. This is same as the code for the Defend: Handling Errors language from class. You should add your own test cases to ensure your submission is correct. You are tasked with extending the language to Con+ in the following ways:
Change the representation of numbers so that denotes only signed 8-bit numbers
Add few unary and binary primitive operations in the language,
Add conditional evaluation with cond
You have to submit one language implementation with all these changes, and not multiple languages.
2.1 New representation of numbers
This processor only supports 8-bit signed integers. You have to change Con such that it only operate on numbers in this range:
Signed 8-bit integers are only integers in the range of -128 to 127 (both inclusive).
Arithmetic operations such as +, -, * and / operate like standard arithmetic when the results are in this range.
If any result overflows or underflows this range, it wraps around.
Any integer values outside this range are not allowed in the language.
For example, a program 345 is not a valid program in our Con+ language. Programs that overflow such as:
(+ 125 6)
yields the value -125. Similarly, for underflow:
(- -120 32)
yields 104.
To do this, you should:
Extend hw2.rkt to update the semantics for these expressions such that values wraparound correctly;
And, add tests in hw2.rkt and run it to see if your programs reflect the above semantics.
2.2 New primitive operations
Add the following forms of expression to the language:
(or e e): (or e1 e2) means e1 if e1 does not mean #f, else (or e1 e2) means the same as e2.
(not e): compute the logical negation of e. Negation of #f is #t, negation of any other value is #f.
(% e e): (% e1 e2) means the remainder when dividing e1 by e2. The Racket builtin remainder will be useful.
To do this, you should:
Extend hw2.rkt to add the semantics for these expressions;
And, add tests in hw2.rkt and run it to see if your programs reflect the above semantics.
2.3 Conditional evaluation with cond
The Con language has a simple form of performing conditional evaluation of subexpressions:
(if e1 e2 e3)
However, in the original paper on Lisp, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, John McCarthy introduced a generalization of if called “conditional expressions,” which we will be better suited for this processor. We could add it to our language with the following syntax:
(cond [e-p1 e-a1] [e-p2 e-a2] ... [else e-an])
A cond expression has any number of clauses [e-pi e-ai] …, followed by an else clause [else en]. For the purposes of this assignment, we will assume every cond expression ends in an else clause, even though this is not true in general. Any cond-expression that does not end in else will result in a parser error.
The meaning of a cond expression is computed by evaluating each expression e-pi in order until the first one that does not evaluate to #f is found, in which case, the corresponding expression e-ai is evaluated and its value is the value of the cond expression. If no such e-pi exists, the expression e-an’s value is the value of the cond.
Let us understand this with an example:
The above program first checks if (zero? (- 6 5)). As this evaluates to #f, it goes to the 2nd conditional expression (<= 6 7). As this condition evaluates to #t, the entire meaning of this cond expression is 2 and no further conditional arms (including else) are evaluated. The else branch is evaluated if no other condition holds.
To implement this, you should:
Update hw2.rkt to correctly interpret cond expressions;
And, add tests in hw2.rkt and run it to see if your programs reflect the semantics of cond.
2.4 Testing
You should test your code by writing test cases and adding them to relevant files. Use the command raco test hw2.rkt to test your code. Alternatively, pressing “Run” in Dr. Racket will also run your test cases. There are few test cases already included in hw2.rkt. These are by no means exhaustive, and you should add your own test cases to check your interpreter is correct.
For grading, your submitted interpreter will be tested on multiple programs drawn from this language. Writing your own test cases will give you confidence that your interpreter can handle previously unseen programs.
2.5 Submitting
You should submit on Gradescope. You should submit only one file: hw2.rkt for grading, so make sure all your work is contained there! You may add any function you need to these files, but do not rename the file or the interp function.