T 0121/06 (Garbage collection/TAO GROUP) 25-01-2007
Download and more information:
Garbage collection
Claims - clarity (yes)
Claims - two-part form (inappropriate)
Garbage collector - computer program as such (no)
Data stream - presentation of information (no)
Text considered by the examining division in the communication under Rule 51(4) EPC agreed by the applicant (no)
Right to be heard (infringed)
Decision reasoned (no)
Substantial procedural violations (yes)
Reimbursement of the appeal fee (yes)
I. This appeal is against the decision of the examining division to refuse European patent application No. 01915523.3 on the ground of lack of clarity (Article 84 EPC).
II. The patent application was filed on 28 March 2001. In a first communication, dated 16 May 2003, the examining division objected inter alia that the independent claims did not contain all the essential features of the invention. The appellants were required to state what features in the claims were not known with respect to two documents contained in the International Search Report and what their technical significance was. In a reply dated 19 November 2003 the appellants filed amendments and explained the prior art to the examining division, indicating the differences the invention in their opinion represented with respect to it.
The examining division's next procedural step was to summon the appellants to oral proceedings. In the annex to the summons the objection that the claimed subject-matter was a non-invention (Article 52(2) EPC) was raised for the first time. At the oral proceedings on 2 April 2004 the appellants filed amended claims. The examining division regarded these claims as overcoming all previous objections and indicated its intention to grant a patent.
A communication under Rule 51(4) EPC was issued on 1 June 2004. In an annex a new document was introduced:
D4: G. May Yip, "Incremental, generational mostly-copying garbage collection in uncooperative environments", Thesis, The Department of Electrical Engineering and Computer Science, MIT, May 1991.
The examining division informed the appellants that D4 was now regarded as the closest prior art. A comparison of the invention and D4 was made, leading to the conclusion that the subject-matter of the claims filed at the oral proceedings lacked an inventive step. The examining division explained that it therefore had amended these claims. The features of dependent claims 8 and 15, said to be essential, had been inserted in independent claims 1 and 9, respectively, together with a passage taken from the description. The independent claims had been drafted in two-part form based on D4. Claims 8 and 15 had been deleted and the description correspondingly modified.
The appellants sharply protested against this course of action, which they qualified as a substantial procedural violation, and disagreed with the majority of the amendments made as well as with the examining division's analysis of D4. The examining division then issued a communication pursuant to Article 96(2) EPC, arguing that the modifications it had proposed to the claims were minor but nevertheless necessary, that it could not discern any gross procedural violations, and that a decision according to the state of the file would be rendered without further delay if the appellants so desired.
By letter dated 20 April 2005 the appellants filed amended claims and indicated that they did not wish to engage in further correspondence prior to grant. If the examining division felt unable to grant a patent on the basis of the papers on file the appellants requested a formal decision which could be taken to appeal. Following this, the examining division issued a brief communication pursuant to Article 96(2) EPC, dated 6 June 2005, stating that the first examiner, after several unsuccessful attempts to contact the appellants' representative by telephone, had left him a voice mail message. The message was that the examining division was in a position to issue a negative decision on the basis of the documents and comments on file unless the applicants informed the division that it was not their actual intention not to request oral proceedings. The appellants replied by letter dated 5 August 2005 that the examining division had not provided any hint of its current reasoning on the basis of which it intended to issue a decision. They confirmed their wish not to receive further communications pursuant to Article 96(2) EPC or attend further oral proceedings at first instance.
The application was refused on 31 August 2005.
III. In the statement of grounds of appeal dated 10 January 2006 the appellants requested that the decision be set aside and a patent be granted on the basis of the claims that were filed at the oral proceedings before the examining division.
The appellants interpreted the decision in the way that the objection of lack of clarity rested on two points, namely the division of claim 1 into two-part form based on D4 and the use of the expression "interior pointer" in claim 1. In the appellants' view these objections were unsustainable.
IV. The appellants further argued that the examining division had committed a number of substantial procedural violations and requested that the appeal fee be accordingly refunded.
Firstly, it was unreasonable and unfair on the appellants for the wording which had been agreed upon in oral proceedings to be entirely overturned by what amounted to a unilateral continuation of the proceedings on an entirely new basis. Searches should be carried out before holding oral proceedings. If in this case an additional search had been carried out after the hearing, this was quite clearly a procedural violation.
Secondly, it was inappropriate in a communication under Rule 51(4) EPC to propose substantial and radical amendments to the claims, making significant restrictions which were not discussed at the oral proceedings and which the applicants had had no opportunity of commenting on. The correct approach would have been to continue the proceedings in writing by the issuance of a further official communication. As it was, the appellants had no option but to prepare and file translations of the claims into French and German. The claims had since been modified again and would almost certainly need to be retranslated at additional cost at the conclusion of the appeal proceedings. These additional costs to the appellants could have been avoided either by the examining division issuing another official communication and/or by promptly withdrawing the Rule 51(4) communication when it became clear that the proposed amendments were unacceptable to the appellants and proceedings would have to be continued in writing.
Thirdly, the official communication of 6 June 2005 set a deadline for the appellants to meet (effectively, to withdraw a previous request) without giving any indication whatsoever of the basis on which the examining division felt it was "in a position to issue a negative decision", as stated in the communication. Neither the communication nor the examiner's earlier telephone calls and voicemail message gave any indication of the alleged deficiencies which still remained. It was a procedural violation to require the appellants to "remedy the indicated deficiencies" within a stated period when, in fact, no such deficiencies had been set out, and it was a significant procedural violation for the examiner to try to force the appellants to take a particular course of action, viz. to rescind an earlier request, while withholding information which must be relevant to whether the appellant wished to take that action. An applicant had a legitimate expectation of being told in advance the precise grounds upon which a decision to refuse is being considered by an examining division.
V. In a communication from the Board of 27 July 2006 the opinion was expressed that the decision under appeal was not well founded and that the claimed subject-matter was patentable. Some amendments to the application mainly of a formal nature were suggested which would enable the Board to order a patent to be granted. The Board considered that the examining division had committed a substantial procedural violation which justified the appeal fee to be reimbursed.
VI. By letter dated 24 August 2006, followed up by a further letter dated 22 November 2006, the appellants filed revised claims 1-25 and description pages 3-7.
Claims 1, 9, 17, 21, 22 and 25 read:
"1. A method of garbage collection in a computer memory, including:
(i) on a creation of a memory allocation (a-g) having a size and location in a memory, adding a reference to said allocation to a dynamic tree structure comprising a plurality of linked nodes (40-52), each node being representative of the size and location of a respective memory allocation, and the nodes being ordered within the tree in dependence upon the said location;
(ii) for an in-use pointer (p), searching the tree to determine the memory allocation (c) to which the pointer points; and
(iii) noting the said memory allocation (c) as being unavailable for garbage collection release."
"9. A garbage collector including:
(i) means for creating memory allocations (a-g) having a size and location in a memory and for adding a reference to each allocation to a tree structure comprising a plurality of linked nodes (40-52), each node being representative of the size and location of a respective memory allocation, and the nodes being within the tree in dependence upon the said location;
(ii) means for searching the tree, for an in-use pointer (p), to determine the memory allocations (c) to which the pointer points; and
(iii) means for noting the said memory allocation (c) as being unavailable for garbage collection release."
"17. An operating system including a garbage collector as claimed in any one of claims 9 to 16."
"21. A data carrier carrying an operating system as claimed in any one of claims 17 to 20."
"22. A data stream which is representative of an operating system as claimed in any one of claims 17 to 20."
"25. A Java virtual machine including a garbage collector as claimed in any one of claims 9 to 16."
1. The invention
Claim 1 sets out a method for garbage collection and claim 9 a corresponding garbage collector. A garbage collector is a computer program serving to release memory allocations which are not required by the current application program. It can be part of a computer's operating system. The program checks the pointers in use and identifies the objects to which they are pointing. These objects are needed and should not be released, whereas all other objects are released. Some pointers are "interior", meaning that they do not point to the start of an object but to a location within it. For interior pointers it is necessary to identify the memory block containing the location pointed at (cf. p. 1 and 2 of the application). This is done by building and searching a tree whose nodes represent the size and the location of every memory allocation. The tree thus provides the data necessary to link the interior pointer to the associated memory block without requiring a particular memory layout or an additional pointer referring to the start of the memory block.
2. The decision under appeal
The present application was refused on the ground that it lacked clarity, which the Board takes to mean the claims, in particular claim 1, were held not to be clear (Article 84 EPC). Furthermore, the separation of the claim features into the two-part form required by Rule 29(1) EPC was found to be incorrect. With respect to the present claims, which correspond to those filed during oral proceedings before the examining division, there has also been an obviousness objection.
3. The prior art
The examining division regarded D4 as the closest document, and indeed none of the other documents in the International Search Report appears to be more relevant. D4 describes a garbage collector which checks what pointers the application program uses and ensures that the objects at the locations referenced by the pointers are not released (cf. e.g. figure 1-1 and associated text). Pointers to an object point to the start of an object (Appendix B, p.63) where a header word is located which contains information about the object size (p.20, last paragraph). To test the efficiency of the garbage collector proposed, the authors of D4 have run two benchmark programs together with different garbage collectors (chapter 4.2). One of the benchmark programs, called WORDS, builds a binary tree of storage records (p.48; Appendix A, p.60).
Claim 1
4. Clarity
The Board regards claim 1 as clear and containing the essential features of the invention (Article 84 and Rule 29(1),(3) EPC). The examining division was of the opinion that the claim should contain the feature "interior pointer". However, the application as filed explicitly mentions that "/not/ all of the pointers need necessarily be interior" (p.8, l. 5,6; cf. also p.11, l.5,6). The invention is thus capable of, but not restricted to, dealing with interior pointers. It follows that the limitation on which the examining division insisted is neither necessary nor suitable. By deleting this unnecessary limitation, any clarity objection against its meaning (cf. the appealed decision, point 2.3) no longer exists as far as claim 1 is concerned. Moreover, the Board considers the term "interior pointer" (now used in dependent claims 7 and 15) to be sufficiently clear in the light of the explanation of it in the description (cf. p.7, l.23-26).
5. Two-part form
The combination of features in claim 1 is not known from D4. It would be detrimental to the logic of the claim to seek to split up its features (i) to (iii) into their basic building blocks merely to indicate which blocks happen to be known from D4, without having regard to their inter-relationships. Thus, the two-part form of claim is here inappropriate (Rule 29(1) EPC).
6. Novelty
6.1 The appellants argued before the examining division that although D4 mentions a binary tree, this was
"not the code of the garbage collector itself but rather of a benchmarking high level program which was used by the author of the paper to test the efficiency of his low level garbage collection program. The tree of the benchmarking applications program has no connection whatsoever with the operation of the garbage collector" (letter dated 20 April 2005, paragraph bridging p. 1 and 2).
From this the appellants concluded that D4 disclosed none of the features (i) to (iii) of claim 1.
6.2 The examining division held that D4 disclosed a method of garbage collection involving a dynamic tree structure whose nodes represented the size and location of memory allocations, the method including searching the tree to determine the memory allocation to which a pointer pointed and noting this allocation as being unavailable for garbage collection release. Reference was made to in particular to p.60 of D4. The division went on to say that
"/the/ applicant submitted D4 was not the disclosure of a garbage collector but a disclosure of a benchmark of a garbage collector and hence not relevant. However, while it is true that D4 provides benchmarks, it also provides an enabling disclosure of a particular garbage collection method and not just a generic method of benchmarking any garbage collector" (decision, point 2.2).
6.3 The Board agrees with the appellants that D4 discloses none of the features (i) to (iii) of claim 1. The examining division has in this connection referred to Appendix A at p.60 of D4. However, this appendix concerns one of the benchmark programs ("The following is the listing of the benchmark program WORDS"), not the garbage collector (whose code is given in Appendix B). This can only mean that when it is said on p.60 "Build a binary tree...", this refers to the benchmark program, not the garbage collector. The examining division has not demonstrated, nor indeed tried to demonstrate, that the described garbage collector makes use of the tree structure built by the benchmark program, nor is this apparent to the Board. Since all features of claim 1 involve the dynamic tree structure defined in feature (i), none of them can be said to be entirely known from D4. From this it follows that the subject-matter of claim 1 is new (Article 54 EPC).
7. Inventive step
7.1 The problem underlying the present invention is that pointers might point at an interior address of an object rather than to its start address. A garbage collector therefore has to identify the memory allocation block to which the interior pointer is pointing (p.2, first paragraph; p.10, l.18-20). The invention achieves this by means of a dynamic tree which is searched using the interior pointer.
7.2 In D4 the pointers point to the start of objects (cf. p. 20 and 63). It therefore appears that the problem caused by interior pointers cannot occur. In the Board's view it would be unreasonable to expect of the skilled person reading D4 to identify this problem which is incompatible with the teaching of the document. Even less can he be assumed to offer a solution to it. Thus, the invention involves an inventive step (Article 56 EPC).
8. It follows that there are no objections against claim 1.
Claims 2-25 and the description
9. Claim 9 is to a garbage collector, which is a computer program. According to decision T 1173/97, point 13 (OJ EPO 1999,609), a computer program is not a program as such (cf. Article 52(2),(3) EPC) if it is capable of achieving a "further" technical effect. The Board holds that the garbage collector of claim 9 achieves a "further" technical effect since it serves to free memory space which would otherwise be unnecessarily blocked and hence modifies the internal functioning of the computer itself. This goes beyond the "normal" technical effects, i.e. the physical interactions between computer program and computer memory which any program involves.
The same applies to the operating system of (dependent) claim 17 and the Java virtual machine of (dependent) claim 25.
10. The data carrier of claim 21 is an invention within the meaning of Article 52(1) EPC for the double reason of being a technical object and comprising a computer program capable of achieving a "further" technical effect (cf. the preceding paragraph).
11. The data stream representative of an operating system of claim 22 is also an invention within the meaning of Article 52(1). A computer program stored on a disc is a data file, and when the file is read out and transmitted it becomes a data stream in the form of an (electrical) signal. A signal, albeit transient, can be patentable if claimed in terms which inherently comprise the technical features of the system in which it occurs (see, in respect of a TV signal, decision T 163/85, OJ EPO 1990,379). It is therefore logical also to allow a claim to a data stream representative of a patentable computer program.
12. Also the other claims fulfil the requirements of the EPC, as does the amended description.
Reimbursement of the appeal fee
13. The appellants have requested reimbursement of the appeal fee due to substantial procedural violations said to have occurred during the examination of the application.
14. The communication under Rule 51(4) EPC
14.1 The examining division issued a Rule 51(4) EPC communication in which they had made changes to the text submitted by the appellants. In the annex to this communication D4 was cited for the first time. It was said that the claims as presented by the appellants at the preceding oral proceedings lacked an inventive step and therefore the independent claims 1 and 9 had to be amended and claims 8 and 15 to be deleted.
14.2 Article 113(2) EPC stipulates that the European Patent Office shall consider and decide upon the European patent application only in the text submitted to it, or agreed, by the applicant. It is the purpose of Rule 51(4) EPC to ensure, at the final stage of the examination procedure, the applicant's approval. From these provisions it follows that it is the applicant who sets the framework of the examination procedure. It is his right and responsibility to formulate the requests he desires to have considered. It is the examining division's task to take a decision on these requests.
14.3 Article 114(1) EPC sets out that the European Patent Office shall examine the facts of its own motion and shall not be restricted to the facts, evidence and arguments provided by the parties and the relief sought. This provision gives the examining division the competence to examine facts in connection with the applicant's requests, but not to alter the requests.
14.4 If an examining division is of the opinion that the claims as requested are not allowable but recognizes how the deficiencies might be overcome, it may well make a corresponding proposal. Normally this will be done in a communication pursuant to Article 96(2) EPC. Article 96(2) EPC stipulates that a communication is to be issued and a time limit to be set if there are deficiencies in the application documents as filed by the applicant. It is then up to the applicant to present arguments or new requests in order to meet these deficiencies, failing which the application may be refused.
14.5 Issuing a Rule 51(4) EPC communication containing amendments is not foreseen in the EPC. However, according to the Guidelines for Examination C-VI, 15.1, an examining division may, instead of issuing an Article 96(2) EPC communication, include amendments in the Rule 51(4) EPC communication. Considering in particular that this communication triggers a phase of strict time limits for paying fees and filing translations, the amendments must be such that the applicant can be reasonably expected to accept them. This procedure is thus only applicable as long as the amendments proposed by the examining division are minor.
In the present case, however, the Rule 51(4) EPC communication indicated substantial amendments to two independent claims based on a document never cited before. This was more than merely tidying up an examination result already agreed upon for final confirmation. The communication effectively initiated an entirely new examination phase, during which the applicant would generally not be expected to agree without presenting arguments. Thus, issuing a communication under Rule 51(4) EPC in which amendments are proposed that the applicant cannot reasonably be expected to accept without further discussion constitutes a substantial procedural violation.
15. The reasoning in the contested decision
15.1 The appellants have not explicitly stated that the decision under appeal is not sufficiently reasoned but have argued repeatedly during the examination that the examining division withheld the reasoning on the basis of which it intended to issue a decision. It is therefore appropriate for the Board to examine this issue.
15.2 According to Rule 68(2) EPC decisions which are open to appeal shall be reasoned. The jurisprudence of the Boards of Appeal tends to make a distinction between deficient or non-persuasive reasoning, which is not objectionable under Rule 68(2) EPC, and non-existing reasoning, which is. Decision T 292/90 (not published in the OJ EPO) defines at point 2 the borderline between the two categories in the way that a properly reasoned decision should enable the appellants and the Board of Appeal to examine whether the decision can be considered to be justified or not.
15.3 Article 113(1) EPC requires that a decision be based on grounds on which a party has had an opportunity to present its comments. Although this Article only mentions the presentation of comments it is self-evident that any comments which have been presented in a readily understandable way must also be duly considered by the deciding body; cf. in this respect decision T 94/84, OJ EPO 1986,337: "The right to be heard in accordance with the principle of due hearing enshrined in Article 113(1) EPC guarantees that grounds put forward are taken into consideration" (headnote; italics added). If an examining division neglects or grossly misinterprets arguments which have been stated in a clear fashion this has the same effect as if the applicant had not been allowed to put them forward at all, contrary to Article 113(1) EPC.
15.4 In the present case the appellants argued before the examining division that
"/the/ tree of the benchmarking applications program has no connection whatsoever with the operation of the garbage collector" (cf. point 6.1 above).
However, in the decision it is stated that the appellants
"submitted D4 was not the disclosure of a garbage collector but a disclosure of a benchmark of a garbage collector and hence not relevant. However, while it is true that D4 provides benchmarks, it also provides an enabling disclosure of a particular garbage collection method and not just a generic method of benchmarking any garbage collector" (cf. point 6.2 above).
Whether or not document D4 disclosed a particular garbage collection method was however not the point since the appellants accepted it did. The issue was instead how the garbage collector in D4 worked: whether it involved the tree or not. Thus, in the decision under appeal the appellants' arguments are misrepresented and trivialized. The argument was crucial and had been presented in a clear manner. Therefore, the examining division was in a position to consider it, should have considered it (Article 113(1) EPC) and should have dealt with it in its decision (Rule 68(2) EPC). By failing to do so, the examining division committed a further substantial procedural violation.
16. In view of the substantial procedural violations discussed above it is equitable to reimburse the appeal fee. It is therefore not necessary to decide whether other substantial procedural violations occurred during the examination, as the appellants maintain (cf. point IV above).
ORDER
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the department of the first instance with the order to grant a patent in the following version:
Claims:
1-6(part), 12-25 filed with letter dated 24/08/2006
6(part)-11 filed with letter dated 22/11/2006
Description:
Pages 1,2,8-12,14-25 as published
Pages 3,4,6,7 filed with letter dated 24/08/2006
Page 5 filed with letter dated 22/11/2006
Page 13 filed with letter dated 19/11/2003
Drawings:
Sheets 1-3 as published.
3. The appeal fee shall be reimbursed.