# Sharing Environments

let f = {x,y,z} \ [] -> M in
  case q of
    n -> let g = {x,y,z} -> N
    0 -> 0
in
f

into

letenv xyz = env {x,y,z} in
let f = {xyz} \ [] -> caseenv xyx of {x,y,z} ->  M in
  case q of
    n -> let g = {xyz} \ [] -> caseenv xyz of {x,y,z} -> N
    0 -> 0
in
f

If n=0 is the hot path, we allocate two more words.

Identifying the hot path would be another nice sub-project. E.g. the recursive path is likely (not guaranteed) to be the hotter path.

## Nested envts

f x y z = let h1 = {x,y}   \p. ...p..x..y...
              h2 = {x,y,z} \q...q...x..y..z
          in blah
          
===>

f x y z = let env1 = ENV { x,y }
              env2 = ENV {env1, z}
              h1 = {env1} \p. caseenv env1 of {x,y} -> ...
              h2 = {env2} \q. caseenv env2 of {env1,z} ->
                              caseenv env1 of {x,y} ->
                              ...

Here env1 is nested inside env2

## Fancy GC (not safe for space -- unless we fix GC)

We might get a lot more sharing if we could share a single envt from multiple function closures -- possibly creating space leaks.

f x y z = let xyz = ENV { x,y,z }
              h1 = {env1} \p. caseenv env1 of {x,y,_} -> ...
              h2 = {env2} \q. caseenv env2 of {x,y,z} ->
                              ...

Now we get more sharing. But maybe a space leak.

I think we could cure the leak (with a bit of work in the RTS/GC). But Step 1 should be to see whether we save (hopefully a lot) more allocation. If not, no point in messing with the GC.

**Idea: measure how much allocation you'd save if you allowed space leaks, to increase sharing**. If it's a lot, we could work on fixing the leak (which seems entirely feasible).

## Function closures that use other function closures as their "env"

f x y z = let h1 = {x,y} \p.  ...p...x...y...
              h2 = {h1,z} \q. caseenv h1 of {x,y} ->
                              ...(h1 5)....

Instead of allocating a separate environment object, h1 is "normal" and h2 simply points to h1 which contains its environment.

Usually if h1 is still *callable* we keep alive all the CAF's accessible from h1's code. But here, we don't want to do that. If h1 is alive only because of `caseenv`, then don't treat h1's *code* as a source of roots.

Works only if one function uses a superset of another function's free vars.

Would not work for thunks, because they get overwritten. (But even that is not quite true. Thunk [code-ptr, value field, free var1, ... free varn]. Thunk update overwrites code ptr and value field.)

**Idea: somehow measure how much improvement we would get**.

## CAFs (background)

-- xs is a CAF: a top-level value of arbitrary size
xs = map expensive [1..] :: [Int]

main = if length (take 3 xs) > 10 
       then <long stuff> 
       else do { <more long stuff>; foo 3 }
       
       
       
       
foo n = ...xs....