Linearity is a multi-faceted and ubiquitous notion in the analysis and development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between domains. We propose a PCF-like language imposing linear constraints on the use of variable to program only linear functions. To entail a full abstraction result, we introduce some higher-order operators related to exception handling and parallel evaluation. We study several notions of operational equivalence and show them to coincide with our language. Finally, we present a new operational evaluation of the language that provides the base for a real implementation. It exploits the denotational linearity to provide an efficient evaluation semantics SECD-like, that avoids the use of closures.

On the reification of semantic linearity

PAOLINI, LUCA LUIGI
;
PICCOLO, Mauro
2016-01-01

Abstract

Linearity is a multi-faceted and ubiquitous notion in the analysis and development of programming language concepts. We study linearity in a denotational perspective by picking out programs that correspond to linear functions between domains. We propose a PCF-like language imposing linear constraints on the use of variable to program only linear functions. To entail a full abstraction result, we introduce some higher-order operators related to exception handling and parallel evaluation. We study several notions of operational equivalence and show them to coincide with our language. Finally, we present a new operational evaluation of the language that provides the base for a real implementation. It exploits the denotational linearity to provide an efficient evaluation semantics SECD-like, that avoids the use of closures.
2016
26
5
829
867
http://journals.cambridge.org/action/displayJournal?jid=MSC
https://www.cambridge.org/core/search?filters[authorTerms]=LUCA PAOLINI&eventCode=SE-AU
Computational linguistics; Semantics; Exception handling; Full abstraction; Higher-order; Linear constraints; Linear functions; Operational evaluation; Parallel evaluation
Marco Gaboard; Luca Paolini; Mauro Piccolo
File in questo prodotto:
File Dimensione Formato  
On the reification of semantic linearity - MSCS 2016 ori.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 409.55 kB
Formato Adobe PDF
409.55 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/149917
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact