another hat in the ring regarding Lua 5.2: static typing

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

another hat in the ring regarding Lua 5.2: static typing

Norman Ramsey-2
I dream of one day being able to do static type inference
on my Lua programs, thereby catching innumerable silly errors.
I worked on this problem one summer with Inna Zakharevich, and
it's not clear that we will ever get anywhere, but I would
dearly love it if Lua 5.2 contained some syntactic hooks
that could be used to write down type definitions and
to write down the types of some variables.  Since we have
no idea what we want, I'd simply ask for a syntax

  typedecl string-literal

which the current compiler would ignore.

I realize the same effect could be achieved at present by simple

  function typedecl() end

but (a) that would have a small run-time cost and (b) I'm really
asking the Lua team to pick a keyword and reserve it for future use.



Norman

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Alex Davies
I'm sorry to say but you'll be disappointed. Lua currently has few keywords, and there is great hesitation before adding a useful one. See the recent multidozen reply continue thread for an example. To add a keyword that does nothing, and will (almost definitely) never do anything, would be very counter-lua.

So why not just use metalua? http://metalua.luaforge.net/ You could easily add a keyword which acts as a single line comment in that. Or if you prefer regular Lua, why not just use a comment? Your editor might even allow colouring --typedecl differently to regular comments, with enough tweaking.

- Alex

----- Original Message ----- From: "Norman Ramsey" <[hidden email]>
To: <[hidden email]>
Sent: Wednesday, February 27, 2008 4:05 AM
Subject: another hat in the ring regarding Lua 5.2: static typing


I dream of one day being able to do static type inference
on my Lua programs, thereby catching innumerable silly errors.
I worked on this problem one summer with Inna Zakharevich, and
it's not clear that we will ever get anywhere, but I would
dearly love it if Lua 5.2 contained some syntactic hooks
that could be used to write down type definitions and
to write down the types of some variables.  Since we have
no idea what we want, I'd simply ask for a syntax

 typedecl string-literal

which the current compiler would ignore.

I realize the same effect could be achieved at present by simple

 function typedecl() end

but (a) that would have a small run-time cost and (b) I'm really
asking the Lua team to pick a keyword and reserve it for future use.



Norman

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Asko Kauppi

LuaSub gives '-sjacket' for making runtime type checks, and it works like this:

tests/test-jacket.lua:

local function mydear( t :string_or_table, i :int, j :[int], n : [number] )
	    : string, table, [int]
		...function body with returns...
	end

't' is either string or table (checked by 'assert.string_or_table()')
'i' is integer ('assert.int()')
'j' is an optional integer (nil or fulfilling 'assert.int()')
'n' is ...

The point is that any 'xxx' can be used to forward to 'assert.xxx' as an assertion for such a type.

'assert', in itself, is a callable table, having some default assertions s.a. '.table', '.number', '.int' and so on.

One can also do more, like ': range(-1,3)' but that's not relevant.

This does _not_ do static checking, but could be the first step towards such analysis. I believe Fabien has some experience in this as well, and a similar notation.

The ': string, table, [int]' are of course the return value assertions.

For real world tests, try out luaSub at: http://luaforge.net/frs/?group_id=311

-asko


Alex Davies kirjoitti 28.2.2008 kello 19:49:

I'm sorry to say but you'll be disappointed. Lua currently has few keywords, and there is great hesitation before adding a useful one. See the recent multidozen reply continue thread for an example. To add a keyword that does nothing, and will (almost definitely) never do anything, would be very counter-lua.

So why not just use metalua? http://metalua.luaforge.net/ You could easily add a keyword which acts as a single line comment in that. Or if you prefer regular Lua, why not just use a comment? Your editor might even allow colouring --typedecl differently to regular comments, with enough tweaking.

- Alex

----- Original Message ----- From: "Norman Ramsey" <[hidden email] >
To: <[hidden email]>
Sent: Wednesday, February 27, 2008 4:05 AM
Subject: another hat in the ring regarding Lua 5.2: static typing


I dream of one day being able to do static type inference
on my Lua programs, thereby catching innumerable silly errors.
I worked on this problem one summer with Inna Zakharevich, and
it's not clear that we will ever get anywhere, but I would
dearly love it if Lua 5.2 contained some syntactic hooks
that could be used to write down type definitions and
to write down the types of some variables.  Since we have
no idea what we want, I'd simply ask for a syntax

typedecl string-literal

