Submission instructions:

Submit the solutions to 1-4 in a single .ss file. Those tasks which
require prose should be written as comments. 

If you have questions about the hand-ins, please ask them in the forum!

You are welcome to discuss the hand-ins in the forum, as long as you do not
share (parts of) the solution.

---------------------

1. Convert (by hand) the following expression to deBruijn form as described in Sec. 3.5 of the textbook:

{with {a 42}
  {with {b {+ a 1}
    {with {c {+ a b}
      {+ a b c}}}}


--------------------

2. Two WAE terms are *alpha-equivalent*, if one term can be transformed into the other one
by renaming identifiers, i.e., uniformly substituting a binding instance and all corresponding
bound instances of an identifier by a different identifier. For example

{with {a 5}
  { with {b 6}
    {+ a b}}}

is alpha equivalent to
{with {a 5}
  { with {c 6}
    {+ a c}}}


It is not allowed, though, to perform a renaming if unrelated identifiers would accidentially be
bound, e.g., renaming "b" to "a" in the example above would incorrectly yield

{with {a 5}
  { with {a 6}
    {+ a a}}}

Implement a function

alphaequivalent : WAE, WAE -> Bool

which checks whether two WAE expressions are alpha-equivalent.

Add a few interesting test cases.

------------------------

3. Consider again the presentation of deBruijn indices in Sec. 3.5 of the textbook.

Here is a data-type to store WAE expressions in deBruijn form:

(define-type WAE-dB
  [num-dB (n number?)]
  [add-dB (lhs WAE-dB?) (rhs WAE-dB?)]
  [sub-dB (lhs WAE-dB?) (rhs WAE-dB?)]
  [with-dB (named-expr WAE-dB?) (body WAE-dB?)]
  [id-dB (name number?)])

Now define a function

to-deBruijn : WAE -> WAE-dB

which converts a WAE expression into its equivalent WAE-dB expression.

Write at least one test case, including one that uses the example from 1.

-----------------------

4. Think about what alpha-equivalent WAE expressions look like after their conversion to WAE-dB.
Now Write a function

alphaequivalent2 : WAE, WAE -> Bool

which has the same meaning as the function in 2., but which is implemented using the
deBruijn conversion from 3.

Add a few tests (using the "test" function) to make sure that the two functions are equivalent.

Hint: You may want to use the "equal?" function, which checks recursively for equality
of structured data types