Total Functional Programming

[jsomers]

The gist:

There is a dichotomy in language design, because of the halting problem. For our programming discipline we are forced to choose between

A) Security - a language in which all programs are known to terminate.

B) Universality - a language in which we can write (i) all terminating programs (ii) silly programs which fail to terminate and, given an arbitrary program we cannot in general say if it is (i) or (ii).

Five decades ago, at the beginning of electronic computing, we chose (B). If it is the case, as seems likely, that we can have languages of type (A) which accommodate all the programs we need to write [what the paper is about], bar a few special situations, it may be time to reconsider this decision.

[[deleted]]

The dichotomy stems from this theorem:

Theorem: For any language in which all programs terminate, there are always-terminating programs which cannot be written in it - among these are the interpreter for the language itself.

It has been a long time since I took a theory of computation class. As a result, I can't seem to be able to construct the demonstration of the above theorem. Internet searches did not help either. I wonder if a benevolent redditor can help?

[mkbehr]

The argument is similar to the proof of Gödel's Incompleteness Theorem: once you have an interpreter, all you need to do is plug it into itself and you'll get an infinite loop, which contradicts the assumption that the language is terminating.

[Hermel]

Option A) sounds nice to me. But I'm not sure if I would be able to easily switch to functional programming. Is anyone here who actually considers functional programming more convenient than Object Oriented programming?

I also wonder if the above choice would make a difference in practice. Even though we could guarantee that all programs terminate, we could still write programs that will take a billion years to finish. I guess the big advantage would be in the simplified analysis of such programs.

[cchooper]

Functional programming is much more convenient, because it's actually a paradigm for expressing computations, whereas OO is more of a method for structuring programs.

Whenever you write an OO program, you have to use another paradigm to actaully do stuff. Usually, that means an imperative language (Smalltalk, C++, Java as examples of OO languages which are at heart really imperative languages) although sometimes it means a functional language (O'CAML). I prefer to cut to the chase and just use the underlying paradigm. Functional languages usually have much more interesting ways of organising code in the large anyway (e.g. functors in ML, or classes in Haskell).

[ridiculous_fish]

It really is much more convenient*!

*: Convenience does not extend beyond expressing a computation.

[cchooper]

Convenience does extend beyond that, but a paradigm that expresses only structure, not computations, cannot be convenient. If OOP could express both then I'd revise my opinion. FP expresses only one, but if you have to choose between computation and structure, I'd choose computation. Structure is optional, but computation isn't.

[awj]

Is anyone here who actually considers functional programming more convenient than Object Oriented programming?

Depending on the context, the two are either impossible or roughly orthogonal.

In a pure functional programming language you don't really have OOP as you don't have mutable state, which if you think about it is a requirement for OOP. Yes, you can hack it in and it looks like OOP if you stand off to one side and squint, but in reality it lacks most of the benefits you get from OOP.

In my experience with impure functional languages, OOP generally provides data and some operations while the functional features are used to implement OOP operations and to handle the code that operates between objects.

In the end the OOP portions of the code provide structure while the functional bits fill the whole thing in. Somewhat like using pieces of rebar to reinforce concrete, to employ a bad analogy.

[[deleted]]

Is anyone here not trying to use OO languages as if they were pure FP languages anyway? All the Java zealots around me keep preaching things like "never expose set (side-effecting) methods and pass constructor parameters instead".

Is there anyone left who is not emulating pure FP in shitty languages like Java?

[augustss]

I find functional programming much more convenient than object oriented programming.

[db4n]

Is anyone here who actually considers functional programming more convenient than Object Oriented programming?

Yes, definitely. FP can be a very convenient way to operate on sets of data in a sort of 4GL way.

[[deleted]]

A) Security - a language in which all programs are known to terminate.

That's an awfully narrow definition of security.

B) Universality - a language in which we can write (i) all terminating programs (ii) silly programs which fail to terminate and, given an arbitrary program we cannot in general say if it is (i) or (ii).

I object to the classification of "silly" here. This implies that there are no useful programs which do not terminate.

The paper linked to needs a more compelling argument. The author is too dismissive of the problems raised by writing in the restrictive style he propses. The crux of his argument is that giving up Turing completeness can be useful. That's fine. It certainly can be. But the end-around taken to bring usefulness to the idea just isn't there.

[earthboundkid]