which the current compiler would ignore.

I realize the same effect could be achieved at present by simple

function typedecl() end

but (a) that would have a small run-time cost and (b) I'm really
asking the Lua team to pick a keyword and reserve it for future use.



Norman


Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Mark Hamburg-4
on 2/28/08 11:16 AM, Asko Kauppi at [hidden email] wrote:

> 
> LuaSub gives '-sjacket' for making runtime type checks, and it works
> like this:
> 
> tests/test-jacket.lua:
> 
> local function mydear( t :string_or_table, i :int, j :[int], n :
> [number] )
>    : string, table, [int]
> ...function body with returns...
> end
> 
> 't' is either string or table (checked by 'assert.string_or_table()')
> 'i' is integer ('assert.int()')
> 'j' is an optional integer (nil or fulfilling 'assert.int()')
> 'n' is ...

It's interesting syntactic sugar. Obviously this could be handled by
assertions in the code but sugar might increase the chance that they would
get written.

Are they optional on a compilation and if so how do you switch them on and
off? Maybe if they only applied to functions it wouldn't matter as much.
Maybe a tracing JIT makes their cost drop low enough in practice so as not
to matter. And if optional, one needs to be careful not to have any side
effects in the functions.

But I like the general notion.

Have you taken any of the standard benchmark code and added type assertions
to see what sort of expense they incur?

Mark



Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Mike Pall-82
Mark Hamburg wrote:
> ... [runtime type assertions] ...
> Maybe a tracing JIT makes their cost drop low enough in practice so as not
> to matter.

Yes, they are usually subsumed or eliminated.

Here's how this works with LuaJIT 2.x for a simple example:

  assert(type(x) == "number")
  y = x + 1.5

The first line is transformed into a single ISNUM ucode. This is
a type-checking guard which exits the trace if its precondition
later turns out not to be true.

The bytecode generated for the first line is not trivial (it has
two calls and a conditional expression). The transformation to a
single ucode is quite involved, but most of it can be done while
recording:

- type() specializes on its argument type by emitting an ISNUM
  (because this is the runtime type of x, NOT because its result
  is later compared to a string). This allows it to return a
  constant value ("number" in this case).

- The comparison "number" == "number" can be constant folded to a
  true value. No code is generated.

  [Some details left out: the bytecode only has branching
  conditionals. Conditional expressions used in a non-conditional
  context need to be transformed to a two-way branch by the
  parser. The two arms hold a true and a false assignment. The
  interpreter already evaluates this, so the recorder can just
  collect the "right" constant assignment.]

- The assert() is passed the constant true value. It's eliminated
  with constant folding, too. The return value (true) is unused
  by the function call statement.

This leaves us with a single ISNUM guard for x. The FP addition
causes the same guard and a FADD. The 2nd instance of the guard
is subsumed with CSE (yes, this works on guards, too). The
remaining unused constants are ignored during code generation
which employs on-the-fly dead-code elimination.

End result: a single type check and the FP addition (two machine
code instructions). The complex type assertion has been
completely optimized away.

The remaining type check can most probably be eliminated, too.
But this depends on the surrounding context: e.g. with x = a*3.5
the multiplication result already has a constant type, or with
x = 1.5 constant folding happens again.

If you call the above code snippet in a loop, the type check can
usually be hoisted out of the loop. It doesn't matter whether
parts of the code are inside of yet another function or not. All
runtime control-flow is inlined, function boundaries are ignored
(so go ahead and define checknum(x)).

Summary: you can leave those assert()'s in with LuaJIT 2.x. But
write them in plain Lua and not in specialized C functions. These
are black boxes for the compiler and cannot be optimized away.

--Mike

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Hisham Muhammad
On Thu, Feb 28, 2008 at 11:23 PM, Mike Pall <[hidden email]> wrote:
>   assert(type(x) == "number")
...
>  Summary: you can leave those assert()'s in with LuaJIT 2.x. But
>  write them in plain Lua and not in specialized C functions. These
>  are black boxes for the compiler and cannot be optimized away.

That's great to hear. I have systematically added such assert()'s to
all function arguments in the code of LuaRocks (and things such as
assert(type(x) == "number" or not x) for optional arguments). They're
somewhat annoying to write (and at times it looks weird that a
function is three lines long and two of them are type assertions), but
they have proven useful quite a few times already.

-- Hisham

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

