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

[Bob Pendleton <bob@pendleton.com>]

On Tue, 2004-04-13 at 04:52, David Olofson wrote:
> On Monday 12 April 2004 21.59, Bob Pendleton wrote:
> [...refcounting and/or GC...]
> > > Meanwhile, I'm trying to keep the language pretty minimal, with
> > > just a few powerful datatypes... There's a conflict there that's
> > > hard to avoid.
> >
> > Yep. Of course, you can do what perl does. It uses reference
> > counting and warns the programmer to break cycles.
> 
> Yeah, I've been thinking along those lines, at least as an=20
> intermediate step... Much work? (Compared to a full blown GC or=20
> hybrid solution, that is.)

Depends on the language and how the code is structured. Adding any kind
of memory manager after the fact is very hard. To add a GC you have to
have the code structured in such a way that the GC can find every
pointer so that it can mark it and follow it. Pointers that are buried
in variables that the GC doesn't know about cause serious errors. If the
GC can't find the pointers it can't mark what they point to and they
wind up collecting values that are not garbage. There are some nice
packages that work with C++ to add GC to existing code. They work very
well, but they work by making assumptions about what binary values are
pointers and by keeping marks in a separate data structure. Of course,
if you have enough knowledge about the range of addresses used by the
heap that approach works pretty well. Any pointer to the heap *usually*
has an address greater than the initial heap base. So, you can scan all
of the programs data memory and the stack and find real references to
the heap.

Reference counting is really hard to retrofit to C code but can be done
to C++ without losing to much sleep and blood... You have to create a
smart pointer type template and replace all pointer variables with that
new type. Once that is done reference counting "just works".

In both cases you run into problems with local variables, temporary
variables, and pointer arithmetic.

> 
> 
> > > > 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.
> > >
> > > Incremental GC seems to be the new fashion in multimedia related
> > > (ie real time) scripting languages. One of the main reasons why I
> > > didn't just go with Lua is that it relies on GC, but doesn't
> > > (yet) have an incremental GC implementation.
> >
> > Yep, for all the same reasons you are running into.
> 
> Yeah... My idea was to simply design around it and use explicit memory=20
> allocation or whatever, just to get started. I guess you could hack=20
> Lua to do that as well, and drop the GC, but I decided that if I had=20
> to do Deep Hacks, I might as well upgrade my own custom engine to do=20
> what I need instead. More control, more fun etc... :-)
> 
> BTW, the Lua team has been working on an incremental GC for a while.=20
> Doesn't help me though, as I need the hard RT stuff to work right=20
> away. (Preferably "yesterday".)
> 

There are a lot of other languages out there. Have you taken a good hard
look at them?

> 
> [...]
> > > Maybe this is a catch 22 situation? People that are serious about
> > > RT generally stay away from scripting languages, and soft RT and
> > > non RT people just don't care enough to worry about the problem.
> > > So, there are no scripting solutions that really work in RT
> > > environments, and as a result, there are no users (ie potential
> > > contributors, if we think in Free/Open Source terms) of RT
> > > scripting systems.
> >
> > I don't think so. I think it is because the papers are written by
> > professors and graduate students who never seem to have any
> > interest in either embedded systems or real time.
> 
> And RT programmers generally don't hack their own scripting engines,=20
> or they blindly trust the professors, only to (incorrectly) conclude=20
> that scripting doesn't work in RT environments? Well, that would=20
> explain it. It would be a bit worrying if programmers in general just=20
> use "well known" algorithms without *really* understanding them, but=20
> I guess it happens...

Very few programmers ever try to *really* understand the code they use.
As long as it is good enough they don't need to.

> 
> 
> > Then there is the point that RT systems tend to lag behind desktop
> > and server systems in overall memory and performance.
> 
> Yes... Although that doesn't exactly apply to games - at least no the=20
> state-of-the-art 3D games. Then again, games are rarely considered=20
> hard RT systems these days, unfortunately. :-/ Not much point if they=20
> have to run on desktop OSes without proper RT scheduling, so I can't=20
> say I blame game programmers in general for having limited knowledge=20
> of, or interest in, hard RT systems.

I don't think games have ever been thought of as hard real time systems.
Seriously, even when they were, the programmers didn't think about them
that way. 

