Hi, Nicolas Pierron wrote:
> 2010/2/14 Sander van der Burg - EWI <[email protected]>: >> So, what are you guys going to do? Implementing a clean room implementation >> of ATerm with the same interfaces or forking ATerm? And if so, why should >> this ATerm version developed inside the Nix repository? > > Nix does not need ATerm, Nix need maximal sharing to implements > maximal laziness. Having given this some more thought, I think that creating another term library to replace ATerm won't solve our problems at all (and it's rather reinventing the wheel). This is because those problems are caused not by the ATerm library but by the evaluation strategy of the Nix expression evaluator. This evaluation strategy is very simple, since it's entirely based on substituting terms in other terms. For instance, a beta redex ((x: E1) E2) is rewritten to (E1 [x := E2]) (i.e. every occurrence of `x' in E1 is replaced by E2). Such a strategy is normally very slow because it leads to work duplication: if `x' is used multiple times, then E2 will be evaluated multiple times. However, thanks to the normal form cache, we can efficiently see whether we've already evaluated E2. This is very simple to implement (just a few lines of code), but it doesn't scale because the normal form cache prevents garbage collection. Using a different term implementation doesn't fix this: - The normal form cache will still grow without bounds. - You still spend lots of time doing substitutions. (According to Valgrind, Nix spends up to 50% of its time in the substitute() function, and 30% or so of the allocations originate there.) A more conventional way to interpret a functional language is to have an explicit environment mapping variables in scope to their values. I.e., when you evaluate ((x: E1) E2), you add [x := E2] to the environment and evaluate E1. If `x' is needed, you fetch its value E2 from the environment, evaluate it to its normal form E2', and update the environment with [x := E2'] so that you don't need to evaluate `x' again. Or you compile to some byte-code representation where variables point to closures in the heap that are overwritten by their normal forms when entered. I'm sort of leaning towards that approach (compile to Parrot or Guile or whatever). -- Eelco Dolstra | http://www.st.ewi.tudelft.nl/~dolstra/ _______________________________________________ nix-dev mailing list [email protected] https://mail.cs.uu.nl/mailman/listinfo/nix-dev
