3 ms·

You don't need custom repair functions, the default is undo-replay, but in some cases it helps performance to have custom repair functions. For example suppose

by jules 14y ago

You don't need custom repair functions, the default is undo-replay, but in some cases it helps performance to have custom repair functions. For example suppose you have a changeable list, and a changeable multiset (a set that also keeps a count for each element). Now you do thelist.tomultiset(). If the list changes, then the multiset has to change as well. If you applied their framework all the way down, this might be reasonably efficient. But with custom repair functions it can be more efficient: if an element in the list gets added, just increment the count of that element in the multiset. If an element gets deleted, decrement the count of that element in the multiset.

seanmcdirmid 14y ago
I feel like we are turning hackernews into lambda-the-ultimate :) I wrote this really bad unpublished paper once [1] that described the abstracting-over-space problem as a dual and complement of the abstracting-over-time problem. It turns out, for simple scalar (non-list) signal (reactive) values, the best thing to do was to simply recompute. However, for non-scalar signals (lists and sets), life gets much more complicated: it makes no sense to rebuild an entire UI table whenever one row is added or removed, and so we want change notifications that tell us what elements have been added and removed. However, I've changed my mind since: it is actually not bad to redo an entire table just to add or remove a row, as long as you can reuse the old row objects for persisting element. If my UI get's too big, I can create sub-components that memoize renderings unaffected by the change (basically partial aggregation). Now how does that relate to theList.toMultiSet example? Well, the implementation of toMultiSet could be reduced to partially aggregated pieces very easily (many computations can actually), which could then be recombined in much the same way as rendering my UI! Yes, the solution that decrements/increments the count on a specific insertion/deletion is going to be "better", but a tree of partially aggregated memoizations works more often in general; its easier to do with minimal effort on behalf of the programmer. I still need to understand their work better, but I approached my work from a direction opposite of algorithms (FRP signals, imperative constraints). I have a lot of catching up to do. [1] http://lampwww.epfl.ch/~mcdirmid/papers/mcdirmid06turing.pdf http://lampwww.epfl.ch/~mcdirmid/papers/mcdirmid06turing.pdf
- jules 14y ago
  > but a tree of partially aggregated memoizations works more often in general; its easier to do with minimal effort on behalf of the programmer. Yes, that's exactly what you get if you do not implement a custom traceable data type (their terminology for a data type that supports repair) provided you write your code in such a way that the memoization is effective. Note that traceable data types do not necessarily need to be compound data structures, it can be e.g. an integer as well. E.g. summing a list of integers to an integer, now if one of the integers in that list gets changed, you do not need to recompute the entire sum, or even a logarithmically sized part of it: you can just subtract the original int and add the new int back in. Here is also an article that does something related but in an imperative context rather than a functional one: http://research.microsoft.com/pubs/150180/oopsla065-burckhardt.pdf http://research.microsoft.com/pubs/150180/oopsla065-burckhar...

by jules 14y ago

seanmcdirmid 14y ago

I feel like we are turning hackernews into lambda-the-ultimate :) I wrote this really bad unpublished paper once [1] that described the abstracting-over-space problem as a dual and complement of the abstracting-over-time problem. It turns out, for simple scalar (non-list) signal (reactive) values, the best thing to do was to simply recompute. However, for non-scalar signals (lists and sets), life gets much more complicated: it makes no sense to rebuild an entire UI table whenever one row is added or removed, and so we want change notifications that tell us what elements have been added and removed. However, I've changed my mind since: it is actually not bad to redo an entire table just to add or remove a row, as long as you can reuse the old row objects for persisting element. If my UI get's too big, I can create sub-components that memoize renderings unaffected by the change (basically partial aggregation). Now how does that relate to theList.toMultiSet example? Well, the implementation of toMultiSet could be reduced to partially aggregated pieces very easily (many computations can actually), which could then be recombined in much the same way as rendering my UI! Yes, the solution that decrements/increments the count on a specific insertion/deletion is going to be "better", but a tree of partially aggregated memoizations works more often in general; its easier to do with minimal effort on behalf of the programmer. I still need to understand their work better, but I approached my work from a direction opposite of algorithms (FRP signals, imperative constraints). I have a lot of catching up to do. [1] http://lampwww.epfl.ch/~mcdirmid/papers/mcdirmid06turing.pdf http://lampwww.epfl.ch/~mcdirmid/papers/mcdirmid06turing.pdf

jules 14y ago
> but a tree of partially aggregated memoizations works more often in general; its easier to do with minimal effort on behalf of the programmer. Yes, that's exactly what you get if you do not implement a custom traceable data type (their terminology for a data type that supports repair) provided you write your code in such a way that the memoization is effective. Note that traceable data types do not necessarily need to be compound data structures, it can be e.g. an integer as well. E.g. summing a list of integers to an integer, now if one of the integers in that list gets changed, you do not need to recompute the entire sum, or even a logarithmically sized part of it: you can just subtract the original int and add the new int back in. Here is also an article that does something related but in an imperative context rather than a functional one: http://research.microsoft.com/pubs/150180/oopsla065-burckhardt.pdf http://research.microsoft.com/pubs/150180/oopsla065-burckhar...