Written Assignment 1

    • Calculator language: Syntax (10)

In the next two exercises, you will develop a small language for a basic calculator. For simplicity, you do not need to model parentheses and precedence. Of course, if we were to design a parser for this language, we would have to carefully sort out how to parse programs like \5 3 + 2".

Let’s start by specifying the syntax of the language, i.e., the structure of valid programs. Integer con-stants are given by a non-empty string of digits 0 9, possibly beginning with for negative numbers. Boolean expressions include: (1) the constants \tt" and \ " for true and false, (2) the \and"/\or" of two Boolean expressions, written \ && " and \ jj " respectively, (3) equality (==) and lesser-than (<) between two arithmetic expressions. Arithmetic expressions include (1) integer constants, (2) addition and multipli-cation of two arithmetic expressions, written \ + " and \ " respectively, and (3) if-then-else, written \if then else ". The guard expression can be any Boolean expression, while the body expressions should both be arithmetic expressions.

Translate this English description of the language into a grammar. Your grammar should have three classes of non-terminals: int for integer constants, ae for arithmetic expressions, and be for boolean expres-sions. You do not need to stick exactly to EBNF, so long as it is clear which symbols in your grammar represent literal characters, and which symbols in your grammar represent expressions.

    • Calculator language: Operational semantics (10)

Now, let’s specify the behavior of programs in this language. We will build a small-step semantics like we saw in class. We rst specify the values, i.e., the programs that are done executing/do not step. We take the Boolean constants tt; and integer constants (e.g., 42, 0, 125) as values.

    1. Give a small-step operational semantics for our calculator language. For if-then-else, the program should rst evaluate the guard to a constant before evaluating the corresponding body expression; the other body expression should not be evaluated. (This behavior is also known as short-circuiting, or a lazy-if.)

    2. Give an alternative operational semantics for if-then-else that evaluates both bodies before evaluating the guard; call this semantics an eager-if. What are some reasons to prefer lazy-if over eager-if ?

    • Lambda calculus (5)

These exercises will give you some practice with the core functional language, also known as the lambda calculus. Throughout, assume that the language is call by value: when evaluating a function application ( x: e1) e2, we rst evaluate e2 to a value before substituting for x in e1. We’ll usually leave out parentheses. For instance, ( x: y: e) a b is short for (( x: y: e) a) b

Evaluate each of the following programs until it reaches a value, or returns to the original program. Show each step in the evaluation.


1

    1. ( f:  x: f x) ( x: x + 1) 5

2. ( f:    x:    y: f y x) ( x:    y: x    y) 5 3

    3. ( x: x x) ( x: x x)

This program is also known as the combinator; it is a building block that can be used to model recursive (i.e., looping) programs.

    • Recursion (5)

Use the program construct x f: e we introduced to write a lambda calculus function that takes in a natural number n and returns the n-th Fibonacci number b(n), de ned by b(0) = 1; b(1) = 1 and b(n) = b(n 1) + b(n 2) for n 2. Test out your program by applying it to 3; show the steps in your reduction.
















































2