2021•Unpublished venueRequires access

Soundness conditions for big-step semantics

Francesco Dagnino, Viviana Bono, Elena Zucca, Mariangiola Dezani-Ciancaglini

Open publisher page 0 citations

Abstract

We propose a general proof technique to show that a predicate is sound, that is, prevents stuck computation, with respect to a big-step semantics.This result may look surprising, since in big-step semantics there is no difference between non-terminating and stuck computations, hence soundness cannot even be expressed.The key idea is to define constructions yielding an extended version of a given arbitrary big-step semantics, where the difference is made explicit.The extended semantics are exploited in the meta-theory, notably they are necessary to show that the proof technique works.However, they remain transparent when using the proof technique, since it consists in checking three conditions on the original rules only, as we illustrate by several examples.

About this research paper

What this paper is about

We propose a general proof technique to show that a predicate is sound, that is, prevents stuck computation, with respect to a big-step semantics.This result may look surprising, since in big-step semantics there is no difference between non-terminating and stuck computations, hence soundness cannot even be expressed.The key idea is to define constructions yielding an extended version of a given arbitrary big-step semantics, where the difference is made explicit.The extended semantics are exploited in the meta-theory, notably they are necessary to show that the proof technique works.However, they remain transparent when using the proof technique, since it consists in checking three conditions on the original rules only, as we illustrate by several examples.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We propose a general proof technique to show that a predicate is sound, that is, prevents stuck computation, with respect to a big-step semantics.This result may look surprising, since in big-step semantics there is no difference between non-terminating and stuck computations, hence soundness cannot even be expressed.The key idea is to define constructions yielding an extended version of a given arbitrary big-step semantics, where the difference is made explicit.The extended semantics are exploited in the meta-theory, notably they are necessary to show that the proof technique works.However, they remain transparent when using the proof technique, since it consists in checking three conditions on the original rules only, as we illustrate by several examples.

Key concepts: Soundness, Semantics (computer science), Computer science, Programming language

Related papers

Back to paper searchBrowse research topicsOriginal source
Soundness conditions for big-step semantics — Research Paper | ScholarLens