[clean-list] Passing an environment around

[Simon Peyton-Jones]

It's interesting that *exactly* this issue came up when Conal
Eliott was implementing Fran in Haskell.  His 'behaviours'
are very like your expressions. 
	type Behaviour a = Time -> a
and he found exactly the loss of sharing that you did.

For some reason, though, I'd never thought of applying the
implicit-parameter
approach to Fran.  (Perhaps because Implicit parameters came along after
Fran.)  
But I think it's rather a good idea. 

I think Conal may have a paper describing the implementation choices
he explored; I'm copying him.

Simon

| -----Original Message-----
| From: José Romildo Malaquias [mailto:romildo@urano.iceb.ufop.br]
| Sent: 18 October 2000 08:12
| To: clean-list@cs.kun.nl
| Subject: [clean-list] Passing an environment around
| 
| 
| Hello.
| 
| I am implementing a Computer Algebra system (CALG) in Clean, 
| and I have a
| problem I would like the opinion of Clean programmers.
| 
| The CALG system should be able to simplify (or better, to transform)
| algebraic expressions (from Mathematics) involving integers, 
| named constants
| (like "pi" and "e"), variables, arithmetic operations (addition,
| multiplication, exponentiation), and other forms of expressions
| (trigonometric, logarithmic, derivatives, integrals, 
| equations, etc.). The
| tansformaations should follow the rules from Algebra and 
| other areas of
| Mathematica. But we know that in general an algebraic 
| expression can be
| transformed in different ways, depending on the goal of the
| transformation. Thus, the algebraic expression
| 
|    a^2 + b^2 + 3*a*b - a*b
| 
| could result in
| 
|    a^2 + 2*a*b + b^2
| 
| or in
| 
|   (a + b)^2
| 
| To control the transformations made with an algebraic 
| expression there is a
| set of flags collected in a record. I will call this record 
| the environment
| in which the expression should be simplified. The algorithms I am
| implementing may change this environment temporarily for some local
| transformations. So the enviroment should be passed around in 
| the function
| calls I am writing. This way the functions that implements the
| transformations will have an extra argument representing the 
| environment in
| which the transformation is to be performed.
| 
| Let's take an example: the algorithm for addition will have 
| two arguments to
| be added and a third argument corresponding to the enviroment:
| 
|    add :: Expr Expr Env -> Expr
| 
| and its result will depend of the flags in the environment. 
| But it is highly
| desirable to define functions like add as BINARY INFIX 
| OPERATORS. Having 3
| arguments, add cannot be made a binary operator!
| 
|   --------------------------------------------------------------------
|   So I am looking for alternative ways to pass the environment around.
|   --------------------------------------------------------------------
| 
| 1. Handle the arguments as functions themselves, which, given 
| an enviroment,
|    returns the simplified algebraic expression in that environment:
| 
|    add :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr)
| 
|    Now add can be made a binary infix operator. This solution has the
|    disadvantage that we loose sharing when doing local 
| simplifications. For
|    example:
| 
|    f :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr)
|    f fx fy = (add (add fx fy) fy)
| 
|    fe1, fe2 :: Env -> Exp
|    fe1 e = ...
|    fe2 e = ...
| 
|    initialEnv :: Env
|    initialEnv = ...
| 
|    Start = f fe1 fe2 initialEnv
| 
|    In this program fragment, fe2 may be applied twice to the same
|    environment value, computing its body twice. The resulting 
| program would
|    be too inneficient. If Clean had a mean of implementing MEMOIZATION
|    FUNCTIONS, the computation of a memoized function 
| application to the same
|    argument would evalute the body of the function only the 
| first time the
|    function is applied. Subsequent applications of that 
| function to the same
|    argument would remember the result of the previous 
| application and would
|    reutilize it. Then this way of handling environment 
| passing would be a
|    good solution.
| 
|    For more on memo functions see
|    <http://www.cse.ogi.edu/~byron/memo/dispose.ps>.
| 
| 2. Extend Clean to support IMPLICIT PARAMETER PASSING (that 
| is, a form of
|    dynamic scoping), as has been done in some Haskell 
| implementations (Hugs,
|    GHC). Than the environment could be passed implicitly and 
| add could be
|    considered to have only 2 arguments
| 
|    add :: (Env ?env) => Exp Exp -> Exp
| 
|    Here ?env represents an implicit parameter. It is not 
| passed explicitly
|    like the two argument parameters. It can be used normally 
| in the function
|    definition, like any normal parameter. To pass an argument 
| implicitly,
|    there is 2 additional forms of expression: dlet and with:
| 
|    dlet ?env = ... in add e1 e2
| 
|    add e1 e2 with ?env = ...
| 
|    I think this could be the best solution to my problem, if Clean had
|    such extension implemented.
| 
|    For more information, see
|    <http://www.cse.ogi.edu/~jlewis/implicit.pdf.gz>
| 
| 3. Join the algebraic expression and the environment in a single value
| 
|    add :: (Env,Exp) (Env,Exp) -> (Env,Exp)
| 
|    The enviroment is then carried around with each expression.
|    But now add has two enviroments to consult. Which one should be
|    used?
| 
| Would be other good alternatives to solve this problem?
| 
| Would future versions of Clean support
| 
|   - memoization functions, or
|   - implciit parameter passing?
| 
| I am open to discussion on this topics.
| 
| Regards,
| 
| Romildo
| -- 
| Prof. José Romildo Malaquias <romildo@iceb.ufop.br>
| Departamento de Computação
| Universidade Federal de Ouro Preto
| Brasil
| 
| _______________________________________________
| clean-list mailing list
| clean-list@cs.kun.nl
| http://www.cs.kun.nl/mailman/listinfo/clean-list
|