recursive types work

[Havoc Pennington]

On Wed, 2004-12-29 at 17:45 -0500, Andy Wingo wrote:
> Let A and B be the typecodes for arrays and booleans. Let N be the
> typecode for our new "nil", which requires no value. Let 1 be the true
> value. In the message writing states below, you'd have:
> 
>  code              state                   message
>  ----              -----                   -------
>  recurse(ARRAY)    {}                      A
>  recurse(ARRAY)    { {} }                  AA
>  write(Bool, true) { { TRUE } }            AAB1
>  unrecurse()       { { TRUE nil } }        AAB1N
>  unrecurse()       { { TRUE nil} nil }     AAB1NN

The problem here is empty arrays, though, which your example doesn't
contain ;-) You have to be able to say "this is an array of bool"
without writing a bool. Similarly on the other levels of the onion, i.e.
you need to be able to have array of array of bool without writing an
array of bool. Extend that to any depth of nested arrays.

Here's another example:

r (a)      {}                   A
  r (a)    {{}}                 AA
  u (a)    {{nil}}              AAN
  r (a)    {{nil}{}}            AAN
  u (a)    {{nil}{nil}}         AANN
  r (a)    {{nil}{nil}{}}       AANN
  u (a)    {{nil}{nil}{nil}}    AANNN
u (a)      {{nil}{nil}{nil}nil} AANNNN

Here there's an array of array of bool of length 3, where each element
is an array of bool of length 0. The point is that recurse()/unrecurse()
create a value, in addition to specifying the type signature.

If an array element *exists* then there's already a way to find the end
of it - it will have a length. Length works better than nil because you
don't have to introduce the idea of parentheses, and you can jump over
arrays without walking the whole array.

With either length or nil we could say something like "empty arrays of
array have a dummy element that isn't a real element" but that seems
odd. I would rather distinguish clearly between when we are iterating
over values (in which case recursing into the first element of an empty
array is not possible) and when we are iterating over types.

Type iteration will have other uses, e.g. unpacking the signature of a
variant type or unpacking Introspect() information.

> After the last unrecurse, the array would be scanned for its type
> signature, array of array of boolean. If two values in the same array
> are of different types, it becomes an array of variant. No error
> possible.

This would break when your peer app received the message though, unless
we have some mechanism on the peer side to convert array of variant to
array of bool (if bool was expected) or array of bool to array of
variant (if variant was expected).

Havoc