Discussion: Incremental Computation with Names (OOPSLA 2015)
Add 2-3 comments or questions about "Incremental Computation with Names" (OOPSLA 2015). These may include posing your own questions, or responding to questions of other students. We will continue this discussion in class on Thursday, Feb 25.
Having a hard time understanding section 2.3, specifically how forking in the inner layer allows it to deterministically generate additional names.
Is the Adapton totally the same as the one in last paper, not the nominal Adapton? And in the nominal matching, is it required to organize a namespace for all variables or only the same names in distinct functions?
Is there any way that naming could be done automatically? Would it make sense to qualify names per function or per module?
For the small number of cases where Nominal Adapton is slower than Adapton, what is the overhead?
forkgenerates the same output names when called on the same input names by definition. This allows the inner layer to recalculate the same names when recalculating a dirtied thunk. In practice,
forkreturns a modified version of the original name similar to adding 'L' or 'R' to a string.
fork 'myname', in this example would return
@trko8371: We generally choose names by using an value that's incremented for each name needed in the outer layer, and let the inner layer chose names with
fork. This is essentially automatic, and we're considering pushing it down to the library level so the user doesn't even have to think about names. As far as overhead, I don't remember specifics, but overall computation time overhead vs non-Adapton was around 20-30x, so there's plenty of room there for the difference. It's the updates that are fast, and we're working on improving initial computation time.
I have a question related to Tristan's: What are instances of good name uses and bad name uses as well as their performance characteristics?
Confused with Figure2 and Figure 5 Eval-scrubEdge and Eval-computeDep. Why do we Clean Edges?
Is it reasonable to think of the original PLDI'14 Adapton as an instance of Nominal Adapton where everything has a unique name and non-incremental computation as an instance where there is exactly one name? It seems to me that this paper's contribution is essentially a knob that you can turn between those two extremes; is there additional behavior that Nominal Adapton provides on a different axis?
Does this mean that if I generate two lists, l1 & l2, that are equal to each other, but have different names, then call
map l1, can it figure out
map l2is the same thing? Unless I'm missing something it appears that it cannot.
@kyho3600: A good name would represent a section of data that should be recomputed all at once. A bad name would collide with another name and corrupt the represented data. The best performance would be the theoretic minimal to adjust a computation (minus some overhead), and bad performance could be any amount of speed or memory usage (imagine infinitely nested names)
@jili8005: Edges are dirtied by
dirty-paths-inwhen a thunk is evaluated by
Eval-thunkDirty. That is, when a change occurs on the outer layer, all dependent edges of the DCG are marked as dirty. Cleaning the edges involves recomputing all thunks necessary to evaluate the
@best9862: The knob analogy is certainly apt, though Nominal Adapton provides at least two knobs, and 'structural'(PLDI'14) Adapton is not necessarily the extreme.
Structural Adapton, from the nominal perspective, generates a name based on the structure(values) of parameters to a function. This means that it can share the results of function calls that appear in disparate parts of a program. You could call this an 'abstraction knob', allowing memo matching to occur on different data if it shares the properties used in the algorithmic construction of the name. (There's a group doing abstract interpretation that is trying to take advantage of this property of names.)
The other knob is the density of thunks in a program. If you memoize a recursive function with structural Adapton, every call is wrapped in a thunk. The Nominal paper suggests first-class names that can be passed as parameters. Optionally passing a name allows the memoization of some calls and not others, which is especially useful for lowering the overhead incurred by memoizing many calls to quick running functions.
@jora2470: You're exactly right, nominal Adapton has no way to determine that your two lists carry the same data. If you want that type of matching, you'd need to use the same names, either directly, or by generating them algorithmically (probably by hash) based on the data contained in the list. This strategy wouldn't work out too well if you wanted to change an element of one list later, because you'd have to do all the work of regenerating the name. The PLDI'14 Adapton could not recognize the lists as equivalent either, because it memo matched based on the pointer address of the links.
This might be addressed later in the paper, but I'm curious about how versatile this approach is. It seems we have to do ad hoc tweaks for whatever data structure and algorithms on it that we might be interested in, besides lists and map for example. Am I mistaken here?
In the part of "The Nominal Approach", we have "let m0 = map f l0 in (tl l1) := Cons(2, new, ref l3)". Why does it dirties the reference b1 instead of d1? By the semantic of Cons, I think we will give a different name to l3.
And in the paper, "let y = ref n 1 , let z = ref n false" is being forbidden since the variables y and z have distinct types. So does it mean that "let y = ref n 1 , let z = ref n 2" is good? Is it updating the cell n from 1 to 2?
@diec7037: I think you've got the right idea. If your goal is a fully optimized incremental program, you'll need to do a lot of tweaking of name and such to get it right. But this is true of most systems (people still tweak assembly code to get the best performance of c). In current work we're building up a collections library that uses general-purpose naming strategies for general-purpose data structures. We'll do the common tweaks there. The versatility is that you can roll your own data structures with your own tweaks.
@erhe9979: I think the use of
refin the paper is confusing. It's used either as a constructor or an accessor. The name in the
Consconstructor is a first-class name that is used later to create new thunks. The name in the
refconstructor is used to name the ref cell. So
Cons(2, new, ref l3)is giving a new name to the Cons, and referring to the old l3.
In the second part you're correct. The cell is updated. This is from
Eval-refDirty. But the paragraph beginning "Returning to the example above", seems to suggest that it would be flagged as an error, since it was just allocated.
Is it possible for a DCG to be dirtied twice before change propagation takes place? Or what happens if a mutable reference is changed while change propagation is under way?