In the call-by-value lambda-calculus solvable terms have been characterised by means of call-by-name reductions, which is disappointing and requires complex reasonings. We introduce the value-substitution lambda-calculus, a simple calculus borrowing ideas from Herbelin and Zimmerman’s call-by-value λ CBV calculus and from Accattoli and Kesner’s substitution calculus λ sub . In this new setting, we characterise solvable terms as those terms having normal form with respect to a suitable restriction of the rewriting relation.

Call-by-value solvability, revisited

PAOLINI, LUCA LUIGI
2012-01-01

Abstract

In the call-by-value lambda-calculus solvable terms have been characterised by means of call-by-name reductions, which is disappointing and requires complex reasonings. We introduce the value-substitution lambda-calculus, a simple calculus borrowing ideas from Herbelin and Zimmerman’s call-by-value λ CBV calculus and from Accattoli and Kesner’s substitution calculus λ sub . In this new setting, we characterise solvable terms as those terms having normal form with respect to a suitable restriction of the rewriting relation.
FLOPS 2012: Eleventh International Symposium on Functional and Logic Programming
Takikawa Memorial Hall, Kobe University, 1-1 Rokkodai-cho, Nada-ku, Kobe 657-8501 JAPAN
May 23 – May 25, 2012
11th International Symposium onFunctional and Logic Programming, FLOPS 2012
Springer Verlag
7294
4
16
9783642298219
http://link.springer.com/chapter/10.1007%2F978-3-642-29822-6_4
Beniamino Accattoli; Luca Paolini
File in questo prodotto:
File Dimensione Formato  
Call-by-Value Solvability; Revisited - LNCS 2012 ori.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 251.8 kB
Formato Adobe PDF
251.8 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/99109
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 15
social impact