[gameprogrammer] Re: Scripting engines: Upvalues and function refs

[Bob Pendleton <bob@pendleton.com>]

On Thu, 2004-04-08 at 06:08, David Olofson wrote:
> On Tuesday 06 April 2004 18.24, Bob Pendleton wrote:
> [...]
> > Yep. Having a GC makes life so much easier for both the language
> > developer and the programmer! But, using a GC based language for a
> > task with RT constraints is difficult.
> 
> I'm leaning towards a hybrid refcount/GC solution eventually. It seems 
> like a properly working refcounting system tends to be slower and 
> more complicated than a proper GC, but I have this feeling that there 
> are shortcuts to be made with a language and compiler designed with 
> this stuff in mind.

Yeah, that is my conclusion also. I've written systems with a GC and
with reference counting and reference counting is harder to get right. I
was looking at the same problem you are actually, a language for
scripting games. 

A reference counting system does need a GC to find cyclic structures
that a reference counting system leaves around. If you provide a rich
set of data types. like queues, sets, and so on you can get rid of a lot
of the cases where a programmer is likely to create cyclic structures.
But, not all of them.

One technique I played with was using an incremental GC. In an
interpretor you can run the GC while waiting for input. You can also run
it "between" instructions in a VM. You can run the VM for N instructions
and then run the incremental GC for X microseconds, and so on. 

If you have a handle based memory allocator you can also merge free
blocks during idle time and "between" instructions, and reduce memory
fragmentation.

> 
> Either way, note that bounded execution time is more important than 
> speed, so most of the conclusions drawn in traditional papers on this 
> matter are more or less irrelevant. For RT work, half the average 
> speed is better than occasional extreme or unbounded peaks. I can get 
> a faster CPU if I have to, but not an infinitely fast CPU.

Exactly the same conclusion I came to. Better to have predictable
behavior and lower performance than to have maximum performance and
unpredictable behavior.

I have noticed that traditional papers on memory management do not
address the memory usage patterns in multimedia programs at all. 

> 
> 
> [...alligator...]
> > If I remember correctly you are somewhere in the far northern part
> > of Europe? I eat a lot more pickled herring and bratwurst (not
> > together) than I do alligator...
> 
> Yep; Sweden. I've never seen alligator or even a Cajun restaurant 
> around here, but you never know... ;-)

Yeah, not likely to see one up there :-)

> 
> 
> > > > It is all in what you are used to. I "grew up" with LISP so it
> > > > seems perfectly normal to me.
> > >
> > > I grew up with 68k asm (though I started with BASIC, like most
> > > home computer people at the time) - so *both* ways seem sensible
> > > to me... :-)
> >
> > The 68K came out a while after I graduated from college.
> 
> That was probably a few years before I started playing with computers. 
> I didn't get in touch with it until it became popular in 
> home/personal computers like the Amiga, Atari ST and Mac. (I went 
> 16/32 bit with an Amiga.) Messed mostly with various 8 bit home 
> computers and BASIC before that, but fortunately, the horrible M$ 
> excuse for BASIC that came with the Amiga had me move to asm pretty 
> soon.
> 
> 
> [...function as class def + constructor...]
> > I've seen something very much like this in early versions of
> > FORTRAN. It supported functions with multiple entry points. Worked
> > just like what you describe. I think you are working through the
> > thought process that finally gave use objects. A lot of languages
> > have static local variables that allow functions to have hidden
> > state and act like "mini" objects.
> 
> Yeah... What I described was basically just a side effect of combining 
> local functions and handling function contexts as objects - or an 
> alternative syntax for class definitions, if you like. The 
> implementation would be essentially the same, short of some minor 
> grammar differences.
> 
> Not sure if I'll use that syntax for actual objects, but it seemed 
> like a nice way of describing simple classes. :-)
> 
> Still no inheritance, virtual methods and stuff, though. I'll try to 
> keep the number of such features to a minimum, and focus on simple 
> but powerful low level features that allow most of this to be 
> implemented in one way or another.
> 
> 
> [...upvalues: implicit arguments or parent variable references?...]
> > Decide what you want and design a syntax to match.
> 
> Well, that's the problem; what do I want? ;-)
> 
> I'm leaning towards thinking of "upvalue contexts" as objects, part 
> because it fits my VM model perfectly, and part because for some 
> reason, it seems more logical to me to think of upvalues as accessing 
> the variables of a parent function, than to think of them as implicit 
> arguments.
> 
> 
> [...]
> > Calling through a reference and a direct call are the same thing.
> > The only difference is that you have to do one level of indirection
> > to get the address of the code when jumping through a reference.
> 
> Not to my compiler - although it's just a matter of some checks that 
> cannot be done compile time when calling through a dynamically typed 
> variable. If the compiler knows what it's calling (which is currently 
> only possibly when calling "hardwired" functions), it can verify 
> argument count and stuff.
> 
> 
> > > > > The "grabbing a refence to f() always gives you the same
> > > > > thing" logic doesn't apply anyway, so why not break the rules
> > > > > properly while at it? ;-)
> > > >
> > > > Why doesn't it always act the same way?
> > >
> > > Well, it always does the same thing, but the behavior of the
> > > function will depend on the current state when the reference is
> > > taken. That is, two references to the exact same function may do
> > > very different things when called with the same (explicit)
> > > arguments. Of course, that's the idea, but it could also be a bit
> > > confusing, as it looks like you're just calling a function.
> >
> > You have to capture the reference into a named variable which will
> > be different for each reference. Not much chance of confusion.
> 
> No, not really... You just have to know what you're capturing 
> (<funcref, context> or <funcref, reference to context>), since that's 
> not obvious from the syntax.

