Concurrent LP Method Patented

Keywords: parallelism.

eggert@twinsun.com 
Paul Eggert
15th February 1994  

andrew@cee.hw.ac.uk 
Andrew Dinn
16th February 1994  

Example: The first Strand implementation had to make a circumlocution in its implementation of process suspension structures to avoid infringing a patent belonging to Ehud Shapiro. The patent was, according to our legal advice, a pretty clear attempt to lay claim to a commonly used programming technique, something which cannot be patented (under English law). Our lawyers' opinion was that the patent should never have been granted. However, we chose to work around the patent because i) for us to challenge it would have cost time & money which we probably would not have recovered from a successful suit ii) if Shapiro had sued us and lost we would not have been able to reclaim costs (under English law) iii) without any evidence of the breach such as a code listing Shapiro could not initiate a suit (under English law), so why manufacture ammunition?

I doubt very much whether any (let alone all!) common Concurrent LP programming techniques (e.g. bounded buffers) could have been validly patented since they have been in the public domain for many years, both in papers, books and Concurrent LP documentation (even Shapiro's own publications like the Logix manual or his collection of papers on Concurrent Prologs). Sounds like the patent quoted above is the one associated with Concurrent LP *implementation* which we had to deal with, not programming techniques. If this report *really* is correct then rubbishing the patent would be easy but who is going to spend the money to do it?

For those interested in CLP patents, ICL hold a patent which covers a technique for asynchronous parallel garbage collection (they bought it, they didn't invent it). It makes it pretty difficult to implement an asynchronous garbage collector without infringing the patent. Guess why Strand never had a asynchronous garbage collector.

roland@cs.monash.edu.au 
Roland Yap
18th February 1994  

Example: The first Strand implementation had to make a circumlocution in its implementation of process suspension structures to avoid infringing a patent belonging to Ehud Shapiro.

I am curious about the programming techniques being used here? Patent law varies significantly between various countries and it is probably not clear what the scope of patenting "known" techniques is.

andrew@cee.hw.ac.uk 
Andrew Dinn
18th February 1994  

Processes in a Concurrent LP language may be suspended waiting for variables (appearing either as arguments or embedded in their arguments) to become bound. If only one such variable is waited on processes can be chained off the variable in an `intrusive' linked list i.e. using a link slot in the process record. When the variable is written the processes can be unlinked and placed in the run queue.

Where processes are chained on several variables there is more of a problem. Intrusive linked lists obviously fail. If non-intrusive linked lists are used (using auxiliary cells to hold the links and point to the processes involved) then these cells must all be removed from the various lists in which the process is inserted whenever one of the variables is written. They could be found by tracing through the arguments but obviously this could be arbitrarily complex and hence inefficient (imagine arg 1 is a 5000000 element list and args 2 and 3 are the variables the process is suspended off :-/)

I think the technique which was patented used circular intrusive linked lists for singly suspended processes and installed surrogate link records in place of multiply suspended processes. The surrogates had a second link field and these fields were chained in a loop which also contained the process.

I say 'I think' because I cannot remember exactly what was patented and what we built. I do remember we had several alternatives but even our best version involved an extra level of indirection on the patented one. So I believe what I have described is the latter (so sue me :-).

So, the patented technique is merely a way of storing items in multiple linked lists in such a way that they can easily be unlinked from all lists at once. This linking scheme sounds rather familiar. I don't have my Bach with me but it certainly rings bells when I recall the Unix buffer page linking described therein. I also seem to recall something similar in Ullman's book on databases. I have not seen a published paper on Concurrent LP languages which describes this technique but I would not be surprised if there is one around. Anybody know for sure where they have seen it before?

eggert@twinsun.com 
Paul Eggert
20th February 1994  

I am curious about the programming techniques being used here?

I don't know about the English patent, but I'll enclose a copy of the US patent below, as posted on the net by Carl Oppedahl. It's a fairly broad patent: it seems to claim any committed-choice logic programming implementation. E.g. see claim 11.

Patent No.: 5,222,221

Method and Apparatus for Implementing a Concurrent Logic Program

Issued: June 22, 1993 (19930622)

Inventor(s): Houri, Avshalom, Netovot, IL (Israel); Shapiro, Ehud, Rehovot, IL (Israel)

Assignee(s): Yeda Research and Development Co Ltd, (A Non-U.S. Company or Corporation), Rehovot, IL (Israel)

Attorney, agent, or firm: Pennie & Edmonds

Abstract

A flat concurrent Prolog (Fcp) computer comprises a memory in which all the data is stored, three sets of registers, several queues or lists and a computer program for controlling the computer. The memory is a single data area called the "heap" which also includes two small data areas called the "trail" and the suspension table as well as the queues. The queues include the resolvent which is also called the active queue or the process queue, the activation queue, the process free list and the suspension free list. The registers include a set of general registers, a set of procedure try registers and a set of clause try registers. The general registers include a heap backtrack register, a queue front register, a queue back register, a process free list register, and a suspension free list register. The procedure try registers include a current process register, a time slice register that identifies the number of process iterations that can be done, a program counter, a failure label register that contains the address of the first instruction in the next clause to be tried, and a suspension table pointer. The clause try registers include a heap pointer register, an activation pointer register, a trail pointer register, an argument pointer register, a structure pointer register that points at an argument of a compound structure, a mode register that can specify either read or write mode, and a plurality of temporary registers for holding intermediate values during a clause try.

What is claimed:

1. A digital computer for reducing a set of unsolved goals (or processes) from a logic program comprising a plurality of clauses, said computer comprising:

a computer memory in which is stored all data on which the program operates as well as a trail for undoing changes in said data when a clause try fails;

means for encoding each clause of the logic program into a set of machine instructions, which, when executed, attempt to reduce the set of unsolved goals (or processes) by a sequence of clause tries;

means for storing and accessing the set of machine instructions in the computer memory;

means for forming in the computer memory a plurality of queues, a first such queue being the set of unsolved goals (or processes);

means for attempting to reduce the set of unsolved goals by a sequence of clause tries by dequeuing one or more of the unsolved goals (or processes) from the first queue and executing the set of machine instructions with respect to the dequeued goals;

means for recording in the trail changes in the computer memory resulting from clause tries, and upon failure of one of said clause tries, undoing the trailed changes;

means for enqueuing unsolved goals (or processes) spawned from successful clause tries onto the first queue; and

means for continuing execution either until the first queue is empty or until no further education is possible and at least one unsolved goal (or process) remains in the first queue.

2. The digital computer of claim 1 wherein second and third queues are also formed by the forming means, said second queue being a list that identifies all unsolved goals (or processes) that are suspended on uninstantiated variables and said third queue being a list of all unsolved goals (or processes) that are to be activated when a clause try commits by adding unsolved goals (or processes) identified in the list to the first queue and the digital computer further comprises:

means for suspending unsolved goals (or processes) upon variables which cause unsuccessful head unification or guard evaluation; and

means for activating suspended unsolved goals upon instantiation of the variables which caused unsuccessful head unification or guard evaluation.

3. A digital computer of claim 1 wherein second and third queues are also formed by the forming means, said second queue being a list of uninstantiated variables upon which clause tries have suspended, each uninstantiated variable of said second queue referencing a list of unsolved goals (or processes) which have suspended on that variable, and said third queue being a list of those elements from said second queue which are to be added to the set of unsolved goals (or processes) because their referencing variables has been instantiated, said computer further comprising:

means for suspending unsolved goals (or processes) upon variables which cause unsuccessful head unification or guard evaluation; and

means for activating suspended unsolved goals upon instantiation of the variables which caused unsuccessful head unification or guard evaluation.

4. The digital computer of claim 1 wherein a clause includes a head and at least one body goal, said computer further comprising:

means from for one of the body goals spawned from said reduction having reduction proceed for a limited time from the body goal spawned from a successful reduction of an unsolved goal.

5. A method for implementing a logic programming language by reducing in parallel a set of unsolved goals (or processes) from a logic program comprising a plurality of clauses of the form H:-G1, G2, ..., Gi, ..., Gm vertical line, B1, B2, ..., Bi, ... Bn, where m,n>=O and H is a head of the clause, each Gi is a system defined test called a guard and each Bi is a general body goal, the method comprising the steps executed by a computer of:

encoding each clause of the logic program into a set of abstract instructions, which when executed reduces the set of unsolved goals by unifying one such unsolved goal with the head of one of the clauses, evaluating the guards of said clause with respect to the goal, and if the unification and guard evaluation are successful, replacing the unsolved goal with the set of goals, Bi, in the body of said clause;

reducing one or more of the unsolved goals (or processes) simultaneously by executing said abstract instructions;

undoing changes caused by unsuccessful head unifications and guard evaluations; and

executing the abstract instructions until no more unsolved goals remain or until no more unification and guard evaluation are possible and there remain unsolved goals.

6. The method of claim 5 wherein the step of reducing one or more of the unsolved goals (or processes) further comprises the steps of:

suspending unsolved goals (or processes) upon variables which cause unsuccessful head unification or guard evaluation; and activating suspended unsolved goals (or process) upon instantiation of the variables which caused unsuccessful head unification or guard evaluation.

7. The method of claim 5 further comprising the step of repeating for a limited number of times the encoding steps of unifying the head and evaluating the guard with a goal from the set of goals in the body of the clause resulting from a successful head unification and guard evaluation.

8. A method for implementing a logic programming language by reducing a set of unsolved goals (or processes) from a logic program comprising a plurality of clauses of the form H:-G1, G2, ..., Gi, ... Gm vertical line, B1, B2, ..., Bi, ... Bn, where m,n>=O and H is a head of the clause, Gi is a system defined test called a guard and each Bi is a general body goal with non-deterministic clause selection, the method comprising the steps executed by a computer of:

encoding each clause of the logic program into a set of abstract instructions which, when executed, reduces the set of unsolved goals by unifying one such unsolved goal with the had of one of the clauses, evaluating the guards of said clause with respect to the goal, and if the unification and guard evaluation are successful, replacing the unsolved goal with the set of goals, Bi, in the body of said clause;

reducing one or more of the unsolved goals (or processes) with one or more of the clauses simultaneously or in any arbitrary order by executing said abstract instructions;

undoing changes caused by unsuccessful head unifications and guard evaluations; and

executing the abstract instructions until no more unsolved goals remain or until no more head unification and guard evaluation are possible and there remain unsolved goals.

9. The method of claim 8 wherein the step of reducing one or more of the unsolved goals (or processes) further comprises the steps of:

suspending unsolved goals (or processes) upon variables which cause unsuccessful head unification or guard evaluation; and

activating suspended unsolved goals (or process) upon instantiation of the variables which caused unsuccessful head unification or guard evaluation.

10. The method of claim 8 further comprising the step of repeating for a limited number of times the encoding steps of unifying the head and evaluating the guard with a goal from the set of goals in the body of the clause resulting from a successful head unification and guard evaluation.

11. A method for implementing a logic programming language by reducing a set of unsolved goals (or processes) from a logic program comprising a plurality of clauses of the form H:- G1, G2, ..., Gi, ... Gm vertical line, B1, B2, ..., Bi, ... Bn, where m,n>=O and H is a head of the clause, each Gi is a system defined test called a guard and each Bi is a general body goal with nondeterministic clause selection, the method comprising the steps executed by a computer of:

encoding each clause of the logic program into a set of abstract instructions which, when executed, reduces the set of unsolved goals by unifying one such unsolved goal with the head of the one of the clauses, evaluating the guards of said clause with respect to the goal, and if the unification and guard evaluation are successful, replacing the unsolved goal with the set of goals, Bi, in the body of said clause;

reducing one of the unsolved goals (or processes) with one or more of the clauses simultaneously or in any arbitrary order by executing said abstract instructions;

undoing changes caused by unsuccessful head unifications and guard evaluations; and

executing the abstract instructions until no more unsolved goals remain or until no more head unification and guard evaluation are possible and there remain unsolved goals.

12. The method of claim 11 wherein the steps of reducing one or more of the unsolved goals (or processes) further comprises the steps of:

suspending unsolved goals upon variables which cause unsuccessful head unification or guard evaluation; and

activating suspended unsolved goals (or process) upon instantiation of the variable which caused unsuccessful head unification or guard evaluation.

13. The method of claim 11 comprising the step of repeating for a limited member of times the encoding steps of unifying the head and evaluating the guard with a goal from the set of goals in the body of the clause resulting from a successful head unification and guard evaluation.

mmh@dcs.qmw.ac.uk 
Matthew Huntbach
21st February 1994  

I propose that Messrs Houri and Shapiro be treated as personae non grata in academic circles until they make some sort of public declaration that they do not intend by this patent to impeded anyone's academic research in any way.

debray@CS.Arizona.EDU 
Saumya K. Debray
21st February 1994  

The patent abstract:

a computer memory in which is stored all data on which the program operates as well as a trail for undoing changes in said data when a clause try fails;

[...]

means for recording in the trail changes in the computer memory resulting from clause tries, and upon failure of one of said clause tries, undoing the trailed changes;

I believe the use of a trail stack for undoing changes on backtracking was mentioned in DHD Warren's 1977 PhD dissertation; I first encountered it in a 1981 paper by Maurice Bruynooghe on memory management in Prolog interpreters.

Similarly:

means for suspending unsolved goals (or processes) upon variables which cause unsuccessful head unification or guard evaluation; and

means for activating suspended unsolved goals upon instantiation of the variables which caused unsuccessful head unification or guard evaluation.

This seems to be the "obvious" way to handle dataflow synchronization. If I remember correctly, IC-Prolog had this facility as a language feature (it was described in the 1981 "White Elephant" book by Clark and Tarnlund, I think): anyone know how suspension/resumption was handled in IC-Prolog?

In any case, assuming that the techniques patented are essentially those described in various implementation papers published by Houri and Shapiro (e.g., in Shapiro's 1988 book "Concurrent Prolog: Collected Papers") -- both the authors and the material seem to match up -- I'm far from convinced that I'd use them much in a high-performance implementation of a concurrent logic language. (We're building one now, and we're doing things very differently in general to get good performance. Of course, we haven't been able to do without the heap, and we still use the binary number system, which someone or the other probably has a patent on.:-) So I guess I'm not losing too much sleep over it.

In general, I can't imagine what use such a patent is expected to serve:

• I'd be surprised if the authors expected to get rich from the royalties from vendors of concurrent logic language implementations;

• I don't think it makes that much of a difference on a vita; and

• it may very well have a negative effect on the community it draws on: I hate to think what the state of Prolog implementations would be today if DHD Warren had decided to patent the WAM back in 1983!

mcovingt@aisun3.ai.uga.edu 
Michael Covington
22nd February 1994  

walter@watson.ibm.com 
Walter Wilson
24th February 1994 

the other major difference between European and US patent law is that the European codes give precedence to the first to file, while US law gives precedence to first to invent. the US code may be more satisfying philosophically, but the european system is much easier to administer.

Being granted a US patent does not mean you have the patent. That is settled in court if it means enough $$ to the parties involved.

I read Shapiro's patent. He is not claiming to have invented the trail stack (for example). He is claiming that the machine he invented has a trail stack in it -- along with a bunch of other stuff. It is a continuation of a patent application started in 1986...so I believe it is only publications before July 1985 that are a problem for him.

Specifically, ICOT TR003 1983 "A Subset of Concurrent Prolog and its Interpreter" is what I would arm my lawyers with ... if it came to a showdown :)

ward@appliedmicro.ns.ca 
Paul Ward
23rd February 1994 

(1) It is not unreasonable to patent what one believes is a good idea.

(2) Most patent lawyers will word patents in one of two ways:

(a) if there is nothing similar, then they will write very broad patents. This seems to be the case here.

(b) if there are similar patents, then they will word it very specifically to fend off a suit from one whose patent is different.

Huntbach writes:

I propose that Messrs Houri and Shapiro be treated as personae non grata in academic circles until they make some sort of public declaration that they do not intend by this patent to impeded anyone's academic research in any way.

I believe that this is, to say the least, quite drastic, especially as so much of the work on concurrent logic languages can be traced to the Weizmann group. Look at the acknowledgements in Vijay Saraswat's dissertation if you want to know just how much of an inspiration Udi has been.

I would also point out that they have done nothing to impede anyone's research to date. Rather, they have encouraged it.

pereira@alta.research.att.com 
Fernando Pereira
26th February 1994 

Patents do interfere with the distribution of systems using patented techniques, whether commercially or not, which indeed may interfere with the way certain kinds of software research is carried out by making experimental systems widely available.