[clean-list] Passing an environment around
S. Doaitse Swierstra
doaitse@cs.uu.nl
Thu, 19 Oct 2000 12:01:41 +0200
We encountered this problem of loss of sharing when implementing our
pretty printing combinators. We solved this problem by using an
attribute grammar systemn to generate the rquired function
definitions. The approach is described in:
http://www.cs.uu.nl/groups/ST/Software/UU_Pretty/
where you find a paper and the generated code. Actually we solve a
more complicated problem in which we have to locate all calls to a
function and compare their arguments, compute a least upper bound of
those, and call the function just once with this argument. The
attribute grammar is really multi pass and I consider the resulting
code to be impossible to write by hand (albeit some people
undoubtedly might manage). Maybe we will find some time to improve
abit on the interface and include a monda, but you should not wait
for that.
Doaitse Swierstra
At 1:51 AM -0700 10/19/00, Simon Peyton-Jones wrote:
>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 =3D 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=C8 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 =3D (add (add fx fy) fy)
>|
>| fe1, fe2 :: Env -> Exp
>| fe1 e =3D ...
>| fe2 e =3D ...
>|
>| initialEnv :: Env
>| initialEnv =3D ...
>|
>| Start =3D 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) =3D> 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 =3D ... in add e1 e2
>|
>| add e1 e2 with ?env =3D ...
>|
>| 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=C8 Romildo Malaquias <romildo@iceb.ufop.br>
>| Departamento de Computa=C1=93o
>| Universidade Federal de Ouro Preto
>| Brasil
>|
>| _______________________________________________
>| clean-list mailing list
>| clean-list@cs.kun.nl
>| http://www.cs.kun.nl/mailman/listinfo/clean-list
>|
>
>_______________________________________________
>clean-list mailing list
>clean-list@cs.kun.nl
>http://www.cs.kun.nl/mailman/listinfo/clean-list
--
__________________________________________________________________________
S. Doaitse Swierstra, Department of Computer Science, Utrecht University
P.O.Box 80.089, 3508 TB UTRECHT, the Netherlands
Mail: mailto:doaitse@cs.uu.nl
WWW: http://www.cs.uu.nl/
PGP Public Key: http://www.cs.uu.nl/people/doaitse/
tel: +31 (30) 253 3962, fax: +31 (30) 2513791
__________________________________________________________________________