Giulio Guerrieri ; Luca Paolini ; Simona Ronchi Della Rocca - Standardization and Conservativity of a Refined Call-by-Value lambda-Calculus

lmcs:4162 - Logical Methods in Computer Science, December 22, 2017, Volume 13, Issue 4 - https://doi.org/10.23638/LMCS-13(4:29)2017
Standardization and Conservativity of a Refined Call-by-Value lambda-CalculusArticle

Authors: Giulio Guerrieri ORCID; Luca Paolini ; Simona Ronchi Della Rocca

    We study an extension of Plotkin's call-by-value lambda-calculus via two commutation rules (sigma-reductions). These commutation rules are sufficient to remove harmful call-by-value normal forms from the calculus, so that it enjoys elegant characterizations of many semantic properties. We prove that this extended calculus is a conservative refinement of Plotkin's one. In particular, the notions of solvability and potential valuability for this calculus coincide with those for Plotkin's call-by-value lambda-calculus. The proof rests on a standardization theorem proved by generalizing Takahashi's approach of parallel reductions to our set of reduction rules. The standardization is weak (i.e. redexes are not fully sequentialized) because of overlapping interferences between reductions.


    Volume: Volume 13, Issue 4
    Published on: December 22, 2017
    Accepted on: December 22, 2017
    Submitted on: December 22, 2017
    Keywords: Computer Science - Logic in Computer Science,03B40, 68N18,F.3.2,D.3.1,F.4.1
    Funding:
      Source : OpenAIRE Graph
    • INITIATIVE D'EXCELLENCE AIX MARSEILLE UNIVERSITE; Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-0001

    4 Documents citing this article

    Consultation statistics

    This page has been seen 1567 times.
    This article's PDF has been downloaded 417 times.