Garbage collection, tail recursion and first-class continuations in stack-oriented languages

Patent 5590332 Issued on December 31, 1996. Estimated Expiration Date:

January 13, 2015. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Symbolic language data processing system
Patent #: 4922414
Issued on: 05/01/1990
Inventor: Holloway, et al.

Method for reducing memory allocations and data copying operations during program calling sequences
Patent #: 4951194
Issued on: 08/21/1990
Inventor: Bradley, et al.

Asynchronous garbage collection
Patent #: 5355483
Issued on: 10/11/1994
Inventor: Serlet

Prolog addressing
Patent #: 5386520
Issued on: 01/31/1995
Inventor: Gillet

Prolog interrupt processing Patent #: 5396632
Issued on: 03/07/1995
Inventor: Gillet

Inventor

Baker, Henry G.

Application

No. 372514 filed on 01/13/1995

US Classes:

717/151, Optimization707/206Garbage collection

Examiners

Primary: Kriess, Kevin A.
Assistant: Chaki, Kakali

Attorney, Agent or Firm

Kimbell; Daniel R.

International Class

G06F 009/45

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.

Other References

Baker, "Cons should not Cons its Arguments", ACM Sig. Plan Notices, vol. 27, No. 3, Mar. 1992, pp. 24-34
Tarditi et al., "No Assembly Required: Compiling Standard ML to C", ACM Letters on Prog. Lang. and Sys., vol. 1, No. 2, 1992, pp. 161-177
R. Hieb et al., "Representing Control in the Presence of First-Class Continuations", ACM SigPlan'90 Conf. on Prog. Lang. Design and Implementation, Jun. 1990, pp. 66-7