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