[clean-list] Passing an environment around

=?iso-8859-1?Q?Jos=E9_Romildo_Malaquias?= romildo@urano.iceb.ufop.br
Thu, 19 Oct 2000 11:40:51 -0200


--OgqxwSJOaUobr8KG
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit

On Thu, Oct 19, 2000 at 03:34:42PM +0200, Pieter Koopman wrote:
> At 09:16 19/10/00 -0200, José Romildo Malaquias wrote:
> >Your sugestion is the first alternative to solve the problem
> >I have posted in the original message of this thread. As you
> >mention, there is the problem of evaluating the body of
> >the operator (of type Memory -> Value) repeated times for
> >the same memory, making the solution ineficient.
> 
> Agreed. I had the impression that you had difficulties to
> make infix operators for this.

Not really.

> >Then
> >you sugest making the sharing explicit in the code. That
> >works for sharing in the same function definition. The
> >biggest problem with that is that when you do that, you
> >substitute the operators by their implementation:
> >
> >   x .+. y .+. y
> >
> >becomes
> >
> >   let vx = x mem; vy = y mem
> >   in  vx + vy + vy
> >       ^^^^^^^^^^^^
> >
> >That is possible in your example because you know the
> >implementation of the operator .+.
> >
> >   (.+.) a b = \mem -> a mem + b mem
> >
> >What about complex operator definitions hidden in the
> >implementation module of the library? This technique is
> >not feasible for them.
> 
> What about using different instances of the same operator?
> 
> instance + [({#Char},Int)] -> Int
> where (+) e1 e2 = \mem -> e1 mem + e2 mem
> 
> instance * [({#Char},Int)] -> Int
> where (*) e1 e2 = \mem ->  e1 mem * e2 mem
> 
> f x y = x + y + y
> 
> fopt x y = \mem -> let vx = x mem; vy = y mem
>                     in  vx + vy + vy
> 
> now the expressions in the body of the function and its optimized version 
> are syntactical equal.

The problem is not a syntatic one, but semantic. In your
example the addition over operators maps directly as
additions over integers. This makes it easy to go from
operators to integers (I am refering to operators as the
values of the type Operator you use in your example:
:: Operator :== Memory -> Int). When you use the
let expression in fopt in order to share some partial
evaluations,

   let vx = x mem
       vy = y mem
    in vx + vy + vy

you do not call the (+) over operators, but over integers.
You do this in your example because you know the
relation between them:

   instance + [({#Char},Int)] -> Int
       where
       (+) e1 e2 = \mem -> e1 mem + e2 mem

Was this relation a complex one it would not
be feasible to aply this technique. That is the case
in the CALG library.

> This still is not very nice...
> You have to indicate the sharing yourself and you need to have knowledge of 
> the structure of Operator, but not of required instance of +.
> However, I think this is the best you can achieve without memoization.
> 
> I do not see how a referential transparent use of implicit parameters or 
> joining the algebraic expression and the environment solve the memoization 
> problem.

These are not solutions for the memoization problem, but to
my original problem of passing around an environment in
function calls in a way that functions of type

   Env Exp Exp -> Exp

could be thought of as having only two arguments, of
type Exp, allowing it to be sintaticaly a binary
operator. Those alternatives allows the implicit passing
of the environment, as a referentialy transparent dynamic
scoped variable or by attaching it to the other arguments.

Some Haskell implementations (Hugs and GCH) has
implicit parameters as an extension. Then you can hide
the environment parameters from the function calls.
Your example would be rewritten in Haskell (extend
with iplicit parameters as) shown in the attachment below.
The output of this progrmam is
   Int 112

As you can see, the environment is passed around
the function calls and the functions .+. and
.*. are infix operators.

This solution is very good to me, but, unfortunatly,
Clean does not support and there is no plans to support it.
I believe next version of Haskell will incorporate
it. Now it is easy for me to implement CALG in
Haskell (extended with implicit parameters) than in
Clean.

Romildo
-- 
Prof. José Romildo Malaquias <romildo@iceb.ufop.br>
Departamento de Computação
Universidade Federal de Ouro Preto
Brasil

--OgqxwSJOaUobr8KG
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="test.hs"

module Main where

type Mem = [(String,Integer)]

look name [] = error ("No value for " ++ name)
look name ((n,v):r)
    | name == n = v
    | otherwise = look name r

data Exp = Int Integer
         | Var String
           deriving Show

value :: (?env :: Mem) => Exp -> Integer
value (Int x) = x
value (Var n) = look n ?env

infix 5 .+.
infix 6 .*.

(.+.), (.*.) :: (?env :: Mem) => Exp -> Exp -> Exp
x .+. y = Int (value x + value y)
x .*. y = Int (value x * value y)

f :: (?env :: Mem) => Exp -> Exp -> Exp
f x y = x .+. y .*. y

ex = Int 2 .*. f (Int 7) (Int 1 .+. Var "y" .*. Var "z")
     with ?env = [("x",1),("y",2),("z",3)]

main = putStrLn (show ex)

--OgqxwSJOaUobr8KG--