Stack effect inference
Slava Pestov <
slava@...>
2008-06-07 19:00:16 GMT
Hi all,
For a while now Factor has required that the stack effect be declared
on recursive words. Non-recursive words did not require a declaration,
but it was considered good style to add one except for the most
trivial words (such as those pushing constants on the stack).
Well, the problem is that I recently realized any word can technically
become recursive, _except_ those that push constants on the stack! So
what we have now is unsound.
Consider this scenario:
You're working at a large enterprisey firm on a project with lots of
developers
Developer A writes the following code:
GENERIC: a ( x -- y )
GENERIC: c ( x -- y )
Developer B writes the following code:
: b ... a ... ; ! no stack effect declaration -- but it's not recursive!
M: foo c ... b ... ;
Developer C writes this:
M: bar a ... c ... ;
Wham, suddenly 'b' is recursive, because we have a cycle in the
control flow graph: a -> c -> b -> a, which didn't exist before! But
developer C doesn't care about the word 'b', they may not know it
exists even, but they just broke it.
This scenario is not contrieved; it comes up in extra/ from time to
time. Someone will add some code which defines a bunch of methods,
then suddenly the compiler starts complaining about some totally
random word being recursive and needing a stack effect, such as this
word from calendar.format:
: YYYY year>> write-0000 ;
Surely it doesn't look recursive, but there is some path through the
call graph where write-0000 calls write, which calls some low-level
Unix I/O code, which somehow calls back into the calendar code...
To make matters worse, it doesn't _always_ complain about a word
needing a stack effect declaration. Sometimes things work out just
fine and it gets along without hitting the code path where it needs
the declaration to be there. So what we have here is that some guy
makes an innocent-looking change to the code, and at some undetermined
point in the future, a totally unrelated word may stop compiling.
The technical term for languages with such features is "toy
language"
Since my plan is to use Factor to take over the world and get
disgustingly rich, this is not an acceptable state of affairs. There
are two solutions:
1) Revive the old stack effect inference algorithm which did not
require annotations at all.
2) Require stack effect declarations on all words except for the most
trivial ones which only push literals on the stack
I don't want to do #1 because the old algorithm was more complex, both
in terms of code and run time. So that leaves us with #2. I don't mind
having to annotate more words, what do you guys think?
Slava
-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php