[Prev][Next][Index][Thread]

Re: Fun-O Basic Edition Compiler



In article <3C2A8116.D7554E21@quiotix.com>, Jeffrey Siegal 
<jbs@quiotix.com> wrote:

> Bruce Hoult wrote:
> > - d2c currently only does tail-call elimination on local functions, and
> > only self-calls at that :-(
> 
> This is a self-call.  What's the problem?

It's not a local function, it's toplevel.  If you write it instead as...

-------------------------------------------------------------
define method tak-times(n :: <integer>)
  local method tak(x :: <integer>, y :: <integer>, z :: <integer>)
   => (result :: <integer>)
    if (y >= x)
      z
    else
      tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
    end if;
  end method tak;
  let result = 0;
  for (index from 1 to n)
    result := tak(18, 12, 6);
  end for;
  result;
end method tak-times;
-------------------------------------------------------------

... then a tail-call is used and the time (on the G4/867) drops from 6.0 
to 4.4 seconds, comparable to the Java and C (3.9, 4.2).

There's no really good reason that self-tail-calls in toplevel functions 
aren't optimized at present.  They just aren't, and I guess it just 
hasn't yet risen to the top of anyone's TODO list.  Personally, I'd 
rather see mutual calls between a collection of local functions 
optimized first.


> > > (This is "safe" mode.  All run-time checks are enabled except
> > > integer/fixint overflow, which Stalin doesn't support.  Integers will
> > > silently wrap.)
> > 
> > As in the Dylan, Java and C code.
> 
> Java is similar in practical effect to Stalin in that it is generally
> type-safe but defines integers as wrapping. (Does Dylan define integers
> this way as well?)

Yes.  <integer> in d2c is a machine word and is defined to wrap.  I seem 
to recall its defined to be 2's complement as well.

Dylan also has <general-integer> which automatically overflows to 
bignums when necessary.  Well, actually, the current implementation in 
d2c *always* uses bignums at the moment.  It's now special-cased on 
bignums that happen to be a single digit (it wasn't a week ago...) but 
those are still using the general representation on the heap.  I'll 
probably redo it a bit more to use an unboxed representation for small 
numbers when I get a chance (or next time the speed annoys me ... my 
changes this week tripled the speed of the nineNines program...).


One niceish thing about Dylan is that if you decide that you'd like 
*all* integers in the program to overflow to bignums instead of wrapping 
then all you have to do is rename <general-integer> to <integer> in the 
imports section.

-- Bruce



Follow-Ups: References: