[Haskell-cafe] Re: Language support for imperative code. Was: Re: monad subexpressions

[apfelmus]

Brian Hulley schrieb:
> apfelmus wrote:
>> However, most "genuinely imperative" things are often just a building
>> block for a higher level functional model. The ByteString library is a
>> good example: the interface is purely functional, the internals are
>> explicit memory control. It's a bad idea to let the internal memory
>> control leak out and pollute an otherwise purely functional program with
>> IO-types.
> 
> Regarding the quote above, if the API must hide explicit memory control 
> from the user the only way I can see of doing this would be to use 
> (unsafePerformIO), which really is unsafe since Haskell relies on the 
> fact that mutable operations can't escape from the IO monad in order to 
> get away with not having to impose a value restriction as in ML.

Indeed, Data.ByteString makes heavy use of unsafePerformIO and
inlinePerformIO. This is safe since it's just used for efficient memory
access and (de-)allocation, the ByteStrings themselves are immutable.

> If you don't use (unsafePerformIO), then the slightest need for mutable 
> data structures pollutes the entire interface.

Well, any code that wants to mutate or read this data structure has to
announce so in the type signature. However, it's debatable whether
certain forms of "mutation" count as pollution. In fact, the simplest
"mutation" is just a function  s -> s  . Haskell is throughly "polluted"
by such "mutations":

   (3+)         :: Int -> Int
   ([1,2]++)    :: [Int] -> [Int]
   insert "x" 3 :: Map String Int -> Map String Int

Of course, from the purely functional point of view, this is hardly
perceived as mutation since the original value is not changed at all and
still available. In other words, the need to "change" a value doesn't
imply the need to discard (and thus mutate) the old one.

Mutable data structures in the sense of ephemeral (= not persistent = 
update in-place) data structure indeed do introduce the need to work in 
ST since the old version is - by definition - not available anymore. 
This may be the right thing to do when the data structure is inherently 
used in a single-threaded fashion. However, most used-to-be ephemeral 
data structures have very good persistent counterparts in Haskell. In 
the end, the type just reflects the inherent difficulty of reasoning 
about ephemeral data structures. And that's what the quoted paper 
illustrates: persistent data structures are much easier to deal with.

> For example in the excellent paper you quoted
> 
>  N. Ramsey and J. Dias.
>  An Applicative Control-Flow Graph Based on Huet's Zipper
>  http://www.eecs.harvard.edu/~nr/pubs/zipcfg-abstract.html 
> <http://www.eecs.harvard.edu/%7Enr/pubs/zipcfg-abstract.html>
>
> the authors are pleased to have found an "Applicative" solution, and 
> indeed their solution has many useful and instructive aspects. However 
> on page 111, hidden away in the definition of their API function to 
> create a label, is a call to (ref 0) !!!! ;-) The equivalent 
> implementation in Haskell would completely destroy all hope of using 
> this in a pure context and force all use of the API into the IO monad.

I don't know enough ML or have the background to judge whether this  ref 
  is really necessary, but I doubt that it can't be designed away.

> Haskell is designed so that any attempt at abstracting mutable
 > local state will infect the entire program

