From: Fernando D. Mato Mira
Subject: Referential transparency support missing
Date:
Message-ID: <38C940EB.E7A4B125@iname.com>
OK. CONSTANTP is wimpy, so if you want to implement the real thing
yourself,
you need to know what functions are pure.
What seems to be needed is:
PURE declaration, so you can give the information yourself if the
implementation
is not smart enough. If the event the impl finds out a function declared
PURE is not, it should raise an error.
Do we need two symbols, or just one is OK? ie:
(declaim (pure identity))
(lambda (x)
(declare pure)
(+ 2 x))
or
(lambda (x)
(declare (pure nil))
(+ 2 x))
or, for eample:
(lambda (x)
(declare pure-function)
(+ 2 x))
PUREP predicate, similar in wimpiness to CONSTANTP (ie, the
implementation is not required to derive
whether a function is pure ot not), but it should at least return T for
those functions declared to be pure).
This should take a function _object_ as argument (maybe names too).
[I guess an implementation should not believe pure declarations it
cannot prove unless safety == 0, or at least
speed > safety]
In the meantime, has anybody compiled a list of all functions in CL
which are pure?
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
From: Fernando D. Mato Mira
Subject: Re: Referential transparency support missing
Date:
Message-ID: <38CC0527.7CCA9DE0@iname.com>
Well, for the time being, I think I'll stick to CONSTANTP, as I have no
time
for implementation-dependent environment hacking or code walking to
properly handle local functions; that it should really be handled by the
compiler;
and perhaps more importantly, it's another differentiating factor which
might warrant purchasing a commercial Lisp.
--
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:
> PURE declaration, so you can give the information yourself [...]
> Do we need two symbols, or just one is OK? ie:
>
> (declaim (pure identity))
>
> (lambda (x)
> (declare pure)
> (+ 2 x))
I rather like the idea of having a way to say "this function" in
declaration lists (since we have anonymous functions):
(lambda (x)
(declare (pure self))
(+ 2 x))
> In the meantime, has anybody compiled a list of all functions in CL
> which are pure?
This list was used in a CLtL1 compiler a long time ago:
(defconstant pure-functions
'(abs acos acosh adjustable-array-p alpha-char-p alphanumericp
array-element-type
array-has-fill-pointer-p array-rank arrayp ash asin asinh atan atanh
bit-vector-p boole both-case-p byte byte-position byte-size ceiling
char-bit char-bits char-code char-downcase char-equal char-font
char-greaterp char-int char-lessp
char-name char-not-equal char-not-greaterp char-not-lessp
char-upcase char/= char< char<= char= char> char>=
character characterp cis code-char coerce commonp
compiled-function-p complex complexp conjugate consp cos cosh
decode-float denominator deposit-field
digit-char digit-char-p dpb endp eq eql evenp exp expt fceiling ffloor
;; Note that the purity of eq depends on subtleties
float float-digits float-precision float-radix float-sign floatp floor
fround ftruncate gcd graphic-char-p hash-table-p imagpart
input-stream-p int-char integer-decode-float integer-length
integerp isqrt lcm ldb ldb-test listp log logand logandc1 logandc2
logbitp logcount logeqv logior lognand lognor lognot logorc1
logorc2 logtest logxor lower-case-p make-char mask-field max min
minusp mod null numberp numerator oddp packagep parse-integer
phase plusp rational rationalize rationalp
readtablep realpart rem round scale-float set-char-bit signum
simple-bit-vector-p simple-string-p simple-vector-p sin sinh
special-form-p sqrt standard-char-p stream-element-type streamp
stringp sxhash symbolp tan tanh truncate
upper-case-p values vectorp 1+ 1- < <= = > >= + - * / /=
;; if used outside the compiler, include the following:
;; atom identity not nth-value zerop
))
;;;The following forms would require a more complicated analysis
;;; decode-universal-time (because of the time-zone argument)
;;; block, tagbody, return-from (the unevaluated subforms)
;;; apply, funcall (depend on the functional argument)
;;; subtypep, typep (types don't have to be defined at compile time)
Note that this list includes no data structure accessors, since we
didn't want to constant-fold them to preserve equality on named
constants, and because their results can changed by destructive
modification of the arguments. These considerations might not apply
in your application, so you'd want to add C[A|D]+R, LENGTH, array
accessors, etc.
Some macros could be regarded pure, as well: AND, OR, UNLESS, WHEN,
PROG1, PROG2.
You might want to do something clever with THE and IF.
--
Pekka P. Pirinen, Harlequin Limited
This article printed on 100% recycled electrons.
From: Erik Naggum
Subject: Re: Referential transparency support missing
Date:
Message-ID: <3161959623274993@naggum.no>
* Pekka P. Pirinen
| I rather like the idea of having a way to say "this function" in
| declaration lists (since we have anonymous functions):
| (lambda (x)
| (declare (pure self))
| (+ 2 x))
`lambda' seems to me a much better choice than `self'.
#:Erik
From: Fernando D. Mato Mira
Subject: Re: Referential transparency support missing
Date:
Message-ID: <38CE4EFE.B369089F@iname.com>
Erik Naggum wrote:
> * Pekka P. Pirinen
> | I rather like the idea of having a way to say "this function" in
> | declaration lists (since we have anonymous functions):
> | (lambda (x)
> | (declare (pure self))
> | (+ 2 x))
>
> `lambda' seems to me a much better choice than `self'.
>
> #:Erik
I think the right way would be NIL. But also note this:
(defun evil-factorial (n &optional (be-bad t))
(declare (pure evil-factorial))
(when be-bad
<do-evil-stuff>)
(if (eql n 1)
1
(* n (evil-factorial (- n 1) nil)))
So that's the way of making local purity declarations. To be perfectly
homogeneous,
you need another symbol, similar to OPTIMIZABLE-SERIES-FUNCTION, say:
(lambda (x)
(declare (pure-function))
(+ 2 x))
There's actually different kinds of "purity" (maybe someone knows the
right names?):
IDENTICAL: when repeatedly called with the same inputs, it always gives
the same
result, eg EQ; CONSP and any other predicates unaffected by
CHANGE-CLASS.
Pure functions of characters and numbers could be considered identical
in the sense
that (let ((x 3)) (eq x x)) is not guaranteed to be true.
PURE: Given "equal" arguments, it gives "the same" result. No side
effects.
[Note that local side-effects are OK, it's not like one must forbid SETQ
inside]
(constructors are `pure')
FUNCTIONAL: Given "equal" arguments, it gives "the same" result.
RPLACA is functional, but not side-effect-free, except when receiving a
unique reference,
eg: (rplaca (cons 'a 'b) 'c) == (cons 'c 'b)
It would be good if someone who really knows this stuff would express
all this kind of thing the right way.
--
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: Joe Marshall
Subject: Re: Referential transparency support missing
Date:
Message-ID: <uog8hr007.fsf@alum.mit.edu>
"Fernando D. Mato Mira" <········@iname.com> writes:
> There's actually different kinds of "purity" (maybe someone knows the
> right names?):
>
> IDENTICAL: when repeatedly called with the same inputs, it always gives
> the same
> result, eg EQ; CONSP and any other predicates unaffected by
> CHANGE-CLASS.
> Pure functions of characters and numbers could be considered identical
> in the sense
> that (let ((x 3)) (eq x x)) is not guaranteed to be true.
>
> PURE: Given "equal" arguments, it gives "the same" result. No side
> effects.
> [Note that local side-effects are OK, it's not like one must forbid SETQ
> inside]
> (constructors are `pure')
>
> FUNCTIONAL: Given "equal" arguments, it gives "the same" result.
> RPLACA is functional, but not side-effect-free, except when receiving a
> unique reference,
> eg: (rplaca (cons 'a 'b) 'c) == (cons 'c 'b)
>
>
> It would be good if someone who really knows this stuff would express
> all this kind of thing the right way.
pure-functional: The compiler is allowed to re-order, coalesce or
split calls to this function. The return value of the function
depends only upon the arguments and not upon time. EQL arguments
produce EQL results.
side-effect-free: The compiler is allowed to re-order calls to this
function, but may not split or coalesce calls.
Joe Marshall <·········@alum.mit.edu> writes:
> "Fernando D. Mato Mira" <········@iname.com> writes:
>
> > There's actually different kinds of "purity" (maybe someone knows the
> > right names?):
> >
> > IDENTICAL: when repeatedly called with the same inputs, it always gives
> > the same
> > result, eg EQ; CONSP and any other predicates unaffected by
> > CHANGE-CLASS.
> > Pure functions of characters and numbers could be considered identical
> > in the sense
> > that (let ((x 3)) (eq x x)) is not guaranteed to be true.
> >
> > PURE: Given "equal" arguments, it gives "the same" result. No side
> > effects.
> > [Note that local side-effects are OK, it's not like one must forbid SETQ
> > inside]
> > (constructors are `pure')
> >
> > FUNCTIONAL: Given "equal" arguments, it gives "the same" result.
> > RPLACA is functional, but not side-effect-free, except when receiving a
> > unique reference,
> > eg: (rplaca (cons 'a 'b) 'c) == (cons 'c 'b)
> >
> >
> > It would be good if someone who really knows this stuff would express
> > all this kind of thing the right way.
>
> pure-functional: The compiler is allowed to re-order, coalesce or
> split calls to this function. The return value of the function
> depends only upon the arguments and not upon time. EQL arguments
> produce EQL results.
>
> side-effect-free: The compiler is allowed to re-order calls to this
> function, but may not split or coalesce calls.
From CMUCL:
(defmacro defknown (name arg-types result-type &optional (attributes '(any))
&rest keys)
"Defknown Name Arg-Types Result-Type [Attributes] {Key Value}*
Declare the function Name to be a known function. We construct a type
specifier for the function by wrapping (FUNCTION ...) around the Arg-Types
and Result-Type. Attributes is a an unevaluated list of the boolean
attributes that the function has. These attributes are meaningful here:
call
May call functions that are passed as arguments. In order to determine
what other effects are present, we must find the effects of all arguments
that may be functions.
unsafe
May incorporate arguments in the result or somehow pass them upward.
unwind
May fail to return during correct execution. Errors are O.K.
any
The (default) worst case. Includes all the other bad things, plus any
other possible bad thing.
foldable
May be constant-folded. The function has no side effects, but may be
affected by side effects on the arguments. e.g. SVREF, MAPC.
flushable
May be eliminated if value is unused. The function has no side effects
except possibly CONS. If a function is defined to signal errors, then
it is not flushable even if it is movable or foldable.
movable
May be moved with impunity. Has no side effects except possibly CONS,
and is affected only by its arguments.
predicate
A true predicate likely to be open-coded. This is a hint to IR1
conversion that it should ensure calls always appear as an IF test.
Not usually specified to Defknown, since this is implementation
dependent, and is usually automatically set by the Define-VOP
:Conditional option.
Name may also be a list of names, in which case the same information is given
to all the names. The keywords specify the initial values for various
optimizers that the function might have."
The file src/compiler/fndb.lisp will probably be a good starting point
for finding out about the side-effects of CL functions. Try to get a
recent version (see http://www.cons.org/cmucl/ and the Web CVS access
there), since some versions did containt wrong attributes for some
functions (cf. the read-sequence bug a couple of years ago, which was
an unwarranted flushable attribute on read-sequence, IIRC).
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
From: Fernando D. Mato Mira
Subject: Re: Referential transparency support missing
Date:
Message-ID: <38CF7A7D.5D984DB9@iname.com>
"Fernando D. Mato Mira" wrote:
> It would be good if someone who really knows this stuff would express
> all this kind of thing the right way.
BTW, probably the first place to look at is "Semantics of Destructive
Lisp",
[still just collecting dust on my bookshelf].
--
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