Re: Turing-incomplete Lua?

[Matt Hellige <matt@...>]

[Jeff Koftinoff <jeffk@jdkoftinoff.com>]
> 
> But if you made the mini-lua grammar simple enough you could guarantee 
> that there would be no possibility of infinite loops.  A timeout is 
> problematic in many ways! Please don't do things like that.

Actually, I agree... 

> If you just restrict the grammar so that all loops have a fixed repeat 
> count (non-variable) and no recursive function definitions are allowed 
> then you don't need a sandbox and you don't need problematic 
> halt-sensing and you can be guaranteed that the config file will never 
> halt your process.  I believe a system like this would be very very 
> useful.

Again, I agree. It's certainly possible, too, but I'm not sure that
adapting an existing language/interpreter is the best way to get
there. For instance, mutually recursive functions are also
problematic, so you'd need a somewhat more sophisticated analysis than
"no recursion". My suspicion is that programs which are provably
bounded in time are also bounded in memory consumption, but maybe
you'd want an additional limit on allocation. 

I recall a recent discussion, maybe on Lambda the Ultimate, about the
usefulness of non-Turing complete DSLs. This is definitely a case of
that. If there's a simple and easily understood restriction of Lua
that fits nicely, I think it would be a very good option. But I wonder
if the restrictions would get too complicated and non-intuitive?

Matt

-- 
Matt Hellige                  matt@immute.net