From: Fernando D. Mato Mira
Subject: Re: Any compilers do not optimize this?
Date:
Message-ID: <38DE1A7E.DAFB4714@iname.com>
If compilers are OK with the non-obfuscated version, ie:
(cl:defun n-integer-values (n)
(cl:labels ((n-integer-values-1 (n &rest args)
(declare (dynamic-extent args))
(cond ((> n 0) (apply #'n-integer-values-1 (1- n) (1- n) args))
(t (values-list args)))))
(n-integer-values-1 n)))
that would be enough.
[Besides legacy issues, I was in a heavy mv-mode while writing the other one.
Anyway, although equivalent, it's not certain that they are handled identically]
Is tail recursion the only hope for efficient iterative generation of multiple
values? Something seems to be seriously missing. Not to mention things like:
(defmacro multiple-value-setf (places vals)
(cl:let* ((n (length places))
(vars (n-gensyms n)))
`(cl:multiple-value-bind ,vars ,vals
(values
,@(mapcar #'(lambda (p v) `(setf ,p ,v)) places vars)))))
(cl:defun polyapply (fun args)
(declare (dynamic-extent args))
(cl:labels ((polyapply-1 (args &rest results)
(declare (dynamic-extent args results))
(if args
(cl:let ((d (cdr args)))
(if d
(apply #'polyapply-1 (cdr args) (cl:funcall fun (car args)) results)
(apply #'values (cl:funcall fun (car args)) results)))
(values))))
(polyapply-1 args)))
(declaim (inline polycall))
(cl:defun polycall (fun &rest args)
(declare (dynamic-extent args))
(polyapply fun args))
(defmacro multiple-value-polycall (fun vals)
`(multiple-value-call #'polycall ,fun ,vals))
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
From: Fernando D. Mato Mira
Subject: Re: Any compilers do not optimize this?
Date:
Message-ID: <38DE1DD3.DABF0EC@iname.com>
I messed up in the tail-recursive version of polyapply (result reversal).
Here's the right def:
(cl:defun polyapply (fun args)
(declare (dynamic-extent args))
(cl:labels ((polyapply-1 (args &rest results)
(declare (dynamic-extent args results))
(if args
(cl:let ((d (cdr args)))
(if d
(cl:multiple-value-call #'polyapply-1 d (values-list result) (cl:funcall fun (car
args)))
(valuate (values-list result) (cl:funcall fun (car args)))
(values))))
(polyapply-1 args)))
REVERSE-VALUES anyone, so that it's possible to write:
(cl:defun polyapply (fun args)
(declare (dynamic-extent args))
(cl:labels ((polyapply-1 (args &rest results)
(declare (dynamic-extent args results))
(if args
(cl:let ((d (cdr args)))
(if d
(apply #'polyapply-1 (cdr args) (cl:funcall fun (car args)) results)
(apply #'reverse-values (cl:funcall fun (car args)) results)))
(values))))
(polyapply-1 args)))
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
"Fernando D. Mato Mira" <········@iname.com> writes:
> If compilers are OK with the non-obfuscated version, ie:
>
> (cl:defun n-integer-values (n)
> (cl:labels ((n-integer-values-1 (n &rest args)
> (declare (dynamic-extent args))
> (cond ((> n 0) (apply #'n-integer-values-1 (1- n) (1- n) args))
> (t (values-list args)))))
> (n-integer-values-1 n)))
That doesn't allocate in LispWorks (and I doubt it's the only
implementation).
> Is tail recursion the only hope for efficient iterative generation
> of multiple values? Something seems to be seriously missing.
Yes, the idea that the producer of multiple values might not create a
fixed set of values. I.e., it was conceived more as a record than a
list. MULTIPLE-VALUES-LIMIT could be as small as 20.
But it's certainly possible to have a list-like multiple-value
feature. There was an interesting proposal by Dybvig and Hieb for
rest args in Scheme and Lisp (R. Kent Dybvig & Robert Hieb: A New
Approach to Procedures with Variable Arity. 1990. Lisp and Symbolic
Computation 3:3, pp. 229-244.), that included an extension that made
multiple values more or less the reflection of argument lists. In
their notation:
(defun n-integer-values (n)
(labels ((n-integer-values-1 (n & vals)
(cond ((> n 0) (n-integer-values-1 (1- n) (1- n) & vals))
(t & vals))))
(n-integer-values-1 n)))
The "rest values" are special and can only be used by passing them
down to a function or returning them as multiple values. Hence it's
possible to guarantee no heap allocation.
> Not to mention things like:
>
> (defmacro multiple-value-setf (places vals) [...]
That's like SETF VALUES, only with wierd order of evaluation.
> (cl:defun polyapply (fun args)
That's (VALUES-LIST (MAPCAR fun args)), once you get the results in
right order. It's hard to convince compilers not to cons for the
MAPCAR, though.
--
Pekka P. Pirinen, Harlequin Limited
Only fools learn by their experience; smart people use the experience
of others. - Bismarck
·····@harlequin.co.uk (Pekka P. Pirinen) writes:
> But it's certainly possible to have a list-like multiple-value
> feature. There was an interesting proposal by Dybvig and Hieb for
> rest args in Scheme and Lisp (R. Kent Dybvig & Robert Hieb: A New
> Approach to Procedures with Variable Arity. 1990. Lisp and Symbolic
> Computation 3:3, pp. 229-244.), that included an extension that made
> multiple values more or less the reflection of argument lists. In
> their notation:
>
> (defun n-integer-values (n)
> (labels ((n-integer-values-1 (n & vals)
> (cond ((> n 0) (n-integer-values-1 (1- n) (1- n) & vals))
> (t & vals))))
> (n-integer-values-1 n)))
>
> The "rest values" are special and can only be used by passing them
> down to a function or returning them as multiple values. Hence it's
> possible to guarantee no heap allocation.
This is being used in Oaklisp, a kind of OO son of both CL and Scheme,
written by Barak Pearlmutter, and is even older than 1990.
It just uses . instead of & and has the values on the stack. But it
won't return multiple values. You must consume them, i.e. pass them to
a function, like you say. That function can be LISTIFY-ARGS.
Regards,
Jorg Hohle
Telekom Research Center -- SW-Reliability
From: Fernando D. Mato Mira
Subject: Re: Any compilers do not optimize this?
Date:
Message-ID: <38DF3604.B055557D@iname.com>
If some compilers can do (values-list (mapcar #'foo <args>)) w/o consing I
would also like to know.
Thanks,
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html