Online partial deduction of large programs

Steven Prestwich

Online partial deduction of large programs

Steven Prestwich

ECRC

Research output: Chapter in Book/Report/Conference proceedings › Chapter › peer-review

Abstract

Partial deduction systems must be guided by an unfolding strategy, telling them which atoms to unfold and when to stop unfolding. Online strategies exploit knowledge accumulated during the unfolding itself, for example in a goal stack, while offline strategies are fixed before unfolding begins. Online strategies are more powerful, but a major overhead for large programs is the analysis time spent on each atom, which increases as the knowledge grows. We describe an online strategy whose analysis time for each atom is independent of the amount of knowledge about that atom. This reduces transformation times for programs with large search spaces by an order of magnitude, while retaining the power of online analysis. Correctness, termination and nontriviality are shown.

Original language	English
Title of host publication	Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation
Editors	Anon
Publisher	Publ by ACM
Pages	111-118
Number of pages	8
ISBN (Print)	0897915941
Publication status	Published - 1993
Externally published	Yes
Event	Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation - Copenhagen, Den Duration: 14 Jun 1993 → 16 Jun 1993

Publication series

Name	Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation

Conference

Conference	Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
City	Copenhagen, Den
Period	14/06/93 → 16/06/93

Cite this

@inbook{b218fc5d10f54d84b9990d64c42273db,

title = "Online partial deduction of large programs",

abstract = "Partial deduction systems must be guided by an unfolding strategy, telling them which atoms to unfold and when to stop unfolding. Online strategies exploit knowledge accumulated during the unfolding itself, for example in a goal stack, while offline strategies are fixed before unfolding begins. Online strategies are more powerful, but a major overhead for large programs is the analysis time spent on each atom, which increases as the knowledge grows. We describe an online strategy whose analysis time for each atom is independent of the amount of knowledge about that atom. This reduces transformation times for programs with large search spaces by an order of magnitude, while retaining the power of online analysis. Correctness, termination and nontriviality are shown.",

author = "Steven Prestwich",

year = "1993",

language = "English",

isbn = "0897915941",

series = "Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation",

publisher = "Publ by ACM",

pages = "111--118",

editor = "Anon",

booktitle = "Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation",

note = "Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation ; Conference date: 14-06-1993 Through 16-06-1993",

}

Prestwich, S 1993, Online partial deduction of large programs. in Anon (ed.), Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation. Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation, Publ by ACM, pp. 111-118, Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Copenhagen, Den, 14/06/93.

TY - CHAP

T1 - Online partial deduction of large programs

AU - Prestwich, Steven

PY - 1993

Y1 - 1993

N2 - Partial deduction systems must be guided by an unfolding strategy, telling them which atoms to unfold and when to stop unfolding. Online strategies exploit knowledge accumulated during the unfolding itself, for example in a goal stack, while offline strategies are fixed before unfolding begins. Online strategies are more powerful, but a major overhead for large programs is the analysis time spent on each atom, which increases as the knowledge grows. We describe an online strategy whose analysis time for each atom is independent of the amount of knowledge about that atom. This reduces transformation times for programs with large search spaces by an order of magnitude, while retaining the power of online analysis. Correctness, termination and nontriviality are shown.

AB - Partial deduction systems must be guided by an unfolding strategy, telling them which atoms to unfold and when to stop unfolding. Online strategies exploit knowledge accumulated during the unfolding itself, for example in a goal stack, while offline strategies are fixed before unfolding begins. Online strategies are more powerful, but a major overhead for large programs is the analysis time spent on each atom, which increases as the knowledge grows. We describe an online strategy whose analysis time for each atom is independent of the amount of knowledge about that atom. This reduces transformation times for programs with large search spaces by an order of magnitude, while retaining the power of online analysis. Correctness, termination and nontriviality are shown.

UR - https://www.scopus.com/pages/publications/0027802105

M3 - Chapter

AN - SCOPUS:0027802105

SN - 0897915941

T3 - Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation

SP - 111

EP - 118

BT - Proc ACM SIGPLAN Symp Partial Eval Semantics Based Program Manipulation

A2 - Anon, null

PB - Publ by ACM

T2 - Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation

Y2 - 14 June 1993 through 16 June 1993

ER -

Online partial deduction of large programs

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this