Is there a standard way to evaluate "recursive" configurations (in lua).
I mean something like this (a simplified example where I configured mass and surface of an ice cube):
I need to periodically call "GetMass" from C. The function is supposed to return whatever is configured.
Now, the configuration is recursive in a sense that in order to calculate "surface" I need to calculate "volume", "volume" needs "width" and finally "width" needs to call "myfunc", whichs result changes over time. The relations defining "surface" do not need to be evaluated at this moment.
Thre real relations are much more and even deeper nested but not cyclic.
Is there a way to do this more effectively than just periodically calculating "everything"?
Is your question about efficiency? Are you trying to avoid computing a value if it has already been computed?
For the calculations you are doing, you won't be saving noticeable amounts of time.
If you need something to be evaluated later with the then-current value of variables, you need the calculation process to be a function.
You can do something like load the file into a function, and then run it in a given scope where you have set the values of interest. This way, the user thinks they're just writing declarative assignments, and you re-evaluate those assignments when necessary.
As Nick said, your problem isn't really one of recursion; it's more of a dependency tree for calculations.
What is the problem being solved here? I'm guessing it's not as simple as just recomputing stuff. Based on previous posts of yours, I'm guessing that you want users to be able to easily specify formulas for various things.
One thing worth noting is that your formulas are given in the wrong order, meaning that when Lua tries to evaluate 'mass', 'volume' and 'density' aren't available yet. This will cause problems.
So maybe "recursive" was not the best word to describe what I ment, since it is certainly nothing like a function calling itself (a self-referred/recursive function like "factorial"). I ment a value determined by a configured formula which uses input values that are themself configured in the same configuration file (a self-referred/recursive(?) configuration).
Maybe I should just call it "nested configuration"?
How would you call it?
I have to evaluate a set of formulas in a configuration: Some are just const values, some are formulas for final values (which are read from C), many are variables and formulas intermediate values which I do not need directly. From the mathematical point of view one could insert the intermediate formulas to get just a few *huge* formulas for the final values - but that's certainly not a good idea.
I want to use the configuration in a way one could also use an Excel spreadsheet. There you can also define "=C3+B7" as a formula in cell D4. Excel knows that an update for D4 is required when C3 changes - without recalculating the entire table, I think.
I don't want to program a static dependency analysis for the configured formulas. So the question is: what are my other options.
I could either let every getter-function recalculate the entire config (maybe even twice because of the order).
I could create an additional task doing nothing else than running lua in a cycle and let it store all values one might need (using CriticalSections, also for the Readers).
Any other (better) ideas?
I know that my formulas are exactly in the oposite order for lua. I did the formulas with exported results on top, the intermediate ones below. I did consider it a more natural way to configure things - so most likely some other people do as well. Since the formulas finally are not written by me I guess they can be in *any* order and the program should be able to deal with it.
Still the user (the author of the configuration) should not write more than a set of formulas with a similar structure to the ones in my last post.
One option is to keep evaluating the whole thing until every variable converges to a stable value, however you will need to deal with the fact that some computations will cause errors. For example, you cannot use variables whose value is nil in most mathematical operations.
You don't need to run it in a cycle, because the variables will converge (at least, with the formulas you gave). You would need to repeat the converging process every time an input changed, however.
Your comparison to Excel isn't really appropriate because its formulas are declarative, whereas you are feeding a program to an interpreter. This is why it is particularly problematic to see something like "mass = volume * density" when you do not have any value for volume and density.
It sounds like what you might need, in the most general case, is a way to get the parse tree of expressions in order to compute dependency graphs of values. But this is much more complicated than what I thought we were talking about.
Are there any more parameters to this problem? Is the set of input variables fixed? If the input names are fixed, then you can initialize them all to zero, then initialize the appropriate ones with user-supplied values, and then run the converging process.
Is there a standard way to evaluate "recursive" configurations (in lua).
As described now, I think I can say "not really".
You might be able to write a simple interpreter (in Lua, for example) that takes something like this:
mass = volume * density
Now if (say) volume is undefined (ie. nil) then it stops trying to evaluate the rest of it because we can't obtain a result.
However if we *can* evaluate mass (because we know both volume and density) then we do. And also our interpreter might know that volume is referred to in this calculation, so that if we ever change volume, then it has to recalculate mass. And then having recalculated mass it might know that some other variable has to be recalculated. But this is more like how a spreadsheet works, and isn't really straight Lua.
Conceivably you might take the simple formulae and (given a final result you actually want, like mass) you might generate the "huge" formula you mentioned by doing a substitution internally, and then evaluating that.
The best and most efficient way (and bearing in mind that fastest, easiest to write, easiest to understand, and the one that uses least memory, might all be mutually exclusive design goals) might depend heavily on what you really want to do as I gather your example of an ice cube was just an example of the general idea.
If you need the results once a week, and don't mind taking an hour to calculate them, then that is a different design environment to (say) needing to calculate it 60 times per second for some sort of interactive game.
However the "once a week" case might be considerably simpler to implement.
The formulas and configurations should be used for various purposes. The most demanding one is certainly a set of formulas used to determine "what to do now", whereas "now" is described by a set of variables which changes over time and "what to do" is determined by the C program by evaluating the formulas for the final value.
Some results need to be calculated several times a second with changing inputs. Consider it a soft realtime task in a sense that it is required for a fluent operation, while occasional lags are undesirably but not fatal. I have to think about whether using the previous value once in a while would be a problem.
So I think I could either use an update task triggered from the multimedia timer in a 100ms cycle (as a first idea - I have to do a more detailed tasking an timing plan in this casE).
The other option - every "GetSomethingFromConfing" call trigger an "update all" (in a worst case iterativ until convergence) could easily lead to the whole configuration being evaluated several thousend times a second (without iterations).
Maybe I have to explain in another example in more datail what my configuration files do:
My desired architecture would be to completly seperate the "engine" code (written in C/C++, containing GUI, IO-handling, network code, ...) from the "specific rules"/"individual requirements" (found in config files). The "rules" are configured by a non-programmer, while the "engine" is programmed by someone who does not know (and should not care about) all individual/specific requirements.
Isn't that a common problem?
One paricular example is to use config files to specify items: the conditions and costs to create an instance of them, conditions defining if they can be activated now (similar to the active/grayed-state in a menu), and what its activation causes. The config must define certain
properties with defined names for the C code - you may consider it a configured "item interface". Some basic manipulations can be done by the C code itself (e.g., the C code understands the concept "item" well enough to be able to MOVE the item), for everything else (activation, joining, ..) it needs to query the config for this item type. The C code needs different information from the configured rules, depending on the situation.
I think you are vastly overestimating how slow calculating those formulas would be. You could calculate those tens of thousands of times per second, maybe even hundreds of thousands of times per second, depending on your hardware. Those are really, really cheap computations. You really should not be worrying about performance for this problem. A much bigger concern is that you want the configuration to be a declarative specification for how to compute formulas.
Quote: The "rules" are configured by a non-programmer, while the "engine" is programmed by someone who does not know (and should not care about) all individual/specific requirements.
Isn't that a common problem?
Sort of. You're pushing it by trying to make the configuration file extremely simple, without even having functions defined.
The problem of separating rules and the engine is certainly common, but not pushed to this extreme AFAIK.
If you were willing to have something like this:
function mass()
return volume() * density()
end
this problem would be much simpler, because every time you called the function, you would get the most up to date values for volume and density (which are themselves functions).
I don't think it is unreasonable to require even a non-programmer to follow some simple rules, like "you need to define something before you use it".
So something like this is just rejected:
mass = volume * density
volume = length * width * height
... on the grounds that, on line 1, volume and density are not defined yet.
I mean, most people (I won't say all people) know that you, for example, get into the car, turn on the ignition, and then drive off. You don't:
* drive off
* then turn on the ignition
* then get into the car
It's just common sense. You could be making thing enormously complicated, and slow here, when ten minutes spent educating the end-user might be all that is required.
I see that for my original concept (specifying configuration as relations/equations in any order) a numerical algebra package (MathCad/Derive/.. - does anyone know an open source package?) might be more suitable than a scripting language. Essentialy I want to allow the user to just type a set of equations then state "solve for mass".
Seens like I have three options here:
1) Use a language as it is. Spend more time in training the users, less in implementation. Demand that users at least enter the relations in the order of evaluation.
2) Allow the user to specify relations in any order, do a replace preprocessing step (e.g., volume -> volume()).
3) Keep the syntax, write my own code to parse it, build my own dependency tree and evaluate it accordingly.
Anything else?
The speed aspect:
I already did some measurements comparing C and lua using the recursive faculty function. Using this function one can specify how many calculation steps should be done in the scripting language, just by changing the parameter. I used values between 0 (to test the input/output speed) and 10000 (I know the result won't fit in a double, but its a long calculation which still does not give a stack overflow).
So for fact(10000) lua needs about 1.6 times the calculation time of C (no matter if factorial was defined in a luac-precompiled lua library or an uncompiled one). This is pretty good - even surprisingly good.
However, by testing fact(0) I found that the bottleneck seems to be to get data into or out of lua. Using lua_genpall, fact(0) takes more than 3 mikroseconds. That's almost 100 times longer than in C. Building the lua stack without this comfort function speeds things up significantly, but a lua_pcall for fact(0) is still about 10 times slower as compared to C. The unprotected lua_call is a few percent faster, but I will exclude that for my purpose, since I need that protection to execute more or less untrusted code.
I expect lua to be a factor of 10 slower as compared to C in my case with a realistic set of equations, which is fully acceptable. However, I should avoid lua_genpcall and use lua_pcall which is less convenient but significantly faster.
Bernhard said: 1) Use a language as it is. Spend more time in training the users, less in implementation. Demand that users at least enter the relations in the order of evaluation.
2) Allow the user to specify relations in any order, do a replace preprocessing step (e.g., volume -> volume()).
3) Keep the syntax, write my own code to parse it, build my own dependency tree and evaluate it accordingly.
Anything else?
You can do some trickery with metatables on the global environment, if you are willing to make certain assumptions...
Set up a metatable such that any variable lookup that doesn't exist will result in zero (or NaN or something). This means that anything that's not found will necessarily be a number, which might not be what you want if you have user functions.
Then, evaluate the function (which is the code block for loading the config file formulas) over and over again until variables stop changing. (Of course, this will be broken if your formulas don't converge on a single value.)
Taking a simple example:
mass = volume * density
density = volume * 2
volume = 2
Pass 1:
mass = volume * density --> evaluated as mass = 0 * 0 = 0
density = volume * 2 --> evaluated as density = 0 * 2 = 0
volume = 2
Pass 2:
mass = volume * density --> evaluated as mass = 2 * 0 = 0
density = volume * 2 --> evaluated as density = 2 * 2 = 4
volume = 2
Pass 3:
mass = volume * density --> mass = 2 * 4 = 8
density = 2 * 2 = 4
volume = 2
Pass 4:
mass = 2 * 4 = 8
density = 2 * 2 = 4
volume = 2
I'm trying my hand at a solution for this, but it's not quite ready. The basic idea is to define these equations arithmetically, rather than using function calls. Each equation in his example would simply construct a function, rather than evaluate the variable.
"c = b + a" -- this would creates two getter instances, b and a, add them (with the _add metamethod) to produce another getter instance, and assign it to c. Since the getters aren't actually evaluated at this time, but simply pieced together, b and a don't need to be defined at this point. They -do- need to be defined by the time you actually use c, though.
Err, sure, but how exactly are you doing this? Are you writing your own parser, etc.?
Obviously a declarative solution is best here; perhaps even something like Prolog would be nice. The problem is that there aren't a lot of embeddable languages out there that let you write expressions declaratively.
Pure Lua. I haven't had a chance to do much with it yet, but each of these items will have a metatable with __add, __sub, etc., and will return a new item. "a + b" will return a new item that, when executed, itself executes a and b, then adds the results.
But how will this work? You still have the issue of evaluation order. You still have the issue of undeclared variables. Even if you use the metatable trick I mentioned to give defaults for the variables, and instead return these "smart objects", you haven't solved the evaluation order problem...
Because they're not evaluated at any point in the context of Bernhard's original example. Each line defines the formula for one variable. This formula is dependant on other variables in the same scope, but none of these variables are actually accessed at any time at this point.
When a formula is defined - __newindex in the scope, "x = ..." - it's placed in a different table than the accesses - __index in the scope, "... = y". When an rvalue is accessed, it gets/creates a getter for that variable, and stores it in a table of getters so more than one is never created for a given name. When an lvalue is set, the definition is stored in a table of definitions, which is never accessed in any way except to set them.
After the file is run, you should be able to access the definitions yourself, which will then evaluate the constructed equations and return a result.
This could work -- except for the problem that you can only handle arithmetic with metatable support, and this can be a big problem.
For example, you can't just do:
math.pow(a, 2)
ok, you can do a^2 and use the __pow__ metamethod. But what about trig functions, etc.
It means that you'd have to provide support under-the-hood for "smart object"-aware mathematical functions, and letting the user write their own functions becomes harder as well.
Additionally, if you go to the original post, he has an example where he does width = myfunc(). This creates more work: as you evaluate this (in Lua) you are losing the fact that you are calling some function. If everything were just an expression, or a function that returns a deferred-computation object, it would be ok, but this is imposing new constraints on users that might be outside the scope of difficulty that Bernhard wanted.
By the way, I don't think you said here what you meant to say:
Quote: When an lvalue is set, the definition is stored in a table of definitions, which is never accessed in any way except to set them.
(If you never access it other than to set it, then in particular you're never retrieving the value you put in...)
David Haley said: By the way, I don't think you said here what you meant to say:
Quote: When an lvalue is set, the definition is stored in a table of definitions, which is never accessed in any way except to set them.
(If you never access it other than to set it, then in particular you're never retrieving the value you put in...)
I did mean that. Again, within the context of the formula script, nothing actually is evaluated. All that script does is define formulae. After it's done - and in the original environment - you can evaluate and retrieve values by using the definitions table I mentioned before.
And yes, I specifically saw the need for using functions within the formulae scope. You just add these functions to the definitions table at any point, and as long as they're defined before you try to evaluate a formula, it should work fine.
That's the idea, anyways. I've barely done any work on it, but I know the premise is sound.
It requires all user functions to be written in this special way as well, which is unfortunate if the goal is to provide an easy syntax.
Also, the whole idea of using a metatable trick is rather dirty in the first place in that it lets uninitialized or incorrectly named variables slip in and seem initialized, but, well, that's kind of the way it goes given the constraints.
Quote: Again, within the context of the formula script, nothing actually is evaluated.
I realize that you're using your vocabulary somewhat loosely, but it's not at all correct to say that "nothing" is evaluated: of course the script is being evaluated.
David Haley said: It requires all user functions to be written in this special way as well, which is unfortunate if the goal is to provide an easy syntax.
Not really. External functions can be inserted from the outside just like the formula definitions on the inside, and they can be accessed on the inside like any other formula.
David Haley said: Also, the whole idea of using a metatable trick is rather dirty in the first place in that it lets uninitialized or incorrectly named variables slip in and seem initialized, but, well, that's kind of the way it goes given the constraints.
Given the constraints, yes, this seems like the best way to go.
David Haley said:
Quote: Again, within the context of the formula script, nothing actually is evaluated.
I realize that you're using your vocabulary somewhat loosely, but it's not at all correct to say that "nothing" is evaluated: of course the script is being evaluated.
No, you're right. But "a = b + c" doesn't evaluate a and b, but hangs on to them for later use. Basically late evaluation.
Quote: External functions can be inserted from the outside just like the formula definitions on the inside, and they can be accessed on the inside like any other formula.
I meant user-specified functions within the same configuration file. I guess you could play games with newindex and see that somebody is assigning a value that happens to be a function, and then wrap the function in some kind of lazy-evaluation chunk... or something.
Something like:
function sphere_vol(r)
return (4.0/3.0) * math.pi * r^3
end
mass = volume * density
volume = sphere_vol(radius)
This requires even more trickery, because you have to replace sphere_vol with a function that returns one of these lazy-evaluation objects, such that when sphere_vol(radius) is evaluated, you get back an object that knows how to call the sphere_vol function with the appropriate parameter etc.
Actually, the requirement is not to use lua in any case, so all right if there is a better choice – unless the licence is problematic. I would prefer to get along without complicated tricks if possible.
I need the system to understand a statement like ‘mass = volume * density’ as
‘In case you need to know the mass: get volume and density, and then multiply them’
instead of
‘Multiply volume and density, then store it in mass NOW’.
So
* drive off
* then turn on the ignition
* then get into the car
must be understood as a set of rules like
‘to get somewhere drive off’
‘to drive off get into the car and turn on the ignition’
‘to turn on ignition get into the car’
=> up to now nothing happened.
Then someone orders >>get somewhere<<, and the system knows what to do.
‘Native’ lua does not understand an ‘x = y*z’ statement like that.
So option 3 would/could be, e.g., to store all formulas (x = y*z) in a hashmap with key ‘x’ and ‘y*z’ as the value. The ‘x*y’ must then be evaluated with a parser that obtains ‘x’ and ‘y’ from the same hashmap, thus, evaluating a set of dependent formulas in the correct order.
Quote: So option 3 would/could be, e.g., to store all formulas (x = y*z) in a hashmap with key ‘x’ and ‘y*z’ as the value. The ‘x*y’ must then be evaluated with a parser that obtains ‘x’ and ‘y’ from the same hashmap, thus, evaluating a set of dependent formulas in the correct order.
You can't really do something like this without the same kind of trickery we were talking about, unless you start writing your own parser for mathematical expressions.
I don't know of any programming languages that allow simple syntax and declarative definitions of variables. Prolog, for example, is declarative but not exactly what I'd call simple for users.
Perhaps Nick's expression parser is pretty close, but you would need to add support for the extra control flow that you want.
Basically, no matter which approach you choose, it looks like you'll have some work do. While you can construct something that will be simple for the end-user, I do not think that you will be able to get away with something really easy for you as the developer as well.
So option 3 would/could be, e.g., to store all formulas (x = y*z) in a hashmap with key ‘x’ and ‘y*z’ as the value. The ‘y*z’ must then be evaluated with a parser that obtains ‘y’ and ‘z’ from the same hashmap, thus, evaluating a set of dependent formulas in the correct order.
<Appendix:>
Since I need the 'do it now' statements as well as the 'do it when you need it' declarations, I should use a slightly different syntax (e.g., := instead of = for one of them) or store it in different files.
Perhaps Nick's expression parser is pretty close, but you would need to add support for the extra control flow that you want.
That's where I started - but I will have to deal with the 'if' issue then (see the corresponding thread).
David Haley said:
Basically, no matter which approach you choose, it looks like you'll have some work do.
Well, if I can't get something out of the box, I'll have to do it myself. Maybe I will try to adapt the parser (and later explain here what I did, in case someone is interested).