Ok, you lost me there. How would you ever have a context and not a
reference to a context?

> 
> 
> [...]
> > > > > Yes, especially compared to some other solutions for this
> > > > > problem... I'm going to need one eventually anyway, so maybe
> > > > > I should just leave this stuff alone until then. (That gives
> > > > > me the "illegal context - let's crash!" behavior of C/C++,
> > > > > which is ok for now.)
> > > >
> > > > As long as you can be sure that it causes a crash. You don't
> > > > want it to work by accident.
> > >
> > > Right. (Though not even that is a showstopper at this point.)
> > > What's the simplest way of ensuring that a function call with an
> > > illegal context will always fail?
> >
> > Design the language so that the default value of a reference is
> > something you can check to see if it is invalid and so that once
> > assigned a valid value the value can not become invalid.
> 
> Not quite sure how to do that in this case... The CCALL (call via 
> constant; ie "hardwired" call) instruction takes an operand that 
> tells the VM how many levels to back up the stack to find the lexical 
> parent function's register frame. The upvalue access instructions 
> work in a similar fashion.

There are some techniques for doing that that are much easier to use.
One is to just push pointers to outer stack frames on the stack before
pushing the function arguments on the stack. So references to outer
stack frames are just made indirect through the appropriate value on the
stack. You don't need to climb the stack, you just indirect through the
appropriate frame pointer. This works with a linked list stack like your
too.

> 
> I could have the CALL (call via reference) instruction put an illegal 
> "upvalue register frame index" value in the called function's 
> register frame. Then I could have the upvalue access instructions 
> throw a runtime exception if they encounter such an illegal index 
> when climbing the stack.
> 
> 
> [...]
> > > I'm considering just keeping an <index, name> table, where
> > > relevant names from imported interfaces are added. The table
> > > would be used when identifier look-ups fail, so that "new"
> > > (previously unknown) names can be mapped to unique indices when
> > > their type is not known at compile time.
> >
> > That is called and alist or "associative list" systems like what
> > you are describing have been used for this task since at least the
> > 1950s.
> 
> Actually, I'm thinking about plain LUTs, to completely avoid 
> searching. 

To me a LUT is simply a look up table. The term doesn't imply a lack of
searching. 

> The idea is that any "typeless" field name should have a 
> globally unique index, so you can look it up by index in any object 
> that has a field by that name. Problem is that each object will need 
> an object LUT that at least spans the indices of the names used, so 
> it only works (efficiently) for small programs.

Yeah, that is why local tables is a good solution. Even if you have to
search the search is short. But, you can have local tables and give
local variables unique indexes in the local context. 

Or, if you like the global table, then you can bind local values in the
global table. On entry to a function you have a list of indexes whose
current value is pushed on the stack. Then you can use those names for
you local variables. On exit you just pop the old values back into the
global table. This is a well know technique for doing dynamic scoping
efficiently.

> 
> 
> [...]
> > > The problem is that this gets ugly if/when objects way down the
> > > line have fields with names that are already in the table - and
> > > spread all over it... Making it a hash table seems like the
> > > obvious answer, but I'm open to suggestions. (Speed is important,
> > > but bounded look-up time is absolutely critical.)
> >
> > Have a table/per object instead of a global table. When you see
> > o.get just look up get in the table belonging to "o". If o doesn't
> > point to a class object then it doesn't have a table and o.get is
> > illegal.
> 
> Yeah, but then you can't look up by index, right? (The compiler can't 
> tell what index "get" will have in any particular object's list, 
> except in the special case where the type is known at compile time.)

You can't have your cake and eat it too. If you have dynamic typing then
you have to pay for dynamic typing. If you want static typing you have
to live with static typing. Mixing them means that sometimes you can use
indexes and sometime you have to search. So, if you have LUTs sometime
you can index into them (when the compiler knows the type) and sometimes
you have to search them (when the compiler does not know the type).

> 
> 
> > That keeps all the tables local to their objects, no global
> > interactions to worry about. Also, since the tables are small you
> > can get good performance with a sequential search of the tables so
> > that you don't have to use space for a hash table. OTOH, hash
> > tables can be pretty small so use a hash table per class.
> 
> Right... It's not *that* expensive, and there are no nasty surprizes, 
> really; objects with many fields have a higher worst case look-up 
> time, but it's still bounded for any given piece of code.
> 
> But O(1) is always better, of course. ;-)

Not necessarily. ;-) Sometimes the flexibility that comes from using an
O(N/2) algorithm is worth the cost. Especially when N is usually small.
Of course, a good hash table has performance that is O(1) in most
practical cases.

		Bob Pendleton

> 
> 
> //David Olofson - Programmer, Composer, Open Source Advocate
> 
> .- Audiality -----------------------------------------------.
> |  Free/Open Source audio engine for games and multimedia.  |
> | MIDI, modular synthesis, real time effects, scripting,... |
> `-----------------------------------> http://audiality.org -'
>    --- http://olofson.net --- http://www.reologica.se ---
> 
> 
-- 
+---------------------------------------+
+ Bob Pendleton: writer and programmer. +
+ email: Bob@Pendleton.com              +
+ web:   www.GameProgrammer.com         +
+---------------------------------------+