Constant Folding and Partial Evaluation

reader asks “is there any reason why VBScript
doesn’t change
= str & “1234567890” & “hello”
 to str
= str & “1234567890hello”
they are both constants?


question.  Yes, there are reasons.


operation you’re describing is called constant
, and it is a very common compile-time optimization.  VBScript
does an extremely limited kind of constant
folding.  In VBScript, these two programs
generate exactly the same code at the call site:


foo = “hello”



exactly the same as



is, the code generated for both says “pass the literal
“hello” to
print subroutine”.  If foo had
been a variable instead of a constant then the code would have been generated to say
“pass the contents of variable
foo…”  But
the VBScript code generator is smart enough to realize that
foo is
a constant, and so it does not generate a by-name or by-index lookup, it just slams
the constant right in there so that there is no lookup indirection at all.


kind of constant folding you’re describing is compile-time
evaluation of expressions which have all operands known at compile time
.  For
short, let’s call it partial evaluation.  In
C++ for example, it is legal to say


int CallMethod = 0x1;

int CallProperty = 0x2;

int CallMethodOrProperty = CallMethod | CallProperty;


C++ compiler is smart enough to realize that it can compute the third value itself.  VBScript
would produce an error in this situation, as the compiler is not that smart.  Neither
VBScript nor JScript will evaluate constant expressions at compile time.


even more advanced form of constant folding is to determine which functions are pure
functions — that is, functions which have no side effects, where the output of the
function depends solely on the arguments passed in.  For
example, in a language that supported pure functions, this would be legal:


Real Pi = 3.14159265358979;

Real Sine60 = sine( Pi / 3);  // Pi /
3 radians = 60 degrees


sine function is a pure function — there’s no reason that it could not be called
at compile time to assign to this constant.  However,
in practice it can be very difficult to identify pure functions, and even if you can,
there are issues in calling arbitrary code at compile time — like, what if the pure
function takes an hour to run?  That’s
a long compile!  What if it throws exceptions?  There
are many practical problems.


JScript .NET compiler does support partial evaluation, but not pure functions.  The
JScript .NET compiler architecture is quite interesting.  The
source code is lexed into a stream of tokens, and then the tokens are parsed to form
a parse tree.  Each node in the parse
tree is represented by an object (written in C#) which implements three methods:
Evaluate, PartialEvaluate and TranslateToIL.  When
you call
PartialEvaluate on
the root of the parse tree, it recursively descends through the tree looking for nodes
representing operations where all the sub-nodes are known at compile time.  Those
nodes are evaluated and collapsed into simpler nodes.  Once
the tree has been evaluated as much as is possible at compile time, we then call
which starts another recursive descent that emits the IL into the generated assembly.


The Evaluate method
is there to implement the
eval function.  JScript
Classic (which everyone thinks is an “interpreted” language) always compiles
the script to bytecode and then interprets the bytecode — even
eval calls
the bytecode compiler in JScript Classic.  But
in JScript Classic, a bytecode block is a block of memory entirely under control of
the JScript engine, which can release it when the code is no longer callable.  In
JScript .NET, we compile to IL which is then jitted into machine code.  If
JScript .NET’s implementation of
eval emitted
IL, then that jitted code would stay in memory until the appdomain went away!  This
means that a tight loop with an
eval in
it is essentially a memory leak in JScript
.NET, but not in JScript Classic.  Therefore,
JScript .NET actually implements a true interpreter!  In
JScript .NET,
eval generates
a parse tree and does a full recursive evaluation on it. 


digressing slightly.  You wanted to know
why the script engines don’t implement partial evaluation.  Well,
first of all, implementing partial evaluation would have made the script engines considerably
more complicated for very little performance gain.  And
if the author does want this gain, then the author can easily fold the constants “by


more important, partial evaluation makes the process of compiling the script into
bytecode much, much longer as you need to do yet another complete recursive pass over
the parse tree.  That’s great, isn’t it?  I
mean, that’s trading increased compilation time for decreased run time.  What
could be wrong with that?  Well, it depends
who you ask.


the ASP implementers’ perspective, that would indeed be great.  An
ASP page, as I’ve already discussed, only gets compiled once, on the first page hit,
but might be run many times.  Who cares
if the first page hit takes a few milliseconds
longer to do the compilation, if the subsequent million page hits each run a few microseconds
faster?  And so what if this makes the
VBScript DLL larger?  ASP updates are
distributed to people with fast internet connections.


from the IE implementers’ perspective, partial evaluation is a step in the wrong direction.  ASP
wants the compilation to go slow and the run to go fast because they are generating
the code once, calling it a lot, and generating strings that must be served up as
fast as possible.  IE wants the compilation
to be as fast as possible because they want as little delay as possible between the
HTML arriving over the network and the page rendering correctly.  They’re
never going to run the script again after its generated once, so there is no amortization
of compilation cost.  And IE typically
uses scripts to run user interface elements, not to build up huge strings as fast
as possible.  Every microsecond does NOT
count in most UI scenarios — as long as the UI events are processed just slightly
faster than we incredibly slow humans can notice the lag, everyone is happy.