Access Restriction

Author Danvy, Olivier
Source ACM Digital Library
Content type Audio ♦ Text
Publisher Association for Computing Machinery (ACM)
File Format PDF ♦ MP4 ♦ MP3
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Defunctionalization ♦ Context-sensitive reduction semantics ♦ Small-step abstract machines ♦ Interruptions ♦ Refocusing ♦ Cps transformation ♦ Reduction semantics ♦ Natural semantics ♦ Big-step abstract machines ♦ Continuations ♦ Structural operational semantics
Abstract This document illustrates how functional implementations of formal semantics (structural operational semantics, reduction semantics, small-step and big-step abstract machines, natural semantics, and denotational semantics) can be transformed into each other. These transformations were foreshadowed by Reynolds in "Definitional Interpreters for Higher-Order Programming Languages" for functional implementations of denotational semantics, natural semantics, and big-step abstract machines using closure conversion, CPS transformation, and defunctionalization. Over the last few years, the author and his students have further observed that functional implementations of small-step and of big-step abstract machines are related using fusion by fixed-point promotion and that functional implementations of reduction semantics and of small-step abstract machines are related using refocusing and transition compression. It furthermore appears that functional implementations of structural operational semantics and of reduction semantics are related as well, also using CPS transformation and defunctionalization. This further relation provides an element of answer to Felleisen's conjecture that any structural operational semantics can be expressed as a reduction semantics: for deterministic languages, a reduction semantics is a structural operational semantics in continuation style, where the reduction context is a defunctionalized continuation. As the defunctionalized counterpart of the continuation of a one-step reduction function, a reduction context represents the rest of the reduction, just as an evaluation context represents the rest of the evaluation since it is the defunctionalized counterpart of the continuation of an evaluation function.
Description Affiliation: University of Aarhus, Aarhus, Denmark (Danvy, Olivier)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 43
Issue Number 9
Page Count 12
Starting Page 131
Ending Page 142

Open content in new tab

   Open content in new tab
Source: ACM Digital Library