[Home] [Downloads] [Search] [Help/forum]


Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Recursive Configuration Evaluation

Recursive Configuration Evaluation

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Pages: 1 2  

Posted by Bernhard   (18 posts)  [Biography] bio
Date Sat 15 May 2010 07:02 AM (UTC)
Message
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):


mass = volume * density
volume = length * width * height
surface = 2*xplane + 2*yplane + 2*zplane

xplane = width*height
yplane = length*height
zplane = length*width

density = 916.7
length = width
width = myfunc()
heigth = above_ground + below_ground

below_ground = above_ground * 9

above_ground = my_volatile_var



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"?

[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #1 on Sat 15 May 2010 07:40 AM (UTC)
Message
Recursion is where a function directly, or indirectly, calls itself. Your example doesn't illustrate that.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #2 on Sat 15 May 2010 09:09 AM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #3 on Sat 15 May 2010 11:48 PM (UTC)
Message
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.
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #4 on Sun 16 May 2010 05:26 AM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #5 on Sun 16 May 2010 06:49 AM (UTC)
Message
Bernhard said:

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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #6 on Sun 16 May 2010 10:11 AM (UTC)
Message
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).



[Go to top] top

Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #7 on Mon 17 May 2010 05:25 PM (UTC)
Message
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.
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #8 on Mon 17 May 2010 07:53 PM (UTC)
Message
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).

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #9 on Mon 17 May 2010 09:21 PM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Bernhard   (18 posts)  [Biography] bio
Date Reply #10 on Wed 19 May 2010 10:53 PM (UTC)
Message


The syntax aspect:

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.

[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #11 on Thu 20 May 2010 04:28 PM (UTC)
Message
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

No change detected, stop evaluation.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #12 on Thu 20 May 2010 06:31 PM (UTC)
Message
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.

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #13 on Thu 20 May 2010 07:46 PM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #14 on Thu 20 May 2010 07:55 PM (UTC)

Amended on Thu 20 May 2010 07:56 PM (UTC) by Twisol

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

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


55,624 views.

This is page 1, subject is 2 pages long: 1 2  [Next page]

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]