> < ^ Date: Tue, 27 Aug 1996 20:22:36 +0100
^ From: Julian Gilbey <j.d.gilbey@qmw.ac.uk >
> ^ Subject: Compiler; Collected

Two thoughts for the Forum. The first is about the compiler-to-be,
and the second is a suggested improvement to the code for Collected.

Consider the following very simple code, designed to take an integer
as input:

f := function (x)
  return x+1;

g := function (y)
  return f(y);

f := function (x)
  return 2*x;


At present, g(2) will return 4, as the current definition of f(x) is
to return 2*x.

However, if we want to have an optimising compiler, then compilation
of g should take into account the definition of f and not simply call
f. This gets even hairier if a function has a recursive definition,
but somewhere in the recursion (perhaps at a lower level?) the
function definition might be changed.

Any thoughts?


Having looked at the code for Collected (in list.g), may I suggest the
following as a possible alternative, which might well be faster in
many cases?

Collected := function(L)
  local i,      # counter for current position in mset
        mset,   # the resulting multiset
        l,      # the current element of the list L
        last_l; # the last element read from L
if Length(L) = 0 then
  return [];

# We take a shallow copy of L before we sort it so that the input list
# remains unchanged
L := ShallowCopy(L);

  mset := [ [L[1],0] ];  # initialise the variables
  last_l := L[1];
  i := 1;
  for l in L do
    if l = last_l then
      mset[i][2] := mset[i][2] + 1;
      i := i + 1;
      mset[i] := [l,1];
      last_l := l;
  return mset;

Julian Gilbey                       Email: J.D.Gilbey@qmw.ac.uk
Dept of Mathematical Sciences
Queen Mary & Westfield College      Finger me or talk to me at:
Mile End Road                         jdg@euclid.maths.qmw.ac.uk
London E1 4NS, ENGLAND              ( Logon info attached )

> < [top]