Hacker News Reader

Heh, check out time-travel debugging and be amazed at how simple a much more powerful “undo” can be made when purity is involved (in FP langs, e.g. Elm or Haskell).

Seriously though, design wise there was not much you said that was specific to OO. Take for example:

- all actions are a data type

- the history is a list of actions (in LIFO style for the purpose of simplicity here)

- undo pops the list and puts undo in another list

- redo replays the undo list onto the history list

A bit more outlined, but nothing OO there, it was in fact entirely functional.

This is a way simpler approach vs the OO way described above. The OO way requires undo/redo to precisely cancel each other, which is extremely difficult to get right.

Isn't the real difficulty of undo the implementation of the undo method for each action? T The action list seems easy.

Store a list of actions, and represent your state as a sum of said actions. That way, no matter what the action is, "undoing" an action is literally just popping it off the list.

  actions = [append("The"), append(" quick"), append(" brown"), append(" fox")]
  state = reduce(actions, some_combiner) // This might give you a string "The quick brown fox"

If you pop the last element `append(" fox")` of the actions and rebuild the state, you can easily see that the new state "The quick brown" is simply the old state without the last action, i.e. an "undo".

If rebuilding the state is expensive, it is not hard to devise caches around state management under this model.

Makes sense. But i don't see how this is related to OO vs FP then. Putting all your actions into a list is easy. Replaying is easy. The main problem is caching the state which can become tricky no matter OO or FP.

You're right in that nothing about this is specific to OO or FP.

However, under this model, you really don't want your actions in the actions list to change after the fact. That means those actions in the list really shouldn't be modeled as "objects" with object-like mutable internal state and all. In fact, you'd probably need them to be as lightweight as possible, which means no sticking methods on them.

With those constraints in mind, OO-style code brings nothing to the table.

I think this unfortunately goes into the same direction a lot of political discussions tend to go. Two rigid philosophies and one has to win. In the real world either one can work if applied correctly. And both can learn from each other.

FP brings a lot of interesting concepts to the table that are useful. But I doubt that people that screw up OOP will screw up less with FP

In the end competent and disciplined (in my view the number one attribute of a good dev) people will produce good software with any paradigm. Clueless people will cause problems no matter what the tool is.

My arguments was actually just that it had nothing to do with OO at all :)

Caching becomes a lot easier though in a pure functional programming lang though, and in a lazy one happens automatically for a lot of things.

Already present in Smalltalk, Lisp and Mesa/Cedar development environments at Xerox PARC, no need for FP advocating for it.

I guess immutability is the actual thing that makes it easy, and arguably Lisp is also an FP lang. m Main point though was the ease of doing it in a pure language, almost trivial.

I pretty much used this exact same approach to implement undo/redo in a programmer's editor and found it worked well.

My code is pretty exactly as you describe, an undo and redo stack holding action objects and the interfaces to the action objects being nothing more than 'undo()' and 'redo()' methods.

In functional programming you would store actions in lists with funs/closures inside those data. For example in erlang list of undo actions would look like this:

  Undo = [ { RemoveJpeg, JpegData} ]

where RemoveJpeg is a fun (like closure) and JpegData is what would be given as argument to this fun. The implementing undo looks like this:

  undo_action(Document,[UndoHead|UndoTail]) ->
    {UndoFun,UndoData} = UndoHead,
    UndoFun(Document,UndoData).

Isn't it simple? RemoveJpeg just returns modified document. undo_action knows only that every action should take two arguments and return modified document.

In Smalltalk:

    RemoveJpeg <- [:data | ...].
    JpegData <- [:data | ...].
    Undo <- #( RemoveJpeg, JpegData ).

As possible implementation of undo could be

    undoAction: document with: undoList
    undoList do: [:aBlock| 
       aBlock value: document].

The fundamental feature that makes such an example easy is first-class functions. You are simply using objects to encode this and not making any use of their identify and mutable state.

> You are simply using objects to encode this and not making any use of their identify and mutable state.

Most software with undo-redo will show you some metadata related to the action (for instance "Undo 'Drag stuff'", "Redo 'Set text in bold'"...) so you have to have a way to associate metadata with the "undo / redo" functions; the class is a good tool for this.

Also, a common optimization is to alter the head of the stack instead of deleting / creating new commands when for instance you are moving an object in the GUI. e.g. say you have a command that moves a box at a specific position. If command objects are immutable, every time the mouse moves, you have to pop the head of your stack and push a new command instead (which may be a waste of resources); instead you can just have an "update" method which will change the position stored inside the command which is microscopic in comparison of malloc / free.

You can do that optimization in FP languages if you have unique types, ie, types that can only have one reference to them. You use the list as if it's immutable, by creating a new list with the new command and the rest of the previous list. But since the compiler can prove that the old list is no longer referenced, it can reuse it and simply make the update in-place.

could you show an actual example where commands are polymorphic types (e.g. they come from a separate DLL) and this optimization actually happens ? (the actual "updating" of the command doesn't need to cross DLL boundaries, eg a DLL both provides a command, instantiates it, and updates it. The command queue is instantiated by another DLL though).

I don't know what icebraining is talking about becaue AFAIK there aren't widely used languages with unique types, except perhaps Rust.

> If command objects are immutable, every time the mouse moves, you have to pop the head of your stack and push a new command instead (which may be a waste of resources)

Have you profiled that?! :)

yes, actually, it used to eat 30% of the CPU on a software I worked on because of malloc-fest when moving the mouse quickly across the screen and dragging multiple objects.

Apart from this being the prime example for the argument for immutable data (i.e. just keep the whole state of your editor at every undo point somewhere; restore to previous states when undoing) the "OO way" doesn't even need OO features, i.e. see typeclasses or traits.

ClojureScript talk, 26:52 is the demo but the whole video is worth watching and key to understanding how it works: https://m.youtube.com/watch?v=-I5ldi2aJTI