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

[Alessandro Baretta <alex@baretta.com>]

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