steve donovan
In reply to this post by Asko Kauppi
On Thu, Feb 28, 2008 at 9:16 PM, Asko Kauppi <[hidden email]> wrote:
>         local function mydear( t :string_or_table, i :int, j :[int], n :
>  [number] )
>             : string, table, [int]
>                 ...function body with returns...
>         end

Nice notation!  I was thinking about this general problem the other
day: how does one explcitly specify type in a dynamic language? The
idea was that types are objects, and one builds them up with
expressions:
    string_or_table = choice(String,Table)
    string_or_nil = choice(String,Nil)
    Location = choice({X=Double,Y=Double},{Double,Double})

A more interesting question is how far one can push static type
inference. I had a brief affair with Boo, which is a Python-like
compiled language where the only type annotations are usually in
method signatures. Cool, but boy the compiler was slow!

steve d.

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Alex Davies
In reply to this post by Mike Pall-82
Impressive that jit 2.x performs loop hoisting, but how is it that neither assert nor type need to be checked? The only thing I can think of is that it is assumed that they are both stored in upvalues, and that jit 2.x checks that nothing modifies those upvalues. If so, wouldn't that cause problems with debug.setupvalue =/? Intrigued. Sounds good though.

- Alex

----- Original Message ----- From: "Mike Pall"


The first line is transformed into a single ISNUM ucode. This is
a type-checking guard which exits the trace if its precondition
later turns out not to be true.

The bytecode generated for the first line is not trivial (it has
two calls and a conditional expression). The transformation to a
single ucode is quite involved, but most of it can be done while
recording:

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Asko Kauppi
In reply to this post by Mark Hamburg-4

Mark Hamburg kirjoitti 29.2.2008 kello 2:11:

on 2/28/08 11:16 AM, Asko Kauppi at [hidden email] wrote:


LuaSub gives '-sjacket' for making runtime type checks, and it works
like this:

tests/test-jacket.lua:

local function mydear( t :string_or_table, i :int, j :[int], n :
[number] )
 : string, table, [int]
...function body with returns...
end

't' is either string or table (checked by 'assert.string_or_table()')
'i' is integer ('assert.int()')
'j' is an optional integer (nil or fulfilling 'assert.int()')
'n' is ...

It's interesting syntactic sugar. Obviously this could be handled by
assertions in the code but sugar might increase the chance that they would
get written.

This is exactly the point. I've often used assertions like that but this just makes it
	- in one place (also returns)
	- less verbose



Are they optional on a compilation and if so how do you switch them on and off? Maybe if they only applied to functions it wouldn't matter as much.

The syntax mod can be told to just skip them.

This will turn them off (just skip them in the source):

	luas -sjacket.OFF yourfile.lua

I used to have different mods for the 'off' and 'on' modes, but the way to signal the one mod is way better; it needs to know the syntax of the extension anyways. Jacket is the only mod I currently use arguments for, but the mechanism is available for any mod for any purpose.


Maybe a tracing JIT makes their cost drop low enough in practice so as not to matter. And if optional, one needs to be careful not to have any side
effects in the functions.

Well, 'assert.*()' functions should hardly have any side effects. :)



But I like the general notion.

Thank You!  :)



Have you taken any of the standard benchmark code and added type assertions
to see what sort of expense they incur?

Nope. I'm currently in the process of transforming Lumikki (XML generation) to use them. I'll draw my performance numbers from that, but you're welcome to test with anything.

Note that some code suits badly to any constraints. That's why they are _always_ optional anyways. You can say:

	a			-- just the parameter, no constraint
	a : table		-- use built in constraints
	a : my_table	-- any assertion about how your table is expected to be
or even
	a : { a=int, b=string, ... }	-- a bit strecthing, but also this works

Constraining also the writing to variables is not implemented, yet, but would follow the same syntax.

-asko




Mark




Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Miles Bader
In reply to this post by steve donovan
"steve donovan" <[hidden email]> writes:
> Nice notation!  I was thinking about this general problem the other
> day: how does one explcitly specify type in a dynamic language?

You might want to look at common-lisp, which has a fairly developed
type-system.

j-Miles

-- 
Neighbor, n. One whom we are commanded to love as ourselves, and who does all
he knows how to make us disobedient.

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Fabien-3
In reply to this post by Norman Ramsey-2
There's some dynamic type checking offered with metalua with -{extension 'types'}. A description of a previous version can be found at http://metalua.blogspot.com/2007/04/type-checking-reloaded.html.

