US5222221A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for implementing a concurrent logic program
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1992-01-16
•
Granted: 1993-06-22
•
Expires: 2012-01-16
Abstract
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.
Inventors
- 👤 Avshalom Houri
- 👤 Ehud Shapiro
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 19:46
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4496
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
245 words
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.
Claim 2
Dependent Claim
245 words
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.
Claim 3
Dependent Claim
117 words
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.
Claim 4
Dependent Claim
129 words
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.
Claim 5
Dependent Claim
54 words
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.
Claim 6
Independent Claim
216 words
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|, 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.
Claim 7
Independent Claim
216 words
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|, 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.
Claim 8
Dependent Claim
59 words
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.
Claim 9
Dependent Claim
51 words
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.
Claim 10
Independent Claim
228 words
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|, 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.
Claim 11
Independent Claim
228 words
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|, 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.
Claim 12
Dependent Claim
59 words
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.
Claim 13
Dependent Claim
51 words
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.
Claim 14
Independent Claim
229 words
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|, 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.
Claim 15
Independent Claim
229 words
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|, 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.
Claim 16
Dependent Claim
57 words
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.
Claim 17
Dependent Claim
50 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-06-21 | 1996-12-21 | 1997-06-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-06-21 | 2000-12-21 | 2001-06-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-06-21 | 2004-12-21 | 2005-06-22 | $7700.00 | Window Closed / Lapsed |