RE: Functional composition operator?

RE: Functional composition operator?

[Andrew Kay]

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

RE: Functional composition operator?

[John Prevost]

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.

RE: Functional composition operator?

[Anton Moscal]

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

RE: Functional composition operator?

[Don Syme]

> 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

RE: Functional composition operator?

[Don Syme]

> 
>  -- 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
------------------------------------------------------------------------

RE: Functional composition operator?

[Don Syme]

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.

Functional composition operator?

[John Whitley]

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

Re: Functional composition operator?

[Pierre Weis]

> 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/

Re: Functional composition operator?

[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.

Re: Functional composition operator?

[Pierre Weis]

> | 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/

Re: Functional composition operator?

[John Harrison]

| > | 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.

Re: Functional composition operator?

[Pierre Weis]

[...]
> 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/