Project 06

Purpose:
	In this phase we complete the construction of the calculator language interpreter by adding a handful of key features and upgrading its data types. What has the language been missing? What keeps us from writing useful programs in it? The answer is simple: Conditional Evaluation Without conditional evaluation, our language can't really be said to be a programming language. It is just a simple macro-expression language. With it, though, it becomes the real thing. (An argument has been made that what really distinguished ENIAC from its predecessors, what made it a computer, rather than a calculator, was the fact that it had a conditional branch instruction.) In this phase we will add conditional evaluation, sequencing, a print statement, and, to round things out, strings as a data type.
Strings as a Datatype
	The lowest level change to the language involves the incorporation of strings as a datatype. To this end, the datatype ConcreteSyntax.number has been replaced with ConcreteSyntax.literal, with three constructors: Int, Real, and String. Similarly, the Number constructor has been replaced with Literal, and all the functions in ConcreteSyntax have been appropriately renamed and modified. Note that when ConcreteSyntax.literal_to_string converts a String literal, it includes double quotes around the underlying string to make the type clear. In order to incorporate this change into the inerpreter, you will need to make various changes in SyntaxConverter, and Evaluator. (In particular, datavalue will now need to be defined as ConcreteSyntax.literal instead of as ConcreteSyntax.number.) The only binary operator to be defined on string literals is '+' which will be overloaded as numeric addition (when it is given a pair of numbers) and as string concatenation (when it is given a pair of strings). In addition, you should implement a new unary built-in called makestring which converts its argument to a string. This operator should accept all three types of literals, but should be a no-op on String literals. (Thus you can't just blindly use ConcreteSyntax.literal_to_string since it would add quotes.) These two changes (along with others described below) will likely require a fair number of changes to the evaluation of applications of built-in operators.
Write and Newline
	You must add a new unary operator write defined at all object types. (By object type I mean types in the object language, the one we are implementing, as opposed to the types of the meta language we are using for the implementation.) When printing strings, do not include quotes around the string. To allow for full generality, the write operator should leave the cursor at the end of the output, and not advance to the next line. Therefore, you should also define the zero-ary operator newline. The write operator should return as its value whatever it is given as its argument, while the newline operator should return the empty String literal. While we could require writeln as a built-in variant of write, this is not necessary as the user can define it (using the sequence construct described below) as: (defun (writeln x) (sequence (write x) (newline)))
Conditonal Evaluation
	In eager languages, conditional evaluation is what is known as a special form. That is, while it will look just like the other built-in operators from a syntactic standpoint, it will require a different operational behavior. Unlike the ordinary built-in operators, this one does not necessarilly evaluate all of its arguments. Instead a prescribed procedure is used to determine which arguments are actually evaluated. The form of conditional evaluation we will include in the language is the cond expression from lisp. It can be seen as a generalization of a case statement, or of the if-then-else-if statement. The syntax of the expression is: (cond (test_1 result_1) (test_2 result_2) ... (test_n result_n)) The operational semantics (i.e. what the system does when it encounters this expression) are as follows: Evaluate the first element of the first argument pair. If that expression evaluates to a non-zero value (as outlined below) then evaluate the second expression in the pair and return its value as the value of the conditional expression. If, on the other hand, the first expression evaluates to zero (as outlined below) then the second expression in the pair is discarded unevaluated, and the process repeats with the next pair. If the last pair is reached and none of the pairs has a test expression that evaluates non-zero then the value of the whole conditional expression is (Int 0). Note that the test expressions can be of any type, so we must have a suitable notion of "zero" at each object type. Therefore we will assume that the following are all "zero" for the purposes of deciding whether to evaluate the other expression in the pair: (Int 0), (Real 0.0), and (String "") (the empty string). In order to distinguish this structure from an ordinary application, a new case has been added to the definition of the datatype AbstractSyntax.cexp: | Ccond of (cexpression * cexpression) list You must modify SyntaxConverter to recognize cond expressions and convert them to this special form. Then add the appropriate code for evaluating them to Evaluator.evaluate_cexpression. Note that AbstractSyntax.cexpression_to_string has already been updated to recognize them.
Relational Operators
	In order to make the conditional statement useful, you need some test expressions. To that end, you should support the following relational operators: <, <=, >, >=, =, <>. Values of the two numeric types should be able to be compared to one another, but strings can only be compared to other strings. (String comparison should just be based on the underlying string comparison function from ML.) Whatever the types of the arguments, the operators should return (Int 1) if the test is true, and (Int 0) if it is false. Note, these are just ordinary built-in operators. They are not new special forms. Also, we are not saying these are the only operators that can be used to construct test expressions. Any expression can be used as the first expression in a cond pair. It is just that we will need these for many applications. (In later projects we will change our notion of "true" and "false" as our data types get richer. Therefore, you may find it useful to define vals for "TRUE" and "FALSE", and a test function isFalse so as to make the change more modular and easier to implement.)
Sequencing
	As shown above, with the addition of side effects to the language, it is natural to add a notion of sequencing. Strictly speaking it is not necessary to add a new special form for this to the language, since function application can be used to accomplish the desired efects. For example, if we knew that the arguments to a function were always evaluated left to right, we could define the writeln function above as: (defun (writeln_aux foo bar) bar) (defun (writeln x) (writeln_aux (write x) (newline))) Even if we did not know the order of evaluation of function arguments, eager evaluation imparts an ordering to nested applications. So, we could define it as: (defun (writeln_aux foo) (newline)) (defun (writeln x) (writeln_aux (write x))) Nevertheless, to avoid such machinations, it is useful to add a syntax for sequencing to the language, and to implement it as a special form. The syntax you are to support is: (sequence exp_1 exp_2 ... exp_n) This syntax should be mapped (in SyntaxConverter) to the following new case that has been added to AbstractSyntax.cexp: | Cseq of cexpression list and evaluated in the way they are in ML. That is, a sequence should evaluate each of the individual expressions in order, and return the value of the last expression as the value of the sequence.
What You Should Turn In
	Only the evaluator and the syntax converter get appreciable changes in this phase. Therefore, you should submit a single file with the functors SyntaxConverterFun and EvaluatorFun. They will be linked with the interpreter from the sample solution to the last phase.

	This page copyright ©1998 by Joshua S. Hodas. It was built on a Macintosh. Last rebuilt on Fri, Apr 9, 1999 at 3:10 PM.
http://cs.hmc.edu/~hodas/courses/cs131/projects/project06.html