3

I often come across this problem.
Say to have a form with some controls:

A
B
C = A + B
D 
E = C * 2 ONLY IF D==TRUE
F
G = A - F

The user fills A, then B.
The system calculates C.
The user fills D (boolean)
The system calcluates E
The user fills F
The system calculates G

But now:
The user clears A
The system clears C, E and G
The user clears B
The system does nothing
The user inserts A
The system recalculates only F
And so on and on.

There clearly is a tree of dependences, and that's not difficult to understand. But pragmatically i found quite difficult implement it without any 'framework' to model it.
Be them inputs in a HTML form or controls in a javafx application, the problem of creating a comprehensive 'recalculation' algorithm still remains.
(Javafx offers a 'binding' architecture that despite being a bit verbose, yet is very powerfull and addresses (part of) this specific issue.) But i'm more interested in a methodology that can be used across the different platforms. I use to use a bunch of tecniques to solve the issues that come across but not yet a methodology, that is a way to go from the definition to the implementation with the minimum amount of trials.
The tecniques are the good old: invalidations, lazy init, wrapping each control in a 'node' of a recalc-graph.
But i feel that there should be a more canonical approach to this recurrent problem, and a paper where this approach is explained and so on. Can anyone suggest me where can i find such information?

EDIT 1: terms of the problem

  • One of the key goals of such a solution is to have a way to organize the code in a predictable way, so that, knowing the method, it should be easy to evaluate its correctness.
  • Initial state: many system fail to return to their initial state, that's the smell of a poor design that such methodology should prevent
  • It should be designed for real cases such as (hitting back to the example): when the user changes A, the system should clear B in the case in which they were coupled. It's easy to think of such cases: a user selects a contry and the system provides a list of regions for the user to choose one. If the user changes the city, the region previously chosen has to be cleared even if it's not strictly a dependent field since it's not calculated by the system.

As an example of a very partial solution:

  1. Each control should have a backing 'update' method that should trigger only update of 'directly connected' controls. This hypothesis should guarantee that when C is based on A, A is always up-to-date.

    function update_A() { update_C; }

    function update_B() { update_C; }

    function update_C() { C.setValue(A + B); update_E(); }

    etc. etc.

  2. since there mustn't be circular references, these update function should form a 'tree'.

Other contributes to come.

1

Assuming the amount of recalculation is trivial, then some kind of Model-View-Controller structure would be appropriate:

  1. The user changes B
  2. The View notifies the Controller (via event, etc.) that B changed (or that something changed) and the Controller passes B (or everything editable) to the Model.
  3. The Model updates internal values and exposes the values for G, etc.
  4. The Controller copies the result values from the Model to the View.

That way, the dependency only exists in the Model. The View is very dumb, and the Controller knows which fields are read/write and which are read-only, but knows nothing of interdependencies.

Edit:

I want to make a point of clarifying the term "Model". There are typically more than one layer of Model in a program, even though we always just talk about "The Model". In the case of a client application talking to a remote server, there is typically a Server Model and a Client Model. If the client is a web browser then the Client Model might be written in JavaScript and the Server Model could be in any server-side language like C#, PHP, etc.

There's a natural question which arises: "Does this recalculation logic belong in the Client Model, the Server Model, or both?" Since you can't trust the client, you're really forced to always implement the recalculation in the Server Model, and optionally implement it in the Client Model if you want to prevent unnecessary round-trips to the server. Unfortunately this can end up violating the once-and-only-once principle, unless you're lucky enough to be working in a language/framework that allows you to re-use certain modules and logic in both the server and client side (Node.js?)

  • it's true, but i am also and perhaps more interested in how to manage the dependencies. This keeps them well wrapped in the model, but yet doesn't say anything about them. As a drawback, MVC has the cost of a non always small amount of code that connects the view to the model – AgostinoX Sep 29 '14 at 20:01
  • 1
    @AgostinoX - assuming a trivial amount of recalculation, you would typically recalculate everything every time a change was made. In fact you could implement the calculation in the property getters, such as GetC() { return GetA() + GetB(); }. If you want to get fancy, then your setters could set a dirty bit, and your getters could call a recalculate() method that checks if it's dirty, recalculates all values, and then sets dirty to false (i.e. lazy evaluation). Going fully lazy on every property is only worth the overhead if you have significant calculation cost. – Scott Whitlock Sep 29 '14 at 20:08
  • recalculating everything has a very major drawback. it's a shortcut that cannot always be taken. in web interfaces, for example, you often have costly remote calls (typically ajax) and usually we want to avoid double-calls. Actually i often use something like the 'getter' approach, ideal in combination with lazy init. the idea is to encompass it into something like a formal analysis method. – AgostinoX Sep 29 '14 at 20:38
  • 1
    @AgostinoX - As I said, you can choose to do the calculation in the JavaScript on the client side, as long as it's just a convenience calculation. When the user commits it, then you have to do that calculation again on the server side to be sure you trust it. I think getter with lazy evaluation is your best bet (and would be the Functional Programming way to do it). Anything else seems like it's overly complex. – Scott Whitlock Sep 29 '14 at 21:12
  • on this point we have different points of view, obviously. – AgostinoX Sep 29 '14 at 21:23
1

The tecniques are the good old: invalidations, lazy init, wrapping each control in a 'node' of a recalc-graph. But i feel that there should be a more canonical approach to this recurrent problem, and a paper where this approach is explained and so on. Can anyone suggest me where can i find such information?

I believe the canonical approach would be the state pattern.

Have a look at http://gameprogrammingpatterns.com/state.html, for instance.

Obviously it's not associated with game programming specifically, I just happen to like this particular explanation.

Especially suiting is the hierarchical state machine, where there is more interdependency between states.

