design-notes.txt

* how to remove shadowed bindings?

* how to remove shadowed bindings?
  option 1: add new bindings to front of list; remove shadowed bindings
    from middle, but preserve ordering.
  option 2: add only non-shadowing bindings to front of list; all shadowing
    bindings will (functionally) replace existing bindings.

  option 1 is O((n + m)^2); option 2 is O(nm), where n is # bindings in
  existing environment and m is # bindings being added.  When n << m or
  vice versa, option 2 is more efficient; when n and m are approximately
  equal, neither implementation is asymptotically faster than the other.

  For displaying to users, though, option 1 is probably more intuitive,
  since the bindings appear in the order in which they were added to the
  environment.  In option 2, the order is less predictable.

* decent contracts on the library.  Could actually write some decent
  contracts if make-empty-env took 2 additional arguments, predicates that
  recognized valid keys and values, respectively.  Then the contracts could
  extract these predicates and use them in the appropriate positions.

  But do people want to have to supply these predicates to make-empty-env?

* Enforcing predicate condition on weaken-env:
  1) specify a contract for the argument that imposes this condition.  What
     would the error message look like for a violation?  (Suggested by Dave
     Herman.)

  2) Dave's other suggestion, coerce the new predicate to ensure that it's
     less precise.  That is, use
        (lambda (x y) (or (old-eq? x y) (new-eq? x y)))

  3) Similar to #1, wrap the function in a new lambda that raises an
     exception if the condition is violated.  Somewhat simpler, and I've
     got more control over the error message.

  I think #3 is best: I don't like implicit coersions, and it's easier to
  implement than #1.  I'm willing to revisit this issue later, if there is
  demand.

* env-domain: We don't want the user to be able to mutate the list of keys
  actually in the environment itself; that could violate invariants.  Two
  options:
  1) Make the list in the env struct immutable and simply return it.
     env-domain is O(1), but extend-env is now slower, as it requires an
     additional O(n) pass across the list.  (Asymptotic complexity
     unchanged.)
  2) Copy the list on demand.  env-domain now O(1).

  I've gone with option 2, on the grounds that you shouldn't have to pay
  for this feature unless you use it.

* Should I use env/c instead of env? in contracts?  Slower, and can't
  really use anything except any/c for keys and values, but better error
  reporting.