4.68 Exercise 4.68

We are tasked with implementing a rule describing the reverse function.

The base case of this rule is simple: the reversal of an empty list is also an empty list:

(rule (reverse () ()))

The recursive case is defined in a mildly-inefficient manner wherein we append the first element of the list with the reversal of the rest of the list:

(rule (reverse (?x . ?xs) ?reversed)

(and (reverse ?xs ?xs-reversed)

(append-to-form ?xs-reversed (?x) ?reversed)))

This will work for expressions of the form (reverse (1 2 3) ?x), but not those like (reverse ?x (1 2 3)). This is because the recursive decomposition of the list only occurs in the first parameter position.