[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: REDUCE args



Received: from SCRC-QUABBIN.ARPA by SAIL.STANFORD.EDU with TCP; 28 Jul 86  11:44:47 PDT
Received: from FIREBIRD.SCRC.Symbolics.COM by QUABBIN.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 24559; Mon 28-Jul-86 09:48:45 EDT
Date: Mon, 28 Jul 86 09:49 EDT
From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
Subject: Re: REDUCE args
To: Skef Wholey <Skef@THINK.COM>, Guy Steele <gls@THINK.COM>,
    DCP@QUABBIN.SCRC.Symbolics.COM, NGALL@G.BBN.COM,
    ALR%OZ.AI.MIT.EDU@XX.LCS.MIT.EDU
cc: common-lisp@SU-AI.ARPA
In-Reply-To: <860725121309.3.SKEF@WENCESLAS.THINK.COM>,
             <860725175113.5.GLS@IGNATIUS.THINK.COM>
Message-ID: <860728094914.9.DCP@FIREBIRD.SCRC.Symbolics.COM>

    Date: Fri, 25 Jul 86 12:13 EDT
    From: Skef Wholey <Skef@Think.COM>

	From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
    
	    Date: Fri, 25 Jul 86 09:55 EDT
	    From: Skef Wholey <Skef@Think.COM>
    
	    In the meantime, you can of course do something like:
		    (reduce #'fun (map 'vector #'key sequence))
    
	Somebody brought up this method the last time.  I had at least two
	reactions: (1) It doesn't really express the intent of the programmer,
	and (2) I don't care what kind of machine you are on, you should care
	about efficiency and consing.

    However, it is very easy to write a compiler transform that turns the
    above into a call to a hidden function that does what the above does
    without consing.  The sequence functions are the most obvious, easiest
    target for source-level optimization in a Common Lisp compiler.  If the
    above were listed as an idiom in the manual, then such optimizers might
    appear in implementations.  This is a real alternative, not some
    pie-in-the-sky "a smart compiler could..." argument.

I agree this is a real alternative.  The in-English thing being
expressed is "compute the sum of the car of each element of the
sequence."  To me "compute the sum of ... the sequence"
translates to (reduce #'+ sequence ...) and "the car of" translates to
:KEY #'CAR.  To you "Compute the sum of" translates to (reduce #'+ ...)
and "the car of the sequcnce" translates to (map 'vector #'CAR
sequence).  Both translations are valid and both are probably correct
given today's ideas about programming.  Here's my justification for
mine: My high level goal is to do something to a sequence.  Since I am
only doing one thing to the sequence, I want only one sequence operation
to be expressed in my code.

    I feel the argument about consistent use of :KEY, :TEST, and :TEST-NOT
    still holds.  I don't object to adding a field selector argument to
    REDUCE, but I don't think that it should be called :KEY.  One might
    introduce a new function, REDUCE-FIELD (or whatever), or a new keyword.

I've thought about this a little.  :TEST/:TEST-NOT should apply before
the key is extracted.  We can either declare that this test must
validiate the key (and must therefore also know how to extract it), or
we can add a :KET-TEST arg, defaulting to #'TRUTH (not #'IDENTITY !),
which validates the key.  Therefore, you could get
	(defun sum-numeric-cadrs-whose-car-is (expected-car sequence)
	  (reduce #'+ sequence
		  :test #'(lambda (element) (eq (car element) expected-car))
		  :key #'cadr
		  :key-test #'numberp))


    Date: Fri, 25 Jul 86 17:51 EDT
    From: Guy Steele <gls@Think.COM>

	Date: Fri, 25 Jul 86 11:39 EDT
	From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>

	    Date: Fri, 25 Jul 86 09:55 EDT
	    From: Skef Wholey <Skef@Think.COM>

	    In the meantime, you can of course do something like:
		    (reduce #'fun (map 'vector #'key sequence))

	    Now-living-on-a-3600-and-not-caring-too-much-about-consing-or-81-character-lines,

	Somebody brought up this method the last time.  I had at least two
	reactions: (1) It doesn't really express the intent of the programmer,
	and (2) I don't care what kind of machine you are on, you should care
	about efficiency and consing.

    I buy your argument (2), but (1) seems to be a bit spurious.
    Why isn't the intent "take all those keys and reduce them"?
    If that is the intent, why can't that be expressed as
    "(take all those keys) and (reduce them)"?  Is it that
    you had rather in mind "reduce all them thar keys"
    and don't consider the other an equivalent formulation?

I think I explained this above.  Indeed, (1) probably is a bit spurious.
It depends on how you view the problem.