Chris Dollin wrote:
> A.Sloman@cs.bham.ac.uk wrote:
>
>> On Mon, 14 Feb 2005, Chris Dollin wrote:
>>
>>> Jonathan L Cunningham wrote:
>>> ...
>>> > I agree that the limit is too small, on current machines.
>>>
>>> If your procedure needs more than 255 locals, it's too big.
>>
>> Not if you are trying to develop a fortran compiler in pop11???
>
> If the procedures of the compiler need more than 255 locals, they are
> too big.
>
> If the Fortran routines being compiled need more than 255 locals,
> *they* are too big; but they're more likely to be handed to you on
> a plate, immutable, and you may have to cope with them. Which you
> can do, being a compiler, in the obvious straightforward pattern.
It has just occurred to me that inlining weakens my claims; even
procedures with just a few locals each may combine to create a
procedure with many locals.
(When the poplog vm does inlining, this might become a real issue.)
--
Chris "electric hedgehog" Dollin
>From jlc1@sofluc.co.uk Mon Feb 14 11:30:12 2005
Path: news.demon.co.uk!mutlu.news.demon.net!peer-uk.news.demon.net!kibo.news.demon.net!demon!newsfeed.vmunix.org!news.cs.univ-paris8.fr!feeder.news.heanet.ie!feed4.jnfs.ja.net!feed2.jnfs.ja.net!jnfs.ja.net!warwick!news-out.ftel.co.uk!bhamcs!news
From: jlc1@sofluc.co.uk
Newsgroups: comp.lang.pop
Subject: Re: Bug: clisp let* causes Stack-empty and/or runaway poplog
Date: Mon, 14 Feb 2005 11:30:12 +0000 (UTC)
Organization: cs.bham.ac.uk MAIL->NEWS gateway
Lines: 83
Message-ID: <cuq244$12au$1@soapbox.cs.bham.ac.uk>
X-Trace: soapbox.cs.bham.ac.uk 1108380612 35166 147.188.192.10 (14 Feb 2005 11:30:12 GMT)
X-Complaints-To: abuse@cs.bham.ac.uk
X-Relay-Info: Relayed through cs.bham.ac.uk MAIL->NEWS gateway
Originator: exim@emily
Xref: news.demon.co.uk comp.lang.pop:1427
[Chris Dollin wrote:]
> Jonathan L Cunningham wrote:
>
> > On Sat, 12 Feb 2005 19:51:23 +0000 (UTC), hebisch@math.uni.wroc.pl
> > wrote:
> >
> >>Currently Poplog can handle at most 255 lvars. However it seems
> >
> >>IMHO the limit is too small. Is there any fundamental reason to
> >>have so small limit? I see that procedure records have only 1 byte
> >>field to stre frame size, but this seem easy to change (at modest
> >>space penalty).
> >
> > I agree that the limit is too small, on current machines.
>
> If your procedure needs more than 255 locals, it's too big.
I did, also, say:
"I can think of a couple of reasons why someone might want larger
stack frames."
> If your procedure needs more than *16* locals, it's probably too big ...
>
> Of course that's assuming human-constructed procedures.
Which I wasn't -- that's one of the two reasons.
> And 16 might actually be 32, since we have to count machine-generated
> temporaries.
Without looking at the source, I suspect that CLISP does not re-use
machine-generated temporaries (this is both quicker at compile time and
probably safer from a code-maintenance POV, although imposes a small
run-time additional overhead). Arguably, it is also the responsibility
of the code-generator to do such optimisations anyway, so a compiler
writer should correctly *not* do such things.
And loop iteration variables, e.g. (DOLIST (Item List) ...)
will declare Item as a lexical temporary. (This is correct language
design; pop11, by using "free" loop variables, looks dated on this
issue: I can't remember if there is now a compiler switch for this,
but certainly a newer pop11 dialect would bind loop variables by default.)
There are also *lots* of (very) useful macros in Lisp which, in general,
may need to generate lexical temporaries, e.g.
(PUSH item (ELT vector-of-lists (INCF i)))
would expand into the pop11 equivalent of:
item :: subscrv((1+i->>i), vector-of-lists)
-> subscrv((1+i->>i), vector-of-lists);
without the use of a lexical temporary (i.e. the correct expansion
is something like:
lblock; lvars temp = (1+i->>i);
item :: subscrv(temp, vector-of-lists) -> subscrv(temp,
vector-of-lists);
endlblock;
I haven't looked at the source of LBLOCK, to see what are the
possibilities for re-use of temporaries, or whether the CLISP
compiler does it.
It's actually more complicated than that, but the above gives you the
general idea. (Hmmm -- checking on a different lisp implementation,
the above example actually needs three(!) lexical temporaries, but
this other implementation generates, and calls, an anonymous
procedure, i.e. it sets up a new stack frame -- which is a run-time
overhead, but avoids the problem.)
If the code-generator doesn't re-use stack space for temporaries, it's
*easy* to run out. Particularly for machine-generated code.
I have an example program which implements the ID3 algorithm to classify
sets of data (features)into a decision tree: then converts that decision
tree into a lisp procedure. It would be *easy* to generate a single
procedure with a million lines of code in it. (Although it probably
wouldn't need lots of lexical variables: it's just lots of nested
conditionals.)
Jonathan
|