4 ms·

The question is if you can have a system that can derive the closed form from the definition. Not one you can feed it to. Right? Similarly, it may be faster

by taeric 3y ago

The question is if you can have a system that can derive the closed form from the definition. Not one you can feed it to. Right? Similarly, it may be faster to use the repeated squares approach to get a large value fib, and I don't know any system that can get that from the recursive definition, either.

toast0 3y ago
Nonfunctional programming doesn't give you that either, so I don't see the problem? If you use the iterative / recursive form, runtime performance isn't great. If you use a lookup table, performance is great, but space might suffer (but then, how many values do you really need?). If you want to use something better, you've got to write it yourself. Maybe one day an optimizing compiler will figure it out, but it's more likely to figure out you never call it with N > 10, and precompute, and that's fine.
- taeric 3y ago
  Right, but the post is "I'd really be impressed with a system that could figure out the closed form based on the definition." Point seeming that coding up a recursive process based on the definition doesn't seem to be the best reason to teach something that way. This goes back to a ton of the talk on early compilers and systems. They would push that you should lean heavily on the system to move from definitions to optimal solutions. (This later got changed heavily to leaning only on the compiler, but the same idea applies.)
  - toast0 3y ago
    That was parenthetical, I was responding to "It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice"
    - taeric 3y ago
      Right, I took that to be that the complaint is the recursive definition is used to teach it. Stated differently, ignoring the parenthetical takes the weakest interpretation of that post.

4 ms·

The question is if you can have a system that can derive the closed form from the definition. Not one you can feed it to. Right? Similarly, it may be faster

by taeric 3y ago

toast0 3y ago
Nonfunctional programming doesn't give you that either, so I don't see the problem? If you use the iterative / recursive form, runtime performance isn't great. If you use a lookup table, performance is great, but space might suffer (but then, how many values do you really need?). If you want to use something better, you've got to write it yourself. Maybe one day an optimizing compiler will figure it out, but it's more likely to figure out you never call it with N > 10, and precompute, and that's fine.
- taeric 3y ago
  Right, but the post is "I'd really be impressed with a system that could figure out the closed form based on the definition." Point seeming that coding up a recursive process based on the definition doesn't seem to be the best reason to teach something that way. This goes back to a ton of the talk on early compilers and systems. They would push that you should lean heavily on the system to move from definitions to optimal solutions. (This later got changed heavily to leaning only on the compiler, but the same idea applies.)
  - toast0 3y ago
    That was parenthetical, I was responding to "It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice"
    - taeric 3y ago
      Right, I took that to be that the complaint is the recursive definition is used to teach it. Stated differently, ignoring the parenthetical takes the weakest interpretation of that post.