From: ajs@prg.ox.ac.uk (Adolfo Socorro)
Newsgroups: comp.object
Subject: Re: Passing functions as parameters in an OO environment
Date: 29 Sep 92 12:49:40 GMT
Reply-To: Adolfo.Socorro@prg.oxford.ac.uk (Adolfo Socorro)
Organization: Oxford University Computing Laboratory, UK
Originator: ajs@ruby.comlab

In article <KERS.92Sep24135934@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes:
>In article ... ajs@prg.ox.ac.uk (Adolfo Socorro) writes:
>
>   Higher-order functions are nice, but their functionality may be achieved
>   with generic modules. 
>
>If you're prepared to do all the explicit instantiations. If the instantiations
>are implicit, why bother with generic modules -- they seem to be overkill for
>the simple cases that HOFs are good for.

Thanks for your comments, Chris. Let me try to clarify some of my points.

I know many cases in which you want to make something generic over various
functions; for example, all sorts of iterators. Syntax need not be cumbersome
for the simple cases, either. A paper by Goguen [1] gives some examples. (This
paper convinced me about some of the issues that we are discussing.)

>
>   Moreover, if you are worried about giving your language a
>   formal semantics, you might want to stay away from higher-order logic.
>
>Since a well-known theorem-proving system, namely Cambridge HOL, uses
>higher-order logic as its basis, and for giving semantics of sub-languages, I'd
>like to know why you think this.

This has to do with verification and implementation.  If you can explain all
that's needed in a logic that's first order, why appeal to a more complex
logic?  In addition, higher-order unification is undecidable.  As a case in
point, note that there exist algorithms associated with equational logic that
give it a strong computational flavor, such as term rewriting, Knuth-Bendix
completion, narrowing, etc. These are not available even to full first-order
logic. 

>
>   Also, an appropriate module mechanism would allow you to impose semantic 
>   constraints on the functions passed as parameters.
>
>So would a more powerful type system.

This remark of mine was vague. See below.

>
>   And in addition, with modules, dozens of functions may be substituted for
>   dozens of other functions, giving increased leverage.
>
>Unless I misunderstand you, the same thing applies with HOFs -- any suitable
>call will be instantiated to the correct type. What's more, only the function's
>you actually *use* are instantiated -- not their clamouring siblings.

The difference here seems to be one between programming-in-the-small and
programming-in-the-large. Module composition is more general than function
composition.  Functions should not be considered in isolation, but in
conjunction with other related functions, types and constants, all of which may
depend on various generic parameters. To me, the important issue is whether
the structure of large programs is made as clear as possible; that's more
valuable than the possibility of saving a few keystrokes.

As for implementation, if you are dealing with an interpreter, then the
extra-instantiations may consume more memory than what is desired. But for a
compiler this should not be a problem: what's not used can be thrown away.

>
>[Stuff about FOOPS deleted]
>--
>
>Regards,    | ``The French teacher does not threaten. She says, | Teen
>Kers.       | "s'il vous plait"''.                              | Agent

Cheers,
Adolfo

[1] J. Goguen, Higher-Order Functions Considered Unnecessary for Higher-Order
Programming. In David Turner, editor, Research Topics in Functional
Programming, Addison-Wesley, 1990.
Newsgroups: comp.object,comp.lang.smalltalk,comp.lang.eiffel