The type description language is fairly rich, with type unions and intersections, parametric and dependent types, intuitive syntax for structures, etc. Types are attached to variables, not values, i.e. if you re-assign a new value to a variable, the value's type will be re-checked. It can obviously be switched off, with -{stat: types.enabled = false}. It also has a namespace handling mechanism, so that you can define as many type declarations, functors etc. as you want without fear that it will interfere with "real" code (type definitions are in http://repo.or.cz/w/metalua.git?a=blob_plain;f=src/lib/extension/types-runtime.mlua).

I've also started working on static type inference with a subset of Lua, but that's more for fun than with real hopes for production use: a static Lua would not be Lua anymore, it would rather feel like a weird cousin of Scala. The main interest of that calculus would rather be to experiment with some academic ideas, by making them much cheaper to implement.

Another track, which seems most promising to me, would be to design some super-lint: static code analysis that raises warnings on suspicious stuff, yet lets you compile them, advises you to protect this and that with dynamic checks, etc. The kind of tool taht would go in a pre-commit hook. I think that static type inference reached its optimal helpfulness with Haskell, we need to explore other approaches if we hope to ever do better. Almost-trivial checks like global vars usage and type-checking of native functions would be an easy first step.

You can play and add typing errors in http://repo.or.cz/w/metalua.git?a=blob_plain;f=src/samples/types_test.mlua to see how they are caught:
-{ extension "types" }
-{ extension "clist" }

-- Uncomment this to turn typechecking code generation off:
-- -{stat: types.enabled=false}


function sum (x :: table(number)) :: number
local acc :: number = 0
for i=1, #x do
acc = acc + x[i]
end
return acc
end

x = { i for i=1,100 }
y = sum (x)
printf ("sum 1 .. %i = %i", #x, y)

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Tomás Guisasola-2
In reply to this post by steve donovan
On Fri, 29 Feb 2008, steve donovan wrote:
> On Thu, Feb 28, 2008 at 9:16 PM, Asko Kauppi <[hidden email]> wrote:
> >         local function mydear( t :string_or_table, i :int, j :[int], n :
> >  [number] )
> >             : string, table, [int]
> >                 ...function body with returns...
> >         end
> 
> Nice notation!  I was thinking about this general problem the other
> day: how does one explcitly specify type in a dynamic language? The
> idea was that types are objects, and one builds them up with
> expressions:
>     string_or_table = choice(String,Table)
>     string_or_nil = choice(String,Nil)
>     Location = choice({X=Double,Y=Double},{Double,Double})
	I like that syntax either, but I have some doubts :-)
	Could you accept a proxy table instead of the real table?
How would you specify that?  How would you specify properties of
objects?  An example of what I am looking for is:

function get_status (db, id)
	local cond = "id="..id.." AND estado_retorno is not null"
	return db:select ("status", "processo", cond)()
end

	How would you specify that you can call db's select?
I am not interested in the real type of db: it could be a userdata
or a table, and in this case it could have the field select or it
could have a metatable with a __index metamethod; also, the select
object could be a function or a "callable" object...  How would you
manage that?
	I am not sure if we should check the _type_ or the operations
we want.  In my case, I only care about db.select being a callable
object.  One might argue that I would have to check its arguments,
but I would delegate it for the call itself.

	Regards,
		Tomas

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Asko Kauppi

The syntax mod only transforms the constraints into 'assert.*()' calls. You can either override 'assert.table' with your own function, or use another name.

The sample case you mentioned would be covered roughly by (in a hurry, but gives the point):

<<
local function callable( v, field )
	if type(v) == "table" and type(v[field])=="function" then
		return true
	else
		local mt= getmetatable(v)
		if mt.__index and type(v[field])=="function" then
			return true
		end
	end
end

assert.select_callable= function( v )
	assert( callable( v, "select" ), "No .select function", 2 )
	return v
end
<<

That code should be somewhere in your app prior to using the ': select_callable' constraint.

There could be more factory support for making such custom asserts easier, but these are the rough edges that will be covered during the spring. Anything is already possible. :)

Happy weekend!
-asko


Tomas Guisasola Gorham kirjoitti 29.2.2008 kello 14:09:

On Fri, 29 Feb 2008, steve donovan wrote:
On Thu, Feb 28, 2008 at 9:16 PM, Asko Kauppi <[hidden email]> wrote:
local function mydear( t :string_or_table, i :int, j : [int], n :
[number] )
           : string, table, [int]
               ...function body with returns...
       end

