[Z-machine] Catch & throw
Marnix Klooster
Hello Zailors,
My recent proposal to add exceptions to Inform raised some questions
about the Z-machine CATCH and THROW instructions. To implement
exceptions it is necessary that these are *correctly* and *portably*
implemented by existing interpreters.
CORRECTNESS
Specification 0.2 says that CATCH <variable> reads the 'frame pointer'
for the current routine call, and that THROW <value> <frame pointer>
returns from the routine call identified by the given frame pointer,
with <value> as the return value.
For clarity here follows an explanation of what a 'frame pointer' is.
First we introduce the concept of the 'call stack'. This is the stack
on which all routine calls and their local data are stored. Every
item on the call stack is a 'frame', and contains the current program
counter (PC), the local variables, and the program stack for this
routine invocation. Thus initially the call stack contains only one
frame, for the initial routine (which Inform calls Main__). On a CALL
instruction a new frame is pushed onto the call stack, with the new PC
and the passed values. On a RETURN the top frame of the call stack is
removed, whereby control is passed back to the calling routine.
Now imagine that every frame on the call stack can have an
identification number attached to it, the so-called frame pointer for
that frame. (A frame need not have an associated frame pointer.)
There are two requirements on frame pointers: (1) once a frame is
assigned a frame pointer, that pointer may not be changed; and (2) at
any given time, all frame pointers of the call stack must be
different.
Performing a CATCH sets the frame pointer of the top frame to an
arbitrary value (subject to the above two conditions) and returns that
value. A THROW <value> <frame pointer> instruction removes frames
from the call stack until the frame with the given <frame pointer>
comes on top. Then it returns from that routine with the given
<value>.
[The above description is admittedly abstract, but it is necessary to
explain the different implementation options, below.]
At least ZIP and Frotz implement CATCH and THROW as stated above, so I
expect their derivatives to be correct. I don't know anything about
the correctness of other interpreters. (On a related note, previous
versions of Inform -- up until 5.5, I think -- compiled the CATCH
instruction wrongly. Upgrade.)
PORTABILITY
The important thing to note about the above description is that CATCH
can choose an arbitrary value, as long as the two conditions are
satisfied. This is the source of non-portability. For imagine two
interpreters that have different ways of choosing frame pointers. A
game using CATCH and THROW is played on interpreter A, and it is
SAVEd. The generated save file then may contain frame pointers: in a
local or global variable, or on some routine's stack. Continuing from
that save file in interpreter B and executing a THROW then fails
horribly: that interpreter may interpret the same frame pointer
differently, leading to unpredictable behaviour.
To make (the save files of games using) exceptions portable between
interpreters, we must Standardize the choice of frame pointers.
Current interpreters usually use the memory address where the frame is
stored, but this is inherently non-portable. I see two portable
schemes that might be declared Standard.
* Number frames by their call stack position. I.e., the bottom
(first) frame is numbered 0, the next 1, etc. The advantage of this
method is that it's simple to implement. The disadvantage is that it
is not possible to have more that 65536 items on the stack, because
that would violate frame pointer property (2). But do that many
nested CALLs really occur in practice? I doubt it. And most
interpreters don't reserve space for that large a call stack anyway.
* When a CATCH is done, give a frame the lowest number possible while
maintaining the frame pointer requirements. I.e., on the first CATCH
the top frame is numbered 0, a nested CATCH then numbers its top frame
1, etc. The advantage is that this method does not limit the call
stack to 65536 items; it instead limits the number of nested CATCHes
to 65536. (The first person to reach this limit should be given a
"most catchy Inform game" award at the annual I-F awards ceremony.)
The disadvantage of this scheme is that it is a little more
complicated to implement, possibly making the interpreter slower or
using up more memory.
Because of the simplicity of the first method, and the unlikeliness of
having 65536 nested CALLs, I propose to use that method for numbering
frame pointers, and to declare it Standard.
There is yet another possibility, of course. Perhaps Infocom
implemented CATCH and THROW consistently in all their interpreters,
then we might choose to follow _their_ method instead. This buys you
no save file portability, however, since no existing non-Infocom
interpreter reads or writes Infocom-compatible save files anyway.
Perhaps some Z-machine hackers would like to delve into the save file
format and the frame pointers of Infocom interpreters?
SO...
If save file portability is important (and previous posts on r.a.i-f
suggest that it is), we should Standardize frame pointers.
(Can anyone tell me why most of my posts here look like they've walked
right out of a thesis?)
Groetjes,
<><
Marnix
--
Marnix Klooster
kloo...@dutiba.twi.tudelft.nl // mar...@worldonline.nl
Matthew T. Russotto
In article <53tr6a$4...@mars.worldonline.nl>,
Marnix Klooster <mar...@worldonline.nl> wrote:
}PORTABILITY
[..]
}To make (the save files of games using) exceptions portable between
}interpreters, we must Standardize the choice of frame pointers.
}Current interpreters usually use the memory address where the frame is
}stored, but this is inherently non-portable. I see two portable
}schemes that might be declared Standard.
ZIP interpreters use a stack pointer-- not a memory address, but an
index into the stack array. A memory address is useless even for
saves within the same interpreter.
} * Number frames by their call stack position. I.e., the bottom
}(first) frame is numbered 0, the next 1, etc. The advantage of this
}method is that it's simple to implement. The disadvantage is that it
}is not possible to have more that 65536 items on the stack, because
}that would violate frame pointer property (2). But do that many
}nested CALLs really occur in practice? I doubt it. And most
}interpreters don't reserve space for that large a call stack anyway.
Call stack is defined by 0.2 as 1024 2-byte words, I think, so no problem here.
}There is yet another possibility, of course. Perhaps Infocom
}implemented CATCH and THROW consistently in all their interpreters,
}then we might choose to follow _their_ method instead. This buys you
}no save file portability, however, since no existing non-Infocom
}interpreter reads or writes Infocom-compatible save files anyway.
I tried, sort of halfheartedly. But never succeeded. Eventually I
decided that the big problem was not catch/throw but the stack format.
BTW, most Infocom games use only a 512-word stack, though I think
there's some exceptions in V5 games.
}If save file portability is important (and previous posts on r.a.i-f
}suggest that it is), we should Standardize frame pointers.
True, but more than that-- we need to have a standard save-stack
format. The one ZIP uses has the disadvantage that you cannot tell
where the stuff pushed by the story file ends and where the local
variables begin. This means that ZIP files simply _can't_ be loaded
into interpreters (like ZPlet) which don't leave the current locals on
the stack.
--
Matthew T. Russotto russ...@pond.com
"Extremism in defense of liberty is no vice, and moderation in pursuit
of justice is no virtue."
Marnix Klooster
Matthew T. Russotto (russ...@wanda.vf.pond.com) wrote:
> }If save file portability is important (and previous posts on r.a.i-f
> }suggest that it is), we should Standardize frame pointers.
> True, but more than that-- we need to have a standard save-stack
> format. The one ZIP uses has the disadvantage that you cannot tell
> where the stuff pushed by the story file ends and where the local
> variables begin. This means that ZIP files simply _can't_ be loaded
> into interpreters (like ZPlet) which don't leave the current locals on
> the stack.
I'll delve into this, and try to specify a standard save file format
that is compact, simple, and general. I'm going to post my thoughts
on the Z-machine mailing list in a couple of days. Everybody who
wants to join the fun, send an e-mail message to
with the following text in the *body* (the subject is ignored):
subscribe z-machine YourEMai...@Goes.Here
Then send your messages to
[I might as well create a special signature file for this. Oh
well...]
> Matthew T. Russotto russ...@pond.com
Groetjes,
<><
Marnix
--
Marnix Klooster
mar...@worldonline.nl