Issue: FUNCTION-COMPOSITION (Version 2)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

An updated copy to reflect discussion since the first draft:
 - Corrected typo in description of COMPLEMENT (notice by Fahlman).
 - Rewrote the rationale to reflect the e-mail discussion.
 - Added endorsements in the Discussion section.

-----
Issue:          FUNCTION-COMPOSITION
References:     None
Category:       ADDITION
Edit history:   21-Jun-88, Version 1 by Pitman
	        05-Oct-88, Version 2 by Pitman
Status:	        For Internal Discussion
Related-Issues: TEST-NOT-IF-NOT

Problem Description:

  A number of useful functions on functions are conspicuously
  absent from Common Lisp's basic set. Among them are functions
  which return constant T, constant NIL, and functions which
  combine functions in common, interesting ways.

Proposal (FUNCTION-COMPOSITION:NEW-FUNCTIONS):

  Add the following functions:

   COMPOSE &REST functions				[Function]

    Returns a function whose value is the same as the composition
    of the given functions. eg, (FUNCALL (COMPOSE #'F #'G #'H) A B C)
    is the same as (F (G (H A B C))). Also, for example, #'CAADR may
    be described as (COMPOSE #'CAR #'CAR #'CDR).

   CONJOIN &REST functions				[Function]

    Returns a function whose value is the same as the AND of the
    given functions applied to the same arguments.

   DISJOIN &REST functions				[Function]

    Returns a function whose value is the same as the OR of the
    given functions applied to the same arguments.
    

   COMPLEMENT function					[Function]

    Returns a function whose value is the same as the NOT of the
    given function applied to the same arguments.

   ALWAYS value						[Function]

    Returns a function whose value is always VALUE.

Examples:

  (MAPCAR #'(LAMBDA (X) (DECLARE (IGNORE X)) T) '(3 A 4.3))
  ==
  (MAPCAR (ALWAYS T) '(3 A 4.3))
  => (T T T)

  (MAPCAR #'(LAMBDA (X) (AND (NUMBERP X) (ZEROP X))) '(3 A 0.0))
  ==
  (MAPCAR (CONJOIN #'NUMBERP #'ZEROP) '(3 A 0.0))
  => (NIL NIL T)

  (FIND-IF #'(LAMBDA (X) (AND (INTEGERP X) (SYMBOLP X))) '(3.0 A 4))
  ==
  (FIND-IF (DISJOIN #'INTEGERP #'SYMBOLP) '(3.0 A 4))
  => A

  (FUNCALL #'(LAMBDA (&REST X) (REVERSE (APPLY #'LIST* X))) 3 4 5 '(6 7))
  ==
  (FUNCALL (COMPOSE #'REVERSE #'LIST*) 3 4 5 '(6 7))
  => (7 6 5 4 3)

  (FIND-IF-NOT #'ZEROP '(0 0 3))
  ==
  (FIND-IF (COMPLEMENT #'ZEROP) '(0 0 3))
  => 3

Rationale:

  The presence of these functions will contribute to syntactic
  conciseness in some cases, and more importantly will permit
  a programming style which is currently discouraged by most
  Common Lisp implementations.

  It is technically possible to define this functionality portably,
  the really important part of this proposal is that native compiler
  support is needed to really do them justice. Portable implementations
  are not likely to be efficient enough for serious use.

  Placing these functions in the core language not only permits
  but encourages a very useful set of compiler optimizations that
  would otherwise be difficult to obtain.

  In principle, a proposal to flush the :TEST-NOT keywords and the
  -IF-NOT functions could even be entertained if the COMPLEMENT
  function were added. [See issue TEST-NOT-IF-NOT.]

Current Practice:

  No Common Lisp implementations provide these primitives, but they do
  exist in the T language.

Cost to Implementors:

  A straightforward implementation is simple to cook up. The definitions
  given here would suffice. Typically some additional work might be
  desirable to make these open code in interesting ways.

  (DEFUN COMPOSE (&REST FUNCTIONS)
    (COND ((NOT FUNCTIONS)
	   (ERROR "COMPOSE requires at least one function."))
	  ((NOT (REST FUNCTIONS))
	   (FIRST FUNCTIONS))
	  (T
	   (LET ((REVERSED-FUNCTIONS (REVERSE FUNCTIONS)))
	     (LET ((LAST-FUNCTION   (FIRST REVERSED-FUNCTIONS))
	           (OTHER-FUNCTIONS (REST  REVERSED-FUNCTIONS)))
               #'(LAMBDA (&REST ARGUMENTS)
                   (DO ((O OTHER-FUNCTIONS (CDR O))
			(VAL (APPLY LAST-FUNCTION ARGUMENTS)
			     (FUNCALL (CAR O) VAL)))
		       ((NULL O) VAL))))))))

  (DEFUN CONJOIN (&REST FUNCTIONS)
    #'(LAMBDA (&REST ARGUMENTS)
        (DO ((F FUNCTIONS (CDR F))
	     (VAL T (AND VAL (APPLY (CAR F) ARGUMENTS))))
	    ((OR (NULL VAL) (NULL F)) VAL))))

  (DEFUN DISJOIN (&REST FUNCTIONS)
    #'(LAMBDA (&REST ARGUMENTS)
        (DO ((F FUNCTIONS (CDR F))
	     (VAL NIL (OR VAL (APPLY (CAR F) ARGUMENTS))))
	    ((OR VAL (NULL F)) VAL))))

  (DEFUN COMPLEMENT (FUNCTION)
    #'(LAMBDA (&REST ARGUMENTS)
        (NOT (APPLY FUNCTION ARGUMENTS))))

  (DEFUN ALWAYS (VALUE)
    #'(LAMBDA (&REST ARGUMENTS) 
        (DECLARE (IGNORE ARGUMENTS))
        VALUE))

Cost to Users:

  None. This change is upward compatible.

Cost of Non-Adoption:

  (COMPLEMENT BENEFITS)

Benefits:

  Some code would be more clear. 
  Some compilers might be able to produce better code.

  Takes a step toward being able to flush the -IF-NOT functions
  and the :TEST-NOT keywords, both of which are high on the list
  of what people are referring to when they say Common Lisp is
  bloated by too much garbage.

Aesthetics:

  In situations where these could be used straightforwardly, the
  alternatives are far less perspicuous.

Discussion:

  Pitman and van Roggen support the proposal.

  Jim McDonald (JLM@Lucid.COM) seemed supportive of this proposal
  and even suggested adding more elaborate operators such as
  PERMUTE and COMMUTE. eg, (COMMUTE #'CONS) would be like what
  Maclisp called XCONS.

  Masinter wavered on this issue, but currently seems to support it.

  Fahlman thinks this slightly gratuitous but is not opposed to 
  it if others think it is a good idea.