Due date: 10/8 @ at the beginning of class
The goal of this problem set is to acquire some basic familiarity with
Redex and to experiment with reduction systems.
The S programming language consists of literal constants and
expressions combined via its only operation, *. The
constants of S are strings.
The purpose of * is to adjoin two strings, separated by one blank
Define the function eval, which consumes a reduction relation
R and a term t and produces the first irreducible form
of t with respect to R.
Develop a Redex model for S. Use eval to test the
Design a meta-function that measures the depth of contexts from the model
for S. The depth is the number of * operations between
the root of the context and the hole of the context. Use rackunit
to test the meta-function.
Develop an alternative reduction for S that refuses to reduce
* expressions if the surrounding context is deeper than 3.
Demonstrate with some tests that an evaluation according to this second
relation may not produce strings while evaluation according to the first
relation (problem 1) always produces strings.
Formulate the Fibonacci function as a Redex model.
Here is the Racket definition of the Fibonacci function:
(define (fib n)
[(= n 0) 1]
[(= n 1) 1]
[else (+ (fib (- n 1)) (fib (-n 2)))]))
Formulate three different variants: the first one should evaluate addition
from left to right; the second one should evaluate addition from right to
left; and the third one should evaluate addition in arbitrary order (and
even switching between the two branches). The three models should share as
much as possible.