Generic Reduction-Based Interpreters

Casper Bach

doi:10.1145/3759427.3760377

Generic Reduction-Based Interpreters

Casper Bach^*

^*Kontaktforfatter

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

Reduction-based interpreters are traditionally defined in terms of a one-step reduction function which systematically decomposes a term into a potential redex and context, contracts the redex, and recomposes it to construct the new term to be further reduced. While implementing such interpreters follows a systematic recipe, they often require interpreter engineers to write a substantial amount of code—much of it boilerplate. In this paper, we apply well-known techniques from generic programming to reduce boilerplate code in reduction-based interpreters.

Originalsprog	Engelsk
Titel	OLIVIERFEST 2025 - Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday
Redaktører	Fritz Henglein, Julia Lawall, Jens Palsberg, Sergey Ilya
Forlag	Association for Computing Machinery
Publikationsdato	12. okt. 2025
Sider	166-179
ISBN (Elektronisk)	9798400721502
DOI	https://doi.org/10.1145/3759427.3760377
Status	Udgivet - 12. okt. 2025
Begivenhed	2025 Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday, OLIVIERFEST 2025 - Singapore, Singapore Varighed: 12. okt. 2025 → 18. okt. 2025

Konference

Konference	2025 Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday, OLIVIERFEST 2025
Land/Område	Singapore
By	Singapore
Periode	12/10/2025 → 18/10/2025
Sponsor	ACM Special Interest Group on Ada Programming Language, ACM Special Interest Group on Programming Languages

Dokumenter og links

10.1145/3759427.3760377Licens: CC BY

Open Access VersionForlagets udgivne version, 433 KBLicens: CC BY

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@inproceedings{cd51068296b545699552548beeefd4fa,

title = "Generic Reduction-Based Interpreters",

abstract = "Reduction-based interpreters are traditionally defined in terms of a one-step reduction function which systematically decomposes a term into a potential redex and context, contracts the redex, and recomposes it to construct the new term to be further reduced. While implementing such interpreters follows a systematic recipe, they often require interpreter engineers to write a substantial amount of code—much of it boilerplate. In this paper, we apply well-known techniques from generic programming to reduce boilerplate code in reduction-based interpreters.",

keywords = "dependent types, generic programming, reduction semantics, reduction-based normalization",

author = "Casper Bach",

year = "2025",

month = oct,

day = "12",

doi = "10.1145/3759427.3760377",

language = "English",

pages = "166--179",

editor = "Fritz Henglein and Julia Lawall and Jens Palsberg and Sergey Ilya",

booktitle = "OLIVIERFEST 2025 - Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2025 Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday, OLIVIERFEST 2025 ; Conference date: 12-10-2025 Through 18-10-2025",

}

Bach, C 2025, Generic Reduction-Based Interpreters. i F Henglein, J Lawall, J Palsberg & S Ilya (red), OLIVIERFEST 2025 - Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday. Association for Computing Machinery, s. 166-179, 2025 Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday, OLIVIERFEST 2025, Singapore, Singapore, 12/10/2025. https://doi.org/10.1145/3759427.3760377

Generic Reduction-Based Interpreters. / Bach, Casper.
OLIVIERFEST 2025 - Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday. red. / Fritz Henglein; Julia Lawall; Jens Palsberg; Sergey Ilya. Association for Computing Machinery, 2025. s. 166-179.

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Generic Reduction-Based Interpreters

AU - Bach, Casper

PY - 2025/10/12

Y1 - 2025/10/12

N2 - Reduction-based interpreters are traditionally defined in terms of a one-step reduction function which systematically decomposes a term into a potential redex and context, contracts the redex, and recomposes it to construct the new term to be further reduced. While implementing such interpreters follows a systematic recipe, they often require interpreter engineers to write a substantial amount of code—much of it boilerplate. In this paper, we apply well-known techniques from generic programming to reduce boilerplate code in reduction-based interpreters.

AB - Reduction-based interpreters are traditionally defined in terms of a one-step reduction function which systematically decomposes a term into a potential redex and context, contracts the redex, and recomposes it to construct the new term to be further reduced. While implementing such interpreters follows a systematic recipe, they often require interpreter engineers to write a substantial amount of code—much of it boilerplate. In this paper, we apply well-known techniques from generic programming to reduce boilerplate code in reduction-based interpreters.

KW - dependent types

KW - generic programming

KW - reduction semantics

KW - reduction-based normalization

U2 - 10.1145/3759427.3760377

DO - 10.1145/3759427.3760377

M3 - Article in proceedings

AN - SCOPUS:105020664210

SP - 166

EP - 179

BT - OLIVIERFEST 2025 - Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday

A2 - Henglein, Fritz

A2 - Lawall, Julia

A2 - Palsberg, Jens

A2 - Ilya, Sergey

PB - Association for Computing Machinery

T2 - 2025 Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday, OLIVIERFEST 2025

Y2 - 12 October 2025 through 18 October 2025

ER -

Generic Reduction-Based Interpreters

Abstract

Konference

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater