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

[Bob Pendleton <bob@pendleton.com>]

On Mon, 2004-04-05 at 06:42, David Olofson wrote:
> On Monday 05 April 2004 04.39, Bob Pendleton wrote:
> [...]
> > > Well, my gut feeling is that functions shouldn't send references
> > > to local functions to the "world outside", if those functions
> > > mess with local stuff.
> >
> > I'm not really sure what you mean by that. You have two choices.
> > You can do what C and C++ and pretty much every language like does
> > and just bomb if reference data that has been deleted. Or, you can
> > keep the data around so that the function can operate in the
> > context it was captured in.
> 
> What I mean is just that if I go for the C/C++ variant, I'd like to 
> have the compiler and/or language prevent such situations, preferably 
> without removing other language features.

Good, I follow you. Notice that in C all functions are essentially
"static" and in C++ you can only get pointers to static methods and they
can only access static data.

> 
> As to preserving the context to make this kind of calls valid, I kind 
> of like the idea, but I'm also worried about side effects. It tastes 
> like implicit objects (OO style) to me, and that sounds like a good 
> idea, but I'm not sure I'm seeing the full picture. (I don't have 
> much experience with languages that support this kind of stuff.) Are 
> there any papers discussing the pros and cons of supporting this in 
> languages?

Yeah, I read several at one time. I can't think of them right now. Look
for anything written about Scheme by Guy Steele about the original
thinking behind scheme will help. One of the motivations behind scheme
was to support exactly the feature you are looking at in a lexically
scoped language. 

This looks like a good place to start looking:
http://library.readscheme.org/page1.html

LISP and all of its relatives and variants have this feature.

> 
> 
> > > Thing is, locals are very much like C/C++/Pascal locals,
> > > which are allocated on the stack when a function is called (that
> > > is, they can exist in multiple instances if the function directly
> > > or indirectly calls itself), and they're supposed to be destroyed
> > > as the function exits.
> >
> > If you want to stick to those semantics you can't let people have
> > references to functions that are declared within a context.
> 
> That would be a problem, since *all* functions (except the root 
> functions of modules) are declared as local functions. Seemed like a 
> good idea at the time, but it's actually starting to look like a can 
> of worms... I could substitute "using upvalues directly or 
> indirectly" for "declared within a context", but that's non-trivial 
> to implement, and there doesn't seem to be much point.

Yeah, I see your problem.

> 
> 
> > > Anyway, that's a matter of taste, I guess... The main reason why
> > > I'm doing it this way is that I want the VM to be RT safe,
> > > without opening up the can of words that is RT safe GC. (Maybe
> > > later... Right now, I just need this stuff to do the job ASAP.)
> >
> > There are actually several questions here. One is, how do I do RT
> > GC and the other is how do I save the semantics of the language.
> >
> > The answer is not as elegant as what I would like, but it works.
> > When you take a reference to a function you save enough of the
> > context as is needed to run the function.
> 
> Right away, as part of the "get funcref" operation?

Yep, right then. That is the only time you know exactly what it is
supposed to be.

> 
> 
> > That is generally a snap
> > shot of some portion of the stack. When you call the function you
> > push the context on the stack call the function, and when it
> > returns save the context. Then you provide the equivalent of free()
> > for contexts. That makes clean up the programmers problem.
> 
> Yes... However, that makes it very important to grab those function 
> references (and context snapshots) at the exact right moment, so you 
> don't accidentally get a snapshot when the context is in an undesired 
> state. Feels a bit weird...

I thought eating alligator was a bit weird, but it tastes pretty good.
:-) It is all in what you are used to. I "grew up" with LISP so it seems
perfectly normal to me. 

> 
> OTOH, if you think of the upvalues as a form of implicit arguments 
> (many languages implement them as invisible arguments and similar 
> "hacks"), this actually makes a lot more sense than managing contexts 
> as real (and shared) objects that hang around for as long as you need 
> them. 

