Can functional programming be liberated from the von Neumann paradigm? (2010)
conal.net
conal.net
Nothing wrong with writing the gist of your program written in functional way, keeping things immutable, allowing for orderless execution and lazy evaluation. But because your program interfaces with the real, consequential world it must realise all that computation at the pivot points where there is I/O and it suddenly matters that the lazy evaluation is complete.
Have a procedural loop to drive your events and other practical stuff and, from there, launch functional computations to calculate a completely or partially new state for your program. Keep things mostly immutable but do mutation in certain specific locations where it makes sense.
Clojure is good at drawing the line where the programmer sees it fit best. Multi-paradigm has always beaten pure ideologies hands down when it comes to delivering useful programs that actually work without making programmers do mental gymnastics for the sake of purity. (They should reserve their efforts to be mentally gymnast in the real-world problem they're solving.)
You don't want to write all of your program in object-oriented, procedural, functional, declarative, or whatever paradigm you have a thing for. They all do some things well and suck at others. Use them like tools, the right one for the right job.
Don't think anyone is arguing with that (even the author of this piece). But the functional patterns that contribute to useful programs today are the direct result of the kind of pure theoretical thinking here.
To me, your argument could be used against any theoretical research in any field. None of it is of practical use until it is.
The author is openly and explicitly arguing for a single paradigm, and he clearly stated in the article that he is in favor of, and calling for people to do the mental gymnastics for the sake of purity.
> the functional patterns that contribute to useful programs today are the direct result of the kind of pure theoretical thinking here.
FP isn’t pure theoretic, so I’m not sure what you mean. The foundations haven’t changed considerably in decades, and it has been possible and practical to write high-level FP code to, say, compute factorials or whatever, for decades.
FP is great as a high-level design tool to simplify and reduce mutable state. But there’s no evidence that taking it to the limit with human interaction and hardware is even possible or what it means or why it’s useful.
> your argument could be used against any theoretical research in any field. None of it is of practical use until it is.
But you neglect to mention that much theoretical research never becomes practical, and some is proven impossible. Practicality is and always will be a useful and valid argument, even if it’s occasionally wrong.
The post was about choosing a representation for sake of composition. In this case, the composition happens to be pure because it is mathmatical, but the simplest composition was the actual goal, not just any kind of purity.
We already have simple composition of programs with Von Neumann I/O, so I’m not sure I can agree with you.
To that end, I found his example of number composition quite unconvincing. He said we use binary and not strings for composability. That’s not true. Numbers represented as strings are no less composable. The only real downside is they’re less memory and time efficient, but string based numbers are just as composable as binary numbers.
If a non-imperative paradigm enables the creation of a different architecture that consistently beats the von Neumann adaptions we can create, you can bet people will get out of their way to write everything on that paradigm, whatever mental gymnastics is required.
Besides, most of the programming world has been imperative-only from the beginning until just a few years ago. I don't know where you see all that multi-paradigm success.
We also have a lot of people rewriting legacy stuff on Rust, just for bit of extra confidence.
Currently, people have got out of their way to create artificial intelligence guided real-time optimizers that converts von Neumann code into graph-machine code on x86, because it performs better. But it gets very close to optimum usage of the graph machine, so there is no need for most people to actually learn it.
No, but it's the best predictor of them.
>If a non-imperative paradigm enables the creation of a different architecture that consistently beats the von Neumann adaptions we can create, you can bet people will get out of their way to write everything on that paradigm, whatever mental gymnastics is required.
Well, if wishes were horses beggars would ride. Let's have someone build and showcase this "different architecture" before we drop the current one.
C# is more imperative with functional mixed in and does little to stop you doing functional "evils"
F# is more functional with ability to mix in imperative and mutations and stops you from doing functional "evils" unless you say you want to be evil
I'm not experienced enough to judge how well it does all this though.
It argues that the idea that there is an ineleminable imperative core in our programming model is just an assumption today, and I agree.
But that doesn’t mean it’s right or wrong, just that we have to wait to prove or disprove that assumption. People should keep trying to disprove it, but I can’t fault the majority of developers for continuing to take it as an assumption.
"Belief, as I use the word here, is the insistence that the truth is what one would “lief” or wish it to be. The believer will open his mind to the truth on the condition that it fits in with his... "Faith, on the other hand, is an unreserved opening of the mind to the truth, whatever it may turn out to be. Faith has no preconceptions; it is a plunge into the unknown. Belief clings, but faith lets go. In this sense of the word, faith is the essential virtue of science, and likewise of any religion that is not self-deception." – Alan Watts
Faith as every human on earth uses it is a belief that that person has opted to exempt from questioning. It means in fact the opposite of his usage and all belief systems are necessarily self deception stories we make up and tell ourselves to render sensory soup a coherent narrative in which we have a part.
Now that's a belief. Doesn't seem like you're open to questioning it though.
> We must here make a clear distinction between belief and faith, because, in general practice, belief has come to mean a state of mind which is almost the opposite of faith. Belief, as I use the word here, is the insistence that the truth is what one would “lief” or wish it to be. The believer will open his mind to the truth on the condition that it fits in with his preconceived ideas and wishes. Faith, on the other hand, is an unreserved opening of the mind to the truth, whatever it may turn out to be. Faith has no preconceptions; it is a plunge into the unknown. Belief clings, but faith lets go. In this sense of the word, faith is the essential virtue of science, and likewise of any religion that is not self-deception.
The previously missing sentence and the very beginning of your quote seem to address your comment: "in general practice, belief has come to mean a state of mind which is almost the opposite of faith. Belief, as I use the word here, ..."
My impression is that belief has become according to Watts as an assertion of a specific hypothesis: I will open myself up to this idea if and only if the idea fits with my preexisting ones. If you are testing a hypothesis, this is a poor attitude to have, and it can affect how you perform the test: the test could be wrong but agree with your preconceptions. This is how "belief clings".
Faith, as the "essential virtue of science", according to his definition would be detachment from the outcome of testing a hypothesis, "whatever it may turn out to be", with "no preconceptions". You have a question, and you are employing a method, and the outcome remains unknown until you complete the test (and perhaps even after). This is how faith "lets go".
Religion of "self deception" is one where those practicing it only open their minds to any particular idea "on the condition that it fits with" their preexisting ideas. Religions that do not deceive themselves must then be religions that open themselves to new ideas, whether or not those new ideas agree with ideas they already hold.
But even from the early days, Rich Hickey said that no pure functional system exists as even an empty HD emits heat, which is a form of IO and I think we should listen to Hitchens and abandon our "fantasy of purity" when it comes to writing real software.
It's kind of like, think about grammars of human languages. Obviously human communication involves commands. But you might still have a good reason to desire a grammar that is "purely functional" in its mathematical formulation.
Pure functional programming is about establishing a certain level of formal discourse where expressions involving applications of functions reduce to values. It's not a fantasy where effects don't exist—it's a way of being precise about effects in a particular style of formalism.
These expressions should be able to describe all kinds of systems, as indeed Haskell's IO type is extremely capable when it comes to describing multithreaded sequential computations involving mutable state and external effects.
Conal is suggesting that the IO type is a bit crude compared to the full potential of "functional reactive programming" which is for sure a powerful paradigm.
1. Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices). 2. Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).
As soon as I/O is involved, functional purity is technically broken and since any real-world system will have I/O I consider the quest for purity to be a fantasy in the same vein as developers who invest a lot of resources in "proving" their functions.
You guys are arguing over the monadic io that he dismisses in the first couple couple paragraphs.
All he really cares about is achieving program composition.
There's also atoms and agents to look at, but the overall perspective is that the world is as the world is and those who observe it always do so with some delay. The discrete timemodels allow you to have consistent views of the world from multiple observers.
This is a the heart of Datomics data-model. Nothing ever changes. If you commit a fact like "fred likes pizza" at 2pm. Fred will always be known to have liked pizza at 2pm. If you later commit that Fred likes apples. That will only be true from the point in time in which you commit, but you'll still be able to see that fred used to like pizza.
The IO is a side-note, but living on the JVM Clojure has native access to everything from files to streams and you can interact with them just like Java people do. There's a few helpers like with-io to manage multiple simultaneous writes, but they're rarely used.
Haskell in this regard, has the IO Monad which is briefly commented on the article. Its sort of a trick and as I understand it Haskell has no ambition of being the go-to concurrency language. It has recently had something like Refs/STM added though, haven't looked into it much.
The IO monad in Haskell is no trick, but I can understand why you would think that.
Everything else, incl the entirety of the core language, is immutable and functional. You have to go out of your way to mutate.
Its a functional Lisp tightly integrated with the JVM and compiles to both Java bytecode and Javascript. I think that makes it unique.
[1] https://clojure.github.io/clojure/clojure.core-api.html#cloj...
The signature is there, eg.
> Usage: (print & more)
'& more' means 'any number of arguments stuffed into a sequence called more'
> (print [1 2 3]) "[1 2 3]" nil
There are a number of ways to print an array of lines and doseq is one. Its designed for statements at have no return.
Anyway, my point was, no effects system. There's no way to determine if something has side effects or prevent them. Very far from Haskell's purity. I wouldn't criticize Haskell for a "trick" that enables the impressive feat of maintaing purity with side effects (while at the same time maintaining strict enforcement of types throughout) when Clojure doesn't even have any kind of effects management.
[0] : https://futureofcoding.org
Strongly recommend anyone interested in such topics (programming languages, rapid prototyping, HCI, low code platforms, etc) to check out his work. Steve is doing some really great work as a individual researcher!
Abstract
> It is well-known that the simply typed lambda-calculus is modeled by any cartesian closed category (CCC). This correspondence suggests giving typed functional programs a variety of interpretations, each corresponding to a different category. A convenient way to realize this idea is as a collection of meaning-preserving transformations added to an existing compiler, such as GHC for Haskell. This paper describes such an implementation and demonstrates its use for a variety of interpretations including hardware circuits, automatic differentiation, incremental computation, and interval analysis. Each such interpretation is a category easily defined in Haskell (outside of the compiler). The general technique appears to provide a compelling alternative to deeply embedded domain-specific languages.
[0]: https://whatis.techtarget.com/definition/von-Neumann-bottlen...
Since this article is almost 10 years old... has any progress been made in demonstrating the existence of pure functional I/O? Reading files and writing to the console is one thing, I’m more curious about human input, GUIs and language. Think about apps Photoshop, Super Mario Bros, or Sublime text. The ways we want to interact with them seem more fundamentally sequential. Not only can I not see how to make them pure functional, I can’t see what that even means or why it would ever be desirable.
> Hand-waving is an important factor in staying stuck in impossibility thinking, since rigorous argument uncovers unconscious limiting assumptions.
You have to admire the effort to discredit any rational thinking before it starts.
Well, there's literally no difference between reading from a file or from a queue of requests from the user on any level of abstraction.
E.g. you could (functionally) apply a list of operations to an image in Photoshop that the user has supplied you with.
You don’t normally have to output intermediate state while reading a file, but you do with human interaction. Human interaction is usually responding and reacting to intermediate the state of the program. Think a bit more about Super Mario Bros.
A file can be read as a single chunk of memory, and it doesn’t need to consist of a queue of sequential operations. We can decide and design what files are and what’s in them. An array in a file doesn’t need to be read one number at a time.
Human interaction, unlike a file, cannot happen all at once, needs intermediate feedback, and cannot be reordered or easily reformulated into another representation, because it’s responding to the intermediate state of the system.
In that sense Mario isn’t really that different!
(Subtly, a purely functional Mario game has more inputs than just the controller. You’ll need a clock signal for the Koopas to walk around at a given pace, but that’s not too different from a file of sequential numbers that’s read at a particular speed.)
Backstory: I used to think that front-end JavaScript programming was too stateful and inherently messy to be compared with, say, handling HTTP requests. But the Elm language (and to a lesser extent React/Redux) has shown me that the messiness is accidental. You actually can apply the techniques of purely functional programming to create arbitrarily sophisticated GUI programs. Here’s a simplified version of Mario in Elm: https://github.com/avh4/elm-mario.)
The human input depends on the intermediate state, where the file input does not.
Manufacturing a case where you output the intermediate state as you read a file is missing that crucial dependency.
You must also assume that the human input cannot be predicted before the intermediate state is known. Assuming that it’s a function of time is cheating.
> You actually can apply the techniques of purely functional programming to create arbitrarily sophisticated GUI programs.
No, you can’t. That’s exactly what this article is talking about. React is a state machine under the hood. You can handle each request in a functional way, but you can’t build the request processing behind the scenes in a function way, it’s not currently possible.
However, from your point of view, all of your code can appear to be functional, so some of the comments here are, reasonably, asking the question, why does it matter?
Not sure what you mean by “depends” here. If I’m at a game controller I can smash buttons for years without caring what the state of the game is. It’s up to the game to make sense of those button presses and do the right thing.
Just because you can smash buttons randomly doesn’t prove anything, that’s not normally how people play games. Normally, they see what’s happening and respond in order to succeed.
If you want a complete cybernetic framework to model the player and the game, I wouldn’t know where to begin.
The reason a file is different than a human is that everything in the file is known in advance, whereas the human reacts to the program. It’s not just about unpredictability, it’s also about the dependency.
The human input is not decided until the program displays it’s intermediate state, and when the human does send input to the program, the input is based on what the human sees, which is the program’s intermediate state. So, the human input depends on the intermediate state.
A file input does not depend on the program’s intermediate state. The file input is a static queue of data that doesn’t change. If you change the program, the file won’t change, but the human input will. A queue of commands in a file is fixed, and showing the program’s output doesn’t affect which command comes next from the file.
The human input is a function of time and also of the program’s intermediate state, and lastly of the human’s whims. These things force the program’s evaluation loop with human input into a specific order that cannot be evaluated or re-ordered or simplified in advance, unlike the file.
Is that making more sense now? All of this is exactly what the author of the article was talking about when he discussed weak vs strong composition. Do you understand what he meant by functional composition being stronger than Von Neumann composition, and why?
Suppose we had a runtime comprised of objects, and execution was represented as messages sent between objects, as in Smalltalk. Unlike Smalltalk, however, objects would never be created or destroyed. All of our program’s logic and behavior would be represented as a pure transformation on every message between objects. In pseudo-Haskell:
-- A message is a receiver identifying an object, like “Program”, and a selector, perhaps containing data
myProgram :: Msg -> Msg
myProgram (Program {begin}) = Window {createWindowWithName="myWindow"}
myProgram (Program {windowCreatedWithName=name}) = (Window {windowWithName=name, setTitleTo="Hello world"})
myProgram (Program {windowWithName=name, didChangeTitle=title}) = (Console {print=title})
myProgram msg = msg
It would be easy to compose programs written using this paradigm, and not hard to imagine what composition of executable programs would mean. For example, to log the name of every window created to the console:
logWindowName :: Msg -> Msg
logWindowName (Program {windowCreatedWithName=name}) = Multicast {messages=[Program {windowCreatedWithName=name}), Console {print=name}]}
finalProgram = logWindowName . myProgram
We could add yet another object representing mutable state, with messages describing changes to it and responses containing data stored there. Without using something like this to explicitly model it, I don't see any explicit sequencing of instructions as in the IO monad.
Are there obvious problems with this approach, or has anything very similar been tried?
The message that is actually left gets sent to the object, which generally do impure things?
Would there be any way to define such objects? (Any such definition would of course basically just be a message translator like the program function, but if users cannot define such an object I'd imagine some real pushback, or at least some complaints.
Without a built in object to handle say MyFavoriteDatabase, doing the equivalent via a message to Network, and its reply message back to Program would feel a lot like completely useless boilerplate. (especially since i would need to transform the high level query to something low level like raw packet contents before i could send it to Network, and do the reverse on the reply, while a MyFavoriteDatabase object could do that all for me.
print :: a->a
Or
print:: a->(a->b)->a
I mean pretty straightforward. id functions in your compositions don't effect the overall program.
This is only for the O part of IO. Input is a different problem.
This is partially problematic because of lazy evaluation. It is not clear when the print-statement will actually print. This could even lead to a re-ordering of the print statements.
Another issue occurs when output is piped to input. In bash you could do something weird like:
foo -i bar.txt >> bar.txt
Async/await is sequential where the operations are asynchronous (you don't move to next async operation until the previous async operation is done, given that the second async operation have dependency on the first operation's result).
See the out of the tar pit paper https://blog.acolyer.org/2015/03/20/out-of-the-tar-pit/
Quoted: > The problem with control is that very often we do not want to have to be concerned with this. Obviously — given that we want to construct a real system in which things will actually happen — at some point order is going to be relevant to someone, but there are significant risks in concerning ourselves with this issue unnecessarily.
a = 1;
b = 2;
foo :: Int -> Int
foo a = let
z = a * c
b = 10
c = 20
in
b + c + z
(Not that I didn't like Prolog -- I did -- I just felt far from freed of mundane concerns of execution order.)
> I just don't get the idea that "sequential" is somehow a bad thing?
and this:
> The whole concept of an algorithm/procedure to perform a computation is about performing a series of operations in a specific order.
are different manifestations of the one thing: you are thinking about programming in a sequential terms only. When you think about programming problem you are trying to solve it by a sequence of operations. You should try something like Haskell, something that force your mind to think differently, it would help you to teach your mind to see programming other way.
Such a "sequential thinking" is acceptable, but you probably not as good as you might be at thinking about programming problems. Functional programming helps to think about code one level higher, without distractions and compications caused by "linearization" of your thoughts to fit them into imperative paradigm. The main reason behind functional paradigm is an ability to prove statements about code, to be able to reason about code.
To throw out idea of sequence from reasoning of code is a futher abstraction from underlying machinery like transistors or machine instruction set. As any abstraction it gives you both benefits (you can think about more complex problems using the same amount of computational power of your brains) and downsides -- you become more restricted by paradigm itself, though I cannot explain what these restrictions are, because I can feel them sometimes, but do not know how to verbalize that feelings.
You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Moreover some of that reasoning you can do by special program, like compiler or static analyzer.
Can you provide a concrete example of this? Otherwise it is just a hand wavy thing to say (which are way too many in programming world).
I should use an artifical task as an example, but the trouble is if someone thinks in imperative terms only, then when he tried to think about a task he would frame the task in imperative terms and he would see it as an imperative problem and would fail to see it as a functional one. It is not because he is stupid or he posess some other disabilities, it is just the way human mind works. It is like people saying "what is so good about language X, if you can do all in Y"? "Why one needs OOP languages, if you can do OOP in C?" The way we think about problems defines how we see problems, and what we see as a problems.
But let us try.
qsort [] = []
qsort (x:xs) = qsort [ y | y <- xs, y < x ] ++ [x] ++ qsort [ y | y <- xs, y > x ]
quicksort of empty sequence is an empty sequence. quicksort of sequence starting with x is a concatenation (operator ++) of three lists: quicksorted list of items from the rest of sequence (sequence without the first element which is designated as x) that are lesser then x, list of one element x, and quicksorted list of elements that are greater than x.
Of course, if you want quicksort to be sorting in place, you would need to think about small details like traversing two pointers, one from the front of the sequence, second from the back, swapping elements, and not forgetting about the choosen one... Yeah, reality is more complicated than that, sometimes you cannot get rid of complexity.
Functional compilers are constantly searching for optimizing techniques to get rid of all these small details, and in some ways they are succeeding. Though no one is good enough to generate machine code for sorting in place by compiling high level code above. But I tried to demonstrate the idea of abstraction of details and how it helps to understand code and to reason about it, and I believe the example is showing it.
As far as imperative vs functional goes: Remove the assignment operator from an imperative language and you will end up with functional language without bell and whistles (then you will have to make conditionals as expressions and instead of loops you will need to use recursion).
Yes, and no. For example B(A(x)), haskell can call A(x), get result, then call B passing result as argument. Or it can call B, passing closure as argument, and when it comes to a point, when calculation of B cannot be continued if we do not know value of A(x) only then A(x) would be calculated. In some sense A(x) was done before B -- before B was finished, but from other hand calculation of A(x) was started after starting calculation of B.
> My question was about "sequence of things to do", which is different concept than "imperative programming".
I'm not sure, that I can see a difference, but nevertheless, in example above there is not sequence of operations. There is almost declarative definition of a quicksorted list. There are multiple ways to linearize it into sequence of operations and even if there was single way I don't mind. It is the task of a compilator to make this linearization, not mine.
If the computation truly is one that is most practically described as a sequence of steps, that is easy to do. In fact, in some sense this is what the infamous "Monad" concept is all about.
If you model it sequentially, it takes a lot of work to make sure the right data is calculated in the right order. But you can also model it as a set of lazily evaluated streams, and that makes life a lot easier – because order of evaluation isn't part of the domain, it's essentially an implementation detail.
ETA: another way to think about it is that this lets the compiler manage evaluation order by default, while you're free to focus on other stuff (with the option to manage manually if you need to.) This is a similar type of benefit to garbage collection.
Sequential: you deal with one item at a time, you can deal with an infinite amount of data with a finite amount of memory. Cons: can't parralellize, early eval of things you don't need, you might need to go through the loop more than once.
Getting rid of order gets rid of the bugs. Like how restricting types with type checking gets rid of all type errors.