internal.doc

Unix下的MUD客户端程序

instructions, usually an instruction type followed by some
information.  For instance, a VTC function call is stored as three
instructions: a type instruction I_FCALL, an integer containing the
argument count, and a pointer to the Func structure containing the
function.

Although the interpreter is reentrant, each call to the interpreter is
treated as a separate program running.  This is important for the
primitives read(), getch(), sleep(), and abort(), which suspend or
abort the currently-running program.  For instance, parse() often
results in a call to interp(), and if a read() occurs at some point
while this program is executing, only the data and call stack entries
for this new program (i.e. down to the topmost detached call frame)
will be suspended, and the function that called parse() will continue.
If interp() is called without a new detached call frame being placed
on the call stack, VT will shortly crash.

According to this design, the callv() primitive does not call
interp() but rather modifies the top of the call and data stacks and
then returns with a message to the interpreter not to execute its
normal cleanup sequence.  If it did call interp() instead, callv()
would act like detach(), which is intended to create an independent
thread.

The call frames on the call stack contain pointers and indices into
the data stack, which can be visualized like so:

            .
            .
        |   .   |
        |-------| <-- dpos
        |       |
        |-------|   (Frames used by program algorithm)
        |       |
        |-------| <-- lvars
        |       |
        |-------|   (Local variable values)
        |       |
        |-------| <-- lvars->vals
        |       |
        |-------|   (Parameter variable values)
        |       |
        |-------| <-- avars->vals (indexed by dstart)
        |   .   |
            .
            .

The dstart element of the call frame is the index of the frame pointed
to be avars->vals, or the start of the data frames used by the call
frame.  The cpush() call initializes a new call frame.  It assumes
that the parameters have already been pushed on the stack.  It extends
the stack by prog->lvarc entries to make room for the local variable
values.  The "progress" argument to the cpush() call is non-zero only
for programs generated by the prog_pcall() call in prmt4.c.  These
pseudo-programs have no local or argument variables, and their only
instruction is to call a primitive.  Thus, they act like a program
with no local or parameter variables that has already pushed several
values onto the stack and is ready to pop them off with a primitive
call.  All other functions begin with dpos indexing the data frame
immediately after the local variables.  If cpush() is called with a
non-zero progress argument, the program should have no local variables
or parameter variables.

When a call frame exits normally, the program has left one data frame
on the stack on top of its argument and local variables.
cpop_normal() removes the variables and moves the top frame down to
the first frame of the argument space.  The net effect of interpreting
a call frame is thus to replace its parameter variables with a return
value.  This is the same effect as calling a primitive.

If the program aborts preternaturally, the interpreter simply cleans
up pointers to the arrays in the call frames and makes a single call
to deref_frames() to remove all the data frames from the dstart
element of the most recent detached data frame up to the top of the
stack.


Parser
------

The parser has to overcome several difficult aspects of the VT design:
first, it must produce linear code rather than parse trees; second, it
must be able to determine what types of expressions can be used as
lvalues (most C-ish extension language compilers do not have pointers,
which greatly simplifies this problem); third, at the tokenizing level
it must be able to accept its input in multiple chunks spaced out in
time, and determine before it starts compiling when a parser directive
is finished.

The primary difficulty in producing linear code is dealing with jumps.
The parser maintains a jump table and two stacks, one for conditional
flow control and one for loops, which are more complicated.  When the
parser comes to a point in the code where loops are required, it
allocates space in the jump table and pushes the current position in
the jump table onto one of the stacks.  The macro interface handles
these operations fairly transparently.  For conditionals, we call
'Jmp(t);', where t is the type of jump (e.g. I_JMPF), and then we call
'Dest;' when we arrive at the destination of the jump, or 'Destnext;'
if it's more convenient to pop the conditional stack one jump
instruction ahead of time.  For loops, we call Incloop(n), where n is
the number of jump destinations required for the loop.  Then we call
Ldest(k) to set destination #k, and Ljmp(k, t) to jump to destination
#k (t is, again, something like I_JMPF).

Because we produce linear code, it is most expedient to handle lvalues
in the syntax.  This results in a second shift-reduce conflict (beyond
the usual if-then-else conflict) resulting from the rule "postlval:
'(' lval ')'", since according to the grammar, the lval could be
reduced to an expr and then to an atom with the parenthesees.  Another
unpleasant side-effect of handling this in the grammar is that yacc's
explicit precedence rules lose a lot of their effectiveness, since
they do not operate once a group of tokens has been reduced to an
lval.  This results in a more complicated expression syntax, but the
linear design of the code precludes handling lvalue-checking in the
semantics.

Since we do not receive our text input all at once, we keep a token
buffer.  The parsing routine, rather than passing tokens directly to
yyparse(), is called directly by the parse() primitive or from the
input window in VTC mode, and places the resulting tokens in the
buffer.  At the end of each line the parser makes an educate guess at
whether a parser directive is complete based on the balance of the '{'
and '}' tokens and whether the "func" keyword is at the beginning of
the token buffer.  The yylex() function simply reads out of the token
buffer until it is empty.

The reduction rules writes the information for some instructions in a
temporary form that is different from the final form of instructions.
They write jump instructions as integer offsets instead of the Instr *
pointers used in the final form, because they do not know while it is
compiling where the instructions will be stored, they store all
references to identifiers as strings in order to avoid adding to the
function and variable dictionaries in case of error.  The function
scan() converts these intermediate forms into the final forms.

The compiler makes a simple optimization for a[0] so that it 
produces code for *a instead of *(a+0).  This results in a third 
shift-reduce conflict because it is done in the grammar.


Efficiency notes for VTC code
-----------------------------

String lengths are stored in memory along with strings, so strlen() is
not required to manually count string elements.  Also, separate copies
of strings are stored in the same physical location in memory as often
as possible.  For instance, the strdup() primitive does not
immediately copy its string argument into another location in memory;
it waits until one of the copies of the strings are modified.  Thus,
avoiding strlen() or strdup() calls will not save a significant amount
of time or space.

If we pass strdup() a pointer to the middle of a string, it will still
make a copy of the whole string if the string is later modified.  If
we are going to store a copy of a substring, this could result in a
considerable space overhead.  So it is better to use something like:
	substring = strcpy("", s, n);
where s is the pointer into the middle of the string and n is the
length of the substring.