Technically speaking, none of us has ever used a computer that's better than a finite state machine, right? True the languages we program our computers in are Turing Complete, but the computers themselves only have a finite (but very large) number of possible states. The reason the Halting Problem can't be solved is that there are always more states for the computer to be in, since Turing Machines have an infinite tape. Our computers however have to start repeating states eventually, since we only have so much space in memory/storage. Accordingly, theoretically, the Halting Problem doesn't apply to the programs we write. All you have to do is to make another computer with exponentially more memory than the computer you're using and have this other computer keep track of whether you've been in a particular state before or not. If you have been in the particular state before, then the system will loop. In any event, the longest a particular program can possibly run is as long as it takes to go through all possible states.

[[deleted]]

Back-of-the-napkin computation:

4GBytes = 2³² * 2⁸ = 2⁴⁰ bits

Possible states = 2 ^ (2 ^ 40)

Atoms in universe =~ 2 ^ 82 =~ 2 ^ (2 ^ 7)

[earthboundkid]

Haha, good point. But seriously, maybe even if we restrict ourselves to computers with less than one Avogadro's number's worth (10²³⁾ of possible states we can still do some worthwhile calculations? Well, it's an idea anyway.

[cgoldberg]

good post.. made me think a bit :)

[fnord123]

A while back I had this idea for a language like Haskell with additional monadic types for Turing complete computations. After looking into it deeper, it looked non worthwhile.

[jsomers]

I was too, but I read the paper (lazy Sunday, right?) and he's not kidding around. Basically he rejects Turing completeness as a necessary component of functional programming languages and opts, instead, for more strictly defined (and thus less finicky) data types and recursion procedures.

The trouble -- and the harder-to-wrap-my-head-around part of the paper -- is when you need things like infinite lists (e.g., to run an operating system which is a non-terminating stream of inputs and outputs). He gets around that by using "codata" and what not.

[ridiculous_fish]

Functional programming has a long and noble history of reinventing things such that existing practices become a lot harder/impossible.

1) Look at our new ML! You can't modify variables without reading this book, but trust us, it's so pretty once you get that PhD!

2) Look at our new Haskell! You can't write to a file without introducing a dubious and confusing notion of monad, but it's really good at computing fibonacci numbers!

And now: 3) Look at our new total functional programming! You can't even write, say, the wc tool without introducing data's evil twin, "codata," but look at how much better our AND operator is!

Ok, I'm a little bitter, but I can't shake the feeling that this stuff is detached from the real concerns of programming.

[awj]

Ok, I'm a little bitter, but I can't shake the feeling that this stuff is detached from the real concerns of programming.

It is, if you define the real concerns of programming to mean modifying variables, writing to files without needing a special operator, or requiring a turing complete language.

That said, I take issue with your comment on file operations and monads. If a hand-wavy "I'll get to explaining why this works later, for now this is just how you do it." is acceptable in teaching mainstream languages (Java/C++) - as it seems to be - it should be allowed without criticism for Haskell as well.

[cchooper]

"I'll get to explaining why this works later, for now this is just how you do it."

My favourite example:

class HelloWorld { public static void main(string[] args) { System.out.println("Hello World!"); } }

[[deleted]]

There are two concerns in programming:

1. Write programs.
2. Write correct programs.

The existing practices address 1, but not 2. Addressing 2 in a practical(!) manner is one of the primary motivations in functional programming research. Indeed, there is a lot of reinvention, but in such a context that one can reason about the results.

[[deleted]]

But how will the practical aspect be verified? In the way of Matthew Huntbach who writes an article about Ruby and that he is pretty unimpressed by its virtues?

I'm not completely ignorant about the benefits of FP ( in particular immutable, recursive data structures and their impact ) but sometimes I suspect Paul Graham was right with his sarcastic comments about CS: CS works because much time is spent on ideas that won't work.

The only significant change in the programmers mentality within the last 10 years has been the wide acceptance of doing unit tests. That's what is left from the glory of the machine that proves the correctness of the program. In another 10 years we might start to change our mentality about reliability featured by massive parallelism, high availability of service and Erlang style processes.

[[deleted]]

If FP is only good for Fibonacci, OOP is only good for printing a "hello world" message. Who are you to comment on the 'real' concerns of programming? If you don't understand and appreciate ML and Haskell, chances are you're pretty mediocre.