Nice notation!  I was thinking about this general problem the other
day: how does one explcitly specify type in a dynamic language? The
idea was that types are objects, and one builds them up with
expressions:
   string_or_table = choice(String,Table)
   string_or_nil = choice(String,Nil)
   Location = choice({X=Double,Y=Double},{Double,Double})
	I like that syntax either, but I have some doubts :-)
	Could you accept a proxy table instead of the real table?
How would you specify that?  How would you specify properties of
objects?  An example of what I am looking for is:

function get_status (db, id)
	local cond = "id="..id.." AND estado_retorno is not null"
	return db:select ("status", "processo", cond)()
end

	How would you specify that you can call db's select?
I am not interested in the real type of db: it could be a userdata
or a table, and in this case it could have the field select or it
could have a metatable with a __index metamethod; also, the select
object could be a function or a "callable" object...  How would you
manage that?
	I am not sure if we should check the _type_ or the operations
we want.  In my case, I only care about db.select being a callable
object.  One might argue that I would have to check its arguments,
but I would delegate it for the call itself.

	Regards,
		Tomas


Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Fabien-3
In reply to this post by steve donovan
On Fri, Feb 29, 2008 at 9:04 AM, steve donovan <[hidden email]> wrote:
I was thinking about this general problem the other
day: how does one explcitly specify type in a dynamic language? The
idea was that types are objects, and one builds them up with
expressions:
   string_or_table = choice(String,Table)
   string_or_nil = choice(String,Nil)
   Location = choice({X=Double,Y=Double},{Double,Double})

I like to reuse regular _expression_ constructs for this. Your examples are written in metalua:
"string or table"
"string or nil" (although you can define "option(string)" with "newtype option(x) = x or nil"
"newtype location = {X=number, Y=number} or {number, number}" (or if you prefer: "newtype location = {X=number, Y=number} or table(2, number)").

Basically, you can redefine the meaning of all operators in a type declaration context, and by default, "and" and "or" are defined as type intersection and union.

A more interesting question is how far one can push static type
inference. I had a brief affair with Boo, which is a Python-like
compiled language where the only type annotations are usually in
method signatures. Cool, but boy the compiler was slow!

Static type checking/inference is a serious burden on code writing. For it to be worth it, you'd better have very strong guarantees of soundness on checked code. In all sound mixed static/dynamic systems I've met, soon enough dynamism creeps in all parts of your code base, and the static type system doesn't know anything useful anymore about your code.

Qi is rather interesting, as an almost practical mixed static/dynamic system, but it's based on sequent calculus, so you'd better be a maths geek if you want to like it.

A final remark about type-checking: I think there are many cases where it makes sense to check plain Lua code, not only extended Lua. It's doable if type declarations are stored either in separate files, or in comments, or in plain Lua data; I've got a couple of related stuff in my heap of unpublished/unfinished hacks...

-- Fabien.
Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Alexander Gladysh
In reply to this post by Mark Hamburg-4
>  > LuaSub gives '-sjacket' for making runtime type checks, and it works
>  > like this:
>  >
>  > tests/test-jacket.lua:
>  >
>  > local function mydear( t :string_or_table, i :int, j :[int], n :
>  > [number] )
>  >    : string, table, [int]
>  > ...function body with returns...
>  > end
>  >
>  > 't' is either string or table (checked by 'assert.string_or_table()')
>  > 'i' is integer ('assert.int()')
>  > 'j' is an optional integer (nil or fulfilling 'assert.int()')
>  > 'n' is ...
>
>  It's interesting syntactic sugar. Obviously this could be handled by
>  assertions in the code but sugar might increase the chance that they would
>  get written.

We heavilly use argument type validation in our engine-level Lua
function (that is, written by experienced programmers, not by end-user
scriptors).

Like this (silly example):

local string_rep = function(s, n)
  n = n or 1
  assert_is_string(s) -- basically a wrapper on assert(type(s) == "string")
  assert_is_number(n)

  if n > 1 then
    local t = {}
    for i = 1, n do
      t[i] = s
    end
    s = table.concat(t)
  end
  return s
end

Actually most of our code have such type checks.

When I saw this post by David Manura on decorators in Lua,

http://lua-users.org/lists/lua-l/2007-09/msg00271.html

I thought of implementing something along these lines:

local string_rep =
  docs
  [[Returns a string that is the concatenation
  of n copies of the string s.]] ..
  args { 'string', optional 'number' (1) } ..
  rets { 'string' } ..
  function (s, n)
    if n > 1 then
      local t = {}
      for i = 1, n do
        t[i] = s
      end
      s = table.concat(t)
    end
    return s
  end

This could allow writing inplace function documentation (suitable for
run-time help) and call contract validation (arguments, preconditions,
return values, postconditons) in plain Lua. Also suitable to ease
automatical code instrumentation for, say, call tracing or profiling
etc..

Contract validation functions could be pre-generated on the
initialization time. Also it should not be hard to skip all those
calls in 'release' version of Lua scripts (just generate them as
no-ops).

Still have to find some time to actually try this though. :-)

