5 ms·

A simple example on how open recursion is harmful. Consider we have a object which computes the factorial: class computer = object(self) method fact

A simple example on how open recursion is harmful. Consider we have a object which computes the factorial: class computer = object(self) method factorial x = if x = 0 then 1 else x * self#factorial (self#pred x) method pred x = x - 1 end Now, somebody redefines `pred` class computer_enhanced = object inherit computer method pred x = x end Now factorial simply hangs in infinite loop (until stack overflow). This example is very trivial, but when you have dozens of methods, mutable variables, locks, parallelism, and you redefine a virtual method (aka adding a recursive call changing the state transition graph) without knowing precisely how other methods work, this ends with annoying bugs, deadlocks and very hard to debug.

fauigerzigerk 7y ago
Here's a functional programming version of a similar bug: function factorial(x, pred) { if (x == 0) return 1; return x * factorial(pred(x), pred); } function makePred(x) { return y => y - x; } console.log(factorial(5, makePred(-1)));
protomolecule 7y ago
A simple example on how higher order functions are harmful. Consider we have a function which computes the factorial: let rec fact(x, prev) = if x <= 1 then 1 else x * fact(prev(x), prev);; let factorial(x) = fact(x, fun x -> x-1);; Now, somebody passes different function as `prev` let enhanced_factorial(x) = fact(x, fun x -> x);; Now enhanced_factorial simply hangs in infinite loop (until stack overflow). This example is very trivial, but when you have dozens of functions taking other functions as arguments and those in turn are taking other function as arguments, and you try to alter behavior by passing a different function somewhere without knowing precisely how other functions work, this ends up with annoying bugs and very hard to debug. Would you agree that this example makes little sense? Is it really different from yours?
- ernst_klim 7y ago
  > Is it really different from yours? Of course it is. In your example you are explicitly breaking factorial. In my example I'm just defining `pred`, and it's unexpectedly and implicitly breaking factorial. Behavior of the factorial depends on explicit argument, behavior of the factorial method depends on implicit recursive call. It's the same as having a global variable and a locally passed argument. let x = ref 0; let f () = x + 1; x := 42; let = f (); is not different from let f x = x + 1; let y = f 42; in a trivial example, but in a complex example with a complex state, the implicitness of the former would cause bugs. Same with open recursion, your code simply mocks a trivial example. In a complex example where methods rely on state and locks, implicit redefinition of a mutually recursive methods causes bugs hard to debug and comprehend, since you can't say what exact virtual method is called (you shouldn't even know that, that's the point of OOP).
  - protomolecule 7y ago
    "In your example you are explicitly breaking factorial. In my example I'm just defining `pred`, and it's unexpectedly and implicitly breaking factorial." In all mainstream languages with OOP features methods by default are not virtual and cannot be overridden by a successor class. You cannot accidentally create an opportunity for breaking factorial by defining 'pred', you'd need to explicitly declare 'pred' as virtual. If you don't do it, factorial cannot be broken and there is no problem. If we pretend that you did it, the question is how is it different from taking 'pred' as an argument in the functional example?
    - ernst_klim 7y ago
      > by default are not virtual and cannot be overridden by a successor class. Non virtual methods has nothing to do with OOP, they are a mere sugar for function calling. We are talking about OOP, which is defined by late binding/open recursion, i.e. virtual methods, and the perils of open recursion. > You cannot accidentally create an opportunity for breaking factorial by defining 'pred', you'd need to explicitly declare 'pred' as virtual. If you don't do it, factorial cannot be broken and there is no problem. Ok, it seems you are confused by the trivial nature of the example, here is a real world example: https://gitlab.freedesktop.org/gstreamer/gstreamer-vaapi/merge_requests/95/commits https://gitlab.freedesktop.org/gstreamer/gstreamer-vaapi/mer... A decoder implementation calls GstElement's `change_state` method, which calls (through the long chain of calls) child's decide_allocation which calls parent and so on and so forth and in the end you have a deadlock. This is pure OOP, where each Class provides needed virtual methods for state change, buffer preparation, allocation etc, and they calling each other in an obscure recursive manner. This leads to fancy implicit bugs if you calling methods without understanding how they work and where they are implemented, which is impossible, since methods could be reimplemented later. > If we pretend that you did it, the question is how is it different from taking 'pred' as an argument in the functional example? How do I know that `decide_allocation` method is calling a method I'm going to reimplement? How do I know that decide_allocation would be reimplemented in some future decoder? In your example you explicitly redefining factorial. In my example I'm just redefining pred without caring about factorial and not even knowing that factorial calls pred (abstraction, remember?).

