3 ms·

"Functional Algorithms" is a strange topic for me since algorithms seem very imperative, compared to the declarative nature of FP.

by mjfl 5y ago

kadoban 5y ago
If you're into the idea, I'd recommend Purely Functional Data Structures by Okasaki and Pearls of Functional Algorithm Design by Bird, both really interesting books IMO.
- nextos 5y ago
  Bird's book and its prequel, Thinking Functionally with Haskell, are outstanding. His approach of calculating algorithms by performing algebraic transformations is very interesting. It attracted some interest during the 80s and 90s, but it has faded away as it's too tough to be followed by a human. I wonder if it could benefit from some automation by using e.g. modern synthesis techniques.
amw-zero 5y ago
Computation is the creation of and executing of algorithms. Even if an algorithm is expressed functionally, it progresses through a sequence of states when executed. Check out Computation and State Machines by Leslie Lamport: https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf. Specifically, in Section 3, he shows how interactive and recursive definitions of the same program are actually executing the same underlying algorithm, even though their source code looks drastically different. Syntax is superficial, and declarativeness is really just an illusion, or maybe a convenience. But, a program is executing a sequence of states no matter what paradigm it’s expressed in. Functional programs are still executed. In this respect, you’re talking about a very superficial aspect of algorithms.
- benlivengood 5y ago
  Additionally lambda calculus, general recursive functions, combinatorial logic, Turing machines, and a number of other systems are equivalently powerful[0] and so any computable function can be expressed in any of the systems. So it's fine to refer either to purely functional algorithms or purely state-machine algorithms since they are equivalent statements. [0] https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
  - Ar-Curunir 5y ago
    Different formalisms can describe the same concept, but they don’t always make the same analyses easy. Eg: one of the main things we do with algorithms is analyze their time and space complexity, and it’s often easier to do this in a state machine model
- zelphirkalt 5y ago
  It might be more correct to say, that a program are the instructions, which lead to the machine transitioning throught some sequence of states.
User23 5y ago
Any imperative algorithm admits functional mathematical interpretations. While humorous, the observation that programming in C is purely functional[1] isn't wrong. Also consider, for example, that the formalism for the Turing Machine, the archetypical imperative automata, is purely functional. More seriously, the semantics of an imperative algorithm are perhaps always best understood as mathematical functions. Predicate transformer semantics reduce verifying an imperative program to proving a first-order formula. Leslie Lamport, who most people doing so-called "formal verification"[2] know for TLA+, is also a shining light in this area of research. They are observably complementary cognitive tools for the task of writing correct programs, even if one is attracting more grants. The trick is learning to write programs that reduce to formula that can practicably be solved, automatically or not. Granted, for many languages that first-order formula might be difficult to solve for many programs, but that doesn't change the fact that there exists a functional description of the procedure's semantics, even if the process the hardware actually executes isn't so analyzed[3]. But then that's true for Haskell too. It's just Haskell and its cousins do a comprehensive job of beating you over the head that you're reasoning about program semantics and not processes. [1] http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... [2] Correctly it should be called automatic verification. Formal reasoning predates the automatic computer and automatic verification is a subset of mathematically rigorous formal program verification. [3] Not to say it necessarily can't be.

"Functional Algorithms" is a strange topic for me since algorithms seem very imperative, compared to the declarative nature of FP.

by mjfl 5y ago

"Functional Algorithms" is a strange topic for me since algorithms seem very imperative, compared to the declarative nature of FP.

kadoban 5y ago

If you're into the idea, I'd recommend Purely Functional Data Structures by Okasaki and Pearls of Functional Algorithm Design by Bird, both really interesting books IMO.

nextos 5y ago
Bird's book and its prequel, Thinking Functionally with Haskell, are outstanding. His approach of calculating algorithms by performing algebraic transformations is very interesting. It attracted some interest during the 80s and 90s, but it has faded away as it's too tough to be followed by a human. I wonder if it could benefit from some automation by using e.g. modern synthesis techniques.

amw-zero 5y ago

Computation is the creation of and executing of algorithms. Even if an algorithm is expressed functionally, it progresses through a sequence of states when executed. Check out Computation and State Machines by Leslie Lamport: https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf. Specifically, in Section 3, he shows how interactive and recursive definitions of the same program are actually executing the same underlying algorithm, even though their source code looks drastically different. Syntax is superficial, and declarativeness is really just an illusion, or maybe a convenience. But, a program is executing a sequence of states no matter what paradigm it’s expressed in. Functional programs are still executed. In this respect, you’re talking about a very superficial aspect of algorithms.

benlivengood 5y ago
Additionally lambda calculus, general recursive functions, combinatorial logic, Turing machines, and a number of other systems are equivalently powerful[0] and so any computable function can be expressed in any of the systems. So it's fine to refer either to purely functional algorithms or purely state-machine algorithms since they are equivalent statements. [0] https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- Ar-Curunir 5y ago
  Different formalisms can describe the same concept, but they don’t always make the same analyses easy. Eg: one of the main things we do with algorithms is analyze their time and space complexity, and it’s often easier to do this in a state machine model
zelphirkalt 5y ago
It might be more correct to say, that a program are the instructions, which lead to the machine transitioning throught some sequence of states.

User23 5y ago

Any imperative algorithm admits functional mathematical interpretations. While humorous, the observation that programming in C is purely functional[1] isn't wrong. Also consider, for example, that the formalism for the Turing Machine, the archetypical imperative automata, is purely functional. More seriously, the semantics of an imperative algorithm are perhaps always best understood as mathematical functions. Predicate transformer semantics reduce verifying an imperative program to proving a first-order formula. Leslie Lamport, who most people doing so-called "formal verification"[2] know for TLA+, is also a shining light in this area of research. They are observably complementary cognitive tools for the task of writing correct programs, even if one is attracting more grants. The trick is learning to write programs that reduce to formula that can practicably be solved, automatically or not. Granted, for many languages that first-order formula might be difficult to solve for many programs, but that doesn't change the fact that there exists a functional description of the procedure's semantics, even if the process the hardware actually executes isn't so analyzed[3]. But then that's true for Haskell too. It's just Haskell and its cousins do a comprehensive job of beating you over the head that you're reasoning about program semantics and not processes. [1] http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... [2] Correctly it should be called automatic verification. Formal reasoning predates the automatic computer and automatic verification is a subset of mathematically rigorous formal program verification. [3] Not to say it necessarily can't be.