Another resource, focused on hierarchical state machine specifically: http://www.eventhelix.com/realtimemantra/hierarchicalstatemachine.htm#.VCm9nPmSzOg

Each state knows what happens when it's switched on, what should happen when it's switched off. It can trigger other states, possibly causing a cascade of updates. This can allow for flexible and maintainable APis.

Take a look at this project, for example - written in my favorite programming language (C#): https://github.com/nblumhardt/stateless (I'm in no way associated with the project or its authors).

I don't mean the code, but the samples. They are clear and instructive, and so they can already serve as a good indication on how to implement the thing:

var phoneCall = new StateMachine<State, Trigger>(State.OffHook);

phoneCall.Configure(State.OffHook)
    .Permit(Trigger.CallDialed, State.Ringing);

phoneCall.Configure(State.Ringing)
    .Permit(Trigger.HungUp, State.OffHook)
    .Permit(Trigger.CallConnected, State.Connected);

phoneCall.Configure(State.Connected)
    .OnEntry(() => StartCallTimer())
    .OnExit(() => StopCallTimer())
    .Permit(Trigger.LeftMessage, State.OffHook)
    .Permit(Trigger.HungUp, State.OffHook)
    .Permit(Trigger.PlacedOnHold, State.OnHold);

// ...

phoneCall.Fire(Trigger.CallDialled);
Assert.AreEqual(State.Ringing, phoneCall.State);

// ...

phoneCall.Configure(State.OnHold)
    .SubstateOf(State.Connected)
    .Permit(Trigger.TakenOffHold, State.Connected)
    .Permit(Trigger.HungUp, State.OffHook)
    .Permit(Trigger.PhoneHurledAgainstWall, State.PhoneDestroyed);

Neat, huh?

  • it seems very neat, even if i don't know c#, so what are the .Permit methods, just to have an idea of what it does? – AgostinoX Sep 29 '14 at 20:33
  • 1
    oldState.Permit(trigger, newState) says: oldState must accept this trigger and react to it by switching to newState. There's plenty of state machine libraries out there, nothing super special about this one. I'm sure you could find one in your language of choice. Java: github.com/hekailiang/squirrel (watch out for: "hierarchical state") – Konrad Morawski Sep 29 '14 at 20:37
  • 1
    It could be an overkill for simple use cases. A ready-made, sophisticated library - for sure. But since you asked about a canonical approach, and a paper and so on... Some sort of a custom mini-implementation, tailored to your needs, could be a smart move though. It's the paradigm itself that matters. – Konrad Morawski Sep 29 '14 at 20:39
  • I've just used one in ruby on rails. It cleans up a lot of things, but i didn't think of state machines to cope with this since here are many states and we are not so interested in states but in dependencies and ways to calculate the tree. Maybe i considered state machines from a too narrow point of view. – AgostinoX Sep 29 '14 at 20:43
  • 1
    But you are defining dependencies between states. This is what happens in these code samples. And you are registering these dependencies in the state machine object whish is like an umbrella class for the states. Thanks to this, the state machine object knows "whom to call" when flag A is going on or off. In your example: it notifies state C and state G. As a consequence, state C switches off and the state machine will have to tell state E about it. – Konrad Morawski Sep 29 '14 at 20:48
1

Well, why not start with a very simple approach? You have "level 0" fields where the user can enter values, "level 1" fields which only depend on "level 0" field, "level 2" fields depending on "level 1" or "level 0" fields, and so on. Behind each "level n" field with n>0 there is a function which takes care of incomplete input values (like C = f(A,B) with f(A,B) = A+B if A and B are numeric, and "no value" if not.

Now, whenever a "level 0" field is changed by a user, recalculate everything, and do this in the order of increasing levels 1, 2 3, ... and so on.

This is probably not the most efficient solution, but in a lot of real-world cases it is just efficient enough. It is the approach you should start with, and only if it turns out to be not fast enough, you should try to implement something more sophisticated. Otherwise you risk to run into the "premature optimization" trap.

  • following my intuition, it's a bit too simple for many real cases that are significantly more complex that the one that i presented. moreover, you're right when you say that usually some calculation in excess worths the gain in simplicity. unfortunately that could not be the case of web interfaces where ajax calls are not something you can do in excess. – AgostinoX Sep 29 '14 at 21:14
  • but the idea that really i don't like is to suppress the granularity, providing groups of fields of the same behavior. Then a customer requests a specific behaviour, your solution doesn't implement it and you end up coding exceptions over exceptions while the method i'm looking for should integrate most of the usual requests without recurring to exceptions to the logic. – AgostinoX Sep 29 '14 at 21:18
  • 1
    @AgostinoX: honestly, I don't understand what you mean by "supress the granularity", maybe you can provide an example? – Doc Brown Sep 29 '14 at 21:53
  • think to a spreadsheet,that is the exact model of relationships between data that i want to be able to implement.you can define a field c4 that depends on b2 that in turn depends on a3 that dep. on d5 etc.etc. introducing dependencies on multiple fields you very soon end up with a tree of dependencies very 'complex' in number. yet conceptually simple . there they don't have levels, just a tree that recalculates all the dependencies that come down the road from a certain point.that's my idea. there, grouping cells in levels has no sense, it's quite clear. – AgostinoX Sep 29 '14 at 22:01
  • @AgostinoX: in any tree (a graph without cycles) the "level" can be defined as its shortest distance from the root. That's what I am talking about, not about "fields of same behaviour". The levels just give you the correct order of recalculation. The approach I described avoids the necessity to implement a complex graph search (to find out the correct order of recalculation at run time), it may recalculate more than necessary, and when you introduce a new derived field, you may have to rebuild the leveling, but it is simple and universal. – Doc Brown Sep 30 '14 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.