Resolving the Time Paradox Implied by Functional Programs | Hacker News Reader

Resolving the Time Paradox Implied by Functional Programs

softwarefordays.com

27 pointsjbmilgrom22 comments

Even "fold : (state -> a -> state) -> state -> a list -> state" implies this resolution. The function is pure, but in some sense it assigns a "program state" to every element of the list. Having created a time evolution of the computation, we then essentially throw away all but the last. For optimisation reasons, of course, we don't actually generate the entire intermediate list of program states.

The fundamental problem is the opposite one: it's the world that throws away intermediate states, and that happens whether you want it to or not. Unfortunately for FP afficionados, physical reality runs with autocommit set to True.

> it's the world that throws away intermediate states, and that happens whether you want it to or not. Unfortunately for FP afficionados, physical reality runs with autocommit set to True.

This fact is unfortunate for OO aficionados who try to build programs by modelling the real world, because it leads them to build programs with the same problem. Whereas FP aficionados realise that even though there's no "undo" in the real world, we can enable it in our programs.

touché!

> physical reality runs with autocommit set to True

Only from the inside ;)

> We may attribute normal object-oriented semantics to the above gif, concluding that “a cat is dancing.” However, we may also attribute functional semantics, concluding that “a cat has arms above its head on frame fᵢ.”

in that case, without adding impure statefulness, how does one differentiate between "a paused frame is being displayed" and "an intermediate frame of a playing video is being displayed"

then at the end, the example from elm looks great, but i see lots of impure state being generated (browser, model) or am i missing something?

> in that case, without adding impure statefulness, how does one differentiate between "a paused frame is being displayed" and "an intermediate frame of a playing video is being displayed"

A "paused" frame could be represented like Fi, Fi+1 ... Fi+N, etc; for every moment i..(i+N), F remains the same and is thus "paused." The thing that's tough to wrap your head around is our language is rooted in object-orientation however. "Pause" is less of a meaningful term when time is discretized. See also https://softwarefordays.com/post/fp-as-a-scientific-revoluti...

> then at the end, the example from elm looks great, but i see lots of impure state being generated (browser, model) or am i missing something?

All functional programs (even if written in Haskel) have side effects - the CPU only has a certain amount of registers that can be used, for example, so any nontrivial program will be constantly overwriting them. That elm program however only exposes pure functions in user land, just like with a Haskel program

thanks for the reply

i guess what i was thinking was, if there was a ui, with a play/pause icon, and playing the video should cause the play icon to switch to a pause icon (because video is now "playing" so we want to be able to click it and "pause" the video) how do we represent that in a purely functional way?

since at any "timeless" instant, t1 vs t2 is just a frame1 vs frame2 issue at the language level (?), how in a purely functional world, would we determine that video is indeed playing and that icon should be swapped while playing vs not?

does user-interactive systems imply that there must inherently be some impurity?

Consider pressing a "play" button to first start playing the video but then also remove itself from the UI and replace it with a "pause" button that when clicked does the inverse. The UI here is acting as a state store but the functions can then be designed as purely functional, acting only on their inputs.

ah, that makes more sense i think... yes, i guess that is one way of accomplishing it, thanks ^^

I don’t recommend this strategy in practice though. It’s brittle and not all application state can even be represented as UI (what about your login cookie?).

In this case, the play/pause button becomes part of the "video." So now the video includes a piece of state which has perhaps been toggled to "paused." And at that point F(i) = F(i+1)... = F(i+n), since nothing will have changed for n moments (until the user interacts again). Kinda hard though to fully get this in the abstract. I struggled with the same questions. All I can say is SICP, all of Rich Hickey's videos, redux, elm, resources listed on haskel.com all helped.

Also putting it all together in writing here https://softwarefordays.com/post/functional-programming-and-....

In this^ blog I've included an interactive user interface that can be seen as purely functional, even though it's a stateful ATM program. I'm actually hoping that this blog could help teach someone what took me 2 years to finally realize. I think it could be worthwhile given your questions - if you take a look, please let me know what you think!

SICP has been on my list since i saw it on a post about alan kays recommend reading but never purchased a copy yet... thank you for posting a link there to it, ill hopefully get to it soon!

User interactions would be modeled as a stream of events. And your functions would take that stream of events and return the rendered video player as it should be based on the given events.

There's two way to do it. One that requires keeping the full history of events, and another which only requires keeping the next one (or next few) and the result of applying the last ones.

I'll start with full history. You'd have something like:

    defn button-icon(click-events):
      if is-even(count(click-events))
        return paused
      else
        return play

With this, when the program starts, click-events has nothing in it, so when we call button-icon with it, it returns paused, if the user clicks the button, we call button-icon again and now there is one click event in click-events, so we return play. If user clicks again, there are now two click events and so we return paused, and so on.

There is still state in the running program, something is remembering all clicks to the button, but your UI logic is pure.

Ok, now this is inefficient and requires lots of memory. Basically every new user action we recompute everything from the program start, and remember all prior actions. That's why there's the second approach. Instead we will do:

    defn button-icon(current-button click-event):
      if click-event
        if (current-button = paused)
          return play
        else
          return paused
      else
        return current-button

Now the running program won't remember the list of all click events from the program start, instead it'll remember the last result from the last call to button-icon and it'll pass that last result to button-icon the next time the user takes an action. This can be bootstrapped recursively or using fold.

i see, those are definitely ways to do it...

> There is still state in the running program, something is remembering all clicks to the button, but your UI logic is pure.

could this be solved by having the whole app be some kind of recursive function that passes the events as a list that gets appended to over time?

then it could remain completely pure?

Yes that's exactly how it would be bootstrapped, but that still will leave the IO itself, and that part will be impure. So as you recurse, even if you carry over the events by passing them back, you'll need to have a part where you block and wait on external input from the user, and that is inherently an impure operation.

You can keep extracting the IO out, but you can't get rid of it. So Haskell or Elm would basically do the "dirty impure" IO on your behalf, so in your code it wouldn't even seem like you're doing impure IO, but your running program still will, just it'll be done by the Haskell/Elm runtime on your behalf. Or if you're not using those languages, the best you can do is extract it to your top level function.

> in that case, without adding impure statefulness, how does one differentiate between "a paused frame is being displayed" and "an intermediate frame of a playing video is being displayed"

You have a paused "state" if that's relevant to you. But you can say "the video pauses at time t1" and "the video resumes at time t2", rather than restricting yourself to "the video is paused" or "the video is not paused".

>> But you can say "the video pauses at time t1" and "the video resumes at time t2", rather than restricting yourself to "the video is paused" or "the video is not paused".

Well then there is something fundamentally different about the video between T1 and T2 vs after T2. That is state - paused or playing. Word games don't change that.

The video at T1.5 is paused, and the video at T2.5 is playing. Those are banal, ordinary facts; the difference between them shouldn't surprise us, any more than the fact that length of the string "hello" is 5 but the length of the string "goodbye" is 7. You only get confused if you imagine that there is somehow a single "state" of "whether the video is playing now" that somehow "changes", which is unfortunately what non-FP programmers tend to do.

Not sure what the point of the article was, it makes hard easy concepts. It would have been easier by properly explaining common functional programming patterns such as event data stores, or even more popular ones used in the javascript world like vuejs store or redx etc.

This feels like a rehash of Zeno’s arrow paradox.

Reply on news.ycombinator.com