Depends on "local". In general, I think is a good thing. The type 
reflects how difficult your program really is, nothing more, nothing 
less. That's how it is: persistent data and prue functions are sooo much 
easier to reason about. Implicit side effects just sweep the difficulty 
under the carpet. (I imagine a tool that makes implicit side effects 
explicitly visible in the types of say C or ML programs. I guess that 
people would scream whole nights when seeing the output of this tool on 
their programs and thus discovering how complicated the code really is 
... Well, maybe not since they're used to it during debugging anyway.)

But if the state is really local, no infection of the entire program 
takes place! The best example is probably indeed the Haskell Graphics 
library. The are pure functions for constructing graphics

   over    :: Graphic -> Graphic -> Graphic
   polygon :: [Point] -> Graphic

and some IO-infected functions to draw those onto the screen

   drawInWindow :: Window -> Graphic -> IO ()

Now,  Graphic  may be implemented as an abstract data type and 
drawInWindow  does the workload of interpreting it. Or, and that's how 
HGL currently implementes it, it can be an IO-action that encodes how to 
draw it

   type Graphics = Draw ()
                ~= (Brush,Font,Pen) -> IO ()

That is, every graphic is "infested" with IO but that doesn't spread to 
the API. (It does a bit with  selectBrush  but that can be corrected.)

 > (modulo use of a highly dangerous function whose
> semantics is entirely unclear, depending on the vagaries of evaluation 
> strategy of the particular compiler)

(yes, unsafePerformIO clearly isn't for ephemeral data structures.)

> For example consider a simple GUI

Ah, the dreaded functional GUI problem. Yes, I agree that a good purely 
functional way of declaring a GUI has not been discovered yet, the 
signals and streams somehow miss something important.

 > I've wasted at
 > least a whole year of sleepless nights trying to work out how to
 > represent an efficient GUI without using mutable data, and the feeling
 > that there should be a pure solution made me abandon a perfectly
 > workable imperative GUI that I started 18 months ago, that if I'd
 > written it in any other language without this pure/impure conundrum,
 > would have made me very happy with it.

It indeed seems that the "mathematics" behind GUIs are inherently 
difficult and the easiest framework to declare GUIs _for now_ is an 
imperative one. That doesn't mean that a simpler one doesn't exist. Note 
that word _declare_: you don't want to mutate state a priori, you want 
to say what is displayed when and somehow describe the data 
dependencies. Once a domain specific language to declare GUIs is found, 
I'm sure that it can naturally be embedded in Haskell.

> For example consider a simple GUI with 2 edit widgets, a splitter,
 > and a single buffer that contains the text being edited. The idea
> is that you  should be able to use either edit widget to interact
 > with the same buffer eg to edit at different locations in the
 > buffer. A simple imperative solution might be something like:
> 
>    main = do
>            buffer <- createBuffer
>            edit1 <- createEdit buffer
>            edit2 <- createEdit buffer
>            splitter <- createSplitter (wrapWidget edit1) (wrapWidget edit2)
>            runMessageLoopWith splitter
> 
> Here it's really clear what's happening, and different objects in the 
> program correspond exactly to how I think about what I'm trying to do ie 
> I want to create individual objects with identity and then plug them 
> together. I don't want to have to bother about passing state around, or 
> having to define a new data type every time I want a different 
> configuration of widgets. Thus the ability to abstract mutable state 
> gives to my mind by far the best solution.

I'm not sure whether mutable state is the real goodie here. I think it's 
the ability to indpendently access parts of a compound state. In other 
words, the IORef created by  buffer  is a part of the total program 
state but you can access it independently. There is a functional idiom 
for that, see also

   Sander Evers, Peter Achten, and Jan Kuper. "A Functional Programming
   Technique for Forms in Graphical User Interfaces".
   http://www.st.cs.ru.nl/papers/2005/eves2005-FFormsIFL04.pdf


 > apfelmus wrote:
 >> However, most "genuinely imperative" things are often just a building
 >> block for a higher level functional model.

Thanks to your response, I think I can better articulate what I mean: 
with "purely functional", I mean "declarative", i.e. the ability to 
write down equations of how different things interact with each other 
and thus to abstract away their implementation. For example,

- For Graphics, I want to build a graphic from smaller ones and then 
draw it. I don't want to know how drawing is implemented and what 
mutable state might be involved.
- For a GUI, I want to write down the data dependencies and a library 
converts this to a mesh of mutable state.

That's what I mean with "higher level functional model". Syntactic sugar 
for applying monadic actions doesn't help with that. In fact, it intends 
to make it easier to write examples and miss the pattern/model behind. 
Likewise, allowing impure functions -> doesn't help with formulating or 
finding a model at all. Rather, it makes describing the model more 
error-prone.

Of course, I want to implement the imperative machinery too. But most 
often, deriving it from the underlying model is straightforward.

Regards,
apfelmus