ADT (monadic) approach to destructive update 
Author Message
 ADT (monadic) approach to destructive update

I've been reading about monads (Phil Wadler's paper "Comprehending Monads")
and how it is possible to encapsulate destructive operations in
a purely functional abstract data type (Paul Hudak's paper "How to
have your state and munge it too").
These techniques have apparently been been implemented by a couple
of the Haskell implementations to provide "monadic I/O", and
the papers discuss their use for destructive array update.

My question is this: can these techniques address the problem of destructive
update in general, or are they limited to essentially _describing_
destructive actions which must be implemented in *other* languages?
It seems to me that the technique of using mutable abstract data types
will only be able to provide destructive update for a fixed set of
data types provided by the implementation, which in a pure functional
language would not be extensible by the user.

What do people think about linear type systems as an alternative?
They appear to have the advantage of providing destructive update in a
way that is extensible to user-defined types. MADTs have the
advantage of much simpler implementation (ie. a simpler language) although
the down-side of this seems to be that the resulting programs are
somewhat more complex.

--



Fri, 19 Jan 1996 18:19:56 GMT  
 ADT (monadic) approach to destructive update

Quote:
> ... can [monads] address the problem of destructive update in
> general, or are they limited to essentially _describing_
> destructive actions which must be implemented in *other* languages?

Not sure this answers your question, but you can certainly use monads
in higher-order imperative languages (e.g., Standard ML) to get better
control over the destructive operations.  Monads aren't limited to
the pure (applicative) arena.

    -- Jim Sasaki



Sun, 21 Jan 1996 00:06:10 GMT  
 ADT (monadic) approach to destructive update

Quote:
James HENDERSON) writes:
> I've been reading about monads (Phil Wadler's paper "Comprehending  
Monads")
> and how it is possible to encapsulate destructive operations in
> a purely functional abstract data type (Paul Hudak's paper "How to
> have your state and munge it too").
> These techniques have apparently been been implemented by a couple
> of the Haskell implementations to provide "monadic I/O", and
> the papers discuss their use for destructive array update.

> My question is this: can these techniques address the problem of  
destructive
> update in general, or are they limited to essentially _describing_
> destructive actions which must be implemented in *other* languages?
> It seems to me that the technique of using mutable abstract data types
> will only be able to provide destructive update for a fixed set of
> data types provided by the implementation, which in a pure functional
> language would not be extensible by the user.

I think you are looking at it the wrong way.  First off, the notion of
"destructive update" is best captured by an operational semantics,
whether it be for an imperative language or a functional language.
After all, I could give an operational semantics for an imperative
language that always copied the entire state when an assignment occurred
(but of course you would not like it!).  I personally believe that
programmers rely quite heavily on operational semantics, even in pure
functional language without monads, MADT's, or whatever.  For example,
if I know that the execution of a function "f" is computationally
expensive, I will most likely write something like:

  (x, x) where x = f 1

rather than:

  (f 1, f 1)

even though the latter is shorter, and especially if I'm interested in  
efficient PORTABLE code (i.e. not implementation dependent).

In my paper that you mention above, I give an operational semantics
for a certain class of ADT's that can be implemented as efficiently
as we would expect from an imperative language.  The programmer
must rely on that operational semantics to reason about efficiency,
and an implementation is obliged to satisfy that semantics.  This is
not at all different from the situation with an imperative language.

As to your question about what set of "destructive" primitives to
include in a language, well, again, the situation is no different
from an imperative language.  A typical imperative language will
provide, for example, mutable variables and mutable arrays, at a
minimum, and in a functional language we could do the same.  An
imperative language might also include mutable lists from which
graphs and other linked data structures could be built, and again,
we could do the same in a functional language.

Quote:
> What do people think about linear type systems as an alternative?
> They appear to have the advantage of providing destructive update in a
> way that is extensible to user-defined types. MADTs have the
> advantage of much simpler implementation (ie. a simpler language)  
although
> the down-side of this seems to be that the resulting programs are
> somewhat more complex.

I think linear type systems are also a very viable solution to the
overall problem, but more work needs to be done (in both arenas) before
we can say which is best.  It's not clear, for example, that linear
programs are necessarily less complex -- there is still a degree of
threading of state that has to happen (programs can become cumbersome),
and one must understand a more complex type system.

-- Paul Hudak

Professor Paul Hudak
Department of Computer Science
Yale University
New Haven, CT 06520
(203) 432-4715



Sat, 27 Jan 1996 23:55:13 GMT  
 ADT (monadic) approach to destructive update

Quote:

> For example,
> if I know that the execution of a function "f" is computationally
> expensive, I will most likely write something like:

>   (x, x) where x = f 1

> rather than:

>   (f 1, f 1)

I presume Paul means computationally expensive in time rather than space.
If it was the latter, this might have the potentiality to produce a big
space leak!!

--

Tony Davie               Department of Mathematical and Computational
Sciences
Tel: +44 334 63257       St.Andrews University
Fax: +44 334 63278       North Haugh

                         Scotland
                         KY16 9SS



Sun, 28 Jan 1996 22:21:57 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Instantiating a generic ADT from another ADT

2. what is destructive update?

3. ACQUISITION REFORM UPDATE - OPEN SYSTEM APPROACH

4. Linguistic approaches to AI Linguistic Approaches to Artificial Intelligence

5. Linguistic approaches to AI Linguistic Approaches to Artificial Intelligence

6. How does one mix monadic screen IO and monadic disk IO?

7. Are "destructive" functions really destructive?

8. is "destructive" function really destructive?

9. Monadic Roll and generating normal distributions in APL

10. monadic verb with Dot (J)

11. Dyadic or monadic?

12. higher-level monadic programming

 

 
Powered by phpBB® Forum Software