Not sure if the author will read this, but there is a simple answer to both problems.
In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program.
This is somewhat dual to imperative programming, and is kind of a shift of the frame of reference. We could make an analogy with an assembly line in a factory. Imperative programming is like looking standing at the factory floor, every machine (procedure) receives a thing (input), does something with it, and outputs it. Functional programming is like being together with the thing as it is manipulated through the factory, in its own frame of reference. So instead of passing the thing (data) around, you see passing of the machinery that modifies that thing (functions), in the opposite direction.
Using the interpreter example in the article, would it be accurate to say that the author's inefficient "each instruction copies the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would eventually be garbage-collected)" is "manipulating the state directly"?
Yes, and also not a data structure that is suitable for the task. If you want to keep every version of the buffer as a value (which has nice properties like versioning) you would need a data structure that shares most of its structure with the previous versions. Like a persistent radix-n tree. Slower than mutable buffer for sure, but not pathological.
Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se).
Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution?
(Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)
Not sure there's any benefit in using the state monad for an interpreter.
My first thought is to model a cycle of the interpreter as a function of old state into new state.
I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data.
Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it.
Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though.
When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluate the application at some point. The go-to technique is to use Normalization by Evaluation [0], where you convert the AST version of a function in the interpreted language to an actual function in the host language, and piggyback off the host language's (presumably very fast) function application.
I suspect you already know this, but other readers might be interested to know that in Haskell you can also use the ST monad which can do local (actual) mutation which is guaranteed to not escape the function's scope.
(Of course you can only access the actual local state and not do I/O or anything like that.)
I was involved with one that wasn't really demanding in terms of computation, but was distributed in a way that required a lot of speculation and rollbacks. The functional approach was pretty sweet.
Highest speed bytecode interpreter is actually one of the few loops where I prefer assembly to C, as the instruction mix, branch prediction and even the use of stack can be weird from the PoV of a modern optimizing compiler.
Isn't there a way to derive efficient/in-place interpretation from pure total recursive functions ?
reading lisp in small pieces, the author migrates interpreters from naive recursive eval to bytecode. It felt there was an underlying model to extract.
No, its not manipulating the state, which is why it is inefficient.
An example of what parent was talking about is instead of looking over a list 10 times calling different functions that build a new result list each time, you compose those inti one big function that visits each element once.
> In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program.
A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write
map (\x -> x+1) mylist
You'll map over a list and add one to every element. this allocates a whole new list where all the elements are increased by one [0]. Now let's say we take the output of that map and map over it again, but this time we multiply every element by two:
map (\x -> x*2) (map (+1) mylist)
Naively implemented that would copy allocate two lists, one where all the numbers are incremented and another where all the incremented numbers are multiplied by two. Any good dev will know that's performance poison. So the Haskell compiler implements "list fusion" – it sees that you don't use the intermediate list for anything, and rewrites your code so it's equivalent (in semantics and performance) to:
map (\x -> (x+1) * 2) mylist)
(For the compiler devs in here, this optimization is commonly known as deforestation.) This leads to huge speedups in many cases. But there's a problem. If elsewhere you use the result of `map (\x -> x+1) mylist` for anything besides mapping over it exactly once, this optimization is impossible! So list fusion has a reputation for being fragile – the compiler has to know with 100% certainty that you aren't going to use the list for anything else, and sometimes innocent-seeming changes (like moving the intermediate map into another module) can break it.
The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you. The compiler is still on the hook for doing the analysis of what's used once and what's used multiple times, but now the programmer and the compiler can be guaranteed to be on the same page.
As for the other issue mentioned in the original post, of modifying a subelement of a tree: this is a well-known problem and there are many solutions. If the tree is only used once, the same optimization as list fusion can be applied to mutate the list in place (although the "you must use the value only once" restriction doesn't help quite as much as you'd think it would). The more common solution, that doesn't depend on compiler optimization at all, is to use a data structure that supports this efficiently. For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying. That's why it's very common to see maps implemented in functional languages using trees, instead of hashmaps. With a hashmap, it's much harder to get around the need to copy the whole thing when you just want to change one part.
[0]: Well, it might do that that once it gets around to it, laziness etc., but let's ignore that for now.
> The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you.
I suspect the contortions required to fit your code into that affine type style will likely lead to code that is just as hard to understand and maintain as the equivalent imperative code (though with better static checking, which might be nice).
It's surprisingly convenient when you get used to it. A very large proportion of values are only used once, so if a function only uses a value once you can mark it as being linear in that argument and get the relevant guarantees for very little mental overhead. You can still pass any value you want to the function, the only restriction is that the function must consume the value exactly once. It's tricky to write performant functional code, but personally I find linearity tagging a small price to pay for salvation (see this article I wrote, posted here: https://news.ycombinator.com/item?id=30762281 ). (Note that GHC currently doesn't use linearity for any performance optimizations, this is just a promising possible route.)
One tidbit you might find interesting. Linear logic requires you use the value exactly once, but if you relax that requirement to "once or zero times" you get affine logic. (Values that don't have the any restriction on how much you can use them are called "exponentials".) With both linear and affine logic, you can pass an exponential to a function that's linear or affine in its argument – the only requirement is that the function uses the value in a linear or affine way. That's not quite the same as what Rust does, which I do find a bit annoying. What rust does is called "uniquenes typing", where a function can always do whatever it wants with any values it gets, but it can mark its parameters as "unique" and the caller has to make sure that any value passed as a parameter to that function is never used anywhere else. This is arguably the more useful of the two, because it means that you can mutate any argument marked as unique and no one can tell, but if you design a language around that you get Rust and I find Rust a bit less pleasant to program in than Haskell.
> For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying.
This still only works if a child has one / a known-ahead-of-time number of parents. If you need to update an object that N objects point to, you need to update all N references.
It just doesn't really happen that much in functional programs, to be honest.
The very concept of n objects pointing to the same, commonly mutated data is something that can be adressed easily by having that data contained by a parent structure. Since functional programs don't think in terms of "methods" within each object trying to access data, but in terms of external function manipulating all the data you need, the only change is the way you'll pass your data to your functions.
You work with monads all day long, you just don't think about them as such.
There is no such thing as "monadic programing", even in Haskell. The thing making haskellers harp about monads is that the std lib went a bit far in making sure that every fitting data structure implements the monad interface, which includes IO.
That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no?
But Clojure also has a habit of implementing core functionality that needs to be fast in imperative Java.
The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary.
Which hints at my own opinion on how to deal with this Gordian knot: just acknowledge that there is no universally best programming paradigm. Some problems are, as a practical matter, best modeled in an imperative manner. That's fine. And I don't think it should be personally threatening to us fans of functional programming. John Backus openly discussed it in the paper where he originally proposed the paradigm, and I personally prefer, for moral reasons, his suggestion for how to solve it. In a world where everyone's trying to build the best spork, I think I'd rather have one good spoon and one good fork.
Yes, but paradigms can be different enough that an intelligent compiler fails to find the same optimal assembly for two solutions for the same problem. Thus the paradigm in which you express the solution matters. Otherwise we would just need to express the problem, and a trivial solution, and the compiler would work the rest (the idea behind declarative programming!)
Clojure's other big thing is "transient" local mutable state within a function, like Haskell's ST (State Transformer) monad (the more efficient alternative to the pure immutable state monad)
Yes, although I suppose even in languages where this isn't mitigated (i.e. Clojure example below), you can offset that inefficiency with the parallelism enabled by functional programming.
> That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no?
You use special data structures to deal with that. There's a great book about them, "Purely Functional Data Structures", by Jeff Okasaki. You generally don't get O(1) update like for traditional arrays, but you can usually get O(log n), like you would get for a database table with B-tree indexes.
Came here to say this. The author wasn't actually describing problems with functional programming, he was describing his troubles due to naive implementations.
Naive implementations will always, by definition, not be great. But instead of spending the time, energy, and money on crafting a custom solution each time, use off-the-shelf libraries that do the job. DataScript, Storm, etc. are great for this.
So, as the trend of forcing functional programming into imperative languages continues on its inexorable path, I just can't help but bring the old joke to mind more and more often:
"Doctor, it hurts when I do this."
"Well, then, don't do that."
You mean, jamming a foreign paradigm into a language, where the advantages of the foreign paradigm are reduced and the disadvantages greatly magnified, hurts sometimes?
Have you considered... not doing that?
I simply can not apprehend the mindset that goes:
1. Wow, map/filter/reduce sure is fun in this language over here
designed to work with it.
2. Now I'm going to use everywhere I go, no matter how much it hurts
and no matter what compromises I have to make.
3. When it hurts, I will blame anything and everything except myself
for forcing a paradigm in where it doesn't belong.
The paradigm has to be good. It just has to! Even if it hurts! Even if I'm really not enjoying using it! Even if it's murdering my runtime and killing my performance and I'm in a language where functions take quite a lot of text rather than \x -> x + 1! Even if my code is hard to read and hard to abstract and hard to refactor. Even if the foreign paradigm is critically based on pervasive laziness my language doesn't have! Or some other foundation my current language totally lacks! Gosh darn it, I'm going to use this paradigm in this code if it kills me! Because it was so much fun... over there.
I'm not saying that it isn't sometimes useful to borrow paradigms in certain places even in languages that don't support it. When it doesn't hurt like this, by all means use it as you like. What I don't understand is this constant, if not growing, stream of posts about "my gosh, my forced FP programming in this not-FP language is kinda painful here... grimaces yup, it's pretty painful all right... grits teeth yup, this is really hurting me and making me really angry and isn't fun at all... but I'm so glad I'm using this style that is making things hard and hurting me and making me angry, wouldn't dream of doing anything else!"
I know Haskell. There are many lessons I've taken from Haskell and applied to other languages, like the virtue of very strongly separating IO code from logic, the virtues of taking extra steps to provide and use composability in your APIs, the virtues of certain things being immutable data. But taking these lessons from functional programming languages shouldn't mean you ape the surface solutions functional programming uses; you should be thinking about how to idiomatically bring the target virtues into the other languages you use. There will be compromises, but sometimes there will also be things the current language does better than Haskell. (Really quite a lot of things. Haskell's great but there's many reasons it hasn't conquered the world.) You shouldn't be so focused on importing the foreign paradigm that you completely throw away the virtues of the environment you're in.
I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages. It's an incredibly aggravating place to try to be. The (near) union, applied with the wisdom gleaned from both camps, is much more fun.
If that's your defense, party on. If you want masochism, by golly you've found it.
But could y'all be more clear about labeling at such? You're fooling young programmers into thinking this is a good engineering idea. In engineering, we do not climb mountains just because they are there. Quite the opposite.
This goes back to the old “this is Hacker News” explanation. Some things are just implemented for the heck of it. Some things are just done according to a certain paradigm for the heck of it. Or in order to see how far you can go.
Why not see how far you can go with pure FP before it breaks down? Or you have to make compromises.
And not everything on this site is about “good engineering practices”. (Not that I would file your original, mocking comment under such a professional label, either.)
On a second skim though the submission is more naive than I would have expected from a Racket programmer. Using imperative datastructures like arrays (contiguous chunks of memory) and then copying for every action is not really recommended. You should use purely functional datastructures if you really want to not do destructive updates.
I don't believe it's true that algebraic data types "came from" FP. The name did, but the concept has existed since before high level languages existed. Actually before computers existed since it's in Type Theory. And before that it's in ordinary human thinking for thousands of years.
I mean, Lambdas came from the Lambda calculus which predates FP. Type inferencing was also formulated as part of typed Lambda calculus. Pattern matching definitely came about prior to FP; SNOBOL (and its predecessor COMIT) is probably the first language that really made it 'a thing'.
Very few things FP uses came from FP; they came from underlying Math and CS, and are themselves specific formulations and implementations that fit within the context of broader well understood concepts.
I think you're being downvoted because your tone is a bit hostile, so I'll bump you up because I think you make a good point.
I love functional idioms as well, but you have to know the cost of those idioms in a non-functional language. The first thing I did when I had to learn go was determine if I could use functional idioms (map, fold, etc.) and did some research and testing and found that, no, functional idioms are a really bad idea in go. It just isn't meant to be used that way.
For the record, I had to learn go because the team I joined used it.
Tried saying it politely. Still get downvoted. Thought I'd try a bit sharper on purpose.
Despite what it may superficially sounds like, it's an attempt to reach out and help people. If it hurts, you know, think about it. Maybe don't do something that hurts so much because it "must" be good.
FP techniques in imperative languages is a tool. A good tool sometimes. But it shouldn't be an aspiration.
I don't really see how this relates to the article. The author specifically mentions that he also encountered these problems in Racket (a functional programming language). Anyway:
>I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages
Because it actually works pretty well? The vast majority of programming languages today are multi-paradigm for a reason. In fact, almost all functional programming languages (Lisp, Scheme, Racket, Clojure, (S)ML, OCaml, F#, Scala) are multi-paradigm. Haskell is really the odd one among functional programming languages. The same applies to lazyness by the way, to claim that functional programming is "critically based on pervasive laziness" is simply wrong.
The idea that people use FP in a language like e.g. JS only because of an ideology driven obsession and that they constantly have to fight against the language just doesn't bear out in reality.
I'm not talking about using it when it's helpful. I do it myself all the time.
I'm talking about forcing it in when it hurts specifically.
It occurs to me that I may have accidentally answered myself at the end, when I referred to the concept of union vs. intersection. When you bring in helpful angles on your current paradigm from light cast by other paradigms, that's helpful. You're expanding your working set of options.
But when you get a bit of a good taste of those other paradigms, and then declare this is always the right way to do it, it may feel like you're expanding your paradigms, but now you're not. When you force sum types into a language that doesn't support them because they're just always the right answer, when you force lots of maps & filters in a language that can't do fusion and function calls are kind of expensive, when you force an algorithm in that depends on laziness to work, and so on, you are no longer working in a sort of union of paradigms. You're working in the intersection.
And that intersection sucks. A worst-of-both-worlds situation for sure.
You can tell, by the way people trying this are constantly screaming in pain about it.
I’m pretty sure half the purpose of the article is to resolve the ambiguity: does it hurt because the paradigm is inelegant for this problem, or because I don’t know how to make it elegant?
Just stopping anytime you struggle is precisely how you learn nothing at all
Sure, it's best to work with rather than against the language, but for most languages support of functional programming is not binary, just like with OOP.
I'm pretty sure most of the complaints are generally of the "This FP thing would work well here, but the language is unfortunately not quite there" nature rather than "I will try to implement profunctor optics in C no matter the cost" square peg in round hole crazyness.
>when you force lots of maps & filters in a language that can't do fusion and function calls are kind of expensive
I think that's perfect example to show that it's really about degrees, because fusion is really a Haskell thing. Sure, it's a nice-to-have, but it's definitely not essential to functional programming.
And when people want sum types (which aren't even really FP, ALGOL had them first!), it's often because the idiomatic alternative just kind of sucks for what they're doing. Trying to "implement" sum types in a language without support is nonsensical, but complaints about lacking them are pretty understandable I think.
The question I am left with, as someone who has a bit of experience with functional languages but much more in imperative/OOP languages, is does it ever make sense to develop something like the GUI applications the author was talking about using a primarily functional paradigm ? Assume you get to pick whatever FP language you want so the issue here isn't with shoehorning FP techniques into a language that doesn't support them well, it's about whether there are certain types of programs that just aren't suited to a functional paradigm.
That is a very good question. The discussion often circles around pro- and against FP. Proponents of "pure FP" seem to suggest that it is the best solution for everything always. Is it?
If not it would be nice to find discussion about when it is and when not and why? What is Haskell NOT the best solution for?
In my experience Haskell is a bad solution when you need fine control over memory usage and control flow. For those cases you should probably use something like C, C++ or Rust. For everything else I think is a viable option.
The hard part is understanding how you should model your problem. I found that you could classify problems into two big groups: pipelines like compilers or web services where you get an input, do some processing and produce an output, and graph problems like GUI applications where the system is a living thing and events change how components should behave. The first group is easy, the second not so much. Excel is the best example of this kind of system: an user describes relationships between cells and lets the runtime perform the appropriate side effects. Ideally we would be able to write arbitrary programs using this same model.
It took me some time to understand how Haskell performs its "magic" but now I think I do. Anybody please correct me if I'm still getting it wrong...
Haskell main program in essence runs a big loop until it decides the program should exit. In Haskell syntax the loop is coded as a call to a tail-recursive function, which on a real hardware of course needs to be translated to do iteration. At the end of each loop it sets the new calculated value of the new state to be used during the next loop.
Using tail-recursion optimization it looks like our whole program executes a single top-level function-call of a recursive function, that is how you code it in Haskell.
This is great but somehow it feels like a trick. It is actually still doing iteration and state mutation internally while running. You could program that in an imperative language writing a top-level loop and iterating over it and modifying the statefull variables at the end of each loop.
And what happens if you cannot write your program as tail-recursive function? What if the problem domain requires you to use general recursion, which can not be optimized away like tail-recursion can?
What you are trying to describe is not Haskell the language but an implementation, and right now the de facto implementation is GHC. I really can't talk about how GHC works internally, but when it comes to the language you need to think your program as a value, just like `5` or `[1,2,3]` or `{ "name": "susan" }`. That is, effects are values, you compose those effects, and, your program being some kind of effect, is also a value. That's the reason behind `main :: IO ()`: your program is an `IO value`.
When it comes to "executing" your program, a runtime (like GHC's runtime) takes your program which is a value and actually performs the requested actions, dealing with mutation, loops, jumps, etc. This is a hack just as much as any other language dealing with variables instead of the stack, heap or registries directly.
In case you're interested, this idea of using some kind of interpreter which loops over your program and performs mutations and side effects is very popular in Scala: libraries like Cats and ZIO do this, allowing you to effectively get Haskell's IO. As far as I know, tail-recursion is not really needed for this, but when implemented on the runtime it allows the end user to write loops using recursion without blowing up the stack.
Right. I was thinking of how to write a game in Haskell or similar. I need to write some kind of loop to keep my program/game running indefinitely. And I need to avoid "blowing up" the stack by writing my program as a set of calls to tail-recursive functions. No?
The program must keep the previous state somewhere and then modify it based on the player's inputs and again store that new state somewhere somehow so it is remembered when next input comes. If loops which keep and modify state are not allowed, then I don't see how it could be done without tail-recursive functions.
No, that's not accurate. The final form of your Haskell program before it's compiled down to some assembly language (currently C-- or LLVM) is a graph reduction problem. The partially imperative part is the runtime system, which actually reduces the graph (= runs your program), but this is significantly more complicated than the sort of high level loop transformations you're talking about. Search "spineless tagless G-machine" for a (somewhat idealized) description of the core architecture of GHC.
For GUI programming I found FRP to be a really good solution. And no, I don't consider React to actually do FRP.
The closest mainstream project to FRP is Angular using RxJS exclusively. You define how each component interacts with each other, and then you delegate to a runtime to actually perform the side effects (change the DOM in this case). Solutions like React + Redux/Elm involve a lot of plumbing that's not relevant to the issue: I just want to define relationships between components, not manually tread changes across a big state tree.
Functional Reactive Programming (FRP) is a really nice paradigm for doing GUI in a functional setting (e.g. Haskell). I build games in Haskell., including UI. It's great.
There are a number of patterns that have arisen over the years to deal with these problems. For the large-object problem, look into persistent data structures or the 'Functional but in Place' paradigm (compiler optimizes modification on a copied unshared array to a mutation).
For the parent-child problem, typed handles, continuation-based state propagation, and reifying state updates for a declarative interpreter may be used.
Monads and effects are common in strongly typed functional languages, but have less bearing on lisp, which usually embraces dynamism to some extent.
This article explains the problems pretty well, but they are old problems and functional programmers have various solutions that the author seems unaware of.
I'm not a Haskell programmer but I do know about monads and have heard of lenses.
Lenses don't help. They just make copying and updating large data structures cleaner to write. They don't solve the performance problem of copying everything.
Incorrect. Optics implementations can ensure updating a node in a large balanced tree is O(log n) instead of O(n), trivially, and I'm sure there are sufficiently clever collections with optics that would enable much better performance than the trivial optimizations I can think of.
Not all data structures are a large balanced tree and a O(1) update is going to be faster than O(log n) updates. There is still going to be a significant performance hit from having to recreate a whole node instead of just updating a single value. While yes you can say large data structures are like a big node of a tree, having to copy all of the different records from the old one to a new one is going to be considerably slower than just modifying a single record.
It does help, but it's still going to be significantly slower than just modifying a single record in a data structure. It is a still a problem that will be slowing down your program.
Purely Functional Datastructures (for example) introduces efficient operations on “large” objects. Next, as Out of the Tarpit suggested in 2006, use a relational model (developed in 1969). Hardly seems vexing. Yes, maybe not as efficient as other ways to compute.
Relational systems (e.g. SQL) solve the parent-child problem by making references explicit -- instead, keys are used to reference children in a well-known collection.
That is, if you're trying to emulate sharing of mutable structures (i.e. pointers) in a functional language -- that is, reflecting changes to children across multiple parents -- model the pointers explicitly (as integer keys) and put the shared structures in a map, which is necessary to interpret a parent in full.
This seems to be what the article is getting at with its "mediator" concept, albeit in very abstract terms. The author seems to find this distasteful, wanting to "hide" these relationships, but I disagree -- the difference between value and reference semantics is very important; making the difference explicit is a good thing.
The a-ha moment for me was that functional programming - in most real world applications - is less about "no state" and "no side effects", and more about "properly managed state" and "properly managed side effects". This is one of the things I really like about Elixir/Erlang/OTP - of course your application needs to manage state, but it's well contained and well managed, avoiding a lot of common pitfalls.
In the Haskell world, folks have solutions to both of these problems:
The "large-object problem" can be tackled in a principled fashion using strict state threads (aka the ST monad: https://wiki.haskell.org/Monad/ST) or using vanilla mutable (IORef) references.
The "parent-child problem" is well-addressed by lenses, also known as functional references. They are basically composable getters and setters that allow you to read or update deep into nested structures.
You mean, Haskell developers ditch the functional idiom and use a more imperative one when they need it for performance? And yes, they do, and it works nicely. But it's not solving any problem with the functional paradigm.
Anyway, none of them is a problem with the semantics of FP. They are a problem of insufficient optimization. So they will probably get solved at some point.
ST is not 'imperative'. The monadic interface can look imperative sure, but then you can also use Applicative and friends and that's back to being functional. Of course, I prefer to think of what you call 'imperative' programming as function composition where >>= is the reverse of the 'normal' composition operator. Indeed, sequential imperative commands and function composition are isomorphic.
Hum... You declare an state and go modifying it with an action after another. Looks quite imperative to me. The fact that it returns an interpreter instead of values is meaningless if it doesn't change the way you think about the program.
If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the language even has specialized syntax to push people into reading the former, and anything minimally complex all but requires it.
travisathougies is not alone on that. Every one of us functional programmers worth their salt will consider a sequence of transformations from one state to the next as a functional program, as long as there are no side effects outside the current function that may transform state in ways that aren't declared in the types of the input and return values (which would break the referential transparency).
Functional Reactive programming (i.e. combining functions over streams of mutating objects) is essentially that, and it's a pure functional paradigm, quite popular in front-end web development (and I hear it's even creeping its way into the back-end).
Here is an STM function: orElse :: STM a -> STM a -> STM a
It returns the first argument if there isn't any synchronicity problem, or the second if some other execution line conflicts with the first.
What exactly do you mean by "same input -> same output" and how exactly does a programmer thinks about that function on this way when composing it into an STM interpreter?
I was referring to the ST monad which bts and travisathougies were talking about, not STM.
I mean that when you run ST code twice with the same input, you will get the same output. E.g., if I write (runST f) + (runST f), that's the same as 2 * (runST f), etc.
As for thinking, it means I don't use step-through debuggers ever, because I don't need the whole program to be in a certain state to watch what happens. I just grab the function, grab the input, and run it in isolation.
I think you should give the guy above the benefit of the doubt and restrict yourself to ST. IO and STM are different beasts, and still they're not imperative. The issue with IO and STM is global state. Mutation of global state can be done imperatively, as many imperative languages do. It can also be done functionally using monads to hide the affine types in a nice wrapper class in the absence of proper affine types or using proper affine type systems. Haskell choose the former. Other languages, like clean, choose the latter.
Same input -> same output is a nice property of referential integrity, which is a common thing we have in functional languages, but it is actually not due to the functional nature. Imperative languages can trivially be made to have this property by disallowing mutation of variables not in the immediate scope and restrict IO side effects (and maybe a few other straightforwards restrictions depending on the language in question).
With that out of the way. Same input -> same output holds for `orElse :: STM a -> STM a -> STM a`. However, you really have to expand out the types.
So, `orElse` should behave the same as a function with this type:
> (State# RealWorld -> (# State# RealWorld, a #)) -> (State# RealWorld -> (# State# RealWorld, a #)) -> State# RealWorld -> (# State# RealWorld, a #)
Now, the definition of 'same input -> same output' is clear. Assuming the global state (State# RealWorld) is the same, then the output state will be the same. Actually, this is not a property of all languages, as most languages allow arbitrary side effects in any code. Haskell does not. This is the key property that makes STM easy in Haskell and difficult in other languages. Note that the 'State# RealWorld' is always handled linearly, so there is no possible way the same 'value' could be passed in twice. Again, hiding this behind a monad enforces that this value is handled linearly, since Haskell doesn't have linear types (or at least didn't when STM, ST, and IO were written).
I don't fully understand how parent-child problem is addressed by lenses. How does lens helps to address the problem that a reference update is akin to changes an external state?
My understanding is that lens helps to address the large-object problem.
You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. The approaches & data structures aren't always the same.
In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post.
There are many good resources on this. I've referenced a few below. Of course there are many more.
If you select the timestamp of a comment (also when you reply to it) you can favorite it. This is much cleaner than leaving scattered "to find them later" comments around this site (in fact, I'm pretty sure it was added precisely to avoid those kinds of comments). You can also favorite submissions themselves. Favorites can be found in your profile.
I was more talking about how you approach solving problems, not the execution model. You can still get tight imperative loops in FP, it's just approached differently than in a traditionally imperative language.
Everything is a tradeoff. FP gives you a lot of flexibility in how you trade space and time of the execution of your program. It's also not a magic wand, just a really powerful tool.
That's arguable, given that every (deterministic) imperative computation can be expressed as a pure functional program. "Imperative" is more of a viewpoint that the developer is using to understand the behavior of the computer, rather than a property of the machine itself.
A pure functional analysis will describe a computation on that "imperative" architecture as an inmutable, monotonic sequence of all the states that the CPU goes through over time; or maybe, if you know enough PL theory, as a chain of rewritings of a program-long expression that is updated, one term at a time, when each expression is replaced by the result of a function as it consumes its input parameters.
And no viewpoint is inherently better than the other (except that the functional version can be analyzed in a natural way with mathematical tools, which is often difficult with the imperative description).
How do you define "imperative" in a way that precludes a functional description of your definition? I'd say that if you're able to do that, you'd have found a contradiction in Turing completeness and win you a Turing award.
Just because every program in C is also expressable in Haskell does not mean that C is Haskell or that C is a functional programming language.
The same is true of CPUs, which at their base level execute instructions line-by-line to move and load things in and out of stateful registers as well as doing simple mathematics.
Not going to keep arguing, as I can see from your other comments that you are going to try to hold this line, and also your reasoning doesn't really make sense.
Everyone has heard of Turing completeness. It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.
> It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.
No, it means that every computable program or device can be described through functional semantics, and therefore that very same program running on that same hardware can be described mathematically with them (not an 'equivalent' program, but the same program with the same runtime behaviour, just described in low level with a different format).
That's a core principle of computer science that predates computers themselves, and people arguing about the benefits of the imperative style tend to be unaware of this fact, making their arguments look weak.
You're definitely stretching here. I could just as easily argue that "all of main memory" is the output of any function. Therefore every function is a pure function, and C is a function language. Using your definition, the concept of functional programming is meaningless.
Main memory is state. Registers and cache are state. The entire purpose of the CPU is to mutate state.
No, I don't believe you could argue C is purely functional by framing memory as the output of the function because C doesn't treat it as such. Memory in C can be changed even if it is not listed in the inputs or outputs of the function.
He's not really stretching the definition, that's just the lens through which FP looks at the world.
Of course there is state. FP doesn't prohibit state, it just makes it explicit and referentially transparent. But this is in the semantics, not the execution model of the program.
> Memory in C can be changed even if it is not listed in the inputs or outputs of the function.
If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'.
If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you can't make that leap for assembly.
It's not syntax, it is semantics. There is a lot to programming language theory/design and this is all formalized. C does not have the semantics you are describing in the formal specifications (C99, etc..). Could they have developed a version of C with these semantics? Possibly. Rust was a step in that direction with it's borrow checker.
The computer is not an imperative machine. It's a physical machine that you describe with an imperative representation in your mind. Can you tell the difference, or are you unaware of the map-territory distinction going on?
Functional programmers are simply choosing to use a different style of map, but we both represent the same reality.
Nope, unless you do some serious contortions and basically say that the universe is a lambda calculus that operates on each moment in time to produce a new view of reality.
Computers that do anything useful have all manner of I/O. Highly oversimplified in modern architecture, but you can think of I/O as a bunch of memory cells that are DMA'd by external forces. Literally the exact opposite of functional, IO registers are the epitome of global mutable state. Then you have interrupts and the CPU operates in response to these events.
The viewpoint of "computers are mutable state" is inherently better because of parsimony - it requires less degrees of indirection to explain what is happening. Just because you could shoehorn reality into a physical model, does not make it equally valid. You basically need to break it down to the Schrodinger equation level to have a purely functional model when even idealized gates are involved because propagation delay impacts things like how fast you can DMA.
> Just because you could shoehorn reality into a physical model, does not make it equally valid.
Hey, physicists do it all the time. Having mathematical representations of how things work in the real world often turn out to give you complex devices that you wouldn't get by intuition alone. Thanks to doing it, we have Special Relativity and Schrodinger equations, that bring you advantages as GPS and insanely-high-speed networks.
There's nothing wrong with modelling interrupts and mutable state as static mathematical entities a.k.a. functions; and if you think it is, you don't know enough about functional programming - in fact, doing it allows for advanced tactics like automatic verification and very high scale generation of electronic devices.
Those less degrees of indirection may make it simple to build some kinds of programs; but they also introduce complexity in modelling the possible states of the system when you allow for arbitrary, unchecked side effects. So no, that representation is not inherently better - only most suited for some tasks than others; but the converse is also true for functional models of computation. If you think it is always better, it's because you're not taking all possible scenarios and utilities into account.
(Besides, as I already said elsewhere, "computers are mutable state" is not incompatible with functional representation; as mutable state can be represented with it). It seems that you're confusing mutable, wich is a property of computational devices, with 'imperative' which is a style of writing source code and defining relations between statements in your written program.
> Literally the exact opposite of functional, IO registers are the epitome of global mutable state.
Yup, you definitively don't know what functional programming is if you think you can't have global mutable state in it. In fact, every top-level Haskell program is defined as a global mutable IO monad...
No, that's the easy part. Computation with FP is very easy. The problems start the moment you have to do persistence and communication. Those aren't part of any pure functional paradigm.
I find this unconvincing. Electronic circuits are well described as a Cartesian Closed Category; and hence by lambda calculus (i.e. we can give semantics to functional programs by interpreting them as descriptions of circuits; as opposed to the "usual" interpretations of x86_64 machine code, or symbolic values, etc.)
Imperative systems are "fitting a square peg in a round hole" by introducing hacks like 'clock signals', 'pipeline flushes', etc.
The category with linear circuits as its morphisms, labelled sets of electronic terminals as its objects, and laying circuits in parallel as the monoidal product (which is the usual notion of the category of circuits; perhaps you have something more sophisticated in mind, but if so you should specify that) is not cartesian closed.
One of the many ways to demonstrate this: all linear circuits have duals (voltage <-> current, series <-> parallel, and so on), but in a cartesian closed category only the terminal object is dualizable.
What you're probably thinking of is the fact that this category is compact closed. The corresponding internal language is going to be some sort of process calculus (I think the pi calculus is too strong, but not sure), not the lambda calculus.
I think anybody who wants to understand Functional Programming should start with Lambda Calculus.
I highly recommend An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson.
You can then see how to express Functional Techniques in your language of choice (i.e. one you already know well eg; Functional Programming in C++ by Ivan Cukic) before learning a new Functional Language. This is to avoid the confusion in syntax/semantic expression of unfamiliar concepts which is a bit too much for a beginning student to handle simultaneously.
I've been coding in functional languages for 10 years, and they have problems, but these are not them.
The first problem is solved in every functional language I've used (clojure, F#, OCaml) by immutable data structures (aka purely functional data structures, which is also the name of the de facto book on the topic, which is excellent but also you don't need to know any of this to use them. [1]). I'm surprised to see this critique without a mention of this.
The second problem seems to be due to trying to do OO in FP. The thing is you don't have a glyph, you have a whole system which contains glyphs. So you can't do an update on a glyph because it won't update the system.
This is a common frustration when you're used to OO and can be really annoying in FP but it's also part of the design modelling that FP forces you to do: the problem was that he was modeling in the small and not the large.
The solution is not the 1, 2, or 3 from the article (1 and 2 are bad, 3 is not as bad but not FP), but is straightforward. When you want to update a glyph, you use a function like `updateGlyph(pathToGlyph, functionToExecuteOnGlyph)`. That's at the top-level, and it allows you compose your lower level `updateGlyph` functions.
I love the Purely Functional Data Structures book (so many cool data structures and ideas!) but does really "solve" it? For e.g. I double checked and the PFDS for an array (the author's example) would be a skew-binary random access list with O(log N) cost for random access, whereas an "imperative random access array" is O(1). Of course, the skew-binary random access list has persistence (you get to keep references to old versions of the data if you wish), while the "imperative random access array" does not, but the author's use-case sounds like he doesn't need persistence. So there is still some gap between this particular approach and the "non-functional" one.
Ultimately, is the Big O scale going to be larger for certain cases? Yes. Is it going to matter? Maybe. Maybe not. The point the original comment is making is that the author seems unaware these data structures even exist; the fact he was having O(n) operations and found them to be too slow tells us nothing about the reasonableness of the O(logn) option for his use case. He mentioned using a 30k byte array; that's the difference between 30k operations, and 15. Cutting it from 15 to 1 is probably not going to be that meaningful; certainly not compared with the first jump.
I wonder if the problem is that efficient persistent arrays aren't in racket's standard library (there are some third-party libraries implementing them though). Since racket isn't a "pure FP" language, they include cons-arrays and mutable vectors, and I imagine they felt that there wasn't a need to include efficient persistent arrays in addition to those.
Sort of - consider when Lisp originated. The heritage/age comes from a time before the research in persistent data structures happened, or even the issues with mutability were fully known. Because of that, idiomatic Lisp tends to be mutable, and no one is writing a new Lisp who isn't already familiar with another one. That's not to say immutability isn't worthwhile there, or that no Lisp standard libraries support it, but mutability tends to be the default assumption from what I've seen.
In addition, the O(logN) only comes into play if you are truly accessing only one item. If you're accessing more you are either reading the whole list (O(N) in total, O(1) per item), or a sublist (in which case it's O(logN) once to get/update the k item sublist and O(k) to operate on it).
If you are accessing just one item, the O(logN) cost is likely dominated by some other cost (eg the user clicking a button, making a web request, etc).
There are cost tradeoffs involved so you have to determine based on your application whether they solve the problem or not.
In a case like this you have several options:
1. Stick with mutation, reuse the original array and don't worry about being purely functional. This will probably be the optimal solution (vice explicitly creating a copy and mutating just the relevant bit). However, if you need the original for some reason then this is a non-solution.
2. Imitate the purely functional style with explicit copies, and accept the massive memory and performance costs that carries. You get to keep the cheaper read cost.
3. Use a better data structure, but losing (in particular) read performance, but largely mitigating the creation and "mutation" costs. (in quotes because the original is, from the perspective of the user, unchanged.)
Assuming you're in a language that doesn't provide (3) for free, and that (1) is a non-solution, you need to profile your system to decide between which of (2) and (3) is appropriate. With a large enough data structure or frequent enough updates, (3) is probably what you will want. If your data structure is small or updates are rare, then you can stick with (2). And if you have no idea which one will occur in the real-world (some users tend towards (2) being better and others towards (3)) you have to make an explicit choice on which one to provide better performance for.
The thing is, functional and imperative programming are mathematically equivalent - to the point that you can express imperative code in a pure functional language, if that's what you really need. If you want a O(1) random access in a functional language, you can formally define it; the problem with this is that you may end up embedding a whole computer in your program to do it, if your program heavily depends on side effects like those in the article. So, if you really need O(1) mutability for a large part of your program, maybe functional programming is not the tool for the job? Being too tied to a paradigm prevents you from finding the best tool at hand.
Functional programs are best used when you want referential transparency[1] as your problem domain benefits from it. If you want to represent mutable state in a functional, transparent way you use a subset of temporal logic[2] - each function has an additional state of the world input parameter, and return an additional updated state of the world value with all the mutated objects in it. The State monad is a version of this with increased legibility (as long as you don't combine many different sources of mutation).
If your needs for mutation are limited to a few objects in each module, you represent those as streams (the generalized version of futures which are able to be repeatedly updated with new values); a stream represents the history of all values that a mutable variable takes during the program execution. This is the basis of the functional reactive paradigm[3] on which modern web frameworks like React and Vue are converging, as it happens that modeling asynchronous state mutations of multiple loosely connected elements is easier in the functional paradigm than in the imperative.
If you used the State monad for the author's interpreter example, and you did it in Racket (your "state of the world" is a cons-list), what would be the run-time of the resulting interpreter? Similar question for streams (although I'm not that familiar with streams, so I don't know how they would apply here, or if they can be implemented without changes to the base language)
A stream is in essence the same as the Observer pattern; every function that depends on the values of a mutable variable must use accessor methods to extract the most recent value when they need it, or pass it 'hook' callback functions that represent the next steps to take on new values.
So, in principle, it should have the same performance as the 'Children can issue notification events' method in the article, since it's using what in essence is the same structure (just with a much nicer syntax, better adapted to functional programs).
The advantage of using functional streams instead of OOP observable callbacks is that it tends to be easier to write the program's large structure as compositions of functions over streams, i.e. it is easy to build modular functions without the bugs introduced by side effects.
I learned this style of programming through the online 'Paradigms'[1] course by Peter Van Roy, which you can take for free if you don't want credits. It uses the multi-paradigm language Oz to explain the essence of each paradigm and the differences between them. The course distills the primitives of different programming languages in terms of how they see state (see Van Roy's diagram in [2]), and how deciding to incorporate and combine some of those primitives and not others gives rise to the different programming styles. I found it enlightening, in the way that programmers' koans refer to.
I think the author somewhat explained why FP "suggests" that. In his explanation, it's because when you read tutorials that operate on "numbers and strings and simple lists" (as the author puts it), you do create and destroy those structures willy-nilly.
So when you operate on a large array (as in his example), a natural approach is to also create and destroy it.
Of course after you gain experience you learn not to do that, and techniques that let you not do that, but I don't think he is missing the point.
1) Uncle Bob's "perpetual state of immaturity" [1]
2) Non-FP languages and "hybrid" languages do a bad enough job of FP to stop people from seeking out more. E.g.
FP lang: Doesn't have null. Uses Maybe in the rare cases its useful. The benefit is not having null.
Imp lang: Keeps null. Adds Optional so now there's two ways not to have a value.
FP lang: Functions are lambdas are first class.
Imp lang: Separate Function object. Lambdas can't throw checked exceptions or update variables in the method's scope.
FP lang: Understands when mutation can and cannot happen. Can share data and fuse code efficiently.
Imp lang: Cannot assume underlying data doesn't change. Programmer needs to make defensive copies.
These problems have lots of other well-known solutions.
For large objects: Persistent data structures with path-copying. Batching small mutations (and using mutation internally in a way that doesn’t leak out). Using the type system somehow to distinguish cases where copying is not necessary (experimental in certain new languages). Structuring your program around a “data store” that is mutable.
For the “references” problem: Explicit references, like by ID. Or mutable “atoms” as in Clojure, which are maybe sort of like the “mediators” in the article.
Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem.
Yes, you aren't constructing an entirely new 30k byte array on each mutation. But you are still adding a lot of overhead to your program.
> Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence.
Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of memory.
> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks.
This is not. The whole point of immutable data structures and concurrency is that iterating over them does not require any locks because the structure won't change! So concurrent reads require absolutely no new code and certainly no locks. For concurrent writes, the usual strategy is a single CAS-like operation at the top-level to swap out the old immutable structure for a new one (e.g. Clojure atoms, Java AtomicReferences, Haskell IORefs, etc.). But that's a single thing for the whole structure, not every level.
In general concurrent update in the functional programming world is handled by CAS not locks.
Not necessarily. Depends on the underlying hardware implementation (with different answers for e.g. x86 vs ARM) since software CAS usually is implemented as a single CPU instruction.
This is also stretching the definition of "lock" quite a bit because usually CAS is used to implement lock-free and wait-free concurrency.
But regardless at most, even in hardware, it's a single top-level lock, and sometimes not even that. Not one along every level of a data structure.
> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks.
Um, what?
Persistent data structures don't require locks at all (because they're immutable), in fact using them in a multithreaded way is 100% safe and thus much easier than their mutable (and ordinarily more efficient) counterparts.
atoms are containers that require no coordination so its a simple Compare and swap. There are Refs that require transactions and change of multiple Refs is coordinated in these transactions. WIth that Clojure has an implementation of Software Transaction Memory.
I really enjoyed this presentation on how roc-lang is being designed to handle optimization using opportunistic in-place mutation: https://yewtu.be/watch?v=vzfy4EKwG_Y&t=1328.
Persistent data structures are very hard. It's basically impossible to cleanly combine them. E.g. if you have an immutable hashtable that contains immutable lists, and you want to modify a list - how do you know if the inner list changed or not (you don't want to be creating new hashtables if the elements don't change).
> you want to modify a list - how do you know if the inner list changed or not
You know for sure that inner list did _not_ change, because it is immutable.
Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?
No, I mean "update" in the persistent sense - create a new list, with some (or none) elements changed/added/removed.
e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap.
Obviously you'd use something like List.filter for the inner operation, but most functional programming languages give you no indication whether the result of filter is the same list (i.e. element is not present) or a new list (i.e. some elements were removed).
So how do you know if you create a new hashtable or return the old one? One solution is complex, the other is wasteful.
Isn't the idea of persistent data structures, that they may be more expensive than their imperative versions, but try to reduce the expense to a minimum? So by using a persistent data structure, one should already have taken that potential additional expense into consideration. The wasteful solution should not be that much more wasteful, if we assume, that there is an OK-performing persistent data structure for the use-case. Otherwise I guess one should not choose a persistent data structure. But then you run into problems, when you want to make use of multiple cores to throw at the problem.
No language will tell you at compile time whether an arbitrary list filter operation will have an effect or not. If it can, it's because the list filter isn't arbitrary, it's probably always a no-op.
The generalisation is that you have some type parent with a way to select a type child, plus a function that modifies a child, you want to lift your child -> child function to a parent -> parent function.
Optics help a lot with this class of problem.
Because you're in the world of persistent data structures, and you're doing a modify operation, there is no avoiding the 'modify hashtable' part of 'modify an element within a hashtable'. You always create a 'new' hashtable.
If it's common that your update operation has no effect it may be worth switching to a function like child -> Modified child for Modified a = NoOp | Mutated a, so the hashtable modify function can determine if it can skip its own update. A list filter is a trivial thing to write, and one that can return NoOp if no elements are filtered is no less efficient.
This only works if you know what to edit up-front.
If you're processing a tree-like structure via recursion (e.g. type-checking an AST implemented with persistent immutable structures in a compiler) it's no longer easy.
I think most persistent data structures would (for most common operations) return exactly themselves in case when no modification happened. So you can very cheaply compare for equality, and that would either resolve to simple one-op comparison of references (to see if they are equal or not), or, in the worst case, comparison of some minor amount of diverging sub-elements (since persistent data structures do extensive structural sharing by definition).
In this sense, linked list is a “bad” persistent collection for your use case, but a persistent set instead would work wonderfully — if nothing changed, you’d get the same reference to a collection as input.
I am pretty sure it either would work this way, or is very easy to optimize for this use case, in Clojure.
In FP I think composability and interchangeability of these higher order functions help, in case the supplied filter did not work like you want: You could write your own filter function variant that guarantees to return the same list if the predicate function returned true for each element.
I can't stand the standard update-based interface of persistent data structures either. https://lib.rs/crates/im wraps persistent structures in a standard vector interface, with instant clones (only copying a pointer to refcounted data) but slower assignments (which may copy data internally if other references exist), which is effectively equivalent to CoW. A persistent update is instead written as a clone followed by in-place assignment, and you can mutate in-place (which copies if there are other references to the data being modified). The nice part is that only IndexMut detaches the underlying data from other references.
I haven't used this crate yet, but if I have a need for persistent data structures I'd definitely try this since it's more accessible.
I think a lot of the pain in Scala/Rust etc immutable data structures comes down to static typing. In Clojure for instance you can very ergonomically do deeply nested persistent updates.
In Haskell you can you Lenses to easily manipulate sub-trees, individual values, or a selection of values in tree like data structures. It is very powerful.
Glad to see Cunningham’s Law working its magic. The article was a good read, and the HN comments section has a lot of good alternative solutions to the proposed problems.
Common Lisp solves the big structure problem using "setf" form. It also generally has both destructive/inplace and nondestructive structure manipulation versions of practically all functions in standard library.
It solves parent-child problem by having symbols as built-in data type. They can be used exactly as the "mutable mediator" describes. And beyond, such as you can generate a code that uses these symbols and have it natively compiled - at runtime.
Have not got the time to read this but. Let me guess. Another programmer in a functional programming language realizing that the state is all over the place and gets copied around but still is so importantly immutable.
That, and the comments in this thread reminding us that you have powerful tools in pure functional languages to represent state and handle those pesky side effects causing the bugs that plague imperative programmers' nightmares.
Nothing prevents you from doing pure functions in other langs. Fact is that it is standard today. The imperative programming model and the core problem with functional programming is much the same. The only difference is that you have a copy of the state in functional programming. The “real” state is still all over the place. That is why any sane business avoids functional langs except for areas were functional langs shine.
> The only difference is that you have a copy of the state in functional programming. The “real” state is still all over the place.
Not necessarily. You can have a reference to state, with no need to copy it; and a single structure containing all of the 'real' program state in one place, neatly referenced from a central point; destroying (i.e. liberating) the old values no longer being used. Same as you would do in an imperative garbage-collected program.
Imperative programs have state all over the place because they sweep it under the carpet of the runtime engine instead of fully embracing it and referencing it at all times, but doing this doesn't make state any more 'real'.
> That is why any sane business avoids functional langs except for areas were functional langs shine.
Yeah, probably. The problem is that sane business should also be avoiding imperative programs except for areas where they shine (namely complex world simulations and low-level access to embedded devices and OS modules), and they aren't doing because of industry inertia.
The mutable cell is one of the most advanced, complex and dangerous features of programming languages, and yet we introduce them to students on their very first lessons on their first week, without even a warning, making them think that using them all over the place is just how things should be done. Many junior developers will never learn to properly handle state other than 'don't use global variables'. This is not the proper way to run an engineering industry.
Thankfully, the industry is finally catching up to functional ways of handling state where it makes more sense, specially in networked asynchronous computation (the web and the cloud), where imperative code for asynchronous coordination is a nightmare; it's one of the areas where functional and agent-based state management shines, seeing updates in the form of promises and streams, not as mutable cells that may be changed at any time by anyone with access to them
> Consistent with my loyalty to the functional-programming idiom, I designed my initial bf implementation so that each instruction would copy the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would eventually be garbage-collected).
> Did this implementation work? Yes. Did it run fast? No. It was glacial. After noodling with the code for a while, I had my galaxy-brain moment: maybe the incessant duplication and deletion of 30K data arrays had something to do with it?
I thought OCaml handled this problem with copy-on-write and/or fancy pointer math. Is there more to it?
These are a little slower than conventional data structures (e.g. Java Collections) but are much more efficient than copying the whole structure every time you want to "change" it. The garbage collector picks up behind you so you're not wasting unbounded space on unreachable versions of the data structures.
Particularly the "parent-child" example feels like a non issue to me. You probably want to keep multiple versions of a glyph anyway to support things like undo, in which case explicit parent update is a requirement, not an annoyance. No reason you can't have both:
I think the crux is that any complex data structure f1 using glyphs would not need to be updated explicitly in an imperative program through a function like updateFontInGlyph; the runtime would do it as part of its semantics. Of course that's a double-edged sword, as you may get undesired side effects as well as the desired ones like this.
There are ways to achieve such "automatic updating" of items in a functional data structure, but you need to build them explicitly instead of relying on the runtime, which gives you more responsibility but also more control. The most direct approach as compared to imperative code would be to build the data structure on top of mutable state-based streams, though there are other possibilities like monotonic or immutable structures.
I believe mutable data-structures per se are not a bad thing. What is bad is Unobservable State Mutation.
When you assign a field into a data-structure it is bad because later on you will see the changed data-structure and try to use it but it has a wrong value which causes an error in your program - maybe not a crash just an error in the output. And then it's really hard to say what caused that error because you have no visibility into who or where did that erroneous assignment happen.
If instead you could forbid direct assignments and could write a "watcher" (a.k.a "setter") for all data-modifications, you could observe how your program-state evolves during its execution, and you could write assertions that prevent wrong type of data-manipulation from happening.
One such language is Smalltalk. You can only modify data by sending a "message" to an object to be modified, and the object can only respond by executing one of its methods. You can then write assertions in those methods to halt in debugger or write to console if you see the program write a specific value or type of value into your data-structure.
Even on the rather primitive level of Arrays you could easily modify their #at:put: -method in Smalltalk and halt or log the stack-trace if somebody tries to store the number 42 into the array. :-)
In the end the problem is understanding what your program does in terms of its state, how the state evolves. Why? Because: Modifying state in essence modifies your program. And to understand your program you must understand all evolving versions of it. Like, if you want to understand a 'caterpillar' you must also understand its next mutated state 'butterfly'.
FP makes it easier to understand the state-evolution because new state is just the result of some calculation which is easy (?) to understand by understanding each "pure" function in your program and reasoning what their combined result is.
But if you can understand the state-evolution of your program by imperative means that is fine too. That is why many suggest using a database to keep the state. A database is mutable by definition. But it makes it easy to observe how your state evolves by observing the UPDATE and DELETE and INSERT calls made into your database.
216 comments
[ 1.3 ms ] story [ 269 ms ] threadIn functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program.
This is somewhat dual to imperative programming, and is kind of a shift of the frame of reference. We could make an analogy with an assembly line in a factory. Imperative programming is like looking standing at the factory floor, every machine (procedure) receives a thing (input), does something with it, and outputs it. Functional programming is like being together with the thing as it is manipulated through the factory, in its own frame of reference. So instead of passing the thing (data) around, you see passing of the machinery that modifies that thing (functions), in the opposite direction.
Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution?
(Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)
My first thought is to model a cycle of the interpreter as a function of old state into new state.
I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data.
Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it.
Disclaimer: Am more Clojure than Haskell person.
When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluate the application at some point. The go-to technique is to use Normalization by Evaluation [0], where you convert the AST version of a function in the interpreted language to an actual function in the host language, and piggyback off the host language's (presumably very fast) function application.
[0]: https://en.wikipedia.org/wiki/Normalisation_by_evaluation
(Of course you can only access the actual local state and not do I/O or anything like that.)
I was involved with one that wasn't really demanding in terms of computation, but was distributed in a way that required a lot of speculation and rollbacks. The functional approach was pretty sweet.
Highest speed bytecode interpreter is actually one of the few loops where I prefer assembly to C, as the instruction mix, branch prediction and even the use of stack can be weird from the PoV of a modern optimizing compiler.
reading lisp in small pieces, the author migrates interpreters from naive recursive eval to bytecode. It felt there was an underlying model to extract.
An example of what parent was talking about is instead of looking over a list 10 times calling different functions that build a new result list each time, you compose those inti one big function that visits each element once.
A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write
You'll map over a list and add one to every element. this allocates a whole new list where all the elements are increased by one [0]. Now let's say we take the output of that map and map over it again, but this time we multiply every element by two: Naively implemented that would copy allocate two lists, one where all the numbers are incremented and another where all the incremented numbers are multiplied by two. Any good dev will know that's performance poison. So the Haskell compiler implements "list fusion" – it sees that you don't use the intermediate list for anything, and rewrites your code so it's equivalent (in semantics and performance) to: (For the compiler devs in here, this optimization is commonly known as deforestation.) This leads to huge speedups in many cases. But there's a problem. If elsewhere you use the result of `map (\x -> x+1) mylist` for anything besides mapping over it exactly once, this optimization is impossible! So list fusion has a reputation for being fragile – the compiler has to know with 100% certainty that you aren't going to use the list for anything else, and sometimes innocent-seeming changes (like moving the intermediate map into another module) can break it.The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you. The compiler is still on the hook for doing the analysis of what's used once and what's used multiple times, but now the programmer and the compiler can be guaranteed to be on the same page.
As for the other issue mentioned in the original post, of modifying a subelement of a tree: this is a well-known problem and there are many solutions. If the tree is only used once, the same optimization as list fusion can be applied to mutate the list in place (although the "you must use the value only once" restriction doesn't help quite as much as you'd think it would). The more common solution, that doesn't depend on compiler optimization at all, is to use a data structure that supports this efficiently. For example, if you have a tree and you want to change one leaf on the tree, the only thing you really need to copy is the part of the tree that's actually different now - for the unchanged branches, the new tree just has a pointer to branches of the old tree, so they can be (and are) reused without copying. That's why it's very common to see maps implemented in functional languages using trees, instead of hashmaps. With a hashmap, it's much harder to get around the need to copy the whole thing when you just want to change one part.
[0]: Well, it might do that that once it gets around to it, laziness etc., but let's ignore that for now.
I suspect the contortions required to fit your code into that affine type style will likely lead to code that is just as hard to understand and maintain as the equivalent imperative code (though with better static checking, which might be nice).
One tidbit you might find interesting. Linear logic requires you use the value exactly once, but if you relax that requirement to "once or zero times" you get affine logic. (Values that don't have the any restriction on how much you can use them are called "exponentials".) With both linear and affine logic, you can pass an exponential to a function that's linear or affine in its argument – the only requirement is that the function uses the value in a linear or affine way. That's not quite the same as what Rust does, which I do find a bit annoying. What rust does is called "uniquenes typing", where a function can always do whatever it wants with any values it gets, but it can mark its parameters as "unique" and the caller has to make sure that any value passed as a parameter to that function is never used anywhere else. This is arguably the more useful of the two, because it means that you can mutate any argument marked as unique and no one can tell, but if you design a language around that you get Rust and I find Rust a bit less pleasant to program in than Haskell.
you mean the compiler, right?
This still only works if a child has one / a known-ahead-of-time number of parents. If you need to update an object that N objects point to, you need to update all N references.
The very concept of n objects pointing to the same, commonly mutated data is something that can be adressed easily by having that data contained by a parent structure. Since functional programs don't think in terms of "methods" within each object trying to access data, but in terms of external function manipulating all the data you need, the only change is the way you'll pass your data to your functions.
OCaml does state without monads the way it does for a reason, because working with monads is a massive headache.
There is no such thing as "monadic programing", even in Haskell. The thing making haskellers harp about monads is that the std lib went a bit far in making sure that every fitting data structure implements the monad interface, which includes IO.
The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary.
Which hints at my own opinion on how to deal with this Gordian knot: just acknowledge that there is no universally best programming paradigm. Some problems are, as a practical matter, best modeled in an imperative manner. That's fine. And I don't think it should be personally threatening to us fans of functional programming. John Backus openly discussed it in the paper where he originally proposed the paradigm, and I personally prefer, for moral reasons, his suggestion for how to solve it. In a world where everyone's trying to build the best spork, I think I'd rather have one good spoon and one good fork.
You use special data structures to deal with that. There's a great book about them, "Purely Functional Data Structures", by Jeff Okasaki. You generally don't get O(1) update like for traditional arrays, but you can usually get O(log n), like you would get for a database table with B-tree indexes.
Naive implementations will always, by definition, not be great. But instead of spending the time, energy, and money on crafting a custom solution each time, use off-the-shelf libraries that do the job. DataScript, Storm, etc. are great for this.
Have you considered... not doing that?
I simply can not apprehend the mindset that goes:
The paradigm has to be good. It just has to! Even if it hurts! Even if I'm really not enjoying using it! Even if it's murdering my runtime and killing my performance and I'm in a language where functions take quite a lot of text rather than \x -> x + 1! Even if my code is hard to read and hard to abstract and hard to refactor. Even if the foreign paradigm is critically based on pervasive laziness my language doesn't have! Or some other foundation my current language totally lacks! Gosh darn it, I'm going to use this paradigm in this code if it kills me! Because it was so much fun... over there.I'm not saying that it isn't sometimes useful to borrow paradigms in certain places even in languages that don't support it. When it doesn't hurt like this, by all means use it as you like. What I don't understand is this constant, if not growing, stream of posts about "my gosh, my forced FP programming in this not-FP language is kinda painful here... grimaces yup, it's pretty painful all right... grits teeth yup, this is really hurting me and making me really angry and isn't fun at all... but I'm so glad I'm using this style that is making things hard and hurting me and making me angry, wouldn't dream of doing anything else!"
I know Haskell. There are many lessons I've taken from Haskell and applied to other languages, like the virtue of very strongly separating IO code from logic, the virtues of taking extra steps to provide and use composability in your APIs, the virtues of certain things being immutable data. But taking these lessons from functional programming languages shouldn't mean you ape the surface solutions functional programming uses; you should be thinking about how to idiomatically bring the target virtues into the other languages you use. There will be compromises, but sometimes there will also be things the current language does better than Haskell. (Really quite a lot of things. Haskell's great but there's many reasons it hasn't conquered the world.) You shouldn't be so focused on importing the foreign paradigm that you completely throw away the virtues of the environment you're in.
I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages. It's an incredibly aggravating place to try to be. The (near) union, applied with the wisdom gleaned from both camps, is much more fun.
Why do you want to climb that mountain? Because it’s there.
But could y'all be more clear about labeling at such? You're fooling young programmers into thinking this is a good engineering idea. In engineering, we do not climb mountains just because they are there. Quite the opposite.
I’m not the author. But that’s one explanation.
This goes back to the old “this is Hacker News” explanation. Some things are just implemented for the heck of it. Some things are just done according to a certain paradigm for the heck of it. Or in order to see how far you can go.
Why not see how far you can go with pure FP before it breaks down? Or you have to make compromises.
And not everything on this site is about “good engineering practices”. (Not that I would file your original, mocking comment under such a professional label, either.)
On a second skim though the submission is more naive than I would have expected from a Racket programmer. Using imperative datastructures like arrays (contiguous chunks of memory) and then copying for every action is not really recommended. You should use purely functional datastructures if you really want to not do destructive updates.
* Algebraic data types
* Pattern matching (with exhaustiveness)
* Lambdas / Closures
* Type inference
I mean, Lambdas came from the Lambda calculus which predates FP. Type inferencing was also formulated as part of typed Lambda calculus. Pattern matching definitely came about prior to FP; SNOBOL (and its predecessor COMIT) is probably the first language that really made it 'a thing'.
Very few things FP uses came from FP; they came from underlying Math and CS, and are themselves specific formulations and implementations that fit within the context of broader well understood concepts.
I love functional idioms as well, but you have to know the cost of those idioms in a non-functional language. The first thing I did when I had to learn go was determine if I could use functional idioms (map, fold, etc.) and did some research and testing and found that, no, functional idioms are a really bad idea in go. It just isn't meant to be used that way.
For the record, I had to learn go because the team I joined used it.
Despite what it may superficially sounds like, it's an attempt to reach out and help people. If it hurts, you know, think about it. Maybe don't do something that hurts so much because it "must" be good.
FP techniques in imperative languages is a tool. A good tool sometimes. But it shouldn't be an aspiration.
>I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages
Because it actually works pretty well? The vast majority of programming languages today are multi-paradigm for a reason. In fact, almost all functional programming languages (Lisp, Scheme, Racket, Clojure, (S)ML, OCaml, F#, Scala) are multi-paradigm. Haskell is really the odd one among functional programming languages. The same applies to lazyness by the way, to claim that functional programming is "critically based on pervasive laziness" is simply wrong.
The idea that people use FP in a language like e.g. JS only because of an ideology driven obsession and that they constantly have to fight against the language just doesn't bear out in reality.
I'm talking about forcing it in when it hurts specifically.
It occurs to me that I may have accidentally answered myself at the end, when I referred to the concept of union vs. intersection. When you bring in helpful angles on your current paradigm from light cast by other paradigms, that's helpful. You're expanding your working set of options.
But when you get a bit of a good taste of those other paradigms, and then declare this is always the right way to do it, it may feel like you're expanding your paradigms, but now you're not. When you force sum types into a language that doesn't support them because they're just always the right answer, when you force lots of maps & filters in a language that can't do fusion and function calls are kind of expensive, when you force an algorithm in that depends on laziness to work, and so on, you are no longer working in a sort of union of paradigms. You're working in the intersection.
And that intersection sucks. A worst-of-both-worlds situation for sure.
You can tell, by the way people trying this are constantly screaming in pain about it.
When it hurts... stop.
Just stopping anytime you struggle is precisely how you learn nothing at all
I'm pretty sure most of the complaints are generally of the "This FP thing would work well here, but the language is unfortunately not quite there" nature rather than "I will try to implement profunctor optics in C no matter the cost" square peg in round hole crazyness.
>when you force lots of maps & filters in a language that can't do fusion and function calls are kind of expensive
I think that's perfect example to show that it's really about degrees, because fusion is really a Haskell thing. Sure, it's a nice-to-have, but it's definitely not essential to functional programming.
And when people want sum types (which aren't even really FP, ALGOL had them first!), it's often because the idiomatic alternative just kind of sucks for what they're doing. Trying to "implement" sum types in a language without support is nonsensical, but complaints about lacking them are pretty understandable I think.
If not it would be nice to find discussion about when it is and when not and why? What is Haskell NOT the best solution for?
The hard part is understanding how you should model your problem. I found that you could classify problems into two big groups: pipelines like compilers or web services where you get an input, do some processing and produce an output, and graph problems like GUI applications where the system is a living thing and events change how components should behave. The first group is easy, the second not so much. Excel is the best example of this kind of system: an user describes relationships between cells and lets the runtime perform the appropriate side effects. Ideally we would be able to write arbitrary programs using this same model.
Haskell main program in essence runs a big loop until it decides the program should exit. In Haskell syntax the loop is coded as a call to a tail-recursive function, which on a real hardware of course needs to be translated to do iteration. At the end of each loop it sets the new calculated value of the new state to be used during the next loop.
Using tail-recursion optimization it looks like our whole program executes a single top-level function-call of a recursive function, that is how you code it in Haskell.
This is great but somehow it feels like a trick. It is actually still doing iteration and state mutation internally while running. You could program that in an imperative language writing a top-level loop and iterating over it and modifying the statefull variables at the end of each loop.
And what happens if you cannot write your program as tail-recursive function? What if the problem domain requires you to use general recursion, which can not be optimized away like tail-recursion can?
When it comes to "executing" your program, a runtime (like GHC's runtime) takes your program which is a value and actually performs the requested actions, dealing with mutation, loops, jumps, etc. This is a hack just as much as any other language dealing with variables instead of the stack, heap or registries directly.
In case you're interested, this idea of using some kind of interpreter which loops over your program and performs mutations and side effects is very popular in Scala: libraries like Cats and ZIO do this, allowing you to effectively get Haskell's IO. As far as I know, tail-recursion is not really needed for this, but when implemented on the runtime it allows the end user to write loops using recursion without blowing up the stack.
The program must keep the previous state somewhere and then modify it based on the player's inputs and again store that new state somewhere somehow so it is remembered when next input comes. If loops which keep and modify state are not allowed, then I don't see how it could be done without tail-recursive functions.
The closest mainstream project to FRP is Angular using RxJS exclusively. You define how each component interacts with each other, and then you delegate to a runtime to actually perform the side effects (change the DOM in this case). Solutions like React + Redux/Elm involve a lot of plumbing that's not relevant to the issue: I just want to define relationships between components, not manually tread changes across a big state tree.
For the parent-child problem, typed handles, continuation-based state propagation, and reifying state updates for a declarative interpreter may be used.
Monads and effects are common in strongly typed functional languages, but have less bearing on lisp, which usually embraces dynamism to some extent.
I'm not a Haskell programmer but I do know about monads and have heard of lenses.
The same holds true for large structure updates.
It does help, but it's still going to be significantly slower than just modifying a single record in a data structure. It is a still a problem that will be slowing down your program.
Either do a nice imperative for-loop as that is an excellent and imperative way of solving the problem (which I don't know what it is.)
Or solve it in any of the normal functional ways. Pick the style that you and your team likes.
That is, if you're trying to emulate sharing of mutable structures (i.e. pointers) in a functional language -- that is, reflecting changes to children across multiple parents -- model the pointers explicitly (as integer keys) and put the shared structures in a map, which is necessary to interpret a parent in full.
This seems to be what the article is getting at with its "mediator" concept, albeit in very abstract terms. The author seems to find this distasteful, wanting to "hide" these relationships, but I disagree -- the difference between value and reference semantics is very important; making the difference explicit is a good thing.
The "large-object problem" can be tackled in a principled fashion using strict state threads (aka the ST monad: https://wiki.haskell.org/Monad/ST) or using vanilla mutable (IORef) references.
The "parent-child problem" is well-addressed by lenses, also known as functional references. They are basically composable getters and setters that allow you to read or update deep into nested structures.
Anyway, none of them is a problem with the semantics of FP. They are a problem of insufficient optimization. So they will probably get solved at some point.
If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the language even has specialized syntax to push people into reading the former, and anything minimally complex all but requires it.
Functional Reactive programming (i.e. combining functions over streams of mutating objects) is essentially that, and it's a pure functional paradigm, quite popular in front-end web development (and I hear it's even creeping its way into the back-end).
Here is an STM function: orElse :: STM a -> STM a -> STM a
It returns the first argument if there isn't any synchronicity problem, or the second if some other execution line conflicts with the first.
What exactly do you mean by "same input -> same output" and how exactly does a programmer thinks about that function on this way when composing it into an STM interpreter?
I mean that when you run ST code twice with the same input, you will get the same output. E.g., if I write (runST f) + (runST f), that's the same as 2 * (runST f), etc.
As for thinking, it means I don't use step-through debuggers ever, because I don't need the whole program to be in a certain state to watch what happens. I just grab the function, grab the input, and run it in isolation.
None of what I said applies to ST.
Same input -> same output is a nice property of referential integrity, which is a common thing we have in functional languages, but it is actually not due to the functional nature. Imperative languages can trivially be made to have this property by disallowing mutation of variables not in the immediate scope and restrict IO side effects (and maybe a few other straightforwards restrictions depending on the language in question).
With that out of the way. Same input -> same output holds for `orElse :: STM a -> STM a -> STM a`. However, you really have to expand out the types.
Here is the definition of STM (from https://hackage.haskell.org/package/base-4.15.0.0/docs/GHC-C...):
> newtype STM = STM (State# RealWorld -> (# State# RealWorld, a #))
So, `orElse` should behave the same as a function with this type:
> (State# RealWorld -> (# State# RealWorld, a #)) -> (State# RealWorld -> (# State# RealWorld, a #)) -> State# RealWorld -> (# State# RealWorld, a #)
Now, the definition of 'same input -> same output' is clear. Assuming the global state (State# RealWorld) is the same, then the output state will be the same. Actually, this is not a property of all languages, as most languages allow arbitrary side effects in any code. Haskell does not. This is the key property that makes STM easy in Haskell and difficult in other languages. Note that the 'State# RealWorld' is always handled linearly, so there is no possible way the same 'value' could be passed in twice. Again, hiding this behind a monad enforces that this value is handled linearly, since Haskell doesn't have linear types (or at least didn't when STM, ST, and IO were written).
My understanding is that lens helps to address the large-object problem.
In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post.
There are many good resources on this. I've referenced a few below. Of course there are many more.
[1] https://www.amazon.com/Pearls-Functional-Algorithm-Design-Ri...
[2] https://www.amazon.com/Purely-Functional-Data-Structures-Oka...
[3] https://www.amazon.com/Algorithm-Design-Haskell-Richard-Bird...
[4] https://www.amazon.com/Structure-Interpretation-Computer-Pro...
This might be part of the problem with FP. Every popular CPU architecture is imperative.
Everything is a tradeoff. FP gives you a lot of flexibility in how you trade space and time of the execution of your program. It's also not a magic wand, just a really powerful tool.
That's arguable, given that every (deterministic) imperative computation can be expressed as a pure functional program. "Imperative" is more of a viewpoint that the developer is using to understand the behavior of the computer, rather than a property of the machine itself.
A pure functional analysis will describe a computation on that "imperative" architecture as an inmutable, monotonic sequence of all the states that the CPU goes through over time; or maybe, if you know enough PL theory, as a chain of rewritings of a program-long expression that is updated, one term at a time, when each expression is replaced by the result of a function as it consumes its input parameters.
And no viewpoint is inherently better than the other (except that the functional version can be analyzed in a natural way with mathematical tools, which is often difficult with the imperative description).
Just because both lambda calculus and assembly are Turing complete does not mean that CPU architecture isn't clearly imperative.
Also, this: https://news.ycombinator.com/item?id=30883863
The same is true of CPUs, which at their base level execute instructions line-by-line to move and load things in and out of stateful registers as well as doing simple mathematics.
Not going to keep arguing, as I can see from your other comments that you are going to try to hold this line, and also your reasoning doesn't really make sense.
Everyone has heard of Turing completeness. It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.
No, it means that every computable program or device can be described through functional semantics, and therefore that very same program running on that same hardware can be described mathematically with them (not an 'equivalent' program, but the same program with the same runtime behaviour, just described in low level with a different format).
That's a core principle of computer science that predates computers themselves, and people arguing about the benefits of the imperative style tend to be unaware of this fact, making their arguments look weak.
Main memory is state. Registers and cache are state. The entire purpose of the CPU is to mutate state.
He's not really stretching the definition, that's just the lens through which FP looks at the world.
Of course there is state. FP doesn't prohibit state, it just makes it explicit and referentially transparent. But this is in the semantics, not the execution model of the program.
If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'.
If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you can't make that leap for assembly.
Functional programmers are simply choosing to use a different style of map, but we both represent the same reality.
https://en.wikipedia.org/wiki/Imperative_programming
Computers that do anything useful have all manner of I/O. Highly oversimplified in modern architecture, but you can think of I/O as a bunch of memory cells that are DMA'd by external forces. Literally the exact opposite of functional, IO registers are the epitome of global mutable state. Then you have interrupts and the CPU operates in response to these events.
The viewpoint of "computers are mutable state" is inherently better because of parsimony - it requires less degrees of indirection to explain what is happening. Just because you could shoehorn reality into a physical model, does not make it equally valid. You basically need to break it down to the Schrodinger equation level to have a purely functional model when even idealized gates are involved because propagation delay impacts things like how fast you can DMA.
Hey, physicists do it all the time. Having mathematical representations of how things work in the real world often turn out to give you complex devices that you wouldn't get by intuition alone. Thanks to doing it, we have Special Relativity and Schrodinger equations, that bring you advantages as GPS and insanely-high-speed networks.
There's nothing wrong with modelling interrupts and mutable state as static mathematical entities a.k.a. functions; and if you think it is, you don't know enough about functional programming - in fact, doing it allows for advanced tactics like automatic verification and very high scale generation of electronic devices.
Those less degrees of indirection may make it simple to build some kinds of programs; but they also introduce complexity in modelling the possible states of the system when you allow for arbitrary, unchecked side effects. So no, that representation is not inherently better - only most suited for some tasks than others; but the converse is also true for functional models of computation. If you think it is always better, it's because you're not taking all possible scenarios and utilities into account.
(Besides, as I already said elsewhere, "computers are mutable state" is not incompatible with functional representation; as mutable state can be represented with it). It seems that you're confusing mutable, wich is a property of computational devices, with 'imperative' which is a style of writing source code and defining relations between statements in your written program.
> Literally the exact opposite of functional, IO registers are the epitome of global mutable state.
Yup, you definitively don't know what functional programming is if you think you can't have global mutable state in it. In fact, every top-level Haskell program is defined as a global mutable IO monad...
Imperative systems are "fitting a square peg in a round hole" by introducing hacks like 'clock signals', 'pipeline flushes', etc.
One of the many ways to demonstrate this: all linear circuits have duals (voltage <-> current, series <-> parallel, and so on), but in a cartesian closed category only the terminal object is dualizable.
What you're probably thinking of is the fact that this category is compact closed. The corresponding internal language is going to be some sort of process calculus (I think the pi calculus is too strong, but not sure), not the lambda calculus.
I highly recommend An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson.
You can then see how to express Functional Techniques in your language of choice (i.e. one you already know well eg; Functional Programming in C++ by Ivan Cukic) before learning a new Functional Language. This is to avoid the confusion in syntax/semantic expression of unfamiliar concepts which is a bit too much for a beginning student to handle simultaneously.
The first problem is solved in every functional language I've used (clojure, F#, OCaml) by immutable data structures (aka purely functional data structures, which is also the name of the de facto book on the topic, which is excellent but also you don't need to know any of this to use them. [1]). I'm surprised to see this critique without a mention of this.
The second problem seems to be due to trying to do OO in FP. The thing is you don't have a glyph, you have a whole system which contains glyphs. So you can't do an update on a glyph because it won't update the system.
This is a common frustration when you're used to OO and can be really annoying in FP but it's also part of the design modelling that FP forces you to do: the problem was that he was modeling in the small and not the large.
The solution is not the 1, 2, or 3 from the article (1 and 2 are bad, 3 is not as bad but not FP), but is straightforward. When you want to update a glyph, you use a function like `updateGlyph(pathToGlyph, functionToExecuteOnGlyph)`. That's at the top-level, and it allows you compose your lower level `updateGlyph` functions.
[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64...
Ultimately, is the Big O scale going to be larger for certain cases? Yes. Is it going to matter? Maybe. Maybe not. The point the original comment is making is that the author seems unaware these data structures even exist; the fact he was having O(n) operations and found them to be too slow tells us nothing about the reasonableness of the O(logn) option for his use case. He mentioned using a 30k byte array; that's the difference between 30k operations, and 15. Cutting it from 15 to 1 is probably not going to be that meaningful; certainly not compared with the first jump.
I wonder if the problem is that efficient persistent arrays aren't in racket's standard library (there are some third-party libraries implementing them though). Since racket isn't a "pure FP" language, they include cons-arrays and mutable vectors, and I imagine they felt that there wasn't a need to include efficient persistent arrays in addition to those.
If you are accessing just one item, the O(logN) cost is likely dominated by some other cost (eg the user clicking a button, making a web request, etc).
In a case like this you have several options:
1. Stick with mutation, reuse the original array and don't worry about being purely functional. This will probably be the optimal solution (vice explicitly creating a copy and mutating just the relevant bit). However, if you need the original for some reason then this is a non-solution.
2. Imitate the purely functional style with explicit copies, and accept the massive memory and performance costs that carries. You get to keep the cheaper read cost.
3. Use a better data structure, but losing (in particular) read performance, but largely mitigating the creation and "mutation" costs. (in quotes because the original is, from the perspective of the user, unchanged.)
Assuming you're in a language that doesn't provide (3) for free, and that (1) is a non-solution, you need to profile your system to decide between which of (2) and (3) is appropriate. With a large enough data structure or frequent enough updates, (3) is probably what you will want. If your data structure is small or updates are rare, then you can stick with (2). And if you have no idea which one will occur in the real-world (some users tend towards (2) being better and others towards (3)) you have to make an explicit choice on which one to provide better performance for.
Functional programs are best used when you want referential transparency[1] as your problem domain benefits from it. If you want to represent mutable state in a functional, transparent way you use a subset of temporal logic[2] - each function has an additional state of the world input parameter, and return an additional updated state of the world value with all the mutated objects in it. The State monad is a version of this with increased legibility (as long as you don't combine many different sources of mutation).
If your needs for mutation are limited to a few objects in each module, you represent those as streams (the generalized version of futures which are able to be repeatedly updated with new values); a stream represents the history of all values that a mutable variable takes during the program execution. This is the basis of the functional reactive paradigm[3] on which modern web frameworks like React and Vue are converging, as it happens that modeling asynchronous state mutations of multiple loosely connected elements is easier in the functional paradigm than in the imperative.
[1] https://en.wikipedia.org/wiki/Referential_transparency
[2] https://en.wikipedia.org/wiki/Temporal_logic
[3] https://en.wikipedia.org/wiki/Functional_reactive_programmin...
So, in principle, it should have the same performance as the 'Children can issue notification events' method in the article, since it's using what in essence is the same structure (just with a much nicer syntax, better adapted to functional programs).
The advantage of using functional streams instead of OOP observable callbacks is that it tends to be easier to write the program's large structure as compositions of functions over streams, i.e. it is easy to build modular functions without the bugs introduced by side effects.
I learned this style of programming through the online 'Paradigms'[1] course by Peter Van Roy, which you can take for free if you don't want credits. It uses the multi-paradigm language Oz to explain the essence of each paradigm and the differences between them. The course distills the primitives of different programming languages in terms of how they see state (see Van Roy's diagram in [2]), and how deciding to incorporate and combine some of those primitives and not others gives rise to the different programming styles. I found it enlightening, in the way that programmers' koans refer to.
[1] https://www.edx.org/es/course/paradigms-of-computer-programm...
[2] https://en.wikipedia.org/wiki/Programming_paradigm#Overview
* Use linear / affine / session types / move semantics
* Describe an interface, then weave side effects through it, such as the State Monad.
* Use lenses
It really saddens me that some people completely miss the point of what FP is about.
How did this happen?
So when you operate on a large array (as in his example), a natural approach is to also create and destroy it.
Of course after you gain experience you learn not to do that, and techniques that let you not do that, but I don't think he is missing the point.
1) Uncle Bob's "perpetual state of immaturity" [1]
2) Non-FP languages and "hybrid" languages do a bad enough job of FP to stop people from seeking out more. E.g.
FP lang: Doesn't have null. Uses Maybe in the rare cases its useful. The benefit is not having null. Imp lang: Keeps null. Adds Optional so now there's two ways not to have a value.
FP lang: Functions are lambdas are first class. Imp lang: Separate Function object. Lambdas can't throw checked exceptions or update variables in the method's scope.
FP lang: Understands when mutation can and cannot happen. Can share data and fuse code efficiently. Imp lang: Cannot assume underlying data doesn't change. Programmer needs to make defensive copies.
FP lang: map (+1) [1,2,3] Imp lang: Arrays.asList(1,2,3).stream().map(x -> x + 1).collect(Collectors.toList())
If I grew up with the kind of FP that made it into mainstream languages I'd probably be against it too.
[1] https://blog.cleancoder.com/uncle-bob/2014/06/20/MyLawn.html
For large objects: Persistent data structures with path-copying. Batching small mutations (and using mutation internally in a way that doesn’t leak out). Using the type system somehow to distinguish cases where copying is not necessary (experimental in certain new languages). Structuring your program around a “data store” that is mutable.
For the “references” problem: Explicit references, like by ID. Or mutable “atoms” as in Clojure, which are maybe sort of like the “mediators” in the article.
Yes, you aren't constructing an entirely new 30k byte array on each mutation. But you are still adding a lot of overhead to your program.
Depending on your definition of "way" this is true. A lot of persistent vector-like structures can have quite good performance, but if your runtime is dominated by iteration and random updating, you will still get a speed up by using raw arrays, i.e. guaranteed contiguous blocks of memory.
> This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks.
This is not. The whole point of immutable data structures and concurrency is that iterating over them does not require any locks because the structure won't change! So concurrent reads require absolutely no new code and certainly no locks. For concurrent writes, the usual strategy is a single CAS-like operation at the top-level to swap out the old immutable structure for a new one (e.g. Clojure atoms, Java AtomicReferences, Haskell IORefs, etc.). But that's a single thing for the whole structure, not every level.
In general concurrent update in the functional programming world is handled by CAS not locks.
This is also stretching the definition of "lock" quite a bit because usually CAS is used to implement lock-free and wait-free concurrency.
But regardless at most, even in hardware, it's a single top-level lock, and sometimes not even that. Not one along every level of a data structure.
Um, what?
Persistent data structures don't require locks at all (because they're immutable), in fact using them in a multithreaded way is 100% safe and thus much easier than their mutable (and ordinarily more efficient) counterparts.
They work in the small, but don't truly scale.
This is a vital question that virtually every programming language overlooks.
If you are using a mainstream language, you do not know if they were modified.
If you use a language which has a type system to segregate mutable operations from immutable operations, then you know if they were modified.
> They work in the small, but don't truly scale.
Go even bigger then. Work with the kind of data that won't fit in memory. Put your data on disk - you can't insert into the middle of a 1GB+ file.
You know for sure that inner list did _not_ change, because it is immutable.
Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?
e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap.
Obviously you'd use something like List.filter for the inner operation, but most functional programming languages give you no indication whether the result of filter is the same list (i.e. element is not present) or a new list (i.e. some elements were removed).
So how do you know if you create a new hashtable or return the old one? One solution is complex, the other is wasteful.
The generalisation is that you have some type parent with a way to select a type child, plus a function that modifies a child, you want to lift your child -> child function to a parent -> parent function.
Optics help a lot with this class of problem.
Because you're in the world of persistent data structures, and you're doing a modify operation, there is no avoiding the 'modify hashtable' part of 'modify an element within a hashtable'. You always create a 'new' hashtable.
If it's common that your update operation has no effect it may be worth switching to a function like child -> Modified child for Modified a = NoOp | Mutated a, so the hashtable modify function can determine if it can skip its own update. A list filter is a trivial thing to write, and one that can return NoOp if no elements are filtered is no less efficient.
If you're processing a tree-like structure via recursion (e.g. type-checking an AST implemented with persistent immutable structures in a compiler) it's no longer easy.
I think most persistent data structures would (for most common operations) return exactly themselves in case when no modification happened. So you can very cheaply compare for equality, and that would either resolve to simple one-op comparison of references (to see if they are equal or not), or, in the worst case, comparison of some minor amount of diverging sub-elements (since persistent data structures do extensive structural sharing by definition).
In this sense, linked list is a “bad” persistent collection for your use case, but a persistent set instead would work wonderfully — if nothing changed, you’d get the same reference to a collection as input.
I am pretty sure it either would work this way, or is very easy to optimize for this use case, in Clojure.
I haven't used this crate yet, but if I have a need for persistent data structures I'd definitely try this since it's more accessible.
It solves parent-child problem by having symbols as built-in data type. They can be used exactly as the "mutable mediator" describes. And beyond, such as you can generate a code that uses these symbols and have it natively compiled - at runtime.
http://pepijndevos.nl/2012/08/12/the-multiple-index-problem....
Not necessarily. You can have a reference to state, with no need to copy it; and a single structure containing all of the 'real' program state in one place, neatly referenced from a central point; destroying (i.e. liberating) the old values no longer being used. Same as you would do in an imperative garbage-collected program.
Imperative programs have state all over the place because they sweep it under the carpet of the runtime engine instead of fully embracing it and referencing it at all times, but doing this doesn't make state any more 'real'.
> That is why any sane business avoids functional langs except for areas were functional langs shine.
Yeah, probably. The problem is that sane business should also be avoiding imperative programs except for areas where they shine (namely complex world simulations and low-level access to embedded devices and OS modules), and they aren't doing because of industry inertia.
The mutable cell is one of the most advanced, complex and dangerous features of programming languages, and yet we introduce them to students on their very first lessons on their first week, without even a warning, making them think that using them all over the place is just how things should be done. Many junior developers will never learn to properly handle state other than 'don't use global variables'. This is not the proper way to run an engineering industry.
Thankfully, the industry is finally catching up to functional ways of handling state where it makes more sense, specially in networked asynchronous computation (the web and the cloud), where imperative code for asynchronous coordination is a nightmare; it's one of the areas where functional and agent-based state management shines, seeing updates in the form of promises and streams, not as mutable cells that may be changed at any time by anyone with access to them
This would be a fun task to attempt with the new linear features of Haskell https://hackage.haskell.org/package/linear-base-0.1.0/docs/D...
I thought OCaml handled this problem with copy-on-write and/or fancy pointer math. Is there more to it?
https://clojure.org/reference/data_structures
These are a little slower than conventional data structures (e.g. Java Collections) but are much more efficient than copying the whole structure every time you want to "change" it. The garbage collector picks up behind you so you're not wasting unbounded space on unreachable versions of the data structures.
There are ways to achieve such "automatic updating" of items in a functional data structure, but you need to build them explicitly instead of relying on the runtime, which gives you more responsibility but also more control. The most direct approach as compared to imperative code would be to build the data structure on top of mutable state-based streams, though there are other possibilities like monotonic or immutable structures.
https://blog.waleedkhan.name/monotonicity/
When you assign a field into a data-structure it is bad because later on you will see the changed data-structure and try to use it but it has a wrong value which causes an error in your program - maybe not a crash just an error in the output. And then it's really hard to say what caused that error because you have no visibility into who or where did that erroneous assignment happen.
If instead you could forbid direct assignments and could write a "watcher" (a.k.a "setter") for all data-modifications, you could observe how your program-state evolves during its execution, and you could write assertions that prevent wrong type of data-manipulation from happening.
One such language is Smalltalk. You can only modify data by sending a "message" to an object to be modified, and the object can only respond by executing one of its methods. You can then write assertions in those methods to halt in debugger or write to console if you see the program write a specific value or type of value into your data-structure.
Even on the rather primitive level of Arrays you could easily modify their #at:put: -method in Smalltalk and halt or log the stack-trace if somebody tries to store the number 42 into the array. :-)
In the end the problem is understanding what your program does in terms of its state, how the state evolves. Why? Because: Modifying state in essence modifies your program. And to understand your program you must understand all evolving versions of it. Like, if you want to understand a 'caterpillar' you must also understand its next mutated state 'butterfly'.
FP makes it easier to understand the state-evolution because new state is just the result of some calculation which is easy (?) to understand by understanding each "pure" function in your program and reasoning what their combined result is.
But if you can understand the state-evolution of your program by imperative means that is fine too. That is why many suggest using a database to keep the state. A database is mutable by definition. But it makes it easy to observe how your state evolves by observing the UPDATE and DELETE and INSERT calls made into your database.