1

Suppose we need an iterative algorithm for mathematical optimisation. Each iteration takes a long and random time. After each iteration, a stopping condition is checked for the iterate x, based on some pre-defined parameter b. An example is "Stop if ||grad(x)|| < b", based on the objective's gradient at x.

Here's is an extremely simplified "algorithm" in pseudo-Scala

val f = (a: Dbl, b: Dbl) => { 
def go(x: Dbl): Dbl = if (x<b) x 
else go(bigComputation(x)) 
go(a)}

The actual algorithm could be recursive or have a while loop.

The user wants to update the stopping parameter b while the algorithm is running. (The reason could be to speed-up convergence or to improve solutions, if a good b is unknown beforehand.) The change is applied the sooner, the better - ideally, at the next iteration.

Q: What would a functional solution be? If such updating is against FP, what's the least bad non-FP design? (A small performance hit is fine, if the code is cleaner.)

There's a discussion of an FRP approach at http://sodium.nz/t/how-can-an-iterative-algorithm-be-controlled-dynamically-with-sodium/333/5, which doesn't fully solve it at the moment of writing.

  • The guy at that other post got it right: "Functions running inside Sodium logic are atomic and referentially transparent (pure) so the idea of stopping the algorithm through an external state change doesn't exist in the Sodium universe." – Robert Harvey Jul 25 '18 at 15:05
  • Yes, but he also suggested a possible solution based on CellLoop. So what's the least bad non-FP solution to this update requirement? – Tupolev._ Jul 25 '18 at 15:24
  • Alas, I lack sufficient Sodium knowledge to know the answer to that. You might want to be a bit more patient and wait for that other guy to answer. – Robert Harvey Jul 25 '18 at 15:26
  • A solution doesn't have to be Sodium specific. – Tupolev._ Jul 25 '18 at 15:30
  • 1
    If you're not constrained to Sodium's referential transparency preferences, then simply go with a mutable solution to the problem. – Robert Harvey Jul 25 '18 at 15:33
2

I would simply pass a cancellation token into the function and have it check whether cancelation has been requested at each iteration.

However, this is obviously not a functional approach as the user would request the cancelation and thus inject state into the function.

Perhaps if you know the cancelation requirements in advance you can specify it as a function itself, (runningtime > 50,000) and get back to the functional paradigm

  • That's very interesting - thanks! Instead of modelling the whole algorithm, with N iterations, as a "big" function, perhaps I could model N calls of an "iteration" function, each time with new parameters? Then the mutability is pushed to the outside of the system, and is less bad. – Tupolev._ Jul 25 '18 at 16:14
  • Actually, the cancellation tokens seem a bit similar to how concurrency works in javafx. A Task implementing a computation has isCancelled() method, which it checks periodically. So we could implement an iteration in a Task, and have a ScheduledService control the iterative optimisation overall. – Tupolev._ Jul 25 '18 at 16:39
  • yes, exactly. not sure if you would have to explicitly check or not. – Ewan Jul 25 '18 at 17:20
0

This would imply to pause the algorithm change the values check the coherency and validity of the values and then continue. The reason for pause is that the change does not happen in the middle of the iteration. The validity must be ensured lets say the value cannot be negative or something else.

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.