COS 371: Programming Languages
Spring 2022
proj7: Primitives
Due: Wednesday, 05/04 at 22:00
1. Goals
To support applying Scheme primitive functions implemented in C; to implement a few primitive functions.2. Introduction
In the previous checkpoint, you implemented the evaluation of lambda expressions, allowing you to create functions within Scheme. Scheme also has primitive functions, which are "built-in" functions that are not written in Scheme themselves. In this checkpoint, implement the framework for supporting primitive functions. Also, implement a few primitive functions to make sure the framework is working; many more primitive functions are to be implemented later.3. Tasks
-
Extend your collection with at least 4 pairs of test files to test the functionality specified in this checkpoint.
(More is better!)
As before, each pair of files should be named
test.eval.input.XX
andtest.eval.output.XX
, whereXX
is a test number. -
Add
PRIMITIVE_TYPE
tovalue.h
to support primitive functions. The value of a primitive functionValue
is a pointer to a function in C. For example, the C function implementing the Scheme primitive+
might look like this:Value *primitiveAdd(Value *args) { // error checking on args, a list of inputs // compute the result as a single value return [the single value]; }
In general, a primitive function implementation takes aValue *
(a list of arguments) as input and returns aValue *
(a single value) as output. The C syntax to express this is fairly nasty:struct Value { valueType type; union { int i; ... /* A pointer to a C implementation of a Scheme primitive function. * Note: `pf' is the variable name I chose for the function pointer. */ struct Value *(*pf)(struct Value *); } }
-
Update
apply
to handle primitive functions. For example:Value *apply(Value *function, Value *args) { ... if (function->type == PRIMITIVE_TYPE) { return (function->pf)(args); } else { ... } }
-
Implement a few primitive functions themselves:
+
,null?
,car
,cdr
, andcons
. See notes below. -
Bind these primitives in the top-level environment.
For example:
void bind(char *name, Value *(*function)(Value *), Frame *frame) { Value *value = makeNull(); value->type = PRIMITIVE_TYPE; value->pf = function; frame->bindings = ... ... } void interpret(Value *tree) { ... Frame *top = makeFrame(NULL); bind("+", primitiveAdd, top); bind("null?", primitiveIsNull, top); ... }
-
Modify your
Makefile
to compile your new interpreter code, if necessary. When I'm in your directory and I execute the commandmake interpreter
, I should get an executable file calledinterpreter
in that directory.
4. Specification
Support the correct application of various Scheme primitive functions.-
+
must handle any number of numerical (integer or float) arguments. (If zero arguments, return0
.) The correct return type is an integer if all arguments are integers, and a float if any argument is a float. -
null?
,car
, andcdr
each takes one argument. Do error checking to make sure that is the case. Similarly, check to make sure that the argument is appropriately typed. -
cons
takes two arguments. Again, do error checking. You'll also need to modify the code you have that handles output, because cons allows you to create non-list (dotted) pairs.(cons 1 (cons 2 3)) (cons (cons 1 2) 3) (cons 1 (cons 2 (cons 3 (quote ()))))
should evaluate to(1 2 . 3) ((1 . 2) . 3) (1 2 3)
In particular, I strongly prefer that you do not output the list(1 2 3)
as the equivalent(1 . (2 . (3 . ())))
after making these modifications.
When you are done, you should be able to handle a test like this one:
(define length (lambda (lst) (if (null? lst) 0 (+ 1 (length (cdr lst)))))) (length (quote ())) (length (quote (4 5 6))) (define append (lambda (lst1 lst2) (if (null? lst1) lst2 (cons (car lst1) (append (cdr lst1) lst2))))) (append (quote (4 5)) (quote (6 7))) (define reverse (lambda (lst) (if (null? lst) lst (append (reverse (cdr lst)) (cons (car lst) (quote ())))))) (reverse (quote ())) (reverse (quote (1 2 3 4))) (reverse (quote (("computer" "science") "is" "awesome")))
5. Possible extensions
- Support infinite precision for integers and integer addition.
An
int
in C has a fixed size in memory and therefore its value is bounded in magnitude. Scheme's integer, in constrast, is not bounded by specification, and can grow arbitrarily large in theory. (In practice, it is obviously limited by the physical machine's memory.) Create aBigInt
struct that can prepresent arbitrarily large integers (untilmalloc
fails to return more memory). AddBigInt
as a type ofValue
, and switch toBigInt
in+
when necessary (or when tokenizing very large numbers). - Support dotted-pair notation for input, such as
(cdr (quote (1 2 . 3)))
. You will likely need to modify your tokenizer.
6. Submission
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using Valgrind. We will be checking this during grading, so you should test your code via Valgrind yourself.
Follow the submission instructions from the previous checkpoint;
tag your commit with proj7
and push the tag to GitHub.
This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Laura Effinger-Dean, and Jed Yang.
Start early, have fun, and discuss questions on Moodle.