> 
> 
> > And,
> > RT/embedded systems have reliability requirements that are many
> > times higher than in desktop/server systems. The result is that
> > RT/embedded developers are (rightly) conservative and therefore
> > software techniques used in RT/embedded systems tend to lag many
> > years (decades :-) behind techniques that are acceptable on
> > desktop/server systems.
> 
> *hehe* Well, the actual software I'm replacing (and still maintaining)=20
> is about a decade old now - though it's actually C++ and (sort of)=20
> OO, which was probably rather cutting edge for an RT system at the=20
> time.
> 
> There are even Z80 based instruments out there still alive, though the=20
> firmware for those is long since declared dead and forgotten. As long=20
> as the hardware can be repaired, the beasts still do the job,=20
> though. :-)
> 
> 
> [...]
> > Each function context needs a pointer to the context of each
> > upvalue context it can see along with the values for each local
> > variable. For example
> >
> > function a(b, c)
> > {
> > 	function d(e, f)
> > 	{
> > 		function g(h, i)
> > 		{
> > 		}
> > 		function j(k, l)
> > 		{
> > 		}
> > 	}
> > }
> >
> > The context for function j always needs a pointer to the context
> > for the last invocation of a() and d(). While function d()'s
> > context needs a pointer to the most recent invocation of a(). Of
> > course, d() can be recursive so it may have many invocations on the
> > stack. And g() and j() may call each other and be recursive so they
> > also may have many invocations on the stack. So, the stack frame
> > for a call to j would contain:
> >
> > j:
> > 	-> last stack frame
> > 	-> d
> > 	-> a
> > 	value k
> > 	value l
> 
> Right... I'm assuming that if j() has a reference to the most recent=20
> context of d(), that context will contain a reference to the right=20
> a() context. (As it's implemented, the return info, upvalue reference=20
> and local variables are all part of a stack frame.) That is,=20
> accessing locals in d() from j() are at j.upvalues, and locals in a()=20
> are in d.upvalues, which is j.upvalues.upvalues.

That works, it just adds some run time overhead that having a local
pointer avoids. 

> 
> (Note that if j() calls g(), it passes d()'s context for upvalues; not=20
> it's own. It's basically the same as accessing variables; you just=20
> pass the context as a "self" reference, rather than just using it for=20
> getting at the value.)
> 
> Did I miss something? (Right, it would probably be more efficient to=20
> have one upvalue reference for each context used, but the current=20
> solution seemed to be the easiest way of doing it at the time.)
> 
> 
> [...static + dynamic typing...]
> > > Speaking of which;
> > >
> > > 	A) No type specifier =3D=3D> default type. (Say, integer.)
> > >
> > > 	B) No type specifier =3D=3D> object becomes dynamically typed.
> > >
> > > 	C) Type specifiers are not optional. Say "dynamic" if
> > > 	   that's what you want.
> > >
> > > What's your vote?
> >
> > I prefer to either have strong typing or dynamic typing. Never
> > both.
> 
> Why not both? (Though I'd agree that it's usually better to pass an OO=20
> interfaces around, and derive various classes from that interfaces as=20
> needed. That avoids run time binding of member names as well, since=20
> you gan use statically typed object references...)

I don't like having both because it is confusing and error prone. You
get into situations where the programmer declares things incorrectly and
yet they still work. Or, they work for a long time and break when a
small change is made to the code.

> 
> =46rom the language POV, I tend to think of static typing mainly as a=20
> way of telling the compiler exactly what you mean, so you simply=20
> can't compile code that won't work, or won't do anything sensible=20
> anyway.

I see it as a way to let the compiler find errors at compile time
instead of run time. A way to reduce the size of the language by
eliminating the need to have a type testing mechanism in the language.
And, as a way to generate better code because you don't have to include
code for run time type testing.

In a completely dynamic system you can derive type information my
looking at the types of constants and other hints and a good job of
assigning types to variables without having to declare them at all.

> 
> (Yes, I've considered allowing specifying variable and argument types=20
> as sets of types, such as "integer:float some_value". Same as dynamic=20
> typing at run time, except for type casts, but more like static=20
> typing at compile time.)
> 
> 
> > But, if I have to have both them I prefer C. Always say what
> > you mean. Defaults breed bugs and they make it hard to find them
> > because you can't see them. Understanding code with defaults means
> > having to keep track of a lot of details about the language all the
> > time.
> 
> Yes, that's my general feeling - not just about this particular case.=20
> Defaults are messy, especially as they tend to differ between=20
> languages, often for no obvious reasons. Dangerous way of saving some=20
> typing...

Defaults are truly evil :-)

> 
> So, the current default and only type will become an explicit type,=20
> named "dynamic", along with integer, real, string etc.
> 
> But now I need to deal with recursive type specifications as well,=20
> such as "reference to function" and whatnot... (Or just not type=20
> references at all, but that sort of eliminates half the point of=20
> having static typing at all, IMHO.) Oh well. :-)
> 
> 
> [...hash tables and stuff...]
> > So, I would stick with the simplest tables you can find until you
> > can prove there is a need for them.
> 
> Yeah, that makes sense.
> 
> 
> //David Olofson - Programmer, Composer, Open Source Advocate
> 
> =2E- 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         +
+---------------------------------------+