Storage management in a Prolog compiler

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Storage management in a Prolog compiler

Full text

Pdf (654 KB)

Source

Symposium on Small Systems archive
Proceedings of the 1986 ACM SIGSMALL/PC symposium on Small systems table of contents

San Francisco, California, United States

Pages: 43 - 52

Year of Publication: 1986

ISBN:0-89791-211-4

Authors

Y-L. Chang	Technical University of Nova Scotia, Halifax, Canada
P. T. Cox	Technical University of Nova Scotia, Halifax, Canada

Sponsor

SIGSMALL : ACM Special Interest Group on Small and Personal Computing Systems and Applications

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 19, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/317559.322747 What is a DOI?

ABSTRACT

With the current intense interest in new computing paradigms based on logic, the efficient implementation of Prolog has become an issue of prime importance. Compiling Prolog involves some unique and difficult problems relating to storage management: in particular, the somewhat conflicting requirements of backtracking, and cut and tail recursion processing. The usual solution is to use garbage collection, an expensive process in small computers with limited storage. We describe a Prolog compiler which maintains the heap as lists of free records, to which records are released at the time they are deallocated, thus avoiding garbage collection. In this compiler, variable bindings are recorded in such a way that the speed of unification does not depend on the length of chains of bound variables. Also, tail recursion optimisation is more thorough than in other implementations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bruynooghe, M., Garbage Collection in Prolog Interpreters, in Implementations of PROLOG, J.A. Campbell (Ed.), Ellis-Horwood, (1984), 259-267.
	2	Bruynooghe, M., The memory management of Prolog implementations, in Logic Programming, S-A. Tarnlund and K. Clark (Eds.), Academic Press (1982)
	3	Bruynooghe, M., An interpreter for predicate logic programs - Part 1, Report CW I0, Applied Maths and Programming Division, Katholieke Univ. Leuven (1976).
	4	Chang, Y-L., Experiments in Prolog Compilation, M.Comp.Sci. Thesis, School of Computer Science, Technical University of Nova Scotia ( 1985).
	5	K. L Clark , F. G McCabe, Micro-PROLOG: programming in logic, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
	6	W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
	7	Christopher John Hogger, Introduction to logic programming, Academic Press Professional, Inc., San Diego, CA, 1984
	8	McCabe, F.G., Abstract Prolog Machine - a specification, DOC 83/12 (2n4 Ed.), Department of Computing, Imperial College, London (1984).
	9	Roberts, G.M., An implementation of Prolog, MMath. Thesis, Department of Computer Science, University of Waterloo (1977).
	10	Roussel, P. Prolog : Manuel de Reference et d'Utilisation, Groupe d'lntelligence Artificielle, U.E.R. de Luminy, Universite d'Aix-Marseille ii (1975).
	11	Warren, D.H.D., An Abstract Prolog Instruction Set, Technical Note 309, SRI International (1983).
	12	Warren, D.H.D., An improved PROLOG implementation which optimises tail recursion, Proc. of Logic Programming Workshop, Debrecen, Hungary (1980), 1 - 11.
	13	Warren, D.H.D., implementing Prolog - Compiling Predicate Logic Programs, vols. l and 2, DAI Research Reports 39, and 40 University of Edinburgh (1977).