On 31/01/2014, at 11:49 AM, john skaller wrote:
> There's a bug in corouitines--01.flx I can't figure out.
Oooo .. I have now. This is what I'm going to call a Srean bug.
There's no bug in the compiler. It's not clear even if there
is a bug in the test case.
So to explain I'm going to backstep a bit. In Felix we can
use heap allocated stack frames. You are allowed to return
a pointer to a local variable because if you do, the GC simply
won't delete the frame (the compiler guesses when it is safe
to put the frame on the machine stack, never the case if you
can return a pointer to local variable!)
There's a problem here though. Unlike a language using
boxed types, a pointer to a single local variable means the
GC keeps the WHOLE frame.
And that frame contains the return address, i.e a pointer to the
calling frame (as well as a pointer to each of the most recent
ascendent frames and the thread frame).
This means if you do a long recursion and then return a pointer
to the 1000'th frame what happens? Well if you pointed at a pointer
which pointer into its callers frame the whole 1000 frames are
reachable. But what if not?
Well the return address means there are still pointers back
through the whole 1000 frames. So if the frame has returned
it makes sense to zero out the return address, so you can
only return once.
Sounds reasonable, except that with non-local gotos you CAN
in fact jump into a frame that has already returned. If you do
that and try to return again, then either you will return to the frame
as before, or exit Felix if the return address is 0 (because that's
the code for "program end"). If we NULL out the return address
we're confusing the normal program end with a hack which is just
meant to stop the whole call chain being held in memory.
But keeping the old return address is nonsense too!
In fact it will go to the caller frame but run that from from
the program counter of that frame, and that will be whatever it was
set to last during the previous execution. It won't be anywhere sane.
So now, an even worse case: a computed goto. In principle this
is nonsense unless it is executed BY the current frame
and is a jump TO the current frame.
So now look at the code:
// silly test of computed goto
proc fred () {
println$ "Hello";
var x = 5;
lab1:>
println$ "Next " + x.str;
--x;
var labvar = (label_address lab1);
if x > 0 do
goto-indirect labvar;
done
noinline proc joe () {
var lv = label_address lab1;
x = -2;
goto-indirect lv;
}
if x >= 0 call joe;
}
fred;
println$ "FRED HAS RUN";
This was actually just some crap I hacked up to see if some
cases of computed jumps and addressing labels worked.
But the results are indeterminate! If I set inlining to a low value, fred isn't
inlined
into the main procedure. Now look at the last statement in fred and you will
see it is a tail call. This is optimised by setting joe's return address to
freds
(the mainline), and zeroing out fred's return address, since a tail call implies
you cannot re-enter the caller, fred.
Only, that's precisely what joe does: it jumps into fred. So when fred
reaches the end it returns 0 which ends the program. It's an accident,
the 0 ends the program and is also used just to NULL out the return
address for GC purposes.
However leaving the address alone will not solve the problem in general
even though it would in this case, and even if you ignore that it might
cause a lot of heap to remain reachable when it shouldn't.
No, the problem is a very high level semantics issue.
I see no way to properly answer the question: what should happen
if you re-enter a procedure that has already returned? What should
happen when and if it tries to return again?
If it aborts, why should it do something first, why no abort
immediately? [What I actually mean is, if its undefined behaviour
to return again, why would the behaviour be defined at
an point prior to doing that?] if it doesn't abort, what can you say
about what happens when the return causes another procedure
to be re-entered at the pointer where it just happened to last
record the program counter?
With coroutines in a pair like the second part of the test case
where control is zig-zaging, its well defined because we're
just "temporarily suspending a thread of control" to do something
else and then later "continuing on".
There is another example where re-entry seems right: if you have
some "tail code" which is not normally executed then jumping
to it non-locally as a way of throwing an exception make sense,
at least until the handler has finished.
An interesting conundrum!
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
WatchGuard Dimension instantly turns raw network data into actionable
security intelligence. It gives you real-time visual feedback on key
security issues and trends. Skip the complicated setup - simply import
a virtual appliance and go from zero to informed in seconds.
http://pubads.g.doubleclick.net/gampad/clk?id=123612991&iu=/4140/ostg.clktrk
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
