October 22nd, 1990

Ideally the type checking phase should determine the type of
most objects; however, unless the entire program is available
(which I think is too big of a restriction, though I may be
wrong) there will always be some need for passing around
arbitrary fp objects. I propose immediate storage for constants,
as follows: fp_data (the stuff that is passed around) is a double,
i.e. 64 bits, but such that it can still be given as argument and
returned by functions even in the most straightforward kind of C.
These 64 bits are mapped via a union to 2 shorts (type, ref?) and
a value which depends on the type. For all but pointer types, the
value is immediate; for pointers, the value is the pointer.

Likewise in vectors: each cell could be 12 bytes long, but the
type encodes (a) whether the car object is stored immediately
(b) the reference count of the car, if not immediate (maybe?)
(c) maybe the reference count of the cdr.


April 14th, 1991

Might be good to try the strategy described in 'An APL compiler'
(Tim Budd, 1988, Springer), which basically computes each element
of a vector 'on demand'. So an apply-to-all, for instance, would
accept a request for element index so-and-so, and request that
element from its input vector, and return f(that element). There
would be no construction of a 'result vector', saving lots of
space and perhaps also time.

Issues:
- for such things as while, insert, or recursion, you have to compute
the whole result before returning any part of it. It might be possible
to get around that in implementing, e.g., 'append', but the resulting
code would be somewhat messy. So it might be easier to compute and
store the intermediate result for these cases.

- the strategy only works for expressions. That is fine as long
as you are (a) within a procedure, or (b) you know the whole text
of the program. (b) could be applicable for an optimizing pass,
which could also get rid of unnecessary recursion and functions.

Or, given the code
Def makevec aa 1 o distl o [1, iota o 1r]
The type-checker could figure out that the types are
<value* number> => <value*>
and the code might look something like this:
fp_type makevec (in)
fp_type in;
{
  fp_type res;
  int i;	/* index over result vector */
  int reslen;

  reslen = in->elem [in->vlen-1].ival; 
/* reslen is len(aa)=len(distl)=len(distl-right-arg)=len(iota)=1r */
  res = newvect (reslen);
  for (i < 0; i < reslen; i++)
    res->elem[i] = in->elem[0];
/* result_i is (1 o distl_i: arg0), which is simply 1: arg0
 * arg0 is ([1, iota o 1r]: in), so result_i is (1 o [1, iota o 1r]: in),
 *	which is simply (1: in). */
  return (res);
}

A more complicated example might be
Def lexlast not o \/and o aa number
The type-checker could figure out that the types are
<value value*> => boolean,
and knowing that the signature of 'number' (which is not inlined) is
value => boolean
the code might look something like
fp_type lexlast (in)
fp_type in;
{
  fp_type res;
  int iv;	/* intermediate boolean result */
  int reslen;
  int i;	/* index over result vector */

  iv = TRUE;			/* initial value for \/and */
  reslen = in->vlen;
  for (i = 0; iv && i < reslen; i++)	/* compute \/and o aa number */
    iv = iv && (number (in->elem [i])).boolv;
  res->boolv = ! iv;		/* compute not */
  res->fp_typ = boolean;
  return (res);
}

Note that this strategy is equivalent to lazy reduction in that elements
are only computed if and when they are needed.


July 2, 1991
# since trans is applied, the right input to mmult is clearly
# a vector of vectors.
# which since they go through '*', is a pair of matrix of numbers.
# distr shows that the left input is also a vector.
# trans in IP shows that each input is actually a vector of vectors.
# aa * shows that each of those elements is numeric
# /+ shows that the each IP returns one number
# mmult therefore returns a matrix of numbers indexed by i,j
# Def IP (/+) o (aa *) o trans
# 
# Def MM (aa aa IP) o (aa distl) o distr o [1, trans o 2]
# 
# Def mmult MM
# 
# inlining:
Def mmult aa aa /+ o aa aa aa * o aa aa trans o aa distl o
    distr o [1, trans o 2]

# mmult(i,j) = /+ o aa * o trans o [i o 1, aa j o 2]

Code for aa aa, which is applied to the entire body of mmult(i,j):
for (i1 = 0; i1 < size1; i+1+)
  for (i2 = 0; i2 < size2; i2++)

code for mmult(i1,i2):
    val [i1][i2] = 0;	/* initializer for /+ */
    for (i3 = 0; i3 < size3; i3++)	/* loop for /+ */
      val [i1][i2] +=	/* update for /+ */
	in [1][i1][i3]	/* i o 1 = 1 o trans o [i o 1, aa j o 2] */
		*	/* aa * */
	in [2][i3][i2];


July 29th, 1991

Identical constants (esp. in the same source file) should be shared.
This means the compiler must keep a table of all constants and
subconstants, sorted by decreasing size, and share whenever it finds
a match.
