[Caml-list] Wasn't O'Caml a functional language?

[Caml-list] Wasn't O'Caml a functional language?

[Alessandro Baretta]

First of all, allow me to RTFM myself before anybody else 
does. I just spent the last hour or so tracking down a bug 
caused by the "procedural-style" side-effect in Queue.iter: 
the queue is actually emptied by that function. Now, if 
O'Caml is a functional language, and Queue.iter is a 
functional iterator, why is there a need for that very 
counterintuitive side-effect? If I use List.iter on a list, 
I do not expect it to flush my list of all it's contents. 
The same with a Hashtbl.iter, and in general with all 
functional iterators, which are the very heart of the 
standard library.

In my opinion, "The Right Way (TM)" to use datastructures in 
O'Caml and in functional languages in general is to build 
them, iterate non-destructively over them as many times as 
necessary, and finally let the GC reclaim them when they are 
no longer accessible from the live scope. What makes this 
approach much simpler to handle, much more intuitive to 
understand and less intricate to debug, is that data 
structure aliasing does not have to be explicitly taken into 
account. On the other hand, if one uses iterators with 
side-effects and the data structures are aliased--as was my 
case in my application, until I figured out what was going 
wrong--all sorts of weird non-local bugs can appear, and 
tracking them down can take quite a few runs of ocamldebug.

Concluding, let me "break a spear"--as we say in Italian--in 
favor of a purely functional standard library, where such 
datastructures as Queue.t's and the like can be freely 
aliased without a second thought.

Cheers, and back to work...

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Wasn't O'Caml a functional language?

[Alessandro Baretta]

John Gerard Malecki wrote:
> I don't see any side effects in Queue.iter?  Here is the code

Neither do I. I probably just need to retire to buddhist 
monastery in Nepal. Here is the quote from the manual:

* iter f q applies f in turn to all elements of q, from the
* least recently entered to the most recently entered. The >
* queue itself is unchanged.

> Can you better describe the problem?  (Maybe what you're saying is
> that if f is side-effecting then iter acts perversely.)

I sure can: it's just a vast degenerative neurological 
disease. Sorry, my mistake, the side-effect is not in 
Queue.iter. It is in Queue.transfer, which I happen to use 
somewhere down the road in the control flux of the function 
I apply to the Queue. The fact that the main data structure 
in my program has type "data_elem Queue.t Queue.t Queue.t" 
adds to the confusion. The iterator giving me trouble is the 
one acting at the central Queue.t level, and the unwanted 
side_effects are situated at the lower level of nesting 
(data_elem Queue.t).

Anyway, my main claim, although misdirected, in not entirely 
faulty. Queue.transfer can be thought of as analogous to 
List.append. When I write let list = list1 @ list2 I do not 
expect side-effects on list1 or list2.

My most sincere apologies for my previous encephalitic post.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: Wasn't O'Caml a functional language?

[Michaël Grünewald]

Alessandro Baretta <alex@baretta.com> writes:



[...]

> Anyway, my main claim, although misdirected, in not entirely
> faulty. Queue.transfer can be thought of as analogous to
> List.append. When I write let list = list1 @ list2 I do not expect
> side-effects on list1 or list2.

Then you maybe should use Lists, why, if queues have the same behavior than
lists, give them a different name ?
-- 
Michaël Grünewald <michael-grunewald@wanadoo.fr>  - RSA PGP Key ID: 0x20D90C12
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wasn't O'Caml a functional language?

[Pixel]

"Michaël Grünewald" <michael-grunewald@wanadoo.fr> writes:

> Alessandro Baretta <alex@baretta.com> writes:
> 
> [...]
> 
> > Anyway, my main claim, although misdirected, in not entirely
> > faulty. Queue.transfer can be thought of as analogous to
> > List.append. When I write let list = list1 @ list2 I do not expect
> > side-effects on list1 or list2.
> 
> Then you maybe should use Lists, why, if queues have the same behavior than
> lists, give them a different name ?

because using (simply linked) lists as FIFOs is costly?
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wasn't O'Caml a functional language?

[Alessandro Baretta]

Michaël Grünewald wrote:
> Alessandro Baretta <alex@baretta.com> writes:

> 
>>Anyway, my main claim, although misdirected, in not entirely
>>faulty. Queue.transfer can be thought of as analogous to
>>List.append. When I write let list = list1 @ list2 I do not expect
>>side-effects on list1 or list2.
> 
> 
> Then you maybe should use Lists, why, if queues have the same behavior than
> lists, give them a different name ?

They don't have the same behavior, and are not supposed to 
have the same behaviour.

let l = [] in
let l = e1 :: l in
let l = e2 :: l in
let l = e3 :: l in
List.iter f l

is equivalent to
f e3; f e2; fe1

