Hudak state emulation discussion - can you give me some idea?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Hudak state emulation discussion - can you give me some idea?

Girish Bhat
Hi Everyone,

I was going through the classic Hudak paper "Conception, Evolution,
and Application of Functional Programming".
Probably the most valuable part is towards the end where he talks
about how state is represented in Haskell.
On Page 48 of the PDF (page 406 of the ACM Computing survey volume),
he gives the following equations
"For expository purposes we would like to make the state as implicit
as possible, and thus we express the result as a composition of
higher-order functions. To facilitate this and to make the result look
as much like the original program as possible, we define the following
higher-order infix operators and functions":


1 f:=g =\s -> +fs(gs)

2? ?f;g =\s -> g(fs)=\s-+fs(gs)

3? ?f;g =\s -> g(fs)

4 goto f = f

5 f+?g=\s-+fs+gs

6 f<?g=\s-+fs<gs

7 if? p c = \s + (if (p s) then (c s) else s)



Unfortunately I am unable to parse/understand what he is doing here.
My closure understanding too seems to be wonky. :)
Would someone be kind enough to translate each of the above into plain
english and explain how to read such eqns in the future?

thanks!
Reply | Threaded
Open this post in threaded view
|

Re: Hudak state emulation discussion - can you give me some idea?

Benjamin L. Russell
On Tue, 17 Mar 2009 14:32:24 +0530, Girish Bhat
<[hidden email]> wrote:

>Hi Everyone,
>
>I was going through the classic Hudak paper "Conception, Evolution,
>and Application of Functional Programming".
>Probably the most valuable part is towards the end where he talks
>about how state is represented in Haskell.
>On Page 48 of the PDF (page 406 of the ACM Computing survey volume),
>he gives the following equations
>"For expository purposes we would like to make the state as implicit
>as possible, and thus we express the result as a composition of
>higher-order functions. To facilitate this and to make the result look
>as much like the original program as possible, we define the following
>higher-order infix operators and functions":
>
>
>1 f:=g =\s -> +fs(gs)
>
>2? ?f;g =\s -> g(fs)=\s-+fs(gs)
>
>3? ?f;g =\s -> g(fs)
>
>4 goto f = f
>
>5 f+?g=\s-+fs+gs
>
>6 f<?g=\s-+fs<gs
>
>7 if? p c = \s + (if (p s) then (c s) else s)
>
>
>
>Unfortunately I am unable to parse/understand what he is doing here.
>My closure understanding too seems to be wonky. :)
>Would someone be kind enough to translate each of the above into plain
>english and explain how to read such eqns in the future?

(FYI, there is a copy of the above-mentioned paper that doesn't
require an ACM account available at
http://www.cs.berkeley.edu/~jcondit/pl-prelim/hudak89functional.pdf.)

Hudak is just defining a series of higher-order infix operators and
functions.  (You have made some notational errors in the
above-mentioned notation, so I am revising it to match the paper as
below.)  A backslash denotes a lambda symbol; i.e., whatever
immediately follows the lambda is a parameter in the following
equation.  Specifically:  

>1 f := g =\s -> f s (g s)

In other words, the infix operator ':=' works between functions f and
g such that lambda s -> f s (g s).

>2 f ; g = \s -> g (f s)

In other words, the infix operator ';' works between functions f and g
such that lambda s -> g (f s).

>3? ?f;g =\s -> g(fs)

I couldn't find this equation on p. 406 of the volume; where did you
find it?

>4 goto f = f

In other words, the function "goto" applied to f is defined as simply
f.

>5 f +' g = \s -> f s + g s

In other words, the infix operator '+'' works between functions f and
g such that lambda s -> f s + g s.

>6 f <' g = \s -> f s < g s

In other words, the infix operator '<'' works between functions f and
g such that lambda s -> f s < g s.

>7 if' p c = \s -> (if (p s) then (c s) else s)

In other words, the function "if'" applied to functions p and c is
such that lambda p c -> (if (p s) then (c s) else s).

Hope this helps....

-- Benjamin L. Russell
--
Benjamin L. Russell  /   DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile:  +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto."
-- Matsuo Basho^

Reply | Threaded
Open this post in threaded view
|

Re: Hudak state emulation discussion - can you give me some idea?

Girish Bhat
> (FYI, there is a copy of the above-mentioned paper that doesn't
> require an ACM account available at
> http://www.cs.berkeley.edu/~jcondit/pl-prelim/hudak89functional.pdf.)
>
> Hudak is just defining a series of higher-order infix operators and
> functions.  (You have made some notational errors in the
> above-mentioned notation, so I am revising it to match the paper as
> below.)  A backslash denotes a lambda symbol; i.e., whatever

Sorry about that.

> >3? ?f;g =\s -> g(fs)
>
> I couldn't find this equation on p. 406 of the volume; where did you
> find it?
>

Again my transcription error.

> In other words, the function "if'" applied to functions p and c is
> such that lambda p c -> (if (p s) then (c s) else s).
>
> Hope this helps....
>
Thanks! It does. I think what threw me was that while there is enough
redundancy in what he states for someone more clever than me, he would
have explicitly stated before hand  that he was defining the operators
[:=], [+'], ['if] etc.:)

thanks again.
Reply | Threaded
Open this post in threaded view
|

Re: Hudak state emulation discussion - can you give me some idea?

Benjamin L. Russell
On Wed, 18 Mar 2009 13:02:34 +0530, Girish Bhat
<[hidden email]> wrote:

>>[...]
>>
>> Hope this helps....
>>
>Thanks! It does. I think what threw me was that while there is enough
>redundancy in what he states for someone more clever than me, he would
>have explicitly stated before hand  that he was defining the operators
>[:=], [+'], ['if] etc.:)

But he did; specifically, on pages 405 (the previous page) to 406 of
the volume, Hudak writes as follows:

>For expository purposes we would like to
>make the state as implicit as possible, and
>thus we express the result as a composition
>of higher-order functions. To facilitate this
>and to make the result look as much like
>the original program as possible, we define
>the following higher-order infix operators
>and functions(22):

So he did in fact explicitly state beforehand that he was defining
those operators.

-- Benjamin L. Russell
--
Benjamin L. Russell  /   DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile:  +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto."
-- Matsuo Basho^

Reply | Threaded
Open this post in threaded view
|

Re: Hudak state emulation discussion - can you give me some idea?

Will Ness-2
Benjamin L. Russell <DekuDekuplex <at> Yahoo.com> writes:

>
> On Wed, 18 Mar 2009 13:02:34 +0530, Girish Bhat
> <girishbhat6620 <at> gmail.com> wrote:
>
> >>[...]
> >>
> >Thanks! It does. I think what threw me was that while there is enough
> >redundancy in what he states for someone more clever than me, he would
> >have explicitly stated before hand  that he was defining the operators
> >[:=], [+'], ['if] etc.:)
>
> But he did; specifically, on pages 405 (the previous page) to 406 of
>
> So he did in fact explicitly state beforehand that he was defining
> those operators.
>

What he didn't do, is specify the precedences associativities of these
operators.

It seems that for the definitions to make sense, together with the code that
follows them in the article, the fixity declarations ought to be as e.g.


infixl 8 +'
infix  8 <'
infix  7 :=
infixl 6 ;              -- infixr is good too

(p; q) s = q (p s)      -- (;)  = CB  -- flip (.)
(x:=f) s = x s (f s)    -- (:=) = S
goto f s = f s          -- id   = I
(f+'g) s = f s + g s
(f<'g) s = f s < g s
if' p c s = if (p s) then (c s) else s
x' (a,b) = a
i' (a,b) = b


so that ( x:=f ; i:=g ; x:=h )
would parse as ( ( (x:=f) ; (i:=g) ) ; (x:=h) ) , so that

( x:=f ; i:=g ; x:=h ) s = (x:=h) . (i:=g) . (x:=f) $ s

The types involved would be as follows. 's' denotes state; (_:=_) denote state
transformers of type (s -> s) (for them to be composable). 'x' and 'f' in
(x:=f) are

f :: s -> v         -- value producer (including x' and i')
x :: s v -> s       -- state updater (with the new value)

so that the combination (x:=f) s = x s (f s) has 'f' produce a new value
and 'x' update its supplied state with it:

(x:=f) s = s' where v = f s; s' = x s v

The whole combination as presented in the article actually defines a new
function to perform all these activities, and would be defined as

prog = x := const 1 ; i := const 0 ; loop
       where loop = x := f ; i := i' +' const 1 ;
                    if' (i' <' const 10) (goto loop)

and used as

prog initState where initState = (0,0)

or something like that. Which is all very reminiscent of monad, a "programmable
semicolon".

Cheers,


Reply | Threaded
Open this post in threaded view
|

Re: Hudak state emulation discussion - can you give me some idea?

Will Ness-2
Will Ness <will_n48 <at> yahoo.com> writes:

> infixl 8 +'
> infix  8 <'
> infix  7 :=
> infixl 6 ;              -- infixr is good too
>
> (p; q) s = q (p s)      -- (;)  = CB  -- flip (.)
> (x:=f) s = x s (f s)    -- (:=) = S
> goto f s = f s          -- id   = I
> (f+'g) s = f s + g s
> (f<'g) s = f s < g s
> if' p c s = if (p s) then (c s) else s
> x' (a,b) = a
> i' (a,b) = b
>

Er, forgot to include the two state updaters of the article,

x (a,b) v = (v,b)
i (a,b) v = (a,v)