Kahrs, Stefan (1993) Compilation of combinatory reduction systems. In: Heering, Jan and Meinke, Karl and Möller, Bernhard and Nipkow, Tobias, eds. Higher-Order Algebra, Logic, and Term Rewriting: First International Workshop. Lecture Notes in Computer Science . Springer, Berlin, Germany, pp. 169-188. ISBN 978-3-540-58233-5. E-ISBN 978-3-540-48579-7. (doi:10.1007/3-540-58233-9_9) (KAR id:21097)
PDF
Language: English |
|
Download this file (PDF/267kB) |
Preview |
Request a format suitable for use with assistive technology e.g. a screenreader | |
Postscript
Language: English |
|
Download this file (Postscript/194kB) |
|
Request a format suitable for use with assistive technology e.g. a screenreader | |
Official URL: http://dx.doi.org/10.1007/3-540-58233-9_9 |
Abstract
Combinatory Reduction Systems generalise Term Rewriting Systems. They are powerful enough to express β-reduction of λ-calculus as a single rewrite rule. The additional expressive power has its price — CRSs are much harder to implement than ordinary TRSs.
We propose an abstract machine suitable for executing CRSs. We define what it means to execute an instruction, and give a translation from CRS rules into sequences of instructions. Applying a rewrite rule to a term is realised by initialising the machine with this term, and then successively executing the instructions of the compiled rule.
Item Type: | Book section |
---|---|
DOI/Identification number: | 10.1007/3-540-58233-9_9 |
Uncontrolled keywords: | CRS, compilation, abstract machine |
Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, |
Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
Depositing User: | Mark Wheadon |
Date Deposited: | 04 Oct 2009 19:03 UTC |
Last Modified: | 16 Nov 2021 09:59 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/21097 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):