Re: Ada vs. LISP

[eachus@mbunix.mitre.org (Robert Eachus)]

     I recieved many responses to my posting about Lisp style
programming in Ada.  Some were a bit extreme--An Ada program which
supports the LISP semantics for (apply (read) (read)) is called a
LISP interpreter.  That is not what I was talking about.  Of course
you can write a LISP _interpreter_ in Ada, I was talking about
compilable Ada code derived from LISP programs or designs.

     Now that I have also recieved several civil responses asking
how to do it, it seems I had better post an example or two.  This
posting won't satisfy the skeptics, but then I could probably write
a book explaining all the details and not satisfy some of them.

     The first thing to realize is that, contrary to the way Ada
generics are usually taught, instantiation of generics happens during
program execution, and that each time the generic instantiation is
elaborated it creates a new instance. (If you think you understand
this, skip ahead to SKIP_TO_HERE:. But I warn you, most Ada
programmers only think they understand what that meant.)

     Those of you who are left, try this on your favorite Ada
compiler:

     generic
       type Element is private;
       type Index is range <>;
       type List is array(Index) of Element;
     function Reverse(L: List) return List;

     function Reverse(L: List) return List is
       R: List; -- OK since List is constrained;
     begin
       for I in L'RANGE loop
         R(I) := L(L'LAST - (I - L'FIRST));
       end loop;
       return R;
    end Reverse;

    There are more elegent ways to write this in Ada, but that is not
the point.  If you write a program to instantiate this generic in a
loop:

    with Text_IO; with Reverse; with Get;
    procedure Test is
    begin
      loop
        declare
          Foo: constant String := Get;
          subtype Foo_Index is Integer range Foo'FIRST..Foo'LAST;
          subtype Foo_Type is String(Foo_Index);
          function Backwards is new Reverse(Character, Foo_Index, Foo_Type);
        begin
          exit when Foo'LENGTH < 1;
          Put_Line(Backwards(Foo));
        end;
      end loop;
    end Test;

    On every pass through the loop, subtype Foo_Type has different
bounds.  Therefore each instance of Backwards expects a different
length string.  (Defining the function Get using TEXT_IO.GET_LINE is
left as an exercise for the reader.)

SKIP_TO_HERE:

    Now most of you are probably saying: "Big deal, we knew that Ada
allowed strings with non-static bounds...", but the big deal is that
subprograms are allowed as generic formals:

    generic
      type Element is private;
      type List is private;
      with function Something (E: in Element) return Element;
      with function "&"(Left: Element; Right: List) return List;
      with function CDR(L: in List) return List;
      with function CAR(L: in List) return Element;
      NUL: List
      -- Note: in a "real" lisp style Ada program only "Something"
      -- would be a generic parameter.
    function MAPCAR (L: in List) return List;

    function MAPCAR (L: in List) return List is
    begin
      if L = NUL then return NUL; end if;
      return Something(CAR(L)) & MAPCAR(CDR(L));
    end MAPCAR;

    Very useful, but not yet LISP.  We sometimes need to be able to
pass functions as objects.  Fortunately there is a way, but Ada
purists will scream:

    function MAPCAR (L: in List; F: SYSTEM.ADDRESS) return List is
      function Something (E: in Element) return Element;
      pragma INTERFACE(System, Something);
      for Something'ADDRESS use F;
    begin
      if L = NUL then return NUL; end if;
      return Something(CAR(L)) & MAPCAR(CDR(L));
    end MAPCAR;

    Obviously not guarenteed to be portable, but if your compiler
supports it, you don't even need to use generics to have (LISP) fun
in Ada.  (Just substitute whatever language name your compiler
requires for System in the pragma.  One or two even allow Ada!)

    The next level of completeness is to create a "real" LISP
environment.  It is very rare to need to go this far, but it is
possible: 

    package LISP is
      type Element is private;

      type List is  array (Natural range <>) of Element;
      -- Lists are defined as arrays so that (a,b,c) works. I usually
      -- cheat and provide visible arrays of Integers, and Float so
      -- that (1,2,3) and (1.0,2.0,3.0) can be recognized and
      -- handled.

     type Element_Type is (Number, Character, Symbol, List, Vector,
                    	   Structure, Function);
      -- You may wish to add others, but this is what I use.  Note
      -- that this is actually only provided as a shortcut for a
      -- special form of my own: 

      function IS_A(Object: Element; Class: Element_Type) return Boolean;

      function MAKE(I: Integer) return Element;
      function MAKE(C: Character) return Element;
      function MAKE(S: String) return Element;
      -- etc.

      NIL: constant Element;

      Apply: Element;
      Eval: Element;
      -- Through all the special forms you use...
    private
      type Object;
      type Element is access Object;
    end LISP;

    What about the package body?  It's fairly simple: Eval looks for a
predefined functions with a case statement, and otherwise follows the
standard (LISP) rules, and so on.  Defun (and this is what keeps
things from being unacceptably slow) actually does instantiation, and
keeps the defined form available for Eval (see above).  If pragma
INTERFACE didn't work, you could treat each new function as a new Ada
task object but I have had to stoop that low.  I prefer to make
available several generics in the specification of package LISP:

    generic
      with procedure X(L: List);
    package New_Procedure is
      New_X: Element;
    end package;

    New_X is, of course a new function object which can be Evaled,
and the semantics are to invoke (the Ada generic formal procedure) X
on the first argument.  (In this case it evals to nil, of course.)
This allows some functions (or in this case a procedure) to use Ada
semantics, and others to use LISP.

					Robert I. Eachus