```holger krekel 7926d02 2005-01-18 ``` ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174``` ```About annotations ================= We are running into limitations of the annotation system used for type inference. This document describes these limitations and how to slightly move the concepts around to fix them, and probably also how the whole issues occurred from having mixed concepts in wrong ways in the first place. Irc log from October, the 28th:: sanxiyn: ok for a few words about annotations? yep! (sorry for being out; I forgot it...) np mutable structures pose some problems e.g. because you cannot say "len(x) = 5" if 'x' is a list, of course because the length of x could change so just propagating the annotation is wrong ah. it's more annoying to say e.g. that x is a list of integers Is it annoying? getitem(x, anything) = y & type(y) = int yep. but what if you call f(x) and f adds strings to the list x ? I think RPython list shall be homogenous. yes, but: x = [] f(x) then f is allowed to put strings in x ah, empty list thing... yes but also: x = ['hello'] f(x) ML languages have precisely the same problem, aren't they? yes but i think we can solve it here but we need to be careful special casing empty list should work. (IIRC that's how it's done in ML, basically) yes but i think we can solve it here (didn't i say that already :-) agreed. so let's solve it; :) won't help verbosity, but let's think bout that later. List length seems to be impossible to guarantee. we can say: deref(x) = z ; getitem(z, anything) = y ; type(y) = int here x is our variable, but z is a Cell() so the list has a life of its own, independently from the variable it is in * sanxiyn reads it carefully. what i'm thinking about is this: we would have (conceptually) a single big pool of annotation not one AnnotationSet per basic block only one, for the whole program Yes. I found annset per block annoying, and felt that it's that way for no real reason. we would map variables to this big annotation set this must probably still be done for each block independently each block would have a map {variable: cell-in-the-big-annset} or maybe not hm because variables are supposed to be unique anyway still, i think the big annset should not use variables at all, just cells and constants. comments in get_variables_ann say otherwise, but I suspect it's outdated. "supposed" to be unique... no, they still aren't really eh, confused. the comment is not outdated what does it mean, then? the same Variable() is still used in several blocks that should be fixed indeed. I commented out XXX: variables must not be shared, and ran test_pyrextrans, and got 6 failures. yes all EggBlocks are wrong, currently I don't know what Spam/Egg Blocks are. :-) Don't know at all. it's funny names describing how the block was built they are all Blocks an EggBlock is used after a fork fork? a split, after a block with two exits but that's not relevant to the other transformations which can simplify the graph after it is built we could have a single big annset it represents "the heap" of an abstract CPython process hm. i.e. objects in the heap like lists, integers, all of them using Cell() to represent abstract objects, and Constant() for concrete ones then a variable is only something which appears in the basic block's SpaceOperations * arigo is confused So Variable() points to Cell(). yes... currently we cannot handle mutable lists because: getitem(x, *) = z is an annotation talking about the variable x so we cannot propagate the annotation forth and back to called sub-functions instead, getitem should talk about an object, not the variable that points to it exactly! That's Python-think. :) http://starship.python.net/crew/mwh/hacks/objectthink.html Is mwh's wonderful piece "How to think like a Pythonista" relevant here? * arigo tries to do 4 things at the same times and fails to So variables are names. It binds. yes mwh wrote: "I find the world variable to be particularly unhelpful in a Python context..." with wonderful diagrams :) yah, introducing namespaces into abstract-interpretation world! :-) namespace? eh, not exactly, I think... hpk: yes, each block is its own namespace here :-) and obviously we need "heap objects" that these names can refer to (namespaces in the meaning of "living" bindings between names and objects) So "objects" are actually cells unless constant-propagated... yes... i think we could even go for a full-Prolog representation: the "big heap" contains cells and constants. cells can become constants when we know more about them. * sanxiyn should read Borges and Calvino as Martellibot suggested. :) seems cleaner than the current cell-variable-constant mix. in other words, a SpaceOperation uses variables only, and the variable can refer to a cell or a constant from the heap... the point is that the objects in the heap can be manipulated say a variable v1 points to a cell c with type(c) = list and len(c) = 3 v2 = v1 and v1 points to the same cell c. you modify v2 and v1 is modified, too, etc. yes exactly if you append an item to the list then the annotation len(c) = 3 is deleted Is "prolog" a pronoun for "non-determinism"? Logic Programming i think arigo: I think that solves "reflow". sanxiyn: yes, possibly you can add annotations freely, at least that's fine we'll just need a trick to delete ("retract") annotations because other annotations may depend on this one like type(c3)=int is only valid if type(c1)=int and type(c2)=int because we used an 'add' operation Currently flowin does similar thing. It recomputes all annotations if len(annset) is decreased. sanxiyn: yes, but it should work without the need to re-flowin eh? without re-flowin? if you delete an annotation, then you must recompute annotations recursively on the rest of the graph yes, how to avoid that? we can record dependencies each annotation "knows" that it depends on some other ones question is if there are different ways of "depending" or just one way hpk: right in a way a space operation modifying the assertions denotes 'edges' in this dependency graph? yes I think annotation should know about *others* which depend on itself, not which itself depends on. yes when you kill an annotation, just follow the forward dependencies to kill the ones it depends on So not dependency... reverse dependency? :) forward dependency... ? Should be easy to add. "reasons"? origin? hpk: no, consequences. hpk: neither reason nor origin. "dependents" ? As in SF novel "time patrol", if you change the past, the future is all changed. how about consequences? I'm not good at naming... too long :-) implication too long ; consequences is fine if you don't have to type it too often :-) hmmm. i guess we need an Annotation class whose constructor takes a list of dependencies, and records 'self' in these dependencies' "consequences" or whatever I think only deletion routine need to refer it. ...cut. So if you have a good name for that attributes, speak up :-) ```