Subject: Re: bug#30237: Generalizing ‘and=>’

From: Mathieu Lirzin <[email-masked]>
Date: Wed, 24 Jan 2018 21:08:25 +0100

Hello Mark,

Mark H Weaver <[email-masked]> writes:

> Mathieu Lirzin <[email-masked]> writes:
>
>> Here is a proposal for generalizing ‘and=>’ to a pipeline of procedures.
>> It acts like a “bind” operator in an ad-hoc “Maybe” monad which uses #f
>> to represent the absence of value.  Not sure if it is useful in
>> practice, but it feels like a natural generalization.
>>
>> The current definition is the following:
>>
>>   (define (and=> value procedure)
>>     (and value (procedure value)))
>>
>> Here is my proposition:
>>
>>   (define-syntax and=>
>>     (syntax-rules ()
>>       ((_) #t)
>>       ((_ val) val)
>>       ((_ val proc)
>>        (and val (proc val)))
>>       ((_ val proc proc* ...)
>>        (and=> (and val (proc val)) proc* ...))))
>
> Be careful, macros are different than procedures!  Instead of binding
> values to variables, they bind _unevaluated_ forms to pattern variables.
> So 'val' is a misleading name for the first operand of the macro above.
> In fact, what's being bound there is an _expression_, and you are then
> expanding this into something that contains two copies of that
> expression.  So, for example:
>
>   (and=> (compile-webkitgtk)
>          test
>          install)
>
> expands into:
>
>   (and=> (and (compile-webkitgtk)
>               (test (compile-webkitgtk)))
>          install)
>
> which expands into:
>
>   (and (and (compile-webkitgtk)
>             (test (compile-webkitgtk)))
>        (install (and (compile-webkitgtk)
>                      (test (compile-webkitgtk)))))
>
> So you end up compiling webkitgtk 4 times, and testing it twice, before
> finally installing it.  More generally, if you pass N+1 operands, the
> first operand will be evaluated 2^N times.

Indeed I overlooked that.

> The other problem is that 'and=>' is currently a procedure, and you're
> replacing it with a macro.  There are a couple of issues with this.  One
> is that procedures are first-class objects in Scheme, but macros aren't.
> Procedures can be passed as arguments to procedures, stored in data
> structures, etc, but macros cannot.
>
> For example, if 'and=>' is a procedure, you can write:
>
>   (map and=> vals procs)
>
> but you can't do this if 'and=>' is a macro.
>
> The other problem with changing 'and=>' to a macro is that this
> effectively changes the ABI of Guile, which we can't do within a stable
> release series (2.2.x).  Existing .go files that use 'and=>' were
> compiled to generate a normal procedure call for 'and=>', and if that
> procedure no longer exists then the code will break.  This change
> requires all users of 'and=>' to be recompiled.

I initially implemented it as a procedure but move to the macro side of
thing in an attempt to generate more efficient code while handling
procedures that return multiple values.  But this can't work given the
issue you described above.

>> Let me know if such change is welcome or not, so I can provide a
>> complete patch including documentation.
>
> I think it's worth considering something along these lines for the
> 'master' branch which will eventually become Guile 3, although in order
> to support existing callers that expect 'and=>' to be a first-class
> procedure, we might want to arrange for a bare 'and=>' to expand into a
> reference to a first-class procedure that does the same job, similar to
> what we do with 'define-inlinable'.

I don't think making it a macro worths the breaking change.

> The other option would be to implement your enhanced 'and=>' as a normal
> procedure using case-lambda, maybe something like this:
>
>   (define and=>
>     (case-lambda
>       ((val proc) (and val (proc val)))
>       ((val . procs)
>        (let loop ((val val) (procs procs))
>          (if (null? procs)
>              val
>              (and val (loop ((car procs) val)
>                             (cdr procs))))))
>       (() #t)))
>
> The first case is not strictly needed, but is included as an
> optimization to avoid heap-allocating a list for the 'procs' rest
> argument in the common case of two arguments.
>
> The second case is implemented as a loop instead of a recursive call to
> 'and=>', to prevent repeatedly heap-allocating the rest list on each
> iteration, which would lead to O(N^2) allocations for N arguments.  It
> would be nicer to use 'match' here, but since 'and=>' is defined early
> in boot-9.scm, we must restrict ourselves to core functionality in its
> implementation.

That's a clear explanation.  IMO It would be nice if multiple values
were handled too.  here is one solution inspired by ‘compose’.

(define and=>
  (case-lambda
    ((val proc) (and val (proc val)))
    ((val proc . procs)
     (let loop ((p proc) (ps procs))
       (if (null? ps)
	   (p val)
	   (loop (lambda args
		   (call-with-values (lambda () (apply p args))
		     (lambda (arg0 . args*)
		       (and arg0 (apply (car ps) arg0 args*)))))
		 (cdr ps)))))))

I am not sure if there is a way to avoid constructing the composition of
functions.

> I'm not sure if it makes sense to include the final (nullary) case.
> Unlike 'and', 'or', '+', '*' and similar operations where every argument
> is treated uniformally, in this case the first argument is qualitatively
> different than the others.  Therefore, it seems to me that this
> procedure naturally generalizes down to 1 argument, but no further.

I don't think so, I defined it only because I took inspiration from
‘and’.

> Finally, there still some question in my mind whether this
> generalization would be useful in practice.  Have you found a real-world
> use case where this generalized 'and=>' makes life easier?

Not really.  :-)

> Do you know about SRFI-2 (and-let*)?  How would that work for your use
> case?

Yes I know about ‘and-let*’ which is a proper way to do pipelining while
checking for #f.  My motivation for extending ‘and=>’ was to have
something similar but without the special syntax.

Thanks for the in-depth review.

-- 
Mathieu Lirzin
GPG: F2A3 8D7E EB2B 6640 5761  070D 0ADE E100 9460 4D37