Jupyter at Bryn Mawr College |
|||
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Assignments |
This assignment is designed to:
When we talk about a programming language, we often refer to its form, or syntax. For example, in C or Java, you might have a function that looks like:
int plus_one(int n) {
return n + 1;
}
We will refer to this kind of syntax as concrete syntax. Concrete syntax is what one actually types to program in a particular language. However, to make processing a language easier, the first step in creating a programming language is to convert concrete syntax into abstract syntax. In fact, we will convert, or parse, concrete syntax into an Abstract Syntax Tree (AST). This is a a "tree" in that it is a recursive data structure representing a program.
In this assignment, you will write a small, but complete, Calculator Language. Your language should be able to at least add, subtract, divide, and multiple. The language should use infix notation, as per these examples. In addition, your language should allow arbitrary recursive expressions.
Typically, we will use strings to represent concrete syntax. So the above example might look like:
(define program "
int plus_one(int n) {
return n + 1;
}")
However, to start out we will use Scheme Expressions (s-expressions) to represent programs instead of strings. These will initially look just like the simple infix expressions from the last homework.
So, our first goal is to write parser
that will take an expression such as (1 + 2)
and turn it into an AST.
To begin, we will have just two kinds of expressions in our Calc language:
lit-exp
plus-exp
lit-exp
will be a list composed of the symbol `lit-exp followed by the number, like:
'(lit-exp 34)
'(lit-exp -1)
'(lit-exp 12133456)
plus-exp
will be a list composed of the symbol `plus-exp followed by two Calc expressions, like:
'(plus-exp (lit-exp 1) (lit-exp 2))
'(plus-exp (lit-exp 1)
(plus-exp (lit-exp 2)
(lit-exp 3)))
Our first goal is to write parser
that takes abstract s-expression Calc representations and turn them into AST's:
In [1]: (parser '(1 + 2))
Out [1]: (plus-exp (lit-exp 1)
(lit-exp 2))
That could look like:
(define parser
(lambda (exp)
(cond
((number? exp) (list 'lit-exp exp))
((eq? (cadr exp) '+)
(list 'plus-exp
(parser (car exp))
(parser (caddr exp))))
(else (error 'parser "Invalid concrete syntax: ~s" exp)))))
(parser '42)
;; (lit-exp 42)
(parser '(1 + 2))
;; (plus-exp (lit-exp 1) (lit-exp 2))
(parser '(100 ^ 2))
;; Traceback (most recent call last):
;; File "stdin", line 1, col 1, in 'parser'
;; File "stdin", line 9, col 12, in 'error'
;; File "stdin", line 9, col 12
;; RunTimeError: Error in 'parser': Invalid concrete syntax: (100 ^ 2)
Extend the parser to include the ability to parse minus, multiply, and divide concrete syntax. Extensively test it to make sure that it works for all valid input, and fails on non-valid input. Don't add additional operators yet... we'll do that below.
In Part 2 we will design and build evaluator
that will take AST's and evaluate/interpret them. That is, we will interpret the AST into their calculated form. The result of evaluator
at this point will always be a number, because both of our forms, plus-exp
and lit-exp
both evaluate to numbers.
(define evaluator
(lambda (ast)
(case (car ast)
(lit-exp (cadr ast))
(plus-exp (+ (evaluator (cadr ast))
(evaluator (caddr ast)))))))
(evaluator (parser '(3 + 2)))
;; 5
(evaluator (parser '2))
;; 2
Extend evaluator to evaluate multiple, divide, and minus. Extensively test your code to make sure that it works correctly. Errors such as divide-by-zero should produce "run time" errors. Errors such as (1 + +)
, (+ 1 2)
and (1 + 2 + 3)
should produce syntax errors.
Things get a bit messy with the cars and cdrs in the above evaluator. We introduce define-datatype
to make these datatypes easier to deal with by giving them named-parts.
define-datatype
is a special form used to create recursive data structures. It takes the form:
(define-datatype NAME TEST?
(SUBNAME1
(PART1 SUBTEST1?))
(SUBNAME2
(PART2 SUBTEST2?))
...)
For example, we can define calc-exp
as being composed of lit-exp
and plus-exp
:
(define-datatype calc-exp calc-exp?
(lit-exp
(var number?))
(plus-exp
(arg1 calc-exp?)
(arg2 calc-exp?)))
The above code automatically defines the following:
(list calc-exp? lit-exp plus-exp)
(lit-exp 1)
(lit-exp 'a)
(calc-exp? (lit-exp 42))
(plus-exp (lit-exp 1) (lit-exp 2))
(plus-exp (plus-exp (lit-exp 23)
(lit-exp 50))
(lit-exp -1))
We can now clean up the parser
and evaluator
by using the new datatypes. Here is the base evaluator
:
(define evaluator
(lambda (ast)
(record-case ast
(lit-exp (value) value)
(plus-exp (arg1 arg2) (+ (evaluator arg1)
(evaluator arg2))))))
(evaluator (lit-exp 42))
(evaluator (parser '((10 + 10) + 13)))
;; 33
(evaluator (parser '((100 * 100) * (26 / 2))))
;; 130000
Note that when you change the parser to use define-datatype, it will produce the exact same output (e.g., tagged lists).
Rewrite the parser and evaluator to use define-datatype
. Test them both thoroughly to make sure that all correct versions work, and that incorrect forms fail.
Refine your grammar so that all infix operators are treated as one expression type, rather than 4 different ones. For example, instead of having plus-exp
and minus-exp
, you will now have something like app-exp
("application expression"). You'll need to add another field to your new expression to store the operation symbol (e.g., '+ or '-).
Add other mathematical operators to make your Calculator Language useful.
Add the following functions to your language by adding them to the grammar. min
, max
should each take two arguments and return the min and max (respectively) of the two numbers. The concrete syntax of min and max should be:
(min 1 2)
(max 3 7)
And they should parse to AST that looks like:
(func-call-exp min calc-exp calc-exp)
(func-call-exp max calc-exp calc-exp)
When evaluated, they will give the min or the max of the two arguments.
Add the functions avg
and sum
which can take any number of expressions, and compute the average.
Here is one way of defining func-call-var-exp
, a datatype with variable args:
(define-datatype calc-exp2 calc-exp2?
(func-call-var-exp
(func symbol?)
(args (list-of number?))))
(func-call-var-exp 'sum '(1 2 3))
(evaluator (parser '(max 10 2)))
;; 10
(evaluator (parser '(min 10 2)))
;; 2
(evaluator (parser '(avg 10 2 4 5 6)))
Add variables to your language. We will pre-define pi as 3.141592653589793, and e 2.718281828459045.
In order to use variables, you will need to pass in the environment to the evaluate function (and everywhere you call evaluate). We will use an association list as the environment. So, an environment will be defined and used like so:
(define env '((pi 3.141592653589793)
(e 2.718281828459045)))
(assq 'pi env)
;; (pi 3.141592653589793)
(assq 'c env)
;; #f ;; because c is not in the association list
Change the evaluate function to take an additional argument, the environment. You will need to add var-exp
to the define-datatype, and be able to parse and evaluate the variables. It should then work as follows:
(evaluate (parser 'e) env)
;; 3.141592653589793
Finally, use your new language to compute something useful. For example, what is the area of a circle of radius 2 feet?
(evaluate (parser '(pi * (2 * 2))) env)
;; 12.5663706143592
Print out your code and examples of it running and bring to class Thursday, October 2, 2014.