[clean-list] Passing an environment around
Simon Peyton-Jones
simonpj@microsoft.com
Thu, 19 Oct 2000 01:51:06 -0700
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
|