* Functional composition operator?
@ 1998-12-08 5:23 John Whitley
1998-12-08 17:02 ` Pierre Weis
0 siblings, 1 reply; 12+ messages in thread
From: John Whitley @ 1998-12-08 5:23 UTC (permalink / raw)
To: caml-list
Andrew Kay <akay@sharp.co.uk> wrote, in the caml-list archives:
> We are in the process of converting our Caml code into OCaml, and
> have a problem choosing an infix syntax for function composition
> [...] What do other OCaml people use for function composition? Is
> there standard emerging?
I found no answer in the archives, so I'd like to raise the same
question again: is there a consensus for choice of infix composition
operator? Failing that, is there some design principle that warranted
its omission?
Thanks,
John Whitley
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Functional composition operator?
1998-12-08 5:23 Functional composition operator? John Whitley
@ 1998-12-08 17:02 ` Pierre Weis
1998-12-08 21:52 ` John Harrison
0 siblings, 1 reply; 12+ messages in thread
From: Pierre Weis @ 1998-12-08 17:02 UTC (permalink / raw)
To: John Whitley; +Cc: caml-list
> Andrew Kay <akay@sharp.co.uk> wrote, in the caml-list archives:
> > We are in the process of converting our Caml code into OCaml, and
> > have a problem choosing an infix syntax for function composition
> > [...] What do other OCaml people use for function composition? Is
> > there standard emerging?
>
> I found no answer in the archives, so I'd like to raise the same
> question again: is there a consensus for choice of infix composition
> operator? Failing that, is there some design principle that warranted
> its omission?
>
> Thanks,
> John Whitley
The normal infix operator should be a o, or more precisely a $\circ$
symbol. Unfortunately if we add o in the syntax of Caml, this will be
a bit strange to have this identifier as an infix operation (moreover
this implies difficult to explain syntax errors in programs).
In fact we discourage the usage of functional composition as a general
programming tool, since:
-- it only save a few characters in programs
(Compare
let h = f o g
with
let h x = f (g x);;)
-- it breaks the polymorphism
(if defined as
let h = f o g
h is not generalized, since its definition is a function
application, whereas inline expansion of functional composition
let h x = f (g x)
being the definition of a function is properly generalized.)
-- it is not so clear, especially in case of composition of curried
functions
(Consider
let f x y z = x + y + z
then the compositions
f o (f 2 3)
or (f 1) o (f 2 3))
It is still possible to define a composition operator to use in
trivial cases. So you may choose any multi-character infix operator
such as ++, if you really need functional composition.
Best regards,
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Functional composition operator?
1998-12-08 17:02 ` Pierre Weis
@ 1998-12-08 21:52 ` John Harrison
1998-12-09 10:58 ` Pierre Weis
0 siblings, 1 reply; 12+ messages in thread
From: John Harrison @ 1998-12-08 21:52 UTC (permalink / raw)
To: caml-list; +Cc: John.Harrison
Pierre Weis writes:
| In fact we discourage the usage of functional composition as a general
| programming tool
A very bad idea, in my opinion.
| -- it only save a few characters in programs
| (Compare
| let h = f o g
| with
| let h x = f (g x);;)
| -- it breaks the polymorphism
| (if defined as
| let h = f o g
| h is not generalized, since its definition is a function
| application, whereas inline expansion of functional composition
| let h x = f (g x)
| being the definition of a function is properly generalized.)
These alternatives are not semantically equivalent. If f and g are
complicated expressions that can be further evaluated, it is often
highly undesirable to perform the evaluation every time h is called,
which is what "let h x = f(g x)" entails.
John.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Functional composition operator?
1998-12-08 21:52 ` John Harrison
@ 1998-12-09 10:58 ` Pierre Weis
1998-12-09 17:17 ` John Harrison
0 siblings, 1 reply; 12+ messages in thread
From: Pierre Weis @ 1998-12-09 10:58 UTC (permalink / raw)
To: John Harrison; +Cc: caml-list
> | In fact we discourage the usage of functional composition as a general
> | programming tool
>
> A very bad idea, in my opinion.
I'm not sure I got the point here. Why is it a very bad idea ?
Do you consider FP style programming the right functional programming style ?
> | -- it only save a few characters in programs
> | (Compare
> | let h = f o g
> | with
> | let h x = f (g x);;)
> | -- it breaks the polymorphism
> | (if defined as
> | let h = f o g
> | h is not generalized, since its definition is a function
> | application, whereas inline expansion of functional composition
> | let h x = f (g x)
> | being the definition of a function is properly generalized.)
>
> These alternatives are not semantically equivalent. If f and g are
> complicated expressions that can be further evaluated, it is often
> highly undesirable to perform the evaluation every time h is called,
> which is what "let h x = f(g x)" entails.
Right, if you consider that efficiency has something to do with the
semantics, which is not the classical acceptation of this term. To be
precise, if f and g are side-effect free, these alternatives are
indeed ``semantically equivalent'' in the classical view of semantics
(same answer). Anyway, I was implicitely assuming that f and g were
functions, and h was invariant by eta-expansion. In my mind, if h is
not invariant by eta-expansion, the program is hard to read and hard
to understand. Anyway, if f and g are not mere functions but ``very
complicated expressions'' the program is likely to be clearer if you
bind these expressions with a let and give them a name, instead of
composing these complex expressions inline. Let alone the case when
these expressions involve side-effects: then, if you still insist at
composing them on the fly, you get an order of evaluation dependant
program and this must be carefully avoided. In conclusion, if you
freely mix inline composition, side-effects and partial evaluation you
get very complex programs, hard to understand and hard to
maintain. That's my experience in maintaining and developping a
compiler written with that style, using a free mixing of composition,
partial evaluation, and continuations.
Anyway, if you can manage the additional complexity, there is no
problem at using a highly ``composing'' style in Caml. However, in my
mind, it is not a good idea to promote this style, especially for the
working programmer.
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Functional composition operator?
1998-12-09 10:58 ` Pierre Weis
@ 1998-12-09 17:17 ` John Harrison
1998-12-11 13:57 ` Pierre Weis
0 siblings, 1 reply; 12+ messages in thread
From: John Harrison @ 1998-12-09 17:17 UTC (permalink / raw)
To: Pierre Weis; +Cc: Don Syme, John Harrison, caml-list
| > | In fact we discourage the usage of functional composition as a general
| > | programming tool
| >
| > A very bad idea, in my opinion.
|
| I'm not sure I got the point here. Why is it a very bad idea ?
| Do you consider FP style programming the right functional programming style ?
The whole point of a higher order functional language is to treat functions
(more) on a par with other values. Therefore it seems wrongheaded to seek
to discourage programmers from using one of the most basic operations on
functions.
| > These alternatives are not semantically equivalent. If f and g are
| > complicated expressions that can be further evaluated, it is often
| > highly undesirable to perform the evaluation every time h is called,
| > which is what "let h x = f(g x)" entails.
|
| Right, if you consider that efficiency has something to do with the
| semantics, which is not the classical acceptation of this term. To be
| precise, if f and g are side-effect free, these alternatives are
| indeed ``semantically equivalent'' in the classical view of semantics
| (same answer).
Well, even for side-effect-free expressions, the difference in efficiency
could be decisive in practical terms. And if you do use side effects it
matters even more.
| Anyway, I was implicitely assuming that f and g were
| functions, and h was invariant by eta-expansion. In my mind, if h is
| not invariant by eta-expansion, the program is hard to read and hard
| to understand. Anyway, if f and g are not mere functions but ``very
| complicated expressions'' the program is likely to be clearer if you
| bind these expressions with a let and give them a name, instead of
| composing these complex expressions inline. Let alone the case when
| these expressions involve side-effects: then, if you still insist at
| composing them on the fly, you get an order of evaluation dependant
| program and this must be carefully avoided.
It depends on what you mean by order of evaluation. If you mean whether
"f" or "x" gets evaluated first in "f(x)", then I agree. But the fact
that the body of a function is not evaluated till it gets its argument
is basic to an ML-like functional language, and a dependence on this is not
at all something to be avoided. On the contrary, a serious use of side
effects requires an understanding of just when things get evaluated, which
is a good reason why the combination of side effects and a lazy language is
unusual.
Here is a simple example (from theorem proving, funnily enough) where
composition seems to me natural and where partial evaluation is important.
let rule = rewrite[theorems2] o rewrite[theorems1];;
Typically, the partial evaluation of "rewrite[theorems?]" is critical
because it builds a data structure from the theorems before starting
the rewrite.
| In conclusion, if you freely mix inline composition, side-effects and
| partial evaluation you get very complex programs, hard to understand and
| hard to maintain. That's my experience in maintaining and developping a
| compiler written with that style, using a free mixing of composition,
| partial evaluation, and continuations.
I wasn't necessarily proposing such a ragbag. But as Don Syme has pointed
out, there are many perfectly natural and disciplined ways of using side
effects within globally functional code.
| Anyway, if you can manage the additional complexity, there is no
| problem at using a highly ``composing'' style in Caml. However, in my
| mind, it is not a good idea to promote this style, especially for the
| working programmer.
I don't really know what you mean by "working programmer". If you mean
"programmer who writes the same kinds of programs as I do", then it's
a poor foundation for a panoptic view of the field. I'm happy for
people to avoid composition if that's what they want. However I don't like
the idea of discouraging new programmers from using it even when it
could be very helpful and natural.
John.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Functional composition operator?
1998-12-09 17:17 ` John Harrison
@ 1998-12-11 13:57 ` Pierre Weis
0 siblings, 0 replies; 12+ messages in thread
From: Pierre Weis @ 1998-12-11 13:57 UTC (permalink / raw)
To: John Harrison; +Cc: caml-list
[...]
> I wasn't necessarily proposing such a ragbag. But as Don Syme has pointed
> out, there are many perfectly natural and disciplined ways of using side
> effects within globally functional code.
I think we agree on the whole thing in fact: the problem is to get
the most readable and clearest program we can write.
> [...] I'm happy for
> people to avoid composition if that's what they want. However I don't like
> the idea of discouraging new programmers from using it even when it
> could be very helpful and natural.
You're absolutely right. The more natural the better.
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
1998-12-08 18:08 Andrew Kay
1998-12-08 20:32 ` John Prevost
@ 1998-12-09 16:17 ` Anton Moscal
1 sibling, 0 replies; 12+ messages in thread
From: Anton Moscal @ 1998-12-09 16:17 UTC (permalink / raw)
To: Andrew Kay; +Cc: caml-list
On Tue, 8 Dec 1998, Andrew Kay wrote:
> From: John Whitley <whitley@cse.buffalo.edu>
> > is there a consensus for choice of infix composition operator?
>
> In the end we settled on >> and << for forward and reverse
> composition respectively, satisfying the equations:
>
> (f << g) x = f (g x) = (g >> f) x
In camlp4 << and >> are used as quotes for invocation of quotation
expander. Your proposals will interfere with camlp4. I propose <<<
and >>> (this also leads to problem with camlp4, but this issue can be
solved).
Regards,
Anton
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
@ 1998-12-09 12:00 Don Syme
0 siblings, 0 replies; 12+ messages in thread
From: Don Syme @ 1998-12-09 12:00 UTC (permalink / raw)
To: 'Pierre Weis', John.Harrison; +Cc: caml-list
> Anyway, if you can manage the additional complexity, there is no
> problem at using a highly ``composing'' style in Caml. However, in my
> mind, it is not a good idea to promote this style, especially for the
> working programmer.
I think it simply depends on what you're doing: highly symbolic work like
theorem proving certainly benefits from a compositional style, but for
anything involving complex state control (interfaces, objects, networking,
i/o, whatever) it is not so appealing. I think the latter tasks are what
Pierre means by "the working programmer" -- (a rather loaded term in the ML
world? ;-) )
> Let alone the case when
> these expressions involve side-effects: then, if you still insist at
> composing them on the fly, you get an order of evaluation dependant
> program and this must be carefully avoided.
Some invisible uses of side effects are highly compatible with a functional
style, e.g. memoizing and building tables based on an environment, and
certainly John uses these effectively in his programs. Externally visible
effects are, of course, to be avoided when using a compositional approach,
as Pierre suggests.
So you're both right, and that's just why CaML is so appealing: when doing
structural data manipulations it supports the functional model, but it also
supports state-based programming in a very traditional fashion (mutable
record fields, objects, arrays, for-loops, while-loops, begin-end statements
all being part of this). For example, I would teach both styles as part of
a CaML programming course, and I frequently use both styles in different
modules of the one program.
Don
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
1998-12-08 18:08 Andrew Kay
@ 1998-12-08 20:32 ` John Prevost
1998-12-09 16:17 ` Anton Moscal
1 sibling, 0 replies; 12+ messages in thread
From: John Prevost @ 1998-12-08 20:32 UTC (permalink / raw)
To: caml-list
On Tue, 8 Dec 1998, Andrew Kay wrote:
> In the end we settled on >> and << for forward and reverse
> composition respectively, satisfying the equations:
{...}
> We're still interested to know if other people have different approaches.
This seems to be a very reasonable approach! I'd been thinking recently
about this very question, and also about reverse composition, and the
chevrons handle this distinction quite nicely.
As for the person who said that composition isn't necessary: there are
places where it is useful, in any case. Take the following example of
an extensible printf system using continuation-passing in O'Caml
(translated from an SML version shown to me by Franklin Chen):
let id x = x
(* continuation, string, args *)
let f_int k s x = k (s ^ string_of_int x)
let f_str k s x = k (s ^ x)
let f_lit x k s = k (s ^ x)
let f_eol k s = k (s ^ "\n")
let f_list t k s = function
| [] -> k (s ^ "[]")
| xs -> let rec loop l k s =
match l with
| [x] -> t (fun s -> k (s ^ "]")) s x
| (x::xs) -> t (fn s => loop xs k (s ^ ", ")) s x
in loop xs k (s ^ "[")
let printf c = c id ""
(* "3 is foo[2, 3, 4]\n" *)
let foo =
printf (f_int $ f_lit " is " $ f_str $ (f_lis f_int) $ f_eol)
3 "foo" [2, 3, 4];;
where $ is normal functional composition.
Notice that this definition of formatting has similar (although not
exactly the same, because it only support writing out a string (this
could be fixed, and possibly in a generic way)) nice properties to
O'Caml's Printf.printf stuff and formats, but doesn't require the
compiler to know about a special type of formats. Note also that
composition serves a very good purpose in this case--you couldn't do
this easily without it, or with a prefix composition operator.
jmp.
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
@ 1998-12-08 20:09 Don Syme
0 siblings, 0 replies; 12+ messages in thread
From: Don Syme @ 1998-12-08 20:09 UTC (permalink / raw)
To: 'Pierre Weis', whitley; +Cc: caml-list
>
> -- it only save a few characters in programs
> (Compare
> let h = f o g
> with
> let h x = f (g x);;)
As you say, you can always define the infix identifier, so there's no
hassle, i.e. I'm not complaining. However, the comparison should be
f1 << f2 << f3 << f4
v.
(fun x -> f1(f2(f3(f4 x))))
because we may not be binding the on-the-fly value to a name. Saving
parentheses is clearly a good idea - most the ML syntax is directed to this.
Even worse consider
f1 << f2 x y z << f3 << f4 a b
v.
(let f4' = f4 a b in
let f2' = f2 x y z in
(fun x -> f1(f2' z(f3(f4' x)))))
since in the latter case we may be taking advantage of the partial
evaluation of the closures to, for example, precompute some tables based on
the information in x,y,z and a,b. I know which I prefer!
In 16,000 lines implementing the interactive theorem prover DECLARE there
are 220 uses of composition, so one every 70 lines or so. There are 500
uses of "map", so it's relatively common in that one random example at
least.
Cheers,
Don
------------------------------------------------------------------------
At the lab: At home:
Microsoft Research Cambridge 11 John St
St George House CB1 1DT
Cambridge, CB2 3NH, UK
Ph: +44 (0) 1223 744797 Ph: +44 (0) 1223 722244
http://research.microsoft.com/users/dsyme
email: dsyme@microsoft.com
"You've been chosen as an extra in the movie
adaptation of the sequel to your life" -- Pavement, Shady Lane
------------------------------------------------------------------------
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
@ 1998-12-08 19:51 Don Syme
0 siblings, 0 replies; 12+ messages in thread
From: Don Syme @ 1998-12-08 19:51 UTC (permalink / raw)
To: 'akay@sharp.co.uk', caml-list
Yes, I chose the same operator, which seems very natural.
Don
> > is there a consensus for choice of infix composition operator?
>
> In the end we settled on >> and << for forward and reverse
> composition respectively, satisfying the equations:
>
> (f << g) x = f (g x) = (g >> f) x
>
> The chevrons give a nice feeling of a data pipeline running from g
> to f in each case. Since composition is associative (in the absence
> of side effects) we can write (f << g << h << i), which is
> more elegant
> than (compose (compose (compose f g) h) i), without fear of being
> misunderstood.
^ permalink raw reply [flat|nested] 12+ messages in thread
* RE: Functional composition operator?
@ 1998-12-08 18:08 Andrew Kay
1998-12-08 20:32 ` John Prevost
1998-12-09 16:17 ` Anton Moscal
0 siblings, 2 replies; 12+ messages in thread
From: Andrew Kay @ 1998-12-08 18:08 UTC (permalink / raw)
To: caml-list
John Whitley raised again a question that I had asked earlier.
We were converting source from caml to ocaml, and needed to
change our infix operator for function compostion.
We found the performance and accuracy of the ocaml compiler (relative
to the caml compiler) to be excellent. There were only two teething
problems in our 1.2MB of source code, once all the syntax changes had
been sorted out with the help of caml2csl, and these were resolved
within a day. (Both were to do with questionable code of our own,
which probably should not have worked in caml, but which somehow
did.) This seems to us to be an amazing achievement of the ocaml
development team, and gives us confidence in using and recommending
ocaml in the future.
From: John Whitley <whitley@cse.buffalo.edu>
> is there a consensus for choice of infix composition operator?
In the end we settled on >> and << for forward and reverse
composition respectively, satisfying the equations:
(f << g) x = f (g x) = (g >> f) x
The chevrons give a nice feeling of a data pipeline running from g
to f in each case. Since composition is associative (in the absence
of side effects) we can write (f << g << h << i), which is more elegant
than (compose (compose (compose f g) h) i), without fear of being
misunderstood.
We're still interested to know if other people have different approaches.
Best wishes
Andrew Kay
--
Sharp Labs Europe Ltd, Oxford Science Park, Oxford, UK, OX4 4GB
Andrew.Kay@sharp.co.uk Tel:+44 1865 747711 FAX:+44 1865 747717
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~1998-12-11 14:15 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1998-12-08 5:23 Functional composition operator? John Whitley
1998-12-08 17:02 ` Pierre Weis
1998-12-08 21:52 ` John Harrison
1998-12-09 10:58 ` Pierre Weis
1998-12-09 17:17 ` John Harrison
1998-12-11 13:57 ` Pierre Weis
1998-12-08 18:08 Andrew Kay
1998-12-08 20:32 ` John Prevost
1998-12-09 16:17 ` Anton Moscal
1998-12-08 19:51 Don Syme
1998-12-08 20:09 Don Syme
1998-12-09 12:00 Don Syme
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).