From: Christopher C. Stacy
Subject: CLOS block compilation type checking
Date:
Message-ID: <uwtqjij1c.fsf@news.dtpq.com>
Are there any actual existing compilers that allow me to check
a block of code to ensure that (within the block) all required
methods have been implemented? This means tracing all sources
of CLOS instances (method arglists, MAKE-INSTANCE calls, and
user type declarations), and comparing all method calls against
those types versus the defined method (eg. DEFMETHOD) definitions.
There still might be places in the program where the method
call could not be determined ahead of time; those would just
be noted. But it seems like most calls could be checked.
(This may or not be related to the implementation of features
for precomputing combined methods or sealing.)
Christopher C. Stacy <······@news.dtpq.com> wrote:
+---------------
| Are there any actual existing compilers that allow me to check
| a block of code to ensure that (within the block) all required
| methods have been implemented?
+---------------
What do you mean by "required" methods? Required by whom?
Your application's internal design methodology? [E.g., "All
calls shall be to methods explicitly specialized on their
first arguments to subclasses of class FOO & third arguments
to subclasses of class BAR."] If so, how is the compiler to
know what that coding style is?
That said, if all you want to do is catch calls that fail
to hit some explicitly-specializing method, then wrap a
macro around DEFGENERIC that defines a method with no
specialized args (a.k.a. specialized on T for each arg),
and put an ERROR call there.
Or am I missing something obvious about your question?
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
>>>>> "RW" == Rob Warnock <····@rpw3.org> writes:
CS> Christopher C. Stacy <······@news.dtpq.com> wrote:
CS> Are there any actual existing compilers
CS> that allow me to check a block of code to ensure that
CS> (within the block) all required methods have been
CS> implemented?
RW> What do you mean by "required" methods? Required by whom?
RW> Your application's internal design methodology? [E.g., "All
RW> calls shall be to methods explicitly specialized on their
RW> first arguments to subclasses of class FOO & third arguments
RW> to subclasses of class BAR."] If so, how is the compiler to
RW> know what that coding style is?
I couldn't see how either. Perhaps he's constraining what he wants in
some way. I think if the types/classes could be statically known at
the call site at compile time, then the dispatch machinery could work
then also and other kinds of wonders could be had. (remember this is
a block, so CLOS in inner loops would cost nothing extra, methods could
be inlined etc.). Chris?
RW> That said, if all you want to do is catch calls that fail to
RW> hit some explicitly-specializing method, then wrap a macro
RW> around DEFGENERIC that defines a method with no specialized
RW> args (a.k.a. specialized on T for each arg), and put an ERROR
RW> call there.
True enough, but he'd get kicked into the debugger anyway if CLOS can't
find an applicable method. No? How is a catch-all method that calls
error an improvement on this? He wanted something to warn at compile
time anyway. Now I am confused both about the question and your answer.
RW> Or am I missing something obvious about your question?
The same thing I am prolly. Am I missing something about your answer?
cheers,
BM
Bulent Murtezaoglu <··@acm.org> wrote:
+---------------
| >>>>> "RW" == Rob Warnock <····@rpw3.org> writes:
| RW> That said, if all you want to do is catch calls that fail to
| RW> hit some explicitly-specializing method, then wrap a macro
| RW> around DEFGENERIC that defines a method with no specialized
| RW> args (a.k.a. specialized on T for each arg), and put an ERROR
| RW> call there.
|
| True enough, but he'd get kicked into the debugger anyway if CLOS can't
| find an applicable method. No? How is a catch-all method that calls
| error an improvement on this? He wanted something to warn at compile
| time anyway. Now I am confused both about the question and your answer.
|
| RW> Or am I missing something obvious about your question?
|
| The same thing I am prolly. Am I missing something about your answer?
+---------------
Yeah, actually, I think *I* missed something about my answer, like
going far enough to make it useful... ;-}
I guess I was thinking about the situation where you had a *very*
general method, say, PRINT-OBJECT, that might have reasonable defaults
for objects in T and subclasses of other types, but where you wanted
to do something specific for subclasses of your own class FOO. Then you
could have the "error" method specialize for FOO, which would catch any
calls for args of subclasses of FOO that *didn't* have PRINT-OBJECT
(or whatever) methods specialized for them. Hmmm... As I recall, there
was even some discussion of this very thing a while back when trying
to ensure that only subclasses of certain classes were permitted to
be instantiated. Something about making INITIALIZE-INSTANCE error when
called on the parent class, and having INITIALIZE-INSTANCE specialized
on the children *not* do CALL-NEXT-METHOD (or something).
And as far as your observation that "He wanted something to warn at
compile time anyway" goes... Oops. I missed that bit. Mea culpa.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Christopher C. Stacy
Subject: Re: CLOS block compilation type checking
Date:
Message-ID: <u1x8nuzxg.fsf@news.dtpq.com>
····@rpw3.org (Rob Warnock) writes:
> Bulent Murtezaoglu <··@acm.org> wrote:
> | RW> Or am I missing something obvious about your question?
> | The same thing I am prolly. Am I missing something about your answer?
> And as far as your observation that "He wanted something to warn at
> compile time anyway" goes... Oops. I missed that bit. Mea culpa.
Is it fairly clear what I am asking for, or is there still confusion?
(Apparently none of the existing compilers do what I am asking for.)
Christopher C. Stacy <······@news.dtpq.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Bulent Murtezaoglu <··@acm.org> wrote:
| > | RW> Or am I missing something obvious about your question?
| > | The same thing I am prolly. Am I missing something about your answer?
| > And as far as your observation that "He wanted something to warn at
| > compile time anyway" goes... Oops. I missed that bit. Mea culpa.
|
| Is it fairly clear what I am asking for, or is there still confusion?
+---------------
If by "required methods" you mean that a covering set of methods
has been defined for which a call of your generic functions will
never invoke NO-APPLICABLE-METHOD at run-time, then I suspect you're
asking for the impossible... in general, that is.
In certain limited domains you (or a "sufficiently-smart compiler")
might be able to prove that no possible input data- or control-flow
path would result in a call of one of your generic functions with
an argument list which would result in a call to NO-APPLICABLE-METHOD
[that is, an arg list for which COMPUTE-APPLICABLE-METHODS would
return NIL]. And wrapping your DEFGENERICs and DEFMETHODs in
"sufficiently-smart macros" might be one approach to that.
But in general [e.g., with data passed in from outside the compilation
block, or really convoluted code] that computation is equivalent to the
Halting Problem, and thus not likely to be provided by a vendor. ;-}
+---------------
| (Apparently none of the existing compilers do what I am asking for.)
+---------------
Yeah, probably not.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Christopher C. Stacy
Subject: Re: CLOS block compilation type checking
Date:
Message-ID: <u64xz9f7u.fsf@news.dtpq.com>
····@rpw3.org (Rob Warnock) writes:
> If by "required methods" you mean that a covering set of methods
> has been defined for which a call of your generic functions will
> never invoke NO-APPLICABLE-METHOD at run-time, then I suspect you're
> asking for the impossible... in general, that is.
Yes, I think you have got it. I want the compiler to check
a complete program to see that applicable methods exist for
every generic function call. (I went on to indicate that
in some situations, the compiler might not be able to do
enough type inferencing on the function call arguments,
and it would be acceptable for it to simply note those.)
This all probably happens at compile-time, but if it helps,
it would be okay to do it after the program has been loaded.
The purpose is to check for undefined functions before
delivering a program (like how normal functions are checked).
In some cases, the results of this static analysis might be
usable for optimization, but that's not what I'm asking for.
> But in general [e.g., with data passed in from outside the compilation
> block, or really convoluted code] that computation is equivalent to the
> Halting Problem, and thus not likely to be provided by a vendor. ;-}
No CLOS objects would be passed in from outside the program.
Data such as numbers and strings are passed in from outside,
But we are not concerned with trick questions like READ or EVAL.
We are concerned only with lexically apparent data types and
other things that the compiler already knows how to infer.
I don't see offhand what's so hard about keeping a list of calls
to MAKE-INSTANCE, keeping track of all constant symbols to see if
they might ever be used as class names passed into MAKE-INSTANCE,
similarly maintaining function and method call graphs, and then
computing the resulting set of CLOS methods that might be called.
Then you check that against all the method signatures that you compiled.
This won't match some calls that are specialized on non-CLOS types.
But otherwise, it's just type inference, and I don't see why it
should be impossible.
A similar feature would be about condition handling, except
that instead of DEFMETHOD and calls, it's HANDLER-CASE/BIND
and SIGNAL. This assumes the compiler knows all the possible
conditions that built-in functions could ever signal (just
like it knows what types PARSE-INTEGER might return).
This seems harder to me, but I think it's probably really
just exactly the same problem with different syntax.
The goal is to make sure that no errors ever escape the
program. (A shortcut is to look at the call graph and
see if the most toplevel function handles ERROR, etc.)
Maybe I'm being dumb and forgetting something obvious?
Hi
I tried to send you something in private, but maybe it did not work.
I have been thinking along these lines for quite some time. This is the
reason why I wrote CL-UNIFICATION to start with.
Essentially I want something that does the following (the inspiration
being ML modules, C++ templates, Ada generics and Java generics)
Suppose you can write something like
(defprotocol dictionary-protocol ()
(:classes (dictionary key))
(defgeneric lookup (dictionary key))
(defgeneric insert (dictionary key value)))
Then you could write something like
(defimplementation dictionary-protocol ((dictionary hash-table)
(key string number symbol))
((:check-when :compile-toplevel))
(defvar *the-dictionary* (make-hash-table :test #'equalp))
;; LOOKUP methods.
(defmethod lookup ((dictionary hash-table) (key string))
#| code here |#)
(defmethod lookup ((dictionary hash-table) (key number))
#| code here |#)
(defmethod lookup ((dictionary hash-table) (key symbol))
#| code here |#)
;; INSERT methods.
(defmethod insert ((dictionary hash-table) (key string) value)
#| code here |#)
(defmethod insert ((dictionary hash-table) (key number) value)
#| code here |#)
(defmethod insert ((dictionary hash-table) (key symbol) value)
#| code here |#)
)
which expanded into something like
(progn
(defvar *the-dictionary* (make-hash-table :test #'equalp))
;;; LOOKUP and INSERT `defmethods' here.
(eval-when (:compile-toplevel)
(let ((new-implementation
(make-protocol-instance 'dictionary
:class-specifications
'((dictionary hash-table)
(key string number symbol)))))
(check-protocol-implementation new-implementation)
new-implementation)
))
The CHECK-PROTOCOL-IMPLEMENTATION routine will check that every
DEFGENERIC in the DEFPROTOCOL has implementations for all the possible
argument combinations specified in the :CLASS-SPECIFICATIONS slot.
IMHO this will go some way along the way you want. I already have some
code sitting around, but it is a toy project for me and don't have much
time to work on it.
Cheers
--
Marco
Christopher C. Stacy wrote:
> ····@rpw3.org (Rob Warnock) writes:
>
>
>>If by "required methods" you mean that a covering set of methods
>>has been defined for which a call of your generic functions will
>>never invoke NO-APPLICABLE-METHOD at run-time, then I suspect you're
>>asking for the impossible... in general, that is.
>
>
> Yes, I think you have got it. I want the compiler to check
> a complete program to see that applicable methods exist for
> every generic function call. (I went on to indicate that
> in some situations, the compiler might not be able to do
> enough type inferencing on the function call arguments,
> and it would be acceptable for it to simply note those.)
> This all probably happens at compile-time, but if it helps,
> it would be okay to do it after the program has been loaded.
>
> The purpose is to check for undefined functions before
> delivering a program (like how normal functions are checked).
>
> In some cases, the results of this static analysis might be
> usable for optimization, but that's not what I'm asking for.
>
>
>>But in general [e.g., with data passed in from outside the compilation
>>block, or really convoluted code] that computation is equivalent to the
>>Halting Problem, and thus not likely to be provided by a vendor. ;-}
>
>
> No CLOS objects would be passed in from outside the program.
> Data such as numbers and strings are passed in from outside,
> But we are not concerned with trick questions like READ or EVAL.
> We are concerned only with lexically apparent data types and
> other things that the compiler already knows how to infer.
>
> I don't see offhand what's so hard about keeping a list of calls
> to MAKE-INSTANCE, keeping track of all constant symbols to see if
> they might ever be used as class names passed into MAKE-INSTANCE,
> similarly maintaining function and method call graphs, and then
> computing the resulting set of CLOS methods that might be called.
> Then you check that against all the method signatures that you compiled.
> This won't match some calls that are specialized on non-CLOS types.
> But otherwise, it's just type inference, and I don't see why it
> should be impossible.
>
> A similar feature would be about condition handling, except
> that instead of DEFMETHOD and calls, it's HANDLER-CASE/BIND
> and SIGNAL. This assumes the compiler knows all the possible
> conditions that built-in functions could ever signal (just
> like it knows what types PARSE-INTEGER might return).
> This seems harder to me, but I think it's probably really
> just exactly the same problem with different syntax.
> The goal is to make sure that no errors ever escape the
> program. (A shortcut is to look at the call graph and
> see if the most toplevel function handles ERROR, etc.)
>
> Maybe I'm being dumb and forgetting something obvious?
>
Christopher C. Stacy <······@news.dtpq.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > If by "required methods" you mean that a covering set of methods
| > has been defined for which a call of your generic functions will
| > never invoke NO-APPLICABLE-METHOD at run-time, then I suspect you're
| > asking for the impossible... in general, that is.
| ..
| I don't see offhand what's so hard about keeping a list of calls
| to MAKE-INSTANCE, keeping track of all constant symbols to see if
| they might ever be used as class names passed into MAKE-INSTANCE,
| similarly maintaining function and method call graphs, and then
| computing the resulting set of CLOS methods that might be called.
| Then you check that against all the method signatures that you compiled.
| This won't match some calls that are specialized on non-CLOS types.
| But otherwise, it's just type inference, and I don't see why it
| should be impossible.
+---------------
[Last try at expressing my concern...]
I think I was more concerned that simple control-flow analysis
might not be enough to solve your problem, specifically, might
not be enough to prevent false positives -- claims of errors
that aren't. For example, suppose you have a conditional:
(if (some-predicate foo)
(method-A foo)
(method-B foo))
where FOO is a passed-in value of some variable class. Now suppose
SOME-PREDICATE was deliberately [or accidentally!] coded as a "guard"
to keep METHOD-A from being called when the value of FOO would cause
NO-APPLICABLE-METHOD, but the tool you're asking for can't tell that --
that is, it isn't a full theorem prover on programs [which is where
the "halting problem" issue came in, a.k.a. "decidability"]. Then you
checking tool would have no choice but to report the (METHOD-A FOO)
call as a violation, because *sometimes* the IF would be executed
when FOO had a value for which there was no applicable METHOD-A
[even though SOME-PREDICATE would never let that happen].
Now you might say, "Oh, I don't care about that; I'll resolve all
the false positives manually myself." You can say that, and it even
might be true for you on the code that you write, with the checking
tool being implemented at some level, but... in *general* I believe
it is not a 100% solvable problem. Specifically, there might be input
programs for which nearly *all* the error messages from the checking
tool are false positives, which would not be good.
All I'm saying is that "it depends": on your coding style, on the
problem domain, on the total complexity of the systems you need to
check, etc. A quick & dirty heuristic algorithm might well get you
95% of what you want... or it might not.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Christopher C. Stacy
Subject: Re: CLOS block compilation type checking
Date:
Message-ID: <u3bt0ldf6.fsf@news.dtpq.com>
····@rpw3.org (Rob Warnock) writes:
> A quick & dirty heuristic algorithm might well get you 95% of what you want
It might well get me 100% of what I want, if I want the false positives.
I am not asking for the code to be proved, just for a list of
all method calls which appear anywhere in the program.