experiment: treat pure ingredients as immutable

This isn't complete yet:

a) If you copy a variable the copy is not checked for mutations.

b) /contained-in might be a hack. It's needed because sometimes I want
to pass in two pointers to a data structure, say for deleting something
from a list. Both are conceptually the same structure, so it's
unnecessary for both to be products as well. There's also technical
reasons you *can't* return both, because if you pass in the same
variable to both ingredients (say you want to remove the first element
of a list), the products now must write to the same variable as well
(thanks to our earlier /same-as-ingredient constraint), and what value
gets written last is not something we want to be thinking about.

c) Even if we stick with /contained-in, it's ambiguous. I'm using it
sometimes to say "a belongs to b", sometimes to say "a _will_ belong to
b after the recipe returns. Perhaps that distinction doesn't matter.
We'll see.

d) Should we be encouraged to say ingredients are contained in products?
At the moment 'push' works only because of mu's incomplete analysis.
Once we fix a) above, it's unclear what the right header should be.

e) edit/ isn't close to working yet.

(No more commit numbers since I'm now starting a branch, and can't rely
on a stable ordering as I rebase. For the same reason I'm not including
the changes to .traces/, to minimize merge conflicts.)

1 files changed, 45 insertions, 48 deletions

diff --git a/075duplex_list.mu b/075duplex_list.mu
index 02bb3152..1f00a0cf 100644
--- a/075duplex_list.mu
+++ b/075duplex_list.mu
@@ -6,17 +6,21 @@ container duplex-list:_elem [
   prev:address:duplex-list:_elem
 ]
 
-recipe push x:_elem, in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
+# should I say in/contained-in:result, allow ingredients to refer to products?
+recipe push x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  result <- new {(duplex-list _elem): type}
+  result:address:duplex-list:_elem <- new {(duplex-list _elem): type}
   val:address:_elem <- get-address *result, value:offset
   *val <- copy x
   next:address:address:duplex-list:_elem <- get-address *result, next:offset
   *next <- copy in
-  reply-unless in
-  prev:address:address:duplex-list:_elem <- get-address *in, prev:offset
-  *prev <- copy result
+  {
+    break-unless in
+    prev:address:address:duplex-list:_elem <- get-address *in, prev:offset
+    *prev <- copy result
+  }
+  reply result  # needed explicitly because we need to replace 'in' with 'result'
 ]
 
 recipe first in:address:duplex-list:_elem -> result:_elem [
@@ -82,11 +86,11 @@ scenario duplex-list-handling [
   ]
 ]
 