fauigerzigerk 7y ago

Here's a functional programming version of a similar bug: function factorial(x, pred) { if (x == 0) return 1; return x * factorial(pred(x), pred); } function makePred(x) { return y => y - x; } console.log(factorial(5, makePred(-1)));

protomolecule 7y ago

A simple example on how higher order functions are harmful. Consider we have a function which computes the factorial: let rec fact(x, prev) = if x <= 1 then 1 else x * fact(prev(x), prev);; let factorial(x) = fact(x, fun x -> x-1);; Now, somebody passes different function as `prev` let enhanced_factorial(x) = fact(x, fun x -> x);; Now enhanced_factorial simply hangs in infinite loop (until stack overflow). This example is very trivial, but when you have dozens of functions taking other functions as arguments and those in turn are taking other function as arguments, and you try to alter behavior by passing a different function somewhere without knowing precisely how other functions work, this ends up with annoying bugs and very hard to debug. Would you agree that this example makes little sense? Is it really different from yours?

ernst_klim 7y ago
> Is it really different from yours? Of course it is. In your example you are explicitly breaking factorial. In my example I'm just defining `pred`, and it's unexpectedly and implicitly breaking factorial. Behavior of the factorial depends on explicit argument, behavior of the factorial method depends on implicit recursive call. It's the same as having a global variable and a locally passed argument. let x = ref 0; let f () = x + 1; x := 42; let = f (); is not different from let f x = x + 1; let y = f 42; in a trivial example, but in a complex example with a complex state, the implicitness of the former would cause bugs. Same with open recursion, your code simply mocks a trivial example. In a complex example where methods rely on state and locks, implicit redefinition of a mutually recursive methods causes bugs hard to debug and comprehend, since you can't say what exact virtual method is called (you shouldn't even know that, that's the point of OOP).
- protomolecule 7y ago
  "In your example you are explicitly breaking factorial. In my example I'm just defining `pred`, and it's unexpectedly and implicitly breaking factorial." In all mainstream languages with OOP features methods by default are not virtual and cannot be overridden by a successor class. You cannot accidentally create an opportunity for breaking factorial by defining 'pred', you'd need to explicitly declare 'pred' as virtual. If you don't do it, factorial cannot be broken and there is no problem. If we pretend that you did it, the question is how is it different from taking 'pred' as an argument in the functional example?
  - ernst_klim 7y ago
    > by default are not virtual and cannot be overridden by a successor class. Non virtual methods has nothing to do with OOP, they are a mere sugar for function calling. We are talking about OOP, which is defined by late binding/open recursion, i.e. virtual methods, and the perils of open recursion. > You cannot accidentally create an opportunity for breaking factorial by defining 'pred', you'd need to explicitly declare 'pred' as virtual. If you don't do it, factorial cannot be broken and there is no problem. Ok, it seems you are confused by the trivial nature of the example, here is a real world example: https://gitlab.freedesktop.org/gstreamer/gstreamer-vaapi/merge_requests/95/commits https://gitlab.freedesktop.org/gstreamer/gstreamer-vaapi/mer... A decoder implementation calls GstElement's `change_state` method, which calls (through the long chain of calls) child's decide_allocation which calls parent and so on and so forth and in the end you have a deadlock. This is pure OOP, where each Class provides needed virtual methods for state change, buffer preparation, allocation etc, and they calling each other in an obscure recursive manner. This leads to fancy implicit bugs if you calling methods without understanding how they work and where they are implemented, which is impossible, since methods could be reimplemented later. > If we pretend that you did it, the question is how is it different from taking 'pred' as an argument in the functional example? How do I know that `decide_allocation` method is calling a method I'm going to reimplement? How do I know that decide_allocation would be reimplemented in some future decoder? In your example you explicitly redefining factorial. In my example I'm just redefining pred without caring about factorial and not even knowing that factorial calls pred (abstraction, remember?).