It is well-known that stable models (as dI-domains, qualitative domains and coherence spaces) are not fully abstract for the language PCF. This fact is related to the existence of stable parallel functions and of stable functions that are not monotone with respect to the extensional order, which cannot be defined by programs of PCF. In this paper, a paradigmatic programming language named StPCF is proposed, which extends the language PCF with two additional operators. The operational description of the extended language is presented in an effective way, although the evaluation of one of the new operators cannot be formalized in a PCF-like rewrite system. Since StPCF can define all finite cliques of coherence spaces the above gap with stable models is filled, consequently stable models are fully abstract for the extended language.

A Stable Programming Language

PAOLINI, LUCA LUIGI
2006-01-01

Abstract

It is well-known that stable models (as dI-domains, qualitative domains and coherence spaces) are not fully abstract for the language PCF. This fact is related to the existence of stable parallel functions and of stable functions that are not monotone with respect to the extensional order, which cannot be defined by programs of PCF. In this paper, a paradigmatic programming language named StPCF is proposed, which extends the language PCF with two additional operators. The operational description of the extended language is presented in an effective way, although the evaluation of one of the new operators cannot be formalized in a PCF-like rewrite system. Since StPCF can define all finite cliques of coherence spaces the above gap with stable models is filled, consequently stable models are fully abstract for the extended language.
204(3)
339
375
http://www.di.unito.it/~paolini/
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WGK-4J0XV83-1&_user=525216&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000026382&_version=1&_urlVersion=0&_userid=525216&md5=427d00b57cd8879734f544f1697860fb
Stable domains; coherence spaces; PCF; full abstraction
L. PAOLINI
File in questo prodotto:
File Dimensione Formato  
A stable programming language - IANDC 2006 ori.pdf

Accesso riservato

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 555.27 kB
Formato Adobe PDF
555.27 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/38194
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 14
social impact