which is not what I need. On the other hand,
let q = Queue.create () in
let _ = Queue.add e1 q in
let _ = Queue.add e2 q in
let _ = Queue.add e3 q in
Queue.iter f q

is equivalent to
f e1; f e2; f e3

which is correct with respect to what I need. This is the 
reason for using Queues. I somehow expected this to be the 
only difference with respect to Lists, and did not suspect 
that some of the functions of the Queue module (other than 
the obvious add and take) had side-effects. I realize that 
"transfer" is a significantly different name than "append", 
and I should have known better than to use it without 
expecting side-effects, but, anyway, I was stumbled on this 
function. And, believe me, it took me quite a while to 
figure out in Ocamldebug/Epeire why in the world my program 
was doing what it was. So let me say, "Long live functional 
iterators which have no side-effects! Down with explicit 
handling of aliasing! " [ ... feel free to add here whatever 
political slogans you like best ;) ]

BTW, picking up on Pixel's comment, I don't really know 
whether Queues are any more efficient than 
lists-used-as-FIFO, although I would expect them to be. I am 
mostly interested in the conciseness of the API.
Queue.iter f q
is much more elegant and readable than the equivalent
List.iter f (List.rev l)

Of course, performance is also important, but the software 
I'm writing will have its bottleneck in IO anyway, so no 
there is no significant advantage to be had by optimising 
the algorithms, other than to increase the fraction of CPU 
idle time, which is already pretty high. Of course, in other 
contexts, performace would matter a lot more.

Cheers,
Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wasn't O'Caml a functional language?

[Alessandro Baretta]

M E Leypold @ labnet wrote:
 >
 > Hello,
 >
 > Alessandro Baretta writes:
 >
 > <...>
 >
 >> is equivalent to f e1; f e2; f e3
 >>
 >> which is correct with respect to what I need. This is
 >> the reason for using Queues. I somehow expected this to
 >> be the only difference with respect to Lists, and did
 >> not suspect that some of the functions of the Queue
 >> module (other than the obvious add and take) had
 >> side-effects. I realize that
 >
 > I'm not so very much surprised. Let's look at stacks. A
 > stack is algebraically equivalent to a list (Queues
 > aren't, that's whay I'm talking about stacks for a
 > moment). ...

Alright. AFAIK, the stack is the fundamental data structure
holding the state of a program in all procedural languages. 
A stack is something very intrinsically procedural in 
nature. A queue is not. From a functional point of view, 
that is, if you disregard "operations" on queues, and forget 
how they are built -- for they are built in a sequential, as 
opposed to recursive, manner -- you can just state that a 
queue is a sequence of data whose iterators act upon in 
direct, as opposed to inverse, order of construction. Of 
course, such a behavior can be achieved using lists and a 
recursive data-structure-traversal to generate them, but for 
some uses a data type with a FIFO nature is just easier to 
imagine and work with.

When I looked at the Queue.transfer function, I was not 
looking for a means of implementing a transition in an 
abstract state machine. I was looking for an implementation 
of the abstract operation of concatenation on the free 
monoid of the sequences of elementary data tokens of a given 
type. Alright, "transfer" is a name that quite transparently 
maps to something a little different, but somehow I just 
overlooked the side-effect.

 > Now, queues are containers, so I'd expect side-effects
 > and in-place update of state.
In computer science, a data type is usually defined as a set 
of values and a set of operations on it. This definition 
coincidentally is the definition of an algebraic structure. 
The algebraic structure I need to work with consists of the 
set of sequences of elementary data tokens. So, you see, I'm 
not really interested in the state model for Queues.

 > Of course this is all very
 > imperative and not functional, but in a sense all ML
 > dialects seem not to be pure in that respect. (OK, don't
 > shoot me for the use of 'pure' here: I'm not a computer
 > scientist, so I might use the word wrongly).

BANG! ;) Yes, ML is not purely functional, whatever that 
means, because you can show that "pure" lambda calculus 
(having only the lamda-abstraction operator and function 
application) has the full expressive power of a full-fledged 
procedural language. You can simulate let-bindings with 
lambda-abstraction and function application ( let t = M in N 
<=> (\t.N) M). You can simulate operation sequences with let 
bindings (let foo1 = M1 N1 in let foo2 = M2 N2 in ...). You 
can simulate any loop with a while loop and a while loop 
with with recursion (letrec f = if M then N else f). 
Finally, you can simulate recursion with lambda-abstraction 
and function application 
(http://www.enseignement.polytechnique.fr/informatique/M2/lp/a1.html).

 > As far as your original problem is concerned: I think a
 > purely functional and efficient 'queue' is not so easy to
 > be implemented: you can't share the tail in such a nice
 > way as lists do. At least: not as easy.
 >
 > Regards -- Markus

On the contrary, if no destructive operations exist on a 
datastructure, aliasing is never a problem. However, the 
meaning of "destructive" has to be defined.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners