Due date: 10/7 @ at the beginning of class

The goal of this problem set is to deepen your understanding of language specifications via relations. Doing so will enhance your familiarity with reduction systems and Redex. Think of problem 1 as a "finger exercise" warm-up for problem 2. The deep domain content of the exercise is relevant for those of you who end up in disciplines that heavily rely on numeric computations.

Problem 1:

The ListSum function consumes a list of numbers and computes the sum.

Formulate the ListSum function as three different Redex reduction model: 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. All meta-operations from Racket must add/multiply exactly two numbers.

Define metafunctions that encapsulate the idea of evaluation-via-reduction in all three models. Find an example that produces distinct results for at least two of three orders of evaluation and formulate the example as a failing test case. Comment out the test case.

Problem 2:

Develop a variant of the language of arithmetic from class so that + and * can be applied to an arbitrary number of numbers just like in Racket and similar programming languages.

part a Extend the language with two distinct reduction relations. The first should reduce the nested expressions from left to right and the second one from right to left. Employ a corresponding strategy to primitive arithmetic, respectively, i.e., for adding or multiplying numbers. Constraint: All meta-operations from Racket must add/multiply exactly two numbers.

part b Include two traces expressions that demonstrate that the reduction graphs for one and the same example differ.

part c Formulate metafunctions that encapsulate the idea of evaluation-via-reduction in both models. We know from grade school that, in principle, the two evaluation functions are equal. Formulate a corresponding conjecture with redex-check. Then formulate a counter-example as a test or record one that redex-check finds. Finally explain the counter-example with a single sentence (at most two lines).