-# Inserts 'x' after 'in'. Returns some pointer into the list.
-recipe insert x:_elem, in:address:duplex-list:_elem -> new-node:address:duplex-list:_elem [
+# insert 'x' after 'in'
+recipe insert x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  new-node <- new {(duplex-list _elem): type}
+  new-node:address:duplex-list:_elem <- new {(duplex-list _elem): type}
   val:address:_elem <- get-address *new-node, value:offset
   *val <- copy x
   next-node:address:duplex-list:_elem <- get *in, next:offset
@@ -100,11 +104,10 @@ recipe insert x:_elem, in:address:duplex-list:_elem -> new-node:address:duplex-l
   y <- get-address *new-node, next:offset
   *y <- copy next-node
   # if next-node is not null
-  reply-unless next-node, new-node
+  reply-unless next-node
   # next-node.prev = new-node
   y <- get-address *next-node, prev:offset
   *y <- copy new-node
-  reply new-node  # just signalling something changed; don't rely on the result
 ]
 
 scenario inserting-into-duplex-list [
@@ -185,7 +188,7 @@ scenario inserting-after-start-of-duplex-list [
     1:address:duplex-list:character <- push 3, 0
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
-    2:address:duplex-list:character <- insert 6, 1:address:duplex-list:character
+    1:address:duplex-list:character <- insert 6, 1:address:duplex-list:character
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
     3:character <- first 2:address:duplex-list:character
@@ -215,38 +218,37 @@ scenario inserting-after-start-of-duplex-list [
   ]
 ]
 
-# Removes 'in' from its surrounding list. Returns some valid pointer into the
-# rest of the list.
+# remove 'x' from its surrounding list 'in'
 #
-# Returns null if and only if list is empty. Beware: in that case any pointers
-# to the head are now invalid.
-recipe remove in:address:duplex-list:_elem -> next-node:address:duplex-list:_elem [
+# Returns null if and only if list is empty. Beware: in that case any other
+# pointers to the head are now invalid.
+recipe remove x:address:duplex-list:_elem/contained-in:in, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
-  # if 'in' is null, return
-  reply-unless in, in
-  next-node:address:duplex-list:_elem <- get *in, next:offset
-  prev-node:address:duplex-list:_elem <- get *in, prev:offset
-  # null in's pointers
-  x:address:address:duplex-list:_elem <- get-address *in, next:offset
-  *x <- copy 0
-  x <- get-address *in, prev:offset
-  *x <- copy 0
+  # if 'x' is null, return
+  reply-unless x
+  next-node:address:duplex-list:_elem <- get *x, next:offset
+  prev-node:address:duplex-list:_elem <- get *x, prev:offset
+  # null x's pointers
+  tmp:address:address:duplex-list:_elem <- get-address *x, next:offset
+  *tmp <- copy 0
+  tmp <- get-address *x, prev:offset
+  *tmp <- copy 0
+  # if next-node is not null, set its prev pointer
   {
-    # if next-node is not null
     break-unless next-node
-    # next-node.prev = prev-node
-    x <- get-address *next-node, prev:offset
-    *x <- copy prev-node
+    tmp <- get-address *next-node, prev:offset
+    *tmp <- copy prev-node
   }
+  # if prev-node is not null, set its next pointer and return
   {
-    # if prev-node is not null
     break-unless prev-node
-    # prev-node.next = next-node
-    x <- get-address *prev-node, next:offset
-    *x <- copy next-node
-    reply prev-node
+    tmp <- get-address *prev-node, next:offset
+    *tmp <- copy next-node
+    reply
   }
+  # if prev-node is null, then we removed the node at 'in'
+  # return the new head rather than the old 'in'
   reply next-node
 ]
 
@@ -256,7 +258,7 @@ scenario removing-from-duplex-list [
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
     2:address:duplex-list:character <- next 1:address:duplex-list:character  # 2 points at second element
-    2:address:duplex-list:character <- remove 2:address:duplex-list:character
+    1:address:duplex-list:character <- remove 2:address:duplex-list:character, 1:address:duplex-list:character
     3:boolean <- equal 2:address:duplex-list:character, 0
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
@@ -283,8 +285,7 @@ scenario removing-from-start-of-duplex-list [
     1:address:duplex-list:character <- push 3, 0
     1:address:duplex-list:character <- push 4, 1:address:duplex-list:character
     1:address:duplex-list:character <- push 5, 1:address:duplex-list:character
-    # removing from head? return value matters.
-    1:address:duplex-list:character <- remove 1:address:duplex-list:character
+    1:address:duplex-list:character <- remove 1:address:duplex-list:character, 1:address:duplex-list:character
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
     3:character <- first 2:address:duplex-list:character
@@ -312,7 +313,7 @@ scenario removing-from-end-of-duplex-list [
     # delete last element
     2:address:duplex-list:character <- next 1:address:duplex-list:character
     2:address:duplex-list:character <- next 2:address:duplex-list:character
-    2:address:duplex-list:character <- remove 2:address:duplex-list:character
+    1:address:duplex-list:character <- remove 2:address:duplex-list:character, 1:address:duplex-list:character
     3:boolean <- equal 2:address:duplex-list:character, 0
     # check structure like before
     2:address:duplex-list:character <- copy 1:address:duplex-list:character
@@ -337,20 +338,16 @@ scenario removing-from-end-of-duplex-list [
 scenario removing-from-singleton-list [
   run [
     1:address:duplex-list:character <- push 3, 0
-    2:address:duplex-list:character <- remove 1:address:duplex-list:character
-    3:address:duplex-list:character <- get *1:address:duplex-list:character, next:offset
-    4:address:duplex-list:character <- get *1:address:duplex-list:character, prev:offset
+    1:address:duplex-list:character <- remove 1:address:duplex-list:character, 1:address:duplex-list:character
   ]
   memory-should-contain [
-    2 <- 0  # remove returned null
-    3 <- 0  # removed node is also detached
-    4 <- 0
+    1 <- 0  # back to an empty list
   ]
 ]
 
 # remove values between 'start' and 'end' (both exclusive)
 # also clear pointers back out from start/end for hygiene
-recipe remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem -> start:address:duplex-list:_elem [
+recipe remove-between start:address:duplex-list:_elem, end:address:duplex-list:_elem/contained-in:start -> start:address:duplex-list:_elem [
   local-scope
   load-ingredients
   reply-unless start
@@ -457,8 +454,8 @@ scenario remove-range-empty [
   ]
 ]
 
-# Inserts list beginning at 'new' after 'in'. Returns some pointer into the list.
-recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+# insert list beginning at 'new' after 'in'
+recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
   reply-unless in
@@ -484,7 +481,7 @@ recipe insert-range in:address:duplex-list:_elem, start:address:duplex-list:_ele
   *dest <- copy in
 ]
 
-recipe append in:address:duplex-list:_elem, new:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+recipe append in:address:duplex-list:_elem, new:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
   local-scope
   load-ingredients
   last:address:duplex-list:_elem <- last in