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

[David Olofson <david@olofson.net>]

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.

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.


[...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... ;-)


> > > 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.


[...]
> > > > 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.

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. 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.


[...]
> > 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.)


> 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. ;-)


//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 ---