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

[Bob Pendleton <bob@pendleton.com>]

On Sun, 2004-04-04 at 12:48, David Olofson wrote:
> On Saturday 03 April 2004 23.35, Bob Pendleton wrote:
> > On Fri, 2004-04-02 at 03:30, David Olofson wrote:
> [...upvalues, funcrefs and contexts...]
> > > Any ideas? How do other languages with upvalues handle function
> > > pointers/references?
> >
> > I assume that by an "upvalue" you mean a value defined in an outer
> > scope?
> 
> Yes... (They're local variables of a function that forms an outer 
> scope for local functions.)
> 
> 
> > If so then the solution to the problem is to not delete
> > contexts until you are actually done with them. If some one has a
> > reference to a function, and the function is in a context, then you
> > can't delete the context until the reference to the function is
> > deleted.
> 
> 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.

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

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

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

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

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

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.

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

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

Yep. 

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

That is a basic property and basic problem of languages with nested
functions and nested scopes.

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

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

		Bob Pendleton

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