Load-time evaluation of compound form operators.
Jean-Claude Beaudoin
Usually the operator of a compound form is evaluated for its
functional value at execution time [1].
What if this evaluation of functional value of operators was rather
done at load time? What would be the consequences?
One obvious consequence would be that some form of forward
reference to function definition would have to be provided by mean
of back-patching or something equivalent. But this is hardly new
and unusual since compilers and linkers in other languages have been
handling such things for many decades now.
Another one is that in a multi-threaded context the following
function has an intuitive and predictable behavior (which is
usually to return T or some other equivalent of true) as long as
function foo is stateless and returns a result that is palatable
to =, this even if foo is redefined during the execution of bar.
(defun bar (y) (= (foo y) (foo y)))
And finally, if parts of the machine code generation is done at
load time by the CL runtime system then some significant new
optimizations become available that were not previously possible.
If load-time evaluation of operators is made the default behavior
of then system then a new declaration, say "fspecial", can easily
be provided to allow access to the old behavior of execution-time
evaluation for the few occasions where this could be desirable
or required.
[1] See HyperSpec 3.1.2.1.2.3 at
http://www.lispworks.com/documentation/HyperSpec/Body/03_ababc.htm
Cheers,
Jean-Claude Beaudoin
Bien faire et laisser braire.
Pascal J. Bourguignon
Check rather: http://www.lispworks.com/documentation/HyperSpec/Body/11_abab.htm
and: http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm
Inside a file, any reference to another function in the same file can
be compiled hard-wired (unless the called function is declared
notinline).
Any function in the CL package can be hard-wired, or open-coded (as if
it was declared inline).
What more do you want?
If your implementation doesn't do what you want, just patch it to do it
(in conformance with ANSI CL).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Jean-Claude Beaudoin
>
> Inside a file, any reference to another function in the same file can
> be compiled hard-wired (unless the called function is declared
> notinline).
>
> Any function in the CL package can be hard-wired, or open-coded (as if
> it was declared inline).
>
>
> What more do you want?
>
File scope is not quite enough, it's too limiting. What one wants is more
at the scope of a whole library or sub-system. At the level of an ASDF
one might say.
But thanks for the references, it shows that they were struggling with
the issue even back then...
Pascal J. Bourguignon
> Pascal J. Bourguignon wrote:
>>
>> Inside a file, any reference to another function in the same file can
>> be compiled hard-wired (unless the called function is declared
>> notinline).
>>
>> Any function in the CL package can be hard-wired, or open-coded (as if
>> it was declared inline).
>>
>>
>> What more do you want?
>>
>
> File scope is not quite enough, it's too limiting. What one wants is more
> at the scope of a whole library or sub-system. At the level of an ASDF
> one might say.
Yes, and for that there is of course WITH-COMPILATION-UNIT.
> But thanks for the references, it shows that they were struggling with
> the issue even back then...
And solved it.
Antony
> and: http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm
>
> Inside a file, any reference to another function in the same file can
> be compiled hard-wired (unless the called function is declared
> notinline).
I know in other (staticky :) ) languages, inline generally means no
function call. I see it's the same in CL too.
But in notinline we have two steps, lookup symbol function value cell
and call function?
I did not see any reference to the symbol function cell in the
inline/notline CLHS page. I guess it does not matter?
Interestingly here 'notinline' is not the exact opposite of inline.
So to skip just the symbol look up part , one should arrange the caller
and callee to be in the same compilation unit.
This is an interesting twist on function look ups for sure.
Pascal, how did you even know this. Did you research this, or you
already knew. Just curious.
I am wondering how to make use of this information as a CL user.
I suppose one lesson is , load the whole file if you intend to redefine
any functions?
Thanks,
-Antony
Tim Bradshaw
> Yes, and for that there is of course WITH-COMPILATION-UNIT.
I don't think that this allows the system to treat multiple files as
one. It looks to me that what it does is to cause the system not to
warn about things like undefined functions until the end of the unit,
but not to be able to make the same assumptions it can within a file
(which are much stronger). That's a deficiency, I think - it would be
nice to be able to have an option which says "treat all these files as
one thing". Obviously one could achieve this by concatenating them...
I think I mentioned earlier that it would be nice to have a
finer-grained way of declaring things than NOTINLINE and INLINE.
NOTINLINE says pretty much "assume nothing, you need to look it up
every time", but INLINE says "not only assume the definition is the one
you can see now, but inline it if you can", which is too much. I'd
like "STATIC" which says "the function you call will be the same one
you can see now, but I'm not encouraging you to inline it
particularly". In particular, this declaration would enable the
compiler to assume as much knowledge about user-defined things as it
has about the symbols exported from the CL package.
Pascal J. Bourguignon
> On 9/4/2010 5:50 AM, Pascal J. Bourguignon wrote:
>> and: http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc.htm
>>
>> Inside a file, any reference to another function in the same file can
>> be compiled hard-wired (unless the called function is declared
>> notinline).
> Thanks. I did not know this.
>
> I know in other (staticky :) ) languages, inline generally means no
> function call. I see it's the same in CL too.
> But in notinline we have two steps, lookup symbol function value cell
> and call function?
> I did not see any reference to the symbol function cell in the
> inline/notline CLHS page. I guess it does not matter?
> Interestingly here 'notinline' is not the exact opposite of inline.
> So to skip just the symbol look up part , one should arrange the
> caller and callee to be in the same compilation unit.
>
> This is an interesting twist on function look ups for sure.
> Pascal, how did you even know this. Did you research this, or you
> already knew. Just curious.
I've been reading cll for more than ten years... You could read
archives, with the advantage that you would be able to skip
uninteresting flames.
> I am wondering how to make use of this information as a CL user.
> I suppose one lesson is , load the whole file if you intend to
> redefine any functions?
For this, you would need to check the documentation of your specific
implementation. What the standard specifies is "MAYs", not "MUSTs",
so the actual behavior depends on the implementation.
clisp doesn't do any inlining and always go thru the symbol.
sbcl inlines functions declared inline with sufficient optimization
levels, but doesn't inline other file local functions.
I've not tried other implementations.
Pascal J. Bourguignon
> On 2010-09-05 01:15:17 +0100, Pascal J. Bourguignon said:
>
>> Yes, and for that there is of course WITH-COMPILATION-UNIT.
>
> I don't think that this allows the system to treat multiple files as
> one. It looks to me that what it does is to cause the system not to
> warn about things like undefined functions until the end of the unit,
> but not to be able to make the same assumptions it can within a file
> (which are much stronger). That's a deficiency, I think - it would be
> nice to be able to have an option which says "treat all these files as
> one thing". Obviously one could achieve this by concatenating them...
You're correct, it seems to restrict that to warnings, but the
discussion of the issue mentions that other things including sharing
the compilation environment could be added as extensions.
> I think I mentioned earlier that it would be nice to have a
> finer-grained way of declaring things than NOTINLINE and INLINE.
> NOTINLINE says pretty much "assume nothing, you need to look it up
> every time", but INLINE says "not only assume the definition is the
> one you can see now, but inline it if you can", which is too much.
> I'd like "STATIC" which says "the function you call will be the same
> one you can see now, but I'm not encouraging you to inline it
> particularly". In particular, this declaration would enable the
> compiler to assume as much knowledge about user-defined things as it
> has about the symbols exported from the CL package.
Tim Bradshaw
> You're correct, it seems to restrict that to warnings, but the
> discussion of the issue mentions that other things including sharing
> the compilation environment could be added as extensions.
Yes, you're right - I either had not read properly or had forgotten,
but even the spec says explicitly that you are allowed to add
extensions.
I'd still like something like my approach of being able to declare
things once and for all about functions as well. I'd guess that most
implementations have something like that, because they presumably want
to be able to allow the compiler to make assumptions about internals of
the implementation.
The flip side of this is: if you do go through the symbol things like
redefinition and tracing are probably easier, and is the cost actually
excessive? My guess is that it might not be, but it would be
interesting to hear from implementors on that.
Scott L. Burson
>
> Usually the operator of a compound form is evaluated for its
> functional value at execution time [1].
>
> What if this evaluation of functional value of operators was rather
> done at load time? What would be the consequences?
In most implementations, I believe, this evaluation consists of a single
indirect load instruction. There's less to be saved here than you might
think.
-- Scott
Rob Warnock
+---------------
| clisp doesn't do any inlining and always go thru the symbol.
|
| sbcl inlines functions declared inline with sufficient optimization
| levels, but doesn't inline other file local functions.
|
| I've not tried other implementations.
CMUCL will produce multiple entry points to functions with complex
arg lists (&OPTIONAL, &KEY, etc.): a "generic" entry point for calls
from outside the compilation unit, and possibly additional specialized
entry points for calling from locations in which the target function
is "known". In the latter case(s), the compiler can ensure that the
argument invariants are met at the call site and then call a special
"NO-ARG-PARSING" entry point that skips the normal tests for that
call signature.
Said another way: the compiler can skip the tests for &OPTIONAL, etc.,
if there is an alternate entry point that exactly matches the call site
signature. [And there often will be, if the callee & caller were compiled
together.]
It also supports the INLINE, NOINLINE, and EXTENSIONS:MAYBE-INLINE
declarations:
The EXTENSIONS:MAYBE-INLINE declaration is a CMUCL extension. It is
similar to INLINE, but indicates that inline expansion may sometimes
be desirable, rather than saying that inline expansion should almost
always be done. When used in a global declaration, EXTENSIONS:MAYBE-INLINE
causes the expansion for the named functions to be recorded, but the
functions aren't actually inline expanded unless space is 0 or the
function is eventually (perhaps locally) declared INLINE.
See "Chapter 5: Advanced Compiler Use and Efficiency Hints" in the
"CMUCL User's Manual".
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
smh
place where X3J13 punted on a difficult issue and drafted nonsense.
The problem is that the term "defined in" is not defined in the ANS.
It might be meaningful referring to a regular function, but is quite
ambiguous applied to a generic function which has a distributed
implementation that might or might not extend beyond a single file.
Tim Bradshaw
There seems to be a current trend of depressingly literalist readings
of the spec - a kind of peculiar fundamentalism with the lack of any
willingness (or perhaps ability) to interpret. I'm not sure why it's
happening: probably it's a combination of no-one who was involved in
creating it still posting here and the declining levels of general
education of programmers as it becomes a more specialised skill. It's
really rather sad.
Anyway, so in this case: absent sealing, the set of methods on a
generic function is unbounded. So no, it is not safe to assume you
know the whole definition of the function. It *is* safe to assume you
know that the GF you know is the one which will you will be calling (so
for instance you can avoid the symbol->function lookup, if that matters
to you, and you can optimise away signature checking).
There is one edge case which is: if when calling the GF you know the
exact type of its arguments, and the GF also has *all possible* methods
which might apply to those arguments defined in the same file (so a
full set of before, after, around, and main methods), can you assume
that you know everything? For the sake of argument, I'll say that I
think you can't.
Duane Rettig
> On 2010-09-07 02:00:09 +0100, smh said:
>
> > I'm not sure how to take the would quoted passage. It is yet another
> > place where X3J13 punted on a difficult issue and drafted nonsense.
>
> > The problem is that the term "defined in" is not defined in the ANS.
> > It might be meaningful referring to a regular function, but is quite
> > ambiguous applied to a generic function which has a distributed
> > implementation that might or might not extend beyond a single file.
>
> There seems to be a current trend of depressingly literalist readings
> of the spec - a kind of peculiar fundamentalism with the lack of any
> willingness (or perhaps ability) to interpret. I'm not sure why it's
> happening: probably it's a combination of no-one who was involved in
> creating it still posting here and the declining levels of general
> education of programmers as it becomes a more specialised skill. It's
> really rather sad.
I'm only going to comment on your metacomment here, which was a bit of
unfortunate timing on your part in unleashing your frustration. The
poster you responded to, smh, who is Steve Haflich, is indeed one of
those originally involved with the standardization process; he also
was the chair of the committee which followed up on the spec for many
years afterward (no changes to the spec were made during that time,
due to extreme lack of will of the Common Lisp community to put their
money where their mouths were for committee memberships, but at least
there was enough of a committee left to re-certify the spec as
needed). Steve knows the spec inside and out, and more importantly,
he knows the intentions of the spec, from many different points of
view - he was there, and can tell you where the spec was well-agreed,
and where the design was thin. Sometimes he can even remember (and if
he doesn't he has notes from the X3J13 committee meetings above and
beyond the formally logged actions to remind him) who said what and
why. I always end up consulting Steve when I need to know not only
the literal meaning of the spec, but the intentions behind it.
I don't know what is sad to you; you're hearing from one of the
originals here. He just doesn't pull any punches, so just roll with
it and get up off the floor and try again.
Duane
Thomas A. Russ
> On 2010-09-05 01:15:17 +0100, Pascal J. Bourguignon said:
>
> > Yes, and for that there is of course WITH-COMPILATION-UNIT.
> I think I mentioned earlier that it would be nice to have a
> finer-grained way of declaring things than NOTINLINE and INLINE.
> NOTINLINE says pretty much "assume nothing, you need to look it up every
> time", but INLINE says "not only assume the definition is the one you
> can see now, but inline it if you can", which is too much. I'd like
> "STATIC" which says "the function you call will be the same one you can
> see now, but I'm not encouraging you to inline it particularly". In
> particular, this declaration would enable the compiler to assume as much
> knowledge about user-defined things as it has about the symbols exported
> from the CL package.
Well, I think with either the INLINE or the STATIC, there is also the
implicit promise on the part of the user that he will NOT redefine the
function.
I would expect, as usual with the spec, that if you were to declare a
function STATIC and then redefine it anyway, you couldn't really predict
if the old or new definition were to be used. You can't even get that
guarantee for INLINE declarations, since the compiler is free to choose
not to inline the code.
So I don't think either of these is a real solution to the OP's problem
of multi-thrreading and handling function redefinition during run-time.
--
Thomas A. Russ, USC/Information Sciences Institute
Madhu
* Tim Bradshaw <i64u72$ejm$1...@news.eternal-september.org> :
Wrote on Tue, 7 Sep 2010 09:47:31 +0100:
| On 2010-09-07 02:00:09 +0100, smh said:
|
| There seems to be a current trend of depressingly literalist readings
| of the spec - a kind of peculiar fundamentalism with the lack of any
| willingness (or perhaps ability) to interpret. I'm not sure why it's
| happening: probably it's a combination of no-one who was involved in
| creating it still posting here and the declining levels of general
| education of programmers as it becomes a more specialised skill. It's
| really rather sad.
lies, lies and more lies. pathological.
--
Madhu
Barry Margolin
t...@sevak.isi.edu (Thomas A. Russ) wrote:
> Tim Bradshaw <t...@tfeb.org> writes:
>
> > On 2010-09-05 01:15:17 +0100, Pascal J. Bourguignon said:
> >
> > > Yes, and for that there is of course WITH-COMPILATION-UNIT.
>
> > I think I mentioned earlier that it would be nice to have a
> > finer-grained way of declaring things than NOTINLINE and INLINE.
> > NOTINLINE says pretty much "assume nothing, you need to look it up every
> > time", but INLINE says "not only assume the definition is the one you
> > can see now, but inline it if you can", which is too much. I'd like
> > "STATIC" which says "the function you call will be the same one you can
> > see now, but I'm not encouraging you to inline it particularly". In
> > particular, this declaration would enable the compiler to assume as much
> > knowledge about user-defined things as it has about the symbols exported
> > from the CL package.
>
> Well, I think with either the INLINE or the STATIC, there is also the
> implicit promise on the part of the user that he will NOT redefine the
> function.
>
> I would expect, as usual with the spec, that if you were to declare a
> function STATIC and then redefine it anyway, you couldn't really predict
> if the old or new definition were to be used. You can't even get that
> guarantee for INLINE declarations, since the compiler is free to choose
> not to inline the code.
What we struggled with when writing the standard was that we didn't want
to require specific compiler strategies. So we tried to specify
high-level semantics, but in a way that allowed (and strongly suggested)
these optimizations.
So the term "INLINE" suggests a particular method of optimization, but
the description of it merely *allows* that technique, by specifying that
a redefinition of the function need not have an effect on callers that
were already compiled. We then realized that this same semantic issue
also works for controlling optimization of intra-file calls.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Tim Bradshaw
> I don't know what is sad to you; you're hearing from one of the
> originals here. He just doesn't pull any punches, so just roll with
> it and get up off the floor and try again.
I did not know it was Steve (though if I'd read the address more
carefully I could probably have inferred that). Obviously I know he
was there.
This does not change my view on the stupidity of what he said
unfortunately: without some kind of sealing a generic function can not
ever be completely defined, let alone defined within a single file or
other compilation unit, so the meaning of the spec is quite clear: "is
defined" is not ambiguous at all.
Tim Bradshaw
> So I don't think either of these is a real solution to the OP's problem
> of multi-thrreading and handling function redefinition during run-time.
I think STATIC is exactly such a solution: if you redefine a function
you have declared STATIC then your program is non-conforming and all
bets are off. If you declare it <whatever the opposite of static is,
which is not quite NOTINLINE> then you should not make any such
assumptions, and redefinition ought to work,
Jean-Claude Beaudoin
>
> What we struggled with when writing the standard was that we didn't want
> to require specific compiler strategies. So we tried to specify
> high-level semantics, but in a way that allowed (and strongly suggested)
> these optimizations.
>
> So the term "INLINE" suggests a particular method of optimization, but
> the description of it merely *allows* that technique, by specifying that
> a redefinition of the function need not have an effect on callers that
> were already compiled. We then realized that this same semantic issue
> also works for controlling optimization of intra-file calls.
>
My concern in my OP was not optimization but thread-safety.
Optimization is optional in nature, thread-safety cannot be optional
or at the discretion of the runtime system.
In these days of multi-core CPUs, a language in which a reasonably
thread-safe application cannot be written using normal construct of
the language does not have much of a future.
From experience I get the impression that the average size of
a software product has grown substantially during the last 20 years,
by a factor of 10 to 50 times. A 10K lines compiler is considered
a mere component these days, if it is not seen as a toy. In that
context the relative value of the file as a unit of scope has been
greatly diminished almost to the point of irrelevance.
Cheers,
Jean-Claude Beaudoin
Jean-Claude Beaudoin
I realize now that when I sent my OP I did not appreciate properly
the game changing nature of generic functions.
The behavior of the "bar" function of my OP cannot be predicted
at all if function "foo" happens to be a generic function in
a multi-threaded context.
As currently specified generic functions are functions forever
in flux. This is a powerful feature but also a very difficult one
to control. We need some way to tame it somewhat.
Something like (close-generic-function <gf-name>*) could do the
trick. Such a closed generic function would have a fixed set of
methods and would not be in flux anymore and thus would be much
closer to a normal function.
What to do if a method is added to a closed generic function?
One option would be to simply signal an error but that would
not be very useful. Another one would be to consider this as
a request to create a whole new generic function, one that picks
up where the previous closed generic function left off but with
a new identity and then add the method to this newly open
generic function. (In this here there is a parallel with the
class redefinition semantics I mentioned in a previous post).
A warning could also be considered.
Closed generic function would be thread-safe in the sense of
the OP's "bar" function behavior being predictable again but
it would not be the case for open generic functions.
Cheers,
Jean-Claude Beaudoin
P.S.: Once in a while this newsgroup turns into a very useful forum.
It seems to me that this is one of those occasions. Some progress
could be made here.
Tim Bradshaw
> Something like (close-generic-function <gf-name>*) could do the
> trick. Such a closed generic function would have a fixed set of
> methods and would not be in flux anymore and thus would be much
> closer to a normal function.
This is basically whas sealing (which I mentioned in an earlier thread)
does, although as specified in Dylan it is more general than this.
But surely no-one writes programs which redefine classes or generic
functions and *expects* that stuff to be thread safe?
Thomas A. Russ
Well, I suppose in a narrow sense this is true. But for the OP's
problem, any function that is in fact static won't cause problems
regardless of whether it is declared as such or not. If you don't
redefine it, ever, then you can't have thread issues with redefinition
(by definition).
Other than perhaps inlining, though, I don't see what use a compiler
might make of this information. So I guess I don't see the practical
benefit. Well, maybe there is a sort of "partial inlining" that could
happen where the reference becomes a fixed jump rather than an indirect
one, but without actually inserting the code in place.
Thomas A. Russ
> As currently specified generic functions are functions forever
> in flux. This is a powerful feature but also a very difficult one
> to control. We need some way to tame it somewhat.
>
> Something like (close-generic-function <gf-name>*) could do the
> trick. Such a closed generic function would have a fixed set of
> methods and would not be in flux anymore and thus would be much
> closer to a normal function.
Well, this can, of course, be accomplished by software engineering
practices, such that you never add additional methods to any of the
generic functions once you deploy your system. That makes them
effectively closed. The benefit of an explicit declaration would be
that it would license certain compiler optimizations.
> What to do if a method is added to a closed generic function?
> One option would be to simply signal an error but that would
> not be very useful. Another one would be to consider this as
> a request to create a whole new generic function, one that picks
> up where the previous closed generic function left off but with
> a new identity and then add the method to this newly open
> generic function. (In this here there is a parallel with the
> class redefinition semantics I mentioned in a previous post).
> A warning could also be considered.
Well, I would be a fan of the error answer.
But I'm not at all sure how this whole new generic function thing would
work. Would it just apply to newly compiled code (similarly to what
happens if you redefine a function that has been in-lined?). And if you
do that, there isn't really any benefit over just creating a real, new
generic function and then programming using that one instead.
Otherwise you still are left with an updating problem since you have to
decide when to substitute the new function into the old one. I don't
see how you would be able to automatically find a safe time to do this.
>
> Closed generic function would be thread-safe in the sense of
> the OP's "bar" function behavior being predictable again but
> it would not be the case for open generic functions.
Well, it would be predictable, but it I don't see how it would be
updatable. Especially when you consider that in a real system, the
potential places you have to check would be rather large. In addition
to
(defun bar (x) (+ (foo x) (foo x)))
you also have to worry about
(defun baz (x) (+ (foo x) (bar x)))
where lexical analysis doesn't solve the problem for you.
I suppose one answer might be to have any new definitions only apply in
newly created threads. Then any executing thread maintains its
environment until it terminates, and changes only affect threads created
after the change takes place. But it seems that could be applied
universally and wouldn't need any notion of closed or static functions
to operate in that manner.
Pascal J. Bourguignon
> smh wrote:
>> I'm not sure how to take the would quoted passage. It is yet another
>> place where X3J13 punted on a difficult issue and drafted nonsense.
>>
>> The problem is that the term "defined in" is not defined in the ANS.
>> It might be meaningful referring to a regular function, but is quite
>> ambiguous applied to a generic function which has a distributed
>> implementation that might or might not extend beyond a single file.
>
> I realize now that when I sent my OP I did not appreciate properly
> the game changing nature of generic functions.
>
> The behavior of the "bar" function of my OP cannot be predicted
> at all if function "foo" happens to be a generic function in
> a multi-threaded context.
>
> As currently specified generic functions are functions forever
> in flux. This is a powerful feature but also a very difficult one
> to control. We need some way to tame it somewhat.
>
> Something like (close-generic-function <gf-name>*) could do the
> trick. Such a closed generic function would have a fixed set of
> methods and would not be in flux anymore and thus would be much
> closer to a normal function.
A normal function. Such as this one for example:
(defvar *commands* (make-hash-table))
(defun do-command (object)
(funcall (gethash (class-name (class-of object)) *commands*
(lambda (object)
(error "There's no command for an ~A such as ~S"
(class-name (class-of object)) object)))
object))
(defun add-command (class cmd)
(setf (gethash class *commands*) cmd))
(defmacro define-command ((object class) &body body)
`(add-command ',class (lambda (,object) ,@body)))
> What to do if a method is added to a closed generic function?
What to do if a function makes use of run-time data?
> Closed generic function would be thread-safe in the sense of
> the OP's "bar" function behavior being predictable again but
> it would not be the case for open generic functions.
Yes. And functions that would not modify data at run-time would be
thread-safe too. You want a pure functional language. Unfortunately:
1- state and state-modification is good (in measured ways),
2- even in a pure functional language, you can reintroduce state and
state-modification (by way of monads). I don't know enough about
them, but I'd suspect you'd be back to step 1, thread-wise.
> P.S.: Once in a while this newsgroup turns into a very useful forum.
> It seems to me that this is one of those occasions. Some progress
> could be made here.
IMO, the newsgroups only fall down to flames and chitchat when there's
no interesting questions like yours passing by. What we need, is more
interesting queries!
Pascal J. Bourguignon
By adding STATIC (or FINAL) to Lisp, you're collapsing it to the level
of the other programming languages where programs are not modifiable
(extendable) at run-time.
Then what would be the point of using Lisp at all?
Barry Margolin
Jean-Claude Beaudoin <jean.claud...@gmail.com> wrote:
> Barry Margolin wrote:
> >
> > What we struggled with when writing the standard was that we didn't want
> > to require specific compiler strategies. So we tried to specify
> > high-level semantics, but in a way that allowed (and strongly suggested)
> > these optimizations.
> >
> > So the term "INLINE" suggests a particular method of optimization, but
> > the description of it merely *allows* that technique, by specifying that
> > a redefinition of the function need not have an effect on callers that
> > were already compiled. We then realized that this same semantic issue
> > also works for controlling optimization of intra-file calls.
> >
>
> My concern in my OP was not optimization but thread-safety.
> Optimization is optional in nature, thread-safety cannot be optional
> or at the discretion of the runtime system.
Unfortunately, when we were writing the standard, we implicitly assumed
single threading. Although we knew that most Lisp implementations
supported multi-threading, it was too big a can of worms to open at the
time in the standard. So if you want to address these issues, you have
to resort to implementation-specific extensions.
Jean-Claude Beaudoin
>
> Unfortunately, when we were writing the standard, we implicitly assumed
> single threading. Although we knew that most Lisp implementations
> supported multi-threading, it was too big a can of worms to open at the
> time in the standard. So if you want to address these issues, you have
> to resort to implementation-specific extensions.
>
We keep hearing about that big can of worms but how big is it really?
Beside two minor issues (one with packages and the other with
readtables) that are almost trivially resolved each by the use of
a specific lock, entirely internal to the runtime system, all I
could find are the two issues I raised in my recent c.l.l. posts
((1) CLOS class redefinition, (2) load-time evaluation of operators
which is in fact addressing function redefinition).
All this can be expressed in less than 2 regular pages of text
in the style of ANSI standard.
What else is there really?
Fear of the unknown seem to have been well at work here.
I think the issues are not that numerous and not that large either.
They may be cutting somewhat deep (like (2)) but that is pretty
much it.
I have also a problem with the idea that "implementation-specific
extensions" are enough to solve the thread-safety question.
Do you consider my two latest propositions ((1) and (2) as
referred above) to be within the scope of such extensions?
Cheers,
Jean-Claude Beaudoin
P.S.: I almost forgot that I said previously that the existence
of a lock on the CLOS metadata had to be part of the CLOS public
interface. That makes for public issue (3). All this one requires
is one more line on the page of each concerned CLOS entry point.
This one can easily be seen as an extension.
Jean-Claude Beaudoin
>
> Well, this can, of course, be accomplished by software engineering
> practices, such that you never add additional methods to any of the
> generic functions once you deploy your system. That makes them
> effectively closed. The benefit of an explicit declaration would be
> that it would license certain compiler optimizations.
>
I certainly hope for those optimizations.
>
> But I'm not at all sure how this whole new generic function thing would
> work. Would it just apply to newly compiled code (similarly to what
> happens if you redefine a function that has been in-lined?). And if you
> do that, there isn't really any benefit over just creating a real, new
> generic function and then programming using that one instead.
I do work with the assumption that operators are to be evaluated at
load-time. So it is not so much newly compiled than newly loaded code.
>
> Otherwise you still are left with an updating problem since you have to
> decide when to substitute the new function into the old one. I don't
> see how you would be able to automatically find a safe time to do this.
> ...
> you also have to worry about
>
> (defun baz (x) (+ (foo x) (bar x)))
>
> where lexical analysis doesn't solve the problem for you.
>
In the CL implementation I am currently working on (that is a
derivative of ECL) the execution of function "load" is done under a
lock therefore there happens to be a single total order imposed
on function (and other) definitions by that lock. I was hoping
not to have to use such an implementation specific detail during
this discussion but it seems unavoidable now.
> I suppose one answer might be to have any new definitions only apply in
> newly created threads. Then any executing thread maintains its
> environment until it terminates, and changes only affect threads created
> after the change takes place. But it seems that could be applied
> universally and wouldn't need any notion of closed or static functions
> to operate in that manner.
>
This one is beyond my understanding right now. I'll have to think some
more about it...
Cheers,
Jean-Claude Beaudoin
Jean-Claude Beaudoin
>
> A normal function. Such as this one for example:
>
> (defvar *commands* (make-hash-table))
>
> (defun do-command (object)
> (funcall (gethash (class-name (class-of object)) *commands*
> (lambda (object)
> (error "There's no command for an ~A such as ~S"
> (class-name (class-of object)) object)))
> object))
>
> (defun add-command (class cmd)
> (setf (gethash class *commands*) cmd))
>
> (defmacro define-command ((object class) &body body)
> `(add-command ',class (lambda (,object) ,@body)))
>
You have here exposed in the application the core of the usual caching
done by generic function on their effective methods. But since all
that data is in the application space and directly available to it
it becomes its responsibility to assure its thread-safety.
What I have issues with is all that state that is hidden inside
the core of the CL runtime system and that is out of direct reach
from the application. That state is the responsibility of the CL
runtime system and its thread-safety must assured by the system.
>
> Yes. And functions that would not modify data at run-time would be
> thread-safe too. You want a pure functional language.
I wouldn't be here if that were the case.
Jean-Claude Beaudoin
Pascal J. Bourguignon
> Barry Margolin wrote:
>>
>> Unfortunately, when we were writing the standard, we implicitly
>> assumed single threading. Although we knew that most Lisp
>> implementations supported multi-threading, it was too big a can of
>> worms to open at the time in the standard. So if you want to
>> address these issues, you have to resort to implementation-specific
>> extensions.
>>
>
> We keep hearing about that big can of worms but how big is it really?
>
> Beside two minor issues (one with packages and the other with
> readtables) that are almost trivially resolved each by the use of
> a specific lock, entirely internal to the runtime system, all I
> could find are the two issues I raised in my recent c.l.l. posts
> ((1) CLOS class redefinition, (2) load-time evaluation of operators
> which is in fact addressing function redefinition).
>
> All this can be expressed in less than 2 regular pages of text
> in the style of ANSI standard.
>
> What else is there really?
A lot actually.
One key feature that makes lisp so interesting, is data structure
sharing. In particular, the fact that there is not LIST abstract data
type in lisp (cf.
http://groups.google.com/group/comp.lang.lisp/msg/61a6e3354faf17ba
) and most lisp functions make it easy to share the tail of a chain of
conses amongst several heads.
On the other hand, lisp doesn't shy away from mutation, (given its
history, it had to run on machines where memory was scarse, and at a
time when garbage collection algorithms where slower, so mutation was
needed to avoid some ineficiencies). Still today, mutation can give
an advantage, in increasing locality.
The combination of these two features with threading is explosive,
because about half of the CL primitive may be implemented with
mutation, and therefore would require locks. The problem being that
you cannot really automatize these locks either, because sometimes the
semantics require global locks, and sometimes they could do with one
lock per cons (which in either case is problematic).
> Fear of the unknown seem to have been well at work here.
> I think the issues are not that numerous and not that large either.
> They may be cutting somewhat deep (like (2)) but that is pretty
> much it.
I would agree with you here, in that the solution so far has been to
acknowledge that in practice, programmers can write threaded programs
without having an underlying thread-safe set of primitives.
The problems really start to occur when you try to find a general
solution to be implemented for all the programs, at the level of the
implementation.
That said, even if there would be theorical problems, again, I agree
with you that you could come up with an implementation having some
thread-safety features that would work well in practice, for actual
programs.
You're free to implement such a thread-safe CL, the standard happily
doesn't restrict you in any way there.
> I have also a problem with the idea that "implementation-specific
> extensions" are enough to solve the thread-safety question.
> Do you consider my two latest propositions ((1) and (2) as
> referred above) to be within the scope of such extensions?
Personnaly, I would prefer an implementation doing a good job at any
feature (eg. thread safety in this case), without adding anything to
the language. A kind of "transparent" extension. But indeed, you
could add, as all implementation does, extensions to help you provide
the feature. Try to make it non-obtrusive.
Pascal J. Bourguignon
> Pascal J. Bourguignon wrote:
>>
>> A normal function. Such as this one for example:
>>
>> (defvar *commands* (make-hash-table))
>>
>> (defun do-command (object)
>> (funcall (gethash (class-name (class-of object)) *commands*
>> (lambda (object)
>> (error "There's no command for an ~A such as ~S"
>> (class-name (class-of object)) object)))
>> object))
>>
>> (defun add-command (class cmd)
>> (setf (gethash class *commands*) cmd))
>>
>> (defmacro define-command ((object class) &body body)
>> `(add-command ',class (lambda (,object) ,@body)))
>>
>
> You have here exposed in the application the core of the usual caching
> done by generic function on their effective methods. But since all
> that data is in the application space and directly available to it
> it becomes its responsibility to assure its thread-safety.
>
> What I have issues with is all that state that is hidden inside
> the core of the CL runtime system and that is out of direct reach
> from the application. That state is the responsibility of the CL
> runtime system and its thread-safety must assured by the system.
This is a preconceived idea. You should assess it on its technical merits.
For example, OS before unix wanted to deal with interuptions during
syscalls. Unix said that after all, if an interrupt occurs even
during a syscall, it's simplier and more efficient to let the
application deal with it. Great success ensued.
Tim Bradshaw
> Other than perhaps inlining, though, I don't see what use a compiler
> might make of this information. So I guess I don't see the practical
> benefit. Well, maybe there is a sort of "partial inlining" that could
> happen where the reference becomes a fixed jump rather than an indirect
> one, but without actually inserting the code in place.
Really, my notion was that this would allow the same assumptions to be
made about things between files as they are within files, without
asking for inlining.
Tim Bradshaw
> By adding STATIC (or FINAL) to Lisp, you're collapsing it to the level
> of the other programming languages where programs are not modifiable
> (extendable) at run-time.
>
> Then what would be the point of using Lisp at all
Well, that's a good question (FINAL is better than STATIC I think). My
idea was really that, at the moment the only way of allowing the
compiler to make various assumptions about things is to put them in the
same file, and in the spirit of flexibility it would be nice if there
was a way of allowing it to make thos assumptions more generally. I
imagine that adding declarations like this would happen very late in
the development process indeed, if at all.
However. I haven't really followed all the details of this thread, but
it does seem to me (as I think I said in some other message) that
there's an enormous difference between (say) making redefinition of
functions/classes/whatever thread-safe, and making a *system* (or
application) thread-safe in the presence of redefinition.
An analogy would be the Unix filesystem. Let's assume that replacing a
file by another file is atomic in Unix. (I think it probably is,
because I think rename(2) is atomic, and you can replace a file by
another file by copying the new file in place next to the original
file, and then using rename(2) to snap the links. The old version will
even continue to exist until the last thing that has it open goes away,
which is a nice property. But if this is wrong, assume we can fix
things so it's right.) Does this property help significantly with
updating software installed on Unix systems? Unfortunately, no, it
doesn't, because almost all software consists of many files &
directories spread over the filesystem which have complex
interdependencies. When updating a package or installing a patch,
there's a significant period where everything is inconsistent because
some of the new stuff is in place, but some of it is not.
So atomicity at the file level isn't what you need: you need something
much more complicated and application-specific, which probably loooks a
lot like transactions in a database: changes to a lot of related things
which either entirely commit or do not commit at all.
For a Lisp system something like the same thing holds: if I want to
make some modification to a running system then unless I am extremely
lucky that modification will not consist of changing the definition of
a single (generic) function or class: it will consist of a whole bunch
of related things which must all either go into the system, or none of
which must. The approach I've taken to this has always been to provide
some mechanism for loading a complete parallel copy of things, and then
snapping some top-level link which changes the world (while leaving the
old world there).