Alexander.

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Mark Hamburg-4
I think one of the chief reasons people use static type checking these days
is to help with refactoring. Maybe dynamic languages just need a different
solution in that regard.

Static type checking automatically gives one something that approximates
code coverage unit tests for a particular class of assertions to be checked,
but from  refactoring standpoint the key issue is being able to do things
like find all calls to a particular function or method.

Mark



Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Mike Pall-83
In reply to this post by Alex Davies
Alex Davies wrote:
> Impressive that jit 2.x performs loop hoisting, but how is it that neither 
> assert nor type need to be checked? The only thing I can think of is that 
> it is assumed that they are both stored in upvalues, and that jit 2.x 
> checks that nothing modifies those upvalues. If so, wouldn't that cause 
> problems with debug.setupvalue =/? Intrigued. Sounds good though.

I've left out some details, but you're right -- this can get
tricky. Function identity checks can be hoisted out just like
type checks (conceptually this is the same).

I use optimistic hoisting for type checks (with a very high
success rate). If this leads to a PHI conflict at the end of the
loop (type has changed), the slots are blacklisted and the
recorder retries automatically.

Hoisting is quite easy for locals and upvalues. With one caveat:
open upvalues can alias locals in an outer frame -- which could
be part of the same trace.

Right now I don't care about interaction of the debug.* functions
with JIT-compiled code. They work fine with the interpreter and
you can just selectively disable compilation if necessary. But I
could use a trick similar to what I'm doing in lua_sethook(): if
you call it, it just aborts trace recording and drops back to the
interpreter. :-)

Hoisting of checks for functions stored in tables is a lot more
involved. This requires alias analysis, which is still on my TODO
list.

Lua's semantics permit use of t[k]-disambiguation (no pointers!).
And it doesn't have type aliasing problems. This is a lot better
than the low-level memory disambiguation one needs to do for
C/C++. And since the trace compiler has knowledge about runtime
values, it can insert appropriate runtime disambiguation checks
if static disambiguation fails.

Some examples for hoisting of the check for math.sqrt (these are
all inside a 'for i=1,n do' loop):

  -- No ambiguity: load with string key vs. load/store with numeric key.
  b[i] = math.sqrt(a[i])

  -- No ambiguity: "foo" ~= "math" and "foo" ~= "sqrt"
  t.foo = math.sqrt(t.foo+a[i])

  -- Needs a (hoisted) runtime check for t ~= math
  t.sqrt = math.sqrt(t.sqrt+a[i])

CSE for loads needs alias analysis, too:

  -- either a ~= b, then the 2nd a.foo is a CS for a.foo
  -- or     a == b, then the 2nd a.foo is a CS for a.foo+1
  b.foo = a.foo+1
  b.bar = a.foo

As you can see this can get arbitrarily complex. But I realize
I'll have to add this optimization sooner or later. It's the only
way to get good performance for methods written in OO-style.

--Mike

Reply | Threaded
Open this post in threaded view
|

Re: another hat in the ring regarding Lua 5.2: static typing

Alex Davies
----- Original Message ----- From: "Mike Pall"


As you can see this can get arbitrarily complex. But I realize
I'll have to add this optimization sooner or later. It's the only
way to get good performance for methods written in OO-style.

--Mike

It'd definitely be the most noticeable optimization that one could make to lua. Although I much rather that it's you and not me. Things like

setmetatable(t, { __newindex = function(t,k,v) rawset(t, "sqrt", v) })

would send me running as far away from the project as I can get =/. Definitely arbitrarily complex ;)

It sounds fair that the debug library (may) only work from within the interpreter. Particularly if jit can be selectively disabled (I'm not sure how that goes on a tracing jiter though).

Anyway, best of luck.

- Alex