Six of one half a dozen of the other. Semantically the same. The thing
is that you want to treat the context the same way no matter how the
function is called. Having two ways of doing it will introduce bugs.

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

> 
> 
> > > As to the implementation, my VM is stack-less, and just moves the
> > > register base around in the heap as needed. That is, the "call
> > > stack" is effectively a linked LIFO stack of register frames.
> >
> > I wish I had read this first! So, you can implement a cactus stack
> > just by keeping a reference count in each chunk of the stack.
> > Saving the context is simply incrementing the reference count and
> > grabbing a pointer to the current stack top. When you free the
> > context you just decrement the reference count and free the block
> > and then decrement the next block down and so on.
> 
> Yes... Apart from the memory management, the structure to take this 
> work should already be in place. As long as the relevant call frames 
> are kept around for as long as needed, things should Just Work(TM).

Yep.

> 
> 
> > > However, allocation of register frame space is currently done by
> > > means of a "top index", so it effectively works like a stack
> > > anyway. It would be pretty easy to allocate memory in a more
> > > malloc() style fashion, but the bad news is that the memory
> > > manager would have to be RT safe. I'm not terribly happy about
> > > code causing memory fragmentation for non-obvious reasons either.
> >
> > RT safe allocators are pretty simple.
> 
> 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.

> 
> I'm thinking about the basic N pools of power-of-two sized blocks, 
> perhaps with block splitting and merging. That has the disadvantage 
> of restricting the maximum block size to a fraction of the size of 
> the memory pool, but that won't be much of an issue if arrays are 
> fragmented at the VM level. (No need for copying data around when 
> resizing dynamic arrays, which is kinda' nice in an RT system...)

I dislike wasting, on average, a quarter of allocated memory. I prefer
using a vector of free lists indexed by size with block merging at the
time when free() is called. Very fast allocations and frees with good
block merging behavior. And, if the free lists are created so that the
most recently freed block on the list is also the first to be allocated
you get good virtual memory and cache behavior as well. 

> 
> 
> > > > The easiest way to do that involves adding a garbage collector
> > > > of some sort and it requires that contexts are savable. When
> > > > you get a reference to a function you actually get a pair with
> > > > a reference to the context and a reference to the function.
> > >
> > > Yes... A bit like calling object member functions. That's what I
> > > thought of first, but then I ran into the context lifetime issue
> > > and realized I didn't like the whole concept of calling functions
> > > using upvalues like that.
> >
> > The fact that I pointed you at a 30 year old paper on the subject
> > should give you a hint that this problem has been discussed for a
> > very long time. I have a book originally published in the '50s that
> > discusses it. What you are describing is a very powerful
> > programming tool that is left out of most languages because it adds
> > a little bit of run time overhead. Now days, that overhead is
> > nothing to worry about.
> 
> Well, the implementation is actually the minor issue here, though it 
> would be nice if I could do something simple that does the Right 
> Thing(TM) right now. If it's too much work, I'll have to leave it in 
> the "C/C++ style" state for now.

Yep.

> 
> Problem is I'm still not sure about this feature, and it's 
> implications. (As you say, it's left out of most languages, so you 
> rarely see code that uses it.)

Yeah. When I first was trying to learn C++ I just about went nuts until
I figured out that C++ doesn't allow this feature. On first reading I
thought the declaration syntax in C++ was executed at run time, not at
compile time. Up 'til then all the OO coding I had done was in LISP and
Scheme where you have these features at your disposal all the time. 

'Tis a wonderful way to program.

Consider this example. I have 4 variables in the local context, x1, y1,
x2, y2 and a function drawLine(). Draw line draws a line from x1, y1 to
x2, y2. So I set those variables to the values I want and get a
reference to drawLine() and store it in dl1. Now, I set the variables to
new value and get another reference to drawLine() and store it in dl2.

You then call dl1 and it draws a line using the first set of values and
you call dl2 and it draws a line using the second set of values. You can
keep dl1 and dl2 as long as you like and every time you call them they
draw the same line. 

In C++ you have to create a line class with drawLine() method, four
class variables, and an initializer that sets the variables. Then you
have to create new instances of the class for each line. It has the same
effect. It just uses a different method to handle the scope.

> 
> 
> > You keep saying that it has to be RT safe. By which I assume you
> > mean that you have to have a bounded execution time for a function.
> > The cactus stack technique gives you a bounded run time. It does
> > result in higher variation of run time. But does not result in
> > unbounded run time.
> 
> Right. The new factors would be the memory manager and the fact that 
> function contexts aren't always removed when functions return, but 
> there's nothing with inherently unbounded execution times in there.
> 
> 
> > > > When you call the
> > > > reference you instantiate the context and call the function.
> > >
> > > That sounds seriously dangerous... How can you create such a
> > > context in a proper way, when it would normally be created
> > > implicitly when some function is called? (The context is
> > > effectively the locals belonging to one "call instance" of that
> > > function.)
> >
> > It isn't hard. Especially if you are using a cactus stack. Then the
> > implicitly created context is retained. Anyway, you can even do
> > this in C using setjmp/longjmp to capture and restore the stack.
> > You can use setjmp/longjmp to implement cooperative threads and
> > even scheme like continuations in C. Fun, huh? Doing it in an
> > interpretor where you control everything is pretty straight
> > forward.
> 
> Yes. I just have to decide what I actually want to achieve. :-)

That is the hardest part :-)

> 
> 
> > > > Take a look at continuations in Scheme for an example of a
> > > > language that does something like what I just described. Also,
> > > > try to find a copy of, Moses, Joel (1970) "The function of
> > > > FUNCTION in LISP or why the FUNARG problem should be called the
> > > > environment problem", M.I.T. Artificial Intelligence Memo 199,
> > > > Cambridge, Mass.
> > >
> > > Thanks! Interesting stuff.
> > >
> > > ALGOL 60 and ALGOL 68 deal with it by simply not allowing
> > > functions to be returned...

Look at call by name parameters in Algol 60. They have pretty much the
same effect and account for the invention of the "thunk". Interesting
even though it is only slightly related to the problem you currently
face.

> >
> > Yep.
> 
> BTW, how do they deal with "returning" through reference arguments? Do 
> those languages pass all arguments by value, or do they just prevent 
> passing of references to functions somehow?

Algol 60 supported call by value and call by name.

> 
> 
> > > That's sort of what I'd like to do, but how do you reliably
> > > prevent that when you have dynamic typing?
> >
> > Don't allow someone to get a reference to a function. If a function
> > isn't in scope, you can't call it.
> 
> Yeah... But I need function references. Or maybe I just *think* I do, 
> as a result of hacking too much C, C++, Pascal and the like?

I suppose you can live without it. But, I would hate to have to. :-) to
many things that are just too easy to implement using function pointers.

> 
> 
> > That is a basic property and basic problem of languages with nested
> > functions and nested scopes.
> 
> Well, you can't have it all... (At least not without some undesired 
> bonus "features".)
> 
> 
> > >  Maybe I should just restrict
> > > function references to statically typed variables, so you can't
> > > accidentally pass functions to the wrong places without the
> > > compiler trapping it.
> >
> > Much better to design the language so that the problem either can
> > not occur or so that it works as expected.
> 
> Well, that's what I had in mind, but I can't see a perfect and obvious 
> solution. There is much more to this than I realized at first, so I 
> think I'll just leave it alone until I have the time to read up on 
> this and deal with it properly.

Sounds like a good plan to me.

> 
> 
> //David Olofson - Programmer, Composer, Open Source Advocate

		Bob Pendleton

P.S.

At one time I was a compiler writer. I got into graphics by working on
tools for developing microcode for graphic accelerators. 

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