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.

Background:

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 space.

Problem 0:

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.

Problem 1:

Develop a Redex model for S. Use eval to test the model.

Problem 2:

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.

Problem 3:

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.

Problem 4:

Formulate the Fibonacci function as a Redex model.

Here is the Racket definition of the Fibonacci function:

   
(define (fib n)
  (cond
    [(= 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.