Re: S-expression I/O in Ada

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

Natasha Kerensikova writes on comp.lang.ada:
> On 2010-08-14, Ludovic Brenta <ludovic@ludovic-brenta.org> wrote:
>> OK, but these two are equivalent if you remember the axiom that (y
>> . nil) is really just y.
>
> Ok, that's the part I have trouble with. When thinking in list terms,
> that cons feels like it's the operation of prepending an item to an
> existing list, right?
>
> Here is my understanding, please correct me where I'm wrong. Oh, I'm
> going to have to type that.
>
> Let's assume we have a Node type, which can be either a List or an Atom
> (little Ada question as an aside, Node would then be a parametrized
> type, and the two cases would be called Node(List) and Node(Atom),
> right? or have I misunderstood something?).

Correct, see my implementation:

   type Access_T is access T;
   type Internal_T (Atom : Boolean := False) is record
      case Atom is
         when True  => Value : Ada.Strings.Unbounded.Unbounded_String;
         when False =>
            Car : Access_T;
            Cdr : Access_T;
      end case;
   end record;
   type Internal_Access_T is access Internal_T;
   type T is new Ada.Finalization.Controlled with record
      Internal : Internal_Access_T;
   end record;

> The cons operation would then take a Node as its first parameter (before
> the dot) and a List as its second, and return a List which is
> semantically the input list prepended by the first parameter taken as a
> list item. Right?

Correct:

   function Cons (Car, Cdr : in T) return T is
      Result : T;
   begin
      Result.Internal := new Internal_T (Atom => False);
      Result.Internal.Car := new T'(Car);
      Result.Internal.Cdr := new T'(Cdr);
      return Result;
   end Cons;

> So nil is of type List and represents the empty list. Then (y . nil) is
> a List containing a single node, which is the Atom y. So I feel that y
> is of type Atom while (y . nil) is of type List.

If you see nil as a list, then it has a car and a cdr, so nil is defined
recursively as (nil . nil), so you then end up with infinite recursion.
So, I'd rather see nil as an atom that, by definition, does not have a
car or cdr and only a value (in this case, the value is empty).  Again
from my implementation:

Nil : constant T := (Ada.Finalization.Controlled with Internal => null);

Now let me explain the (y . nil) = y axiom.

Definition: a list node is a cons pair consisting of a car and a cdr
that point to other nodes.

Definition: an atom is a node consisting only of a value (i.e. it has no
car and no cdr).

Now let us look at (y . nil), where y is an arbitrary node.

This (y . nil) is a cons pair where the car points to an actual node but
the cdr points to nil.  If you traverse this node, you will find y and
then stop.  So essentially it is a node with a single value, y.

If you look at just y and you traverse that, you will find y and then
stop.  This is exactly the same result as traversing (y . nil).  Hence
the equivalence.

> (Then (x . (y .nil)) is the previous list with x prepended, therefore
> the two-item list containing x then y.

Correct, and it is also equivalent to just (x . y).

> And then (z . (x . (y . nil))) would be a three-item list.
> But then what of ((x . (y. nil)) . (z . nil))? It looks to me like
> a two-item list whose first item is a list, followed by the atom z.

((x . (y. nil)) . (z . nil)) is not terminated by nil; it is equivalent
to
(((x . (y. nil)) . (z . nil)) . nil)
and to
((x . y) . z)

> But then how would reverse list be written?

(z . (x . y)), I suppose.

> Maybe (z . ((x . (y . nil)) . nil))? But that doesn't fit with your
> derivation pattern on tcp-connect, so I'm lost.)
>
> Now I can understand that in an untyped environment, an Atom can be
> automagically cast into a single-item list. In such a case, (x . y) is
> first translated into (x . LY) where LY is the List containing the Atom
> y a its only item (i.e. (y . nil)). And now that cons is correctly typed
> like (Node . List), it ends up with the two-item List containing the
> Atom x followed by the Atom y.
>
> But then how would you make a list ending with LY? My guess would be
> (x . (LY . nil)), but then it is not equivalent to (x . LY), so I'm lost
> again.
>
> Or are single-item lists prohibited in lisp?

I guess so, because if nil is a list, then it must be defined as (nil
. nil); the definition would be infinitely recursive.  So a single-item
list is, by definition, an atom.

-- 
Ludovic Brenta.