The Imperative Core Language (ImpCore) extends Expression Language 1 by adding assignment, while, write, and block expressions. The source code is linked to the Files subsection below.
As exercises, we will extend use ImpCore and extend it in various ways.
Assignment #2 is built around this case study. The assignment requires use and extension of the interpreter whose source code is linked into the Files section below.
For convenience in parsing, we choose a (Lisp-like) parenthesized prefix syntax relatively close to the abstract syntax used by our family of interpreters. The grammar for ImpCore extends the prefix grammar we used for Expression Language 1 by adding the four new types of expressions.
In the following BNF grammar, all words beginning with capital letters are nonterminals. The BNF metasymbols are ::= to show derivation rules for nonterminals, | for alternatives, { and } enclosing optional items, ^* for zero or more repetitions, and ^+ for one or more repetitions. All other words (e.g., while) and symbols (e.g., the left and right parentheses and operators such as +) are literals.
Exp ::= Value | (Op1 Exp) | (Op2 Exp Exp)
| ( := Variable Exp )
| ( if Exp Exp Exp)
| ( while Exp Exp )
| ( write Exp )
| ( block Exp^* )
Value ::= Number | Variable
Op1 ::= neg
Op2 ::= + | - | * | / | == | ~= | < | > | <= | >=
Variable ::= Leading alphabetic or underscore followed by zero or
more alphabetic, numeric, or underscore characters
Number ::= One or more decimal digits with optional leading -Variables cannot be keywords in the grammar (neg, if, while, write, block, etc.) or REPL command interface (quit). Command quit typed to the REPL's prompt terminates the program.
Also, a semicolon ; causes the rest of that line to be ignored by the parser (i.e., is an end-of-line comment).
The semantics of ImpCore expressions builds on the semantics of the Expression Language 1 expressions by adding assignment (:=), while, write, and block expressions. (Expression Language 1 consists of the language from Assignment #1 including all four arithmetic operations, all six relational expression, and if. It does not include the min and max operations from that assignment.)
As with Expression Language 1, the value space consists of the integers. (Of course, Lua 5.2 and earlier represents all numbers in double precision floating point, but with most hardware platforms, integers are exact to 53 bits.)
The interpreter represents the Boolean value "false" by integer 0 and "true" by nonzero values, canonically by the value 1.
The semantics (meaning) of the various ImpCore expressions are as follows. Unless otherwise noted, an expresion has the same meaning as in Expression Language 1.
Number returns the integer value of the decimal literal. (That is, 12 returns the integer value twelve.)
Variable returns the integer value associated with that variable name in the current environment. If the variable does not occur in the current environment, then its value is undefined.
Note: This interpreter only supports global variables currently.
(:= v e) is a new feature of ImpCore. It first evaluates expression e, then it assigns the resulting value to the variable named v in the current environment and also returns the value.
If variable v already exists, the assignment changes its value; otherwise, the assignment dynamically creates a new variable named v. (These work a lot like global variables in Lua.)
A subsequent reference to variable v in an expression gets the most recently assigned value of v. That is, assignment is an expression whose evaluation has the side effect of changing the environment.
(if e1 e2 e3) first evaluates expression e1, the condition test. If the expression is true, then the if evaluates and returns expression e2; otherwise, the if evaluates and returns expression e3. The interpreter evaluates only one of e2 and e3.
(while e1 e2) is a new feature of ImpCore. It first evaluates expression the expression e1. If e1 evaluates to false, then the while returns 0. Otherwise, the while evaluates the body expression e2, then reevaluates e1. It repeats this until e1 evaluates to false.
A while always returns 0, but e2 usually includes side effecting subexpressions such as := or write.
(block e1 ...en) is a new feature of ImpCore. It evaluates each of expression e1 through en in that order and returns the value of en. It returns 0 if there are no expressions in the block.
(+ e1 e2) first evaluates e1 and e2 and then returns the sum of those integer values.
Similarly, the builtin arithmetic operators -, *, and / are the operators for subtraction, multiplication, and division.
Note: Because of Lua's use (before 5.3) of double precision floating point for all numbers, division may result in a nonintegral value. The evaluator applies math.floor to that result. Expression Language 1 should be modified in this way as well.
(< e1 e2) first evaluates e1 and e2 and then returns 1 (true) if e1 < e2 in the usual integer ordering; otherwise it returns 0 (false).
Similarly for == (equals), ~- (not equals), <=, >. and >=.
(write e) is a new feature of ImpCore. It first evaluates e and then writes the string to the standard output (i.e., a side effect) as well as returning the value of e.
To print the first n positive integers:
(block ; print first n integers
(:= n 10)
(:= x 1)
(while (<= x n)
(block
(write x)
(:= x (+ x 1)))
)
)To print the factorial of the first n positive integers:
(block ; compute first n factorials
(:= n 16)
(:= i 1)
(:= f 1)
(while (<= i n)
(block
(write f)
(:= i (+ i 1))
(:= f (* f i))
)
)
)To print m modulo n:
(block ; compute m modulo n
(:= m 16)
(:= n 3)
(:= mm (- m (* (/ m n) n)))
(write mm)
)Note: / yields the integer result from the division.
To print the positive integers whose squares are less than n:
(block
(:= n 1000) ; upper bound
(:= i 1) ; integer
(:= s 1) ; its square
(while (< s n)
(block
(write i)
(:= i (+ i 1))
(:= s (* i i))
)
)
)To compute the logical "and" and "or" of two boolean values b and c:
(if b c 0) ; and
(if b 1 c) ; orOf course, we can substitute expressions for b and c as needed. (These expression are the same for Expression Language 1.)
In comparison to the modularized Expression Language 1 interpreter, the Imperative Core interpreter makes the following changes.
The Utilities module was not changed.
The Environment module was not changed. It already had the needed support for assigning values, although that was not used in Expression Language 1.
The Values module was not changed.
The Parser module was adapted from the Expression Language 1 prefix parser. It adds new lexical elements, grammar rules, and semantic actions to implement the assignment, while, write, and block expressions. (It also provides parsing and semantic action hooks for the read and for exercises.)
I also moved the functions trimSpaces, trimComment, and getCommand from the REPL module to the Parser module. These are more closely tied to the parsing functionality than specifically to the REPL. I also added public function isQuit. (These changes should be folded back into the Expression Language 1 interpreter.)
The Abstract Syntax module added new constructors and query functions for the assignment (Set), while, write, and block expressions.
The module adds support in exprToString for new Set (assignment) element. The existing mechanism already supported the other new elements.
I also added support for a variable number of arguments in the abstract syntax tree representations (e.g., for block). This involved the introduction of the new public function numArgs. This capability should be upwardly compatible from the Expression Language 1 features (and probably should be folded back into that program).
The Evaluator module added new branches of the eval function to handle the four new expressions types.
The REPL module changed in three ways:
I moved the trimSpaces, trimComment, and getCommand functions to the Parser module and added a new isQuit function. This enabled the LPEG dependency to be removed.
I factored out the internal function parseEval. It is now called by readEvalPrint and by new function startREPL (discussed below). Both functions now take an optional environment argument that default to a global environment that REPL creates.
The new public function startREPL first evaluates the ImpCore scripts in the file names given as command line arguments and then starts the interactive REPL.
This new capability is compatible with Expression Language 1 and should be folded back into that interpreter.
The instructor will add the needed features in the parser to support read and for below.
Add a read expression to the ImpCore language. The is a no-argument operation that reads a number from the terminal and returns it to the evaluating ImpCore program.
Add a new for expression to the ImpCore language. It has the syntax
( for Variable Exp Exp Exp ) Evaluating (for x e1 e2 e3) first evaluates e1 to a value v1 and stores v1 into x. It then repeats the following steps:
e2 to a value v2xx > v2, then exit the for and return the value 0e3 and discard the resultx and store the result back in x (then repeat steps)For example, (for i 1 10 (write i)) prints the integers from 1 to 10 in order.
Make sure you get the order of evaluation correct. For example, the odd program
(for n 0 (block (:= n (+ n 2)) 10) (block (write n) (:= n (+ n 3))))prints the numbers 2, 8 and returns 0.
The exclusive-or (xor) of boolean values b and c is true when exactly one of the two values is true and is false otherwise. Write an ImpCore expression that computes the exclusive-or of b and c.
The Fibonacci sequence is defined by the function fib where fib(0) = 0, fib(1) = 1, and, for m > 1, fib(m) = fib(m-1) + fib(m-2). Implement an Imperative Core language program that writes the Fibonacci sequence for some positive integer n. (Use the ImpCore interpreter to test the program.)
Write a version of the factorial program from the notes above using the for expression you added to ImpCore.
Challenge: As an extension to the for loop, add an expression that gives the increment value (instead of just 1).
Challenge: Extend ImpCore with a repeat-until expression with the usual semantics. You will need to extend the parser to do so.
Challenge: Design an infix syntax for ImpCore and implement a parser (using LPEG).
Challenge: Implement a compiler back-end for ImpCore that compiles for a stack machine. (Talk to the instructor.)
Challenge: Consider how to add function definitions and calls, local variables, different data types, etc. We will do some of this in the future. (Talk to the instructor.)
The Parser and REPL modules require the module "lpeg" from the developers of Lua. It can be installed via the luarocks utility.
