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.

Standardization and Conservativity of a Refined Call-by-Value lambda-Calculus

PAOLINI, LUCA LUIGI;RONCHI DELLA ROCCA, Simonetta
2017-01-01

Abstract

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.
2017
13
4
1
27
https://lmcs.episciences.org/4162
Giulio Guerrieri; Luca Paolini; Simona Ronchi Della Rocca
File in questo prodotto:
File Dimensione Formato  
Standardization and Conservativity of a Refined Call-by-Value lambda-Calculus - arXiv 2016.pdf

Accesso aperto

Tipo di file: PDF EDITORIALE
Dimensione 414.76 kB
Formato Adobe PDF
414.76 kB Adobe PDF Visualizza/Apri
paolini_1611.07255.pdf

Accesso aperto

Tipo di file: PDF EDITORIALE
Dimensione 532.13 kB
Formato Adobe PDF
532.13 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1635801
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact