Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation

John P. Gallagher; Manuel V. Hermenegildo; José F. Morales; Pedro López-García

doi:10.1007/978-3-031-45784-5_3

Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation

John P. Gallagher^*, Manuel V. Hermenegildo, José F. Morales, Pedro López-García

^*Corresponding author for this work

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

Abstract

Natural semantics (big-step) and structural operational semantics (small-step) each have advantages, so it can be useful to produce both semantic forms for a language. Previous work has shown that big-step semantics can be transformed to small-step semantics. This is also the goal of our work, but our main contribution is to show that this can be done by specialisation of an interpreter that imposes a small-step execution on big-step transition rules. This is arguably more direct, transparent and flexible than previous methods. The paper contains two examples and further examples are available in an online repository

Original language	English
Title of host publication	Logic-Based Program Synthesis and Transformation : 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings
Editors	Robert Glück, Bishoksan Kafle
Number of pages	11
Volume	14330
Publisher	Springer
Publication date	2023
Pages	28-38
ISBN (Print)	9783031457838
ISBN (Electronic)	978-3-031-45784-5
DOIs	https://doi.org/10.1007/978-3-031-45784-5_3
Publication status	Published - 2023
Event	33rd International Symposium on Logic-Based Program Synthesis and Transformation - Cascais, Portugal Duration: 23 Oct 2023 → 24 Oct 2023 Conference number: 33

Symposium

Symposium	33rd International Symposium on Logic-Based Program Synthesis and Transformation
Number	33
Country/Territory	Portugal
City	Cascais
Period	23/10/2023 → 24/10/2023

Series	Lecture Notes in Computer Science
Number	14330

Keywords

Interpreter specialisation
Operational semantics

Link to document

10.1007/978-3-031-45784-5_3

Transforming Big-step to Small-step Semantics using Interpreter SpecialisationAccepted author manuscript, 300 KBLicence: Other

https://doi.org/10.1007/978-3-031-45784-53

Cite this

Gallagher, J. P., Hermenegildo, M. V., Morales, J. F., & López-García, P. (2023). Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation. In R. Glück, & B. Kafle (Eds.), Logic-Based Program Synthesis and Transformation: 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings (Vol. 14330, pp. 28-38). Springer. https://doi.org/10.1007/978-3-031-45784-5_3

Gallagher, John P. ; Hermenegildo, Manuel V. ; Morales, José F. et al. / Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation. Logic-Based Program Synthesis and Transformation: 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings. editor / Robert Glück ; Bishoksan Kafle. Vol. 14330 Springer, 2023. pp. 28-38 (Lecture Notes in Computer Science; No. 14330).

@inproceedings{b0e04b096b074593901aa7d5ec698451,

title = "Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation",

abstract = "Natural semantics (big-step) and structural operational semantics (small-step) each have advantages, so it can be useful to produce both semantic forms for a language. Previous work has shown that big-step semantics can be transformed to small-step semantics. This is also the goal of our work, but our main contribution is to show that this can be done by specialisation of an interpreter that imposes a small-step execution on big-step transition rules. This is arguably more direct, transparent and flexible than previous methods. The paper contains two examples and further examples are available in an online repository",

keywords = "Interpreter specialisation, Operational semantics",

author = "Gallagher, {John P.} and Hermenegildo, {Manuel V.} and Morales, {Jos{\'e} F.} and Pedro L{\'o}pez-Garc{\'i}a",

year = "2023",

doi = "10.1007/978-3-031-45784-5_3",

language = "English",

isbn = "9783031457838",

volume = "14330",

series = "Lecture Notes in Computer Science",

number = "14330",

pages = "28--38",

editor = "Robert Gl{\"u}ck and Bishoksan Kafle",

booktitle = "Logic-Based Program Synthesis and Transformation",

publisher = "Springer",

note = "33rd International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2023 ; Conference date: 23-10-2023 Through 24-10-2023",

}

Gallagher, JP, Hermenegildo, MV, Morales, JF & López-García, P 2023, Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation. in R Glück & B Kafle (eds), Logic-Based Program Synthesis and Transformation: 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings. vol. 14330, Springer, Lecture Notes in Computer Science, no. 14330, pp. 28-38, 33rd International Symposium on Logic-Based Program Synthesis and Transformation, Cascais, Portugal, 23/10/2023. https://doi.org/10.1007/978-3-031-45784-5_3

Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation. / Gallagher, John P.; Hermenegildo, Manuel V.; Morales, José F. et al.
Logic-Based Program Synthesis and Transformation: 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings. ed. / Robert Glück; Bishoksan Kafle. Vol. 14330 Springer, 2023. p. 28-38 (Lecture Notes in Computer Science; No. 14330).

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

TY - GEN

T1 - Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation

AU - Gallagher, John P.

AU - Hermenegildo, Manuel V.

AU - Morales, José F.

AU - López-García, Pedro

N1 - Conference code: 33

PY - 2023

Y1 - 2023

N2 - Natural semantics (big-step) and structural operational semantics (small-step) each have advantages, so it can be useful to produce both semantic forms for a language. Previous work has shown that big-step semantics can be transformed to small-step semantics. This is also the goal of our work, but our main contribution is to show that this can be done by specialisation of an interpreter that imposes a small-step execution on big-step transition rules. This is arguably more direct, transparent and flexible than previous methods. The paper contains two examples and further examples are available in an online repository

AB - Natural semantics (big-step) and structural operational semantics (small-step) each have advantages, so it can be useful to produce both semantic forms for a language. Previous work has shown that big-step semantics can be transformed to small-step semantics. This is also the goal of our work, but our main contribution is to show that this can be done by specialisation of an interpreter that imposes a small-step execution on big-step transition rules. This is arguably more direct, transparent and flexible than previous methods. The paper contains two examples and further examples are available in an online repository

KW - Interpreter specialisation

KW - Operational semantics

U2 - 10.1007/978-3-031-45784-5_3

DO - 10.1007/978-3-031-45784-5_3

M3 - Article in proceedings

SN - 9783031457838

VL - 14330

T3 - Lecture Notes in Computer Science

SP - 28

EP - 38

BT - Logic-Based Program Synthesis and Transformation

A2 - Glück, Robert

A2 - Kafle, Bishoksan

PB - Springer

T2 - 33rd International Symposium on Logic-Based Program Synthesis and Transformation

Y2 - 23 October 2023 through 24 October 2023

ER -

Gallagher JP, Hermenegildo MV, Morales JF, López-García P. Transforming Big-Step to Small-Step Semantics Using Interpreter Specialisation. In Glück R, Kafle B, editors, Logic-Based Program Synthesis and Transformation: 33rd International Symposium, LOPSTR 2023, Cascais, Portugal, October 23-24, 2023, Proceedings. Vol. 14330. Springer. 2023. p. 28-38. (Lecture Notes in Computer Science; No. 14330). doi: 10.1007/978-3-031-45784-5_3