Implementing IronLua

Jan 24, 2011 at 12:45 PM
Edited Jan 24, 2011 at 12:53 PM

Hello all,

I've been working on Lua 5.2 (alpha, work 4) via F# in my spare time (http://ironlua.codeplex.com). I hope there's a few hardcore Lua fans hanging around here. :)

I usually turn to IronJS for implementation details, but there are a few Lua-specific features that I could use some help with before I actually start writing the "compiler".

Lua debug methods are particularly nasty: for example, with debug.setlocal you can change a function's local var.

debug.setlocal ([thread,] level, local, value)

This function assigns the value value to the local variable with index local of the function at level level of the stack. The function returns nil if there is no local variable with the given index, and raises an error when called with a level out of range. (You can call getinfo to check whether the level is valid.) Otherwise, it returns the name of the local variable.

The way I see it, you should have almost complete control on the underlying VM to be able to perform these tricks - I'm almost tempted to not support these methods.

How would I go about modeling this and similar other peculiarities using the DLR? I wonder if it's feasible without resorting to horrible hacks.

Thanks for reading - let me know if there's something unclear.

Jan 24, 2011 at 1:08 PM
Edited Jan 24, 2011 at 1:09 PM

This response will concern debug.setlocal since it's looking pretty nasty. Now the problem here is, if I understand it correctly this: You need to be able to modify local variables in functions above the currently executing function on the call stack? Something like this (this will be javascript-pseudo-code, I haven't done any Lua in ages):

function bar() {
	debug.setlocal(null, 1, 1, 5); //set x (assuming x is index 1) to 5 in function at stack index 1
}

function foo() {
	var x = 10;
	bar();
	return x; //returns 5, not 10
}

I've been playing with something similar in IronJS (which would be a compiler option to turn on for debugging, etc.) and the fastest/best way I got this to work is the following:

  1. Each local scope is represented as an array of values (for simplicity we can say it's an object[] array, but if you read the IronJS source you'll see that it's actually a custom struct - not important here though), where each index is a local variable who's name is mapped to an index into this array at compile time
  2. The runtime keeps an internal call stack with these object[] local arrays, that is an object[][] is allocated (and expanded upon need) 
  3. The runtime also keeps a stack pointer (index into the object[][]) to where it currently is
  4. So, take the two functions above, assume we're calling foo(); this would happen:
    1. Increment the stack pointer by one
    2. Allocate a "new object[1]" array for the local variables in foo (that would be x)
    3. Store the new locals object in callstack[1]
    4. Enter foo()
    5. Set (x) locals[0] to 10
    6. Increment the stack pointer by one
    7. Allocate a "new object[0]" array for the local variables in bar (there are none)
    8. Store the new locals object in callstack[2]
    9. Enter bar()
    10. Call debug.setlocal(null, 1, 1, 5)
    11. debug.setlocal looks at callstack[1][1] to see that it exists and then sets it to 5
    12. bar() returns
    13. set callstack[2] = null
    14. decrement the stackpointer
    15. foo() returns
    16. set callstack[1] = null
    17. decrement the stackpointer
    18. program done.

This gives you complete control over the stack, allowing you to change values at will anywhere in the call-stack. The same structure "object[]" and "object[][]" lends itself to implement very flexible closures also (IronJS uses something akin to this for closures and the magic "arguments" object in JavaScript). This also allows you to save stack-state for when you need to implement continuations in Lua!

Jan 24, 2011 at 4:28 PM
Edited Jan 24, 2011 at 4:29 PM

fholm, thanks for your reply (and for IronJS of course).

Your solutions sounds right, and I did think of something similar - after all, no better way to managing locals than to managing them ourselves (though there may be an obscure Reflection method for this very purpose somewhere).

 

Still, if I'm not mistaken but may very well be, all of this must be some kind of custom expression that can be reduced to basic nodes. All part of a big expression tree that is eventually compiled. But basically all we're doing is inserting runtime shims into compiled methods? Sounds correct?

 

I'm also interested in your opinions about debug.sethook.

 

(Codeplex has a few issues on Opera, it seems).

 

 

Coordinator
Jan 24, 2011 at 4:31 PM

Also look at RuntimeVariablesExpression and IRuntimeVariables. The Expr Tree spec describes these, and Python uses them for its "locals" built in that returns a dict of name/value mappings. The interface lets the language implementation build mechanisms for inspecting and setting the local values of the ParamExprs listed in the RuntimeVariables expr.

Bill

From: fholm [email removed]
Sent: Monday, January 24, 2011 5:09 AM
To: Bill Chiles
Subject: Re: Implementing IronLua [dlr:243033]

From: fholm

This response will concern debug.setlocal since it's looking pretty nasty. Now the problem here is, if I understand it correctly this: You need to be able to modify local variables in functions above the currently executing function on the call stack? Something like this (this will be javascript-pseudo-code, I haven't done any Lua in ages):

function bar() {
  debug.setlocal(null, 1, 1, 5); //set x (assuming x is index 1) to 5 in function at stack index 1
}
 
function foo() {
  var x = 10;
  bar();
  return x; //returns 5, not 10
}

I've been playing with something similar in IronJS (which would be a compiler option to turn on for debugging, etc.) and the fastest/best way I got this to work is the following:

1. Each local scope is represented as an array of values (for simplicity we can say it's an object[] array, but if you read the IronJS source you'll see that it's actually a custom struct - not important here though), where each index is a local variable who's name is mapped to an index into this array at compile time

2. The runtime keeps an internal call stack with these object[] local arrays, that is an object[][] is allocated (and expanded upon need)

3. The runtime also keeps a stack pointer (index into the object[][]) to where it currently is

4. So, take the two functions above, assume we're calling foo(); this would happen:

1. Increment the stack pointer by one

2. Allocate a "new object[1]" array for the local variables in foo (that would be x)

3. Store the new locals object in callstack[1]

4. Enter foo()

5. Set (x) locals[0] to 10

6. Increment the stack pointer by one

7. Allocate a "new object[0]" array for the local variables in bar (there are none)

8. Store the new locals object in callstack[2]

9. Enter bar()

10. Call debug.setlocal(null, 1, 1, 5)

11. debug.setlocal looks at callstack[1][1] to see that it exists and then sets it to 5

12. bar() returns

13. set callstack[2] = null

14. decrement the stackpointer

15. foo() returns

16. set callstack[1] = null

17. decrement the stackpointer

18. program done.

This gives you complete control over the stack, allowing you to change values at will anywhere in the call-stack. The same structure "object[]" and "object[][]" lends itself to implement very flexible closures also (IronJS uses something akin to this for closures and the magic "arguments" object in JavaScript). This also allows you to save stack-state for when you need to implement continuations in Lua!

Jan 24, 2011 at 5:04 PM

rcollina: Yes, it's all runtime "hooks" (not to be confused with the debug.sethook you talked about) that are inserted into the expression tree before it's compiled. This was the only way I could get the full flexibility I wanted (saving and restoring the whole callstack, easily managed closures, mutating the the callstack as it's executing). Yes there is a tiny overhead of using object[] arrays to store all local variables instead of using the RuntimeVariables expression that billchi talked about - but I've found it worth it because it allows me to keep all variable and value representations as one single type: object[] (the real type is IronJS is BoxedValue[], but that's not really relevant).

Now, about debug.sethook (and the rest of the pretty awkward debug. functions) - it looks pretty messy, especially the "l" hook which is supposed to be called on every line of code. The way I see this there's two ways of doing it: 

  1. You're going to have some type of Environment object you're passing around (you always do) - have a boolean flag for each type of hook on it that get's set to true if a hook for that type has been set, for example Environment.LineHook, then after (or before) each line/function/return you have a statement that basically says "if(env.LineHook) { /* call hooks */ }". This is pretty messy and slows down your overall execution speed, even with branch-prediction it'll cost you a fair bit.
  2. (This is what IronJS does to handle all these "weird"/"odd" cases, for example "eval", etc.) You implement functionality to re-compile all the executing code/functions when you hit a call to debug.sethook, this will mean you take a slight performance hit when you step into the first debug.sethook. You still use the same scheme as described in #1 with .LineHook, .CallHook and .ReturnHook but the checks and calls to them only get injected into the code when it's re-compiled when you hit the first debug.sethook. I would recommend that you do lazy re-compilation and re-compile functions as they get called and not re-compile every piece of loaded code by marking all active functions with some bit- or boolean-flag that it needs to be re-compiled the next time it gets invoked.

 

Jan 24, 2011 at 5:16 PM
Edited Jan 24, 2011 at 5:18 PM

Thanks Bill, I'll be sure search for those in the spec. Is there something akin for closed-over variables as well?

As for call stack frames, I think IronPython solves this already, it's a matter of digging it up from the source I believe.

Just for reference, this is how debug.sethook works:

debug.sethook ([thread,] hook, mask [, count])

Sets the given function as a hook. The string mask and the number count describe when the hook will be called. The string mask may have the following characters, with the given meaning:
"c": the hook is called every time Lua calls a function;
"r": the hook is called every time Lua returns from a function;
"l": the hook is called every time Lua enters a new line of code.

With a count different from zero, the hook is called after every count instructions.

When called without arguments, debug.sethook turns off the hook.

When the hook is called, its first parameter is a string describing the event that has triggered its call: "call" (or "tail call"), "return", "line", and "count". For line events, the hook also gets the new line number as its second parameter. Inside a hook, you can call getinfo with level 2 to get more information about the running function (level 0 is the getinfo function, and level 1 is the hook function).

As you can see, these niceties are why almost every Lua implementation for .NET failed so far (and we've barely mentioned coroutines).

 Edit: I'm going to read your reply now fholm, posted while I was writing this.

Jan 24, 2011 at 5:27 PM

Yes the DLR supports closures. They are quite slow however due to a CLR bug that haven't been fixed yet. So I would recommand to implement your own stack frames and closures like IronPython, IronRuby and IronJS do.

Jan 24, 2011 at 5:28 PM
fholm wrote:

(This is what IronJS does to handle all these "weird"/"odd" cases, for example "eval", etc.) You implement functionality to re-compile all the executing code/functions when you hit a call to debug.sethook, this will mean you take a slight performance hit when you step into the first debug.sethook. You still use the same scheme as described in #1 with .LineHook, .CallHook and .ReturnHook but the checks and calls to them only get injected into the code when it's re-compiled when you hit the first debug.sethook. I would recommend that you do lazy re-compilation and re-compile functions as they get called and not re-compile every piece of loaded code by marking all active functions with some bit- or boolean-flag that it needs to be re-compiled the next time it gets invoked. 

Very well thought out. Thanks!

The Lua philosophy behind debug methods is that they can be (and most likely are) slow, and it's not something you'd use routinely - in 5.2 you have to require the debug module explicitly as opposed to begin already imported like in 5.1. I'm perfectly fine with compiling debug-ready methods. The biggest issue was enabling these hooks, but with smart recompilation I can deal with this just fine.

Rob

Jan 24, 2011 at 5:31 PM

BTW, are you sure these debugging APIs are critical to implement? I believe you can provide a debugging/profiling story that is tailored to .NET, might be easier to implement and even work better.

Jan 24, 2011 at 5:36 PM
Edited Jan 24, 2011 at 5:48 PM
TomasMatousek wrote:

Yes the DLR supports closures. They are quite slow however due to a CLR bug that haven't been fixed yet. So I would recommand to implement your own stack frames and closures like IronPython, IronRuby and IronJS do.

--

BTW, are you sure these debugging APIs are critical to implement? I believe you can provide a debugging/profiling story that is tailored to .NET, might be easier to implement and even work better.

 Ouch. Where can I read more about this CLR bug? Merely out of curiosity.

This is unexpected. I'll have to commit more time to source reading I guess. An outline of the current state of the art would be nice, just to pinpoint the most important source files.

Thanks, TomasMatousek.

Edit: the thought of implementing .NET-tailored debugging facilities is temping, and if things get tough, this time the tough won't get going but just accept and change route... :)

Coordinator
Jan 24, 2011 at 5:37 PM

Actually Python doesn’t use these at all anymore. The big problem was that performance of these when mixed with dynamic methods was pretty bad because you can’t do ldftn on a dynamic method (a limitation of ref emit). Instead it needs to make a reflection call which creates the delegate and is quite slow. So now we manually construct functions which receive the closure argument so we only need to create the delegate to them once – and can then re-use that delegate with different closures. For a serious language implementation I would suggest doing the same.

From: billchi [email removed]
Sent: Monday, January 24, 2011 8:32 AM
To: Dino Viehland
Subject: Re: Implementing IronLua [dlr:243033]

From: billchi

Also look at RuntimeVariablesExpression and IRuntimeVariables. The Expr Tree spec describes these, and Python uses them for its "locals" built in that returns a dict of name/value mappings. The interface lets the language implementation build mechanisms for inspecting and setting the local values of the ParamExprs listed in the RuntimeVariables expr.

Bill

From: fholm [email removed]
Sent: Monday, January 24, 2011 5:09 AM
To: Bill Chiles
Subject: Re: Implementing IronLua [dlr:243033]

From: fholm

This response will concern debug.setlocal since it's looking pretty nasty. Now the problem here is, if I understand it correctly this: You need to be able to modify local variables in functions above the currently executing function on the call stack? Something like this (this will be javascript-pseudo-code, I haven't done any Lua in ages):

function bar() {
  debug.setlocal(null, 1, 1, 5); //set x (assuming x is index 1) to 5 in function at stack index 1
}
 
function foo() {
  var x = 10;
  bar();
  return x; //returns 5, not 10
}

I've been playing with something similar in IronJS (which would be a compiler option to turn on for debugging, etc.) and the fastest/best way I got this to work is the following:

1. Each local scope is represented as an array of values (for simplicity we can say it's an object[] array, but if you read the IronJS source you'll see that it's actually a custom struct - not important here though), where each index is a local variable who's name is mapped to an index into this array at compile time

2. The runtime keeps an internal call stack with these object[] local arrays, that is an object[][] is allocated (and expanded upon need)

3. The runtime also keeps a stack pointer (index into the object[][]) to where it currently is

4. So, take the two functions above, assume we're calling foo(); this would happen:

1. Increment the stack pointer by one

2. Allocate a "new object[1]" array for the local variables in foo (that would be x)

3. Store the new locals object in callstack[1]

4. Enter foo()

5. Set (x) locals[0] to 10

6. Increment the stack pointer by one

7. Allocate a "new object[0]" array for the local variables in bar (there are none)

8. Store the new locals object in callstack[2]

9. Enter bar()

10. Call debug.setlocal(null, 1, 1, 5)

11. debug.setlocal looks at callstack[1][1] to see that it exists and then sets it to 5

12. bar() returns

13. set callstack[2] = null

14. decrement the stackpointer

15. foo() returns

16. set callstack[1] = null

17. decrement the stackpointer

18. program done.

This gives you complete control over the stack, allowing you to change values at will anywhere in the call-stack. The same structure "object[]" and "object[][]" lends itself to implement very flexible closures also (IronJS uses something akin to this for closures and the magic "arguments" object in JavaScript). This also allows you to save stack-state for when you need to implement continuations in Lua!

Jan 24, 2011 at 5:55 PM

rcollina: There are several other benefits of having the ability to dynamically re-compile functions during runtime, IronJS for example uses a static analyzer and a per-function type-specializing JIT compiler to achieve as much static typing as possible (which gives a pretty hefty performance boost). However I would strongly recommend you to closely evaluate the way IronRuby, IronPython and IronJS deal with things such as stack frames, scope and closures to get a good overview of your options. Even though I have read most of the IronRuby and IronPython sources I am of course most familiar with IronJS, though IR and IPy are a lot more mature then Ijs but the way I described previously - using arrays and arrays of arrays to represent the locals, closures, stack frames and the stack itself - is by far the fastest I've been able to come up with over the year I've been working on Ijs.

Another way you can do is to have a compiler flag that sets if you allow the import of debug or not, and if the flag is present you put the checks + calls in for .LineHooks, .CallHooks, .ReturnHooks, etc. This would make the compiler easier to construct, not needing access to it from the runtime or be able to "switch out" functions.

 

Jan 24, 2011 at 6:15 PM
Edited Jan 24, 2011 at 6:16 PM

dinov: thanks for the clarification.

fholm: thanks again for your help. It's much appreciated. I guess I have to invest some time in source code reading. Also, learning a bit of Python and Ruby won't hurt.

Just to make sure I got it right: there's currently three implementations of call stack frames, closures and local value introspection on top of the DLR right now?

Rob

Jan 24, 2011 at 6:23 PM

rcollina: Well, I would say there is one implementation per language on the DLR - as far as I know there isn't any re-use of code between languages for these constructs (or any other then the core of the DLR). If you have any more specific questions about implementation details you can add me on msn: fredrik@loveandtheft.org or hop in on ##fsharp on irc.freenode.net

Jan 24, 2011 at 6:32 PM
fholm wrote:

rcollina: Well, I would say there is one implementation per language on the DLR - as far as I know there isn't any re-use of code between languages for these constructs (or any other then the core of the DLR). If you have any more specific questions about implementation details you can add me on msn: fredrik@loveandtheft.org or hop in on ##fsharp on irc.freenode.net

Thanks, I don't use MSN that often anymore but should I ever have questions about IronJs I'll be sure to add you and ask the author directly :)