Homework 3 (Mid-term exam) COSE212, Fall 2020
Hakjoo Oh
10/22, 0:0 – 10/28, 23:59
Problem 1 Let us design and implement a programming language called ML−. ML− is a small yet Turing-complete functional language that supports built-in lists and (mutually) recursive procedures.
Language Design The syntax of ML− is defined inductively as follows: P→E
E → |
| | | | | | | | | | | | | | | | | | |
()
true | false
n
x
E+E|E-E|E*E|E/E E=E|E
which takes a program, evaluates it, and produces its value. Whenever the se- mantics is undefined, raise exception UndefinedSemantics.
Examples Check your implementation by running the following example pro- grams (and more).
1. Evaluating the program
let x = 1
in let f = proc (y) (x + y)
in let x = 2
in let g = proc (y) (x + y)
in (f1)+(g1)
represented by
LET (“x”, CONST 1,
LET (“f”, PROC (“y”, ADD (VAR “x”, VAR “y”)),
LET (“x”, CONST 2,
LET (“g”, PROC (“y”, ADD (VAR “x”, VAR “y”)),
ADD (CALL (VAR “f”, CONST 1), CALL (VAR “g”, CONST 1)))))) should produce the value Int 5.
2. Evaluating the program
letrec double(x) = if (x = 0) then 0 else (double (x-1) + 2
in (double 6)
represented by
LETREC (“double”, “x”,
IF (EQUAL (VAR “x”, CONST 0), CONST 0,
ADD (CALL (VAR “double”, SUB (VAR “x”, CONST 1)), CONST 2)),
CALL (VAR “double”, CONST 6))
should produce Int 12. 3. Evaluating the program
5
letrec even(x) = if (x = 0) then true else odd(x-1)
odd(x) = if (x = 0) then false else even(x-1)
in (even 13)
represented by
LETMREC
((“even”, “x”,
IF (EQUAL (VAR “x”, CONST 0), TRUE,
CALL (VAR “odd”, SUB (VAR “x”, CONST 1)))),
(“odd”, “x”,
IF (EQUAL (VAR “x”, CONST 0), FALSE,
CALL (VAR “even”, SUB (VAR “x”, CONST 1)))),
CALL (VAR “odd”, CONST 13))
should produce Bool true. 4. Evaluating the program
letrec factorial(x) =
if (x = 0) then 1
else factorial(x-1) * x
in letrec loop n =
if (n = 0) then ()
else (print (factorial n); loop (n-1))
in (loop 10)
represented by
LETREC (“factorial”, “x”,
IF (EQUAL (VAR “x”, CONST 0), CONST 1,
MUL (CALL (VAR “factorial”, SUB (VAR “x”, CONST 1)), VAR “x”)),
LETREC (“loop”, “n”,
IF (EQUAL (VAR “n”, CONST 0), UNIT,
SEQ (PRINT (CALL (VAR “factorial”, VAR “n”)),
CALL (VAR “loop”, SUB (VAR “n”, CONST 1)))),
CALL (VAR “loop”, CONST 10)))
should produce Unit after printing out the following lines:
3628800
362880
40320
5040
720
120
6
24 6 2 1
5. Evaluating the program
letrec range(n) =
if (n = 1) then (cons 1 nil)
else n::(range (n-1))
in (range 10)
represented by
LETREC (“range”, “n”,
IF (EQUAL (VAR “n”, CONST 1), CONS (CONST 1, NIL),
CONS (VAR “n”, CALL (VAR “range”, SUB (VAR “n”, CONST 1)))),
CALL (VAR “range”, CONST 10))
should produce List [Int 10; Int 9; Int Int 4; Int 3; Int 2; Int 1].
6. Evaluating the program
letrec reverse(l) =
if (isnil l) then []
else (reverse (tl l)) @ (cons hd l)
8; Int 7; Int 6; Int 5;
in (reverse (cons (1, cons (2, cons (3, nil)))))
represented by
LETREC (“reverse”, “l”,
IF (ISNIL (VAR “l”), NIL,
APPEND (CALL (VAR “reverse”, TAIL (VAR “l”)), CONS (HEAD (VAR “l”), NIL))),
CALL (VAR “reverse”, CONS (CONST 1, CONS (CONST 2, CONS (CONST 3, NIL)))))
should produce List [Int 3; Int 2; Int 1].
7. An interesting fact in programming languages is that any recursive func- tion can be defined in terms of non-recursive functions (i.e., letrec is syntactic sugar1 in ML−). Consider the following function:
let fix = proc (f) ((proc (x) f (proc (y) ((x x) y)))
(proc (x) f (proc (y) ((x x) y))))
1 https://en.wikipedia.org/wiki/Syntactic_sugar
7
which is called fixed-point-combinator (or Z-combinator).2 Note that fix is a non-recursive function, although its structure is complex and repeti- tive. Any recursive function definition of the form:
letrec f(x) =
can be defined as follows using fix:
let f = fix (proc (f) (proc (x) ())) in …
For example, the factorial program
letrec f(x) = if (x = 0) then 1 else f(x-1) * x
in (f 10)
can be defined using fix:
let fix = proc (f) ((proc (x) f (proc (y) ((x x) y)))
(proc (x) f (proc (y) ((x x) y))))
in let f = fix (proc (f) (proc (x) (if (x = 0) then 1 else f(x-1) * x)))
in (f 10)
which is represented in our implementation as follows:
LET (“fix”,
PROC (“f”,
CALL
(PROC (“x”,
CALL (VAR “f”, PROC (“y”, CALL (CALL (VAR “x”, VAR “x”), VAR “y”)))),
PROC (“x”,
CALL (VAR “f”, PROC (“y”, CALL (CALL (VAR “x”, VAR “x”), VAR “y”)))))),
LET (“f”,
CALL (VAR “fix”,
PROC (“f”,
PROC (“x”,
IF (EQUAL (VAR “x”, CONST 0), CONST 1,
MUL (CALL (VAR “f”, SUB (VAR “x”, CONST 1)), VAR “x”))))),
CALL (VAR “f”, CONST 10)))
EvaluatingthisprogramwithyourinterpretershouldproduceInt 3628800. For another example, consider the function range defined above:
in letrec range(n) = if (n = 1) then (cons 1 nil)
else n::(range (n-1))
in (range 10)
2 https://en.wikipedia.org/wiki/Fixed- point_combinator 8
We can translate it to a non-recursive version as follows:
let fix = proc (f) ((proc (x) f (proc (y) ((x x) y)))
(proc (x) f (proc (y) ((x x) y))))
in let f = fix (proc (range)
(proc (n)
in (f 10)
In OCaml:
LET (“fix”,
PROC (“f”,
CALL
(PROC (“x”,
(if (n = 1) then (cons 1 nil)
else n::(range (n-1)))))
CALL (VAR “f”, PROC (“y”, CALL (CALL (VAR “x”, VAR “x”), VAR “y”)))),
PROC (“x”,
CALL (VAR “f”, PROC (“y”, CALL (CALL (VAR “x”, VAR “x”), VAR “y”)))))),
LET (“f”,
CALL (VAR “fix”,
PROC (“range”,
PROC (“n”,
IF (EQUAL (VAR “n”, CONST 1), CONS (CONST 1, NIL),
CONS (VAR “n”, CALL (VAR “range”, SUB (VAR “n”, CONST 1))))))),
CALL (VAR “f”, CONST 10)))
Evaluating this program should produce List [Int 10; Int 9; Int 8; Int 7; Int 6; Int 5; Int 4; Int 3; Int 2; Int 1].
9