Patent US5590332A successfully refreshed from Google Patents.
US5590332A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Garbage collection, tail recursion and first-class continuations in stack-oriented languages
Assignee: Individual
•
Filing: 1995-01-13
•
Granted: 1996-12-31
•
Expires: 2015-01-13
Abstract
Abstract Methods for implementing garbage collection, tail recursion and first-class continuations for advanced computer applications in a stack-oriented language. Objects, including assignable cells, subprogram closure objects and continuation objects, can be allocated within the invocation frames of the stack-oriented language and these objects will be evacuated from the invocation frames before these frames are deallocated. The techniques enable a tail-call optimization by which a tail-recursion can be executed in constant net space for the invocation frames of the tail-recursive subprogram. The technique, when combined with a continuation-passing style of programming in stack-oriented computer languages, also allows an efficient implemention of garbage collection and first-class continuations. Our technique is useful in the interpretation and compilation of advanced computer languages which incorporate the features of tail-recursion, first-class continuations and/or garbage collection.
Inventors
- 👤 Henry G. Baker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 22:05
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; G06F12/0276
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
167 words
A method for executing an advanced application, said application comprising a number of related subprograms implemented in a stack-oriented language which includes both a stack and a heap, comprising the steps of: converting one or more of said application subprograms into continuation-passing style (CPS) in the stack-oriented language; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the application such that the initial invocation stack frame is within the limits of the stack buffer; interrupting any of said CPS-converted subprograms when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 2
Independent Claim
167 words
A method for executing an advanced application, said application comprising a number of related subprograms implemented in a stack-oriented language which includes both a stack and a heap, comprising the steps of: converting one or more of said application subprograms into continuation-passing style (CPS) in the stack-oriented language; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the application such that the initial invocation stack frame is within the limits of the stack buffer; interrupting any of said CPS-converted subprograms when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 3
Dependent Claim
19 words
The method of claim 1 in which the step of CPS conversion constructs closure objects as local stack-allocated objects.
Claim 4
Dependent Claim
20 words
The method of claim 1 in which the step of CPS conversion constructs assignable cell objects as local stack-allocated objects.
Claim 5
Dependent Claim
14 words
The method of claim 1 in which the stack-oriented language is the C language.
Claim 6
Dependent Claim
14 words
The method of claim 1 in which the stack-oriented language is the C++ language.
Claim 7
Independent Claim
164 words
A method for executing one or more mutually recursive subprograms implemented in a stack-oriented language which includes both a stack and a heap to achieve the benefits of tail recursion, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 8
Independent Claim
164 words
A method for executing one or more mutually recursive subprograms implemented in a stack-oriented language which includes both a stack and a heap to achieve the benefits of tail recursion, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 9
Dependent Claim
19 words
The method of claim 6 in which the step of CPS conversion constructs closure objects as local stack-allocated objects.
Claim 10
Dependent Claim
20 words
The method of claim 6 in which the step of CPS conversion constructs assignable cell objects as local stack-allocated objects.
Claim 11
Dependent Claim
14 words
The method of claim 6 in which the stack-oriented language is the C language.
Claim 12
Dependent Claim
14 words
The method of claim 6 in which the stack-oriented language is the C++ language.
Claim 13
Independent Claim
187 words
A method for executing one or more subprograms of an application implemented in a stack-oriented language which includes both a stack and a heap to achieve the benefits of first-class continuations, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language so that continuation closure objects are local stack-allocated objects; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; capturing one of the stack-allocated continuation closure objects; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects including live continuation closure objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 14
Independent Claim
187 words
A method for executing one or more subprograms of an application implemented in a stack-oriented language which includes both a stack and a heap to achieve the benefits of first-class continuations, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language so that continuation closure objects are local stack-allocated objects; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; capturing one of the stack-allocated continuation closure objects; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the heap any live data objects including live continuation closure objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 15
Dependent Claim
21 words
The method of claim 11 in which the step of CPS conversion also constructs assignable cell objects as local stack-allocated objects.
Claim 16
Dependent Claim
14 words
The method of claim 11 in which the stack-oriented language is the C language.
Claim 17
Dependent Claim
14 words
The method of claim 11 in which the stack-oriented language is the C++ language.
Claim 18
Independent Claim
193 words
A method for executing one or more subprograms of an application implemented in a stack-oriented language which includes both a stack and a heap and a further garbage collector for said heap to achieve the benefits of precise garbage collection, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language so that continuation closure objects are local stack-allocated objects; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the first generation of a garbage-collected heap any live data objects including live continuation closure objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 19
Independent Claim
193 words
A method for executing one or more subprograms of an application implemented in a stack-oriented language which includes both a stack and a heap and a further garbage collector for said heap to achieve the benefits of precise garbage collection, comprising the steps of: converting the subprograms into continuation-passing style (CPS) in the stack-oriented language so that continuation closure objects are local stack-allocated objects; determining the extent and limit points of a stack buffer on the execution stack of the stack-oriented language, which buffer is capable of holding a plurality of invocation stack frames; commencing the execution of the mutually recursive subprograms such that the initial invocation stack frame is within the limits of the stack buffer; interrupting a CPS-converted subprogram when the execution stack pointer is beyond a limit point of the stack buffer; initiating an evacuation process to transport out of the stack buffer into the first generation of a garbage-collected heap any live data objects including live continuation closure objects found in the stack buffer; contracting the execution stack of the stack-oriented language back to the beginning of the stack buffer; and resuming the execution of the interrupted CPS-converted subprogram.
Claim 20
Dependent Claim
21 words
The method of claim 15 in which the step of CPS conversion also constructs assignable cell objects as local stack-allocated objects.
Claim 21
Dependent Claim
14 words
The method of claim 15 in which the stack-oriented language is the C language.
Claim 22
Dependent Claim
14 words
The method of claim 15 in which the stack-oriented language is the C++ language.
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) | 1999-12-31 | 2000-07-01 | 2000-12-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-31 | 2004-07-01 | 2004-12-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-31 | 2008-07-01 | 2008-12-31 | $7700.00 | Window Closed / Lapsed |