parrot stack and Z-machine
Amir Karger
natively on Parrot" project, namely translating Z-code into a Perl
executable. (My brother, who's a CS professor so he should know, says
I'm actually *compiling* it. Compiling bytecode to an interpreted
language? Weird!) I'm making some progress, but now I have to deal with
the harder opcodes I'd ignored, like I/O and save/restore. (Interesting
to hear about Parrot curses, wrt Z-code I/O, btw.)
I figured I could just use the Perl subroutine mechanism to emulate
Z-machine calls. So I just translate Z-code's "call routine arg0
arg1..." to "&routine(arg0, arg1, ...)" and "ret value" becomes "return
$value".
I realized that I get in trouble when we get to the save/restore
commands. Those are supposed to save and restore the call stack, which
includes the subroutine addresses & all the local variables in the
various routines. Am I right in thinking I don't actually have access
to that in Perl? (That is, I can't change the call stack at runtime,
such that when I "return" it'll return to a different subroutine than
the one that actually called the current routine.)
In Perl, I can fake it by making my entire program have no subroutines
(yuck!) and using gotos and manually storing the call stack. Then I
thought, "but what do I do about Parrot?", which is supposed to be the
whole point of this project. Then I thought that maybe I *do* have
access to Parrot's stack!
So the question is, will I be able to write a Parrot opcode that resets
the Parrot call stack? And I guess to reset the register stacks too?
Otherwise, I won't be able to save/restore games.
-Amir
__________________________________
Do you Yahoo!?
The New Yahoo! Shopping - with improved product search
http://shopping.yahoo.com
Luke Palmer
> Still working on the prelude to the preface to the "Z-machine running
> natively on Parrot" project, namely translating Z-code into a Perl
> executable. (My brother, who's a CS professor so he should know, says
> I'm actually *compiling* it. Compiling bytecode to an interpreted
> language? Weird!)
Yeah. Actually, Perl 5 is even compiling itself, into bytecode, which
is then interpreted. An example of a language that isn't compiled is,
say, Bourne Shell, which is executed based on repeated text
substitutions.
> I'm making some progress, but now I have to deal with
> the harder opcodes I'd ignored, like I/O and save/restore. (Interesting
> to hear about Parrot curses, wrt Z-code I/O, btw.)
>
> I figured I could just use the Perl subroutine mechanism to emulate
> Z-machine calls. So I just translate Z-code's "call routine arg0
> arg1..." to "&routine(arg0, arg1, ...)" and "ret value" becomes "return
> $value".
>
> I realized that I get in trouble when we get to the save/restore
> commands. Those are supposed to save and restore the call stack, which
> includes the subroutine addresses & all the local variables in the
> various routines. Am I right in thinking I don't actually have access
> to that in Perl? (That is, I can't change the call stack at runtime,
> such that when I "return" it'll return to a different subroutine than
> the one that actually called the current routine.)
You mean.. in Parrot? In Perl 5, using just the language, no you don't.
In parrot, however, you do. There is actually no call stack; it's
implicit in the cascade of P1 registers. That's why we call it the
'call chain'.
> In Perl, I can fake it by making my entire program have no subroutines
> (yuck!) and using gotos and manually storing the call stack. Then I
> thought, "but what do I do about Parrot?", which is supposed to be the
> whole point of this project. Then I thought that maybe I *do* have
> access to Parrot's stack!
>
> So the question is, will I be able to write a Parrot opcode that resets
> the Parrot call stack? And I guess to reset the register stacks too?
> Otherwise, I won't be able to save/restore games.
From disk, right? No, I don't think that's possible using the basic
Parrot mechanisms. That is, in general, a fairly hard thing to do
(although, it might be done, considering how people have been talking
about serialization recently. In any case, it's not available at the
moment).
So you could wait until it might be implemented. But I don't recommend
that, because then you're counting on the timelyness of open source,
which doesn't exist :-).
Then let's think of some other solutions to the problem. This will be
pretty abstract, mind you.
My first thought is that you can create a "call frame" object. This
object then holds a reference to the current lexical pad, the bytecode
address, and a reference to the caller's call frame object. This object
would be passed into new functions much in the manner of the return
continuations we now pass. To save, you walk up these frames,
serializing whatever is there (presuming you know the exact set of
possible data types that might be in your lexical pads).
Because of the explicitness of the bytecode format, it's possible to
take this data and re-create the stack out-of-band, and then jump to the
proper address. It'd be a lot of work, but possible nonetheless.
There are problems with that, however. The biggest one is that it
places a lot of restrictions on what kinds of data you're allowed to
have in your program. I don't know Z-code well enough to say whether
this will be too limiting.
Maybe continuations aren't so hard to serialize after all (well,
excluding things like open filehandles and such). What's the status on
the serialization subsystem?
Luke
Leopold Toetsch
> Maybe continuations aren't so hard to serialize after all (well,
> excluding things like open filehandles and such). What's the status on
> the serialization subsystem?
*nobody* did answer my summary of different schemes.
> Luke
leo
Amir Karger
> Amir Karger writes:
> >
> > I realized that I get in trouble when we get to the save/restore
> > commands. Those are supposed to save and restore the call stack,
which
> > includes the subroutine addresses & all the local variables in the
> > various routines. Am I right in thinking I don't actually have
access
> > to that in Perl? (That is, I can't change the call stack at
runtime,
> > such that when I "return" it'll return to a different subroutine
than
> > the one that actually called the current routine.)
>
> You mean.. in Parrot? In Perl 5, using just the language, no you
don't.
I was first asking for Perl, because my pre-pre-project project is to
translate Z-code into executable Perl.
> In parrot, however, you do. There is actually no call stack; it's
> implicit in the cascade of P1 registers. That's why we call it the
> 'call chain'.
I'm obviously going to need to read the parrot sub docs.
> > So the question is, will I be able to write a Parrot opcode that
resets
> > the Parrot call stack? And I guess to reset the register stacks
too?
> > Otherwise, I won't be able to save/restore games.
>
> From disk, right?
Yeah. (Well, there's also the "undo" command, which can be implemented
with the same mechanism, only you load & save from memory.)
> No, I don't think that's possible using the basic
> Parrot mechanisms. That is, in general, a fairly hard thing to do
> (although, it might be done, considering how people have been talking
> about serialization recently. In any case, it's not available at the
> moment).
>
> So you could wait until it might be implemented. But I don't
recommend
> that, because then you're counting on the timelyness of open source,
> which doesn't exist :-).
Good call. OTOH, given the rate at which I'm developing, I probably
won't get to this for a year anyway. (OK, I'm really hoping that's not
true, but we'll see.)
> Then let's think of some other solutions to the problem. This will
be
> pretty abstract, mind you.
Right. I should probably explain a bit about Z-code, because saving the
stack in Z is way easier (I think) than with some other languages. For
example, I'll point out that EVERYTHING we're saving here is guaranteed
to be an integer. No strings, floats, objects, or anything.
The Z-machine has an "evaluation stack", which is a regular old
subroutine-scoped stack that you optionally push & pop while you're
doing calculations. It's got a program counter, which is also an
integer. And it's got a call stack, which is just a stack of call
frames. Each frame contains: the PC, the subroutine-scoped local
variables (up to 15), and the evaluation stack when you left that
particular subroutine (due to calling another sub).
The other thing that Z-machine does is store all of its global
variables
and any data that might change in the program (E.g., is the axe in the
living room, in the player's possession, or has it been stolen by the
thief?) in "dynamic memory", which is < 64K of, again, integers.
The neat thing about the Z-machine (maybe true of other VM's? But
amazingly convenient for troll-filled adventure games) is that you can
save the entire game state by saving (1) the call stack and (2) an XOR
of the current dynamic memory with the original dynamic memory. Which
means that saved games range from maybe 2 to 10 or rarely 20 K max even
for bigger, post-Infocom games. Save stores exactly these things, in a
rigorously specified format.
Restore's job is a bit tougher. It loads the XOR and XORs it with the
original dynamic memory. Then it REPLACES the existing call stack with
the saved call stack, and goes to the PC at which the game was saved.
At
whcih point it will act exactly the same as the original game before
saving! Brilliant! But it means we need to be able to (a) replace the
call stack and (b) jump to an arbitrary address in the game.
> My first thought is that you can create a "call frame" object. This
> object then holds a reference to the current lexical pad, the
bytecode
> address, and a reference to the caller's call frame object. This
object
> would be passed into new functions much in the manner of the return
> continuations we now pass. To save, you walk up these frames,
> serializing whatever is there (presuming you know the exact set of
> possible data types that might be in your lexical pads).
Exactly! And that's what I'm going to end up doing in Perl. Requirement
(b) above requires me to have no subroutines in my program, but it's
still doable. (Will it require the same in Parrot? Maybe.) And the call
stack is pretty easy to maintain manually in Perl (especially when I
can steal existing code that does it from Games::Rezrov).
> Because of the explicitness of the bytecode format, it's possible to
> take this data and re-create the stack out-of-band, and then jump to
the
> proper address. It'd be a lot of work, but possible nonetheless.
>
> There are problems with that, however. The biggest one is that it
> places a lot of restrictions on what kinds of data you're allowed to
> have in your program. I don't know Z-code well enough to say whether
> this will be too limiting.
In fact, it's not at all limiting, because as I said, I'm guaranteed
integers. The main reason I didn't want to do this is that the
pie-in-the-sky dream of this project is to run Z-code "natively" on
Parrot. Which I gradually realized means we want to use as much
existing
Parrot code as possible, only grafting on extra code when necessary. To
me, it seems more native to use Parrot's stack - saving it and
recreating it for save/restore commands - than to keep an entire
separate call stack going the whole time the program is running.
So my question is really whether I can write Parrot save/restore
opcodes
in C that'll evilly manipulate the P1 call chain (whatever that is) and
the register stacks.
> Maybe continuations aren't so hard to serialize after all (well,
> excluding things like open filehandles and such). What's the status
on
> the serialization subsystem?
Um, I assume this is related to "places a lot of restrictions on your
data" and not a solution to my integer-only problems. Oh well.