Questions About the Paper (Practical Static Memory Management)

[andrewthad]

First, thanks for doing all of this. I'm not sure that I would have been able to understand the original ASAP paper without your thesis, and I think it's a fascinating space to explore for automatic memory management.

I have two questions about the paper. The first is the claim, in section 3.4, that "wild paths sets are, in general, not closed under + ... the + operator no longer serves to compute the meet of two paths". Are wild path sets not closed under + because a wild path has no defined return type? That is, if we took the wild path of a type Person { age : s64, name : string }, we have:

(Person . age) + (Person . name)
==>
Person . (age + name)

Which doesn't really make sense (but I didn't even need to take the meet of paths to create the situation). I'm just not totally certain what the claim in the paper means or what an example of it looks like.

The other question is about the super-linear slowdown in list_len.mmtn. The paper doesn't discuss why this happens. Based on my understanding of ASAP, I would expect that this could be caused by the tail of the list being traced over and over again before each recursive call to list_len. That would degrade performance from O(n) to O(n^2). But it doesn't seem like ASAP should cause this to happen. I wondered if you had any additional insight into what was going on.

[doctorn]

It's been several years since I've thought about this so my answers may be a bit clunky but let me do my best!

In terms of the closure of wild path sets under '+', I think the comment was merely that the formal operation of '+'--i.e., simply putting two paths next to each other with a plus in the middle--doesn't take wild paths to wild paths. You have to 'do some work' in order to 'repair' a path (as you have done in your question). I can't remember if Proust explicitly defines a join operator for wild paths in his thesis but it's a very complex operation in any case!

As for the performance: I have absolutely no idea. I would really like to know, but my research has taken me very far away from this sort of work. I'd really like to get back to it at some point in the future though. There are all kinds of inefficiencies in the scanning code generated by this implementation and I've got several pages of notes on cool tricks to try out to speed things up.