Partial Evaluation of Call-by-value lambda-calculus with Side-effects (bibtex)
by Kenichi Asai, Hidehiko Masuhara and Akinori Yonezawa
Abstract:
We present a framework of an online partial evaluator for a call-by-vahre A-calculus with destructiveupdatesof data structures. It properly and correctly specializes expressions that contain side-effects, while preserving pointer equality, which is an important property for programs using updates. Our partial evaluator uses a side-effect analysis to extract immutable data structures and then performs an online specialization using preactions. Once mutable and immutable data structures are separated, partial evaluation is done in such a way that accesses to immutable ones are performed at specialization time, while accesses to mutable ones are residualized. For the correct residualization of side-effecting operations, preactions are used to solve various issues, including code elimination, code duplication, and execution order preservation. The preaction mechanism also enables us to reduce expressions that were residualized when the conventional let-expression approach of Similix was used. The resulting partial evaluator is simple enough to prove its correctness. Based on the framework, we have constructed a partial evaluator for Scheme, which is powerful enough to specialize fairly complicated programs with side-effects, such as an interpreter.
Reference:
Partial Evaluation of Call-by-value lambda-calculus with Side-effects (Kenichi Asai, Hidehiko Masuhara and Akinori Yonezawa), In Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'97), 1997.
Bibtex Entry:
@inproceedings{asai97pepm,
  year = 1997,
  booktitle = {Workshop on Partial Evaluation and Semantics-Based
		  Program Manipulation (PEPM'97)},
  pdf = {pepm1997.pdf},
  doi = {10.1145/258993.258997},
  url = {https://dl.acm.org/doi/proceedings/10.1145/258993},
  author = {Kenichi Asai and Hidehiko Masuhara and Akinori
		  Yonezawa},
  title = {Partial Evaluation of Call-by-value lambda-calculus
		  with Side-effects},
  pages = {12--21},
  serialno = {6-12},
  keywords = {Black, Scheme},
  abstract = {We present a framework of an online partial evaluator for a call-by-vahre A-calculus with destructiveupdatesof data structures. It properly and correctly specializes expressions that contain side-effects, while preserving pointer equality, which is an important property for programs using updates. Our partial evaluator uses a side-effect analysis to extract immutable data structures and then performs an online specialization using preactions. Once mutable and immutable data structures are separated, partial evaluation is done in such a way that accesses to immutable ones are performed at specialization time, while accesses to mutable ones are residualized. For the correct residualization of side-effecting operations, preactions are used to solve various issues, including code elimination, code duplication, and execution order preservation. The preaction mechanism also enables us to reduce expressions that were residualized when the conventional let-expression approach of Similix was used. The resulting partial evaluator is simple enough to prove its correctness. Based on the framework, we have constructed a partial evaluator for Scheme, which is powerful enough to specialize fairly complicated programs with side-effects, such as an interpreter.}
}
Powered by bibtexbrowser