Bounding linear head reduction and visible interaction through skeletons
In this paper, we study the complexity of execution in higher-order programming languages. Our study has two facets: on the one hand we give an upper bound to the length of interactions between bounded P-visible strategies in Hyland-Ong game semantics. This result covers models of programming langua...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-06-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1566/pdf |
| _version_ | 1797268647820918784 |
|---|---|
| author | Pierre Clairambault |
| author_facet | Pierre Clairambault |
| author_sort | Pierre Clairambault |
| collection | DOAJ |
| description | In this paper, we study the complexity of execution in higher-order
programming languages. Our study has two facets: on the one hand we give an
upper bound to the length of interactions between bounded P-visible strategies
in Hyland-Ong game semantics. This result covers models of programming
languages with access to computational effects like non-determinism, state or
control operators, but its semantic formulation causes a loose connection to
syntax. On the other hand we give a syntactic counterpart of our semantic
study: a non-elementary upper bound to the length of the linear head reduction
sequence (a low-level notion of reduction, close to the actual implementation
of the reduction of higher-order programs by abstract machines) of simply-typed
lambda-terms. In both cases our upper bounds are proved optimal by giving
matching lower bounds. These two results, although different in scope, are
proved using the same method: we introduce a simple reduction on finite trees
of natural numbers, hereby called interaction skeletons. We study this
reduction and give upper bounds to its complexity. We then apply this study by
giving two simulation results: a semantic one measuring progress in
game-theoretic interaction via interaction skeletons, and a syntactic one
establishing a correspondence between linear head reduction of terms satisfying
a locality condition called local scope and the reduction of interaction
skeletons. This result is then generalized to arbitrary terms by a local
scopization transformation. |
| first_indexed | 2024-04-25T01:35:49Z |
| format | Article |
| id | doaj.art-9dfc5690da864f3ba4e04715819e0b84 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:49Z |
| publishDate | 2015-06-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-9dfc5690da864f3ba4e04715819e0b842024-03-08T09:39:43ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-06-01Volume 11, Issue 210.2168/LMCS-11(2:6)20151566Bounding linear head reduction and visible interaction through skeletonsPierre ClairambaultIn this paper, we study the complexity of execution in higher-order programming languages. Our study has two facets: on the one hand we give an upper bound to the length of interactions between bounded P-visible strategies in Hyland-Ong game semantics. This result covers models of programming languages with access to computational effects like non-determinism, state or control operators, but its semantic formulation causes a loose connection to syntax. On the other hand we give a syntactic counterpart of our semantic study: a non-elementary upper bound to the length of the linear head reduction sequence (a low-level notion of reduction, close to the actual implementation of the reduction of higher-order programs by abstract machines) of simply-typed lambda-terms. In both cases our upper bounds are proved optimal by giving matching lower bounds. These two results, although different in scope, are proved using the same method: we introduce a simple reduction on finite trees of natural numbers, hereby called interaction skeletons. We study this reduction and give upper bounds to its complexity. We then apply this study by giving two simulation results: a semantic one measuring progress in game-theoretic interaction via interaction skeletons, and a syntactic one establishing a correspondence between linear head reduction of terms satisfying a locality condition called local scope and the reduction of interaction skeletons. This result is then generalized to arbitrary terms by a local scopization transformation.https://lmcs.episciences.org/1566/pdfcomputer science - logic in computer science |
| spellingShingle | Pierre Clairambault Bounding linear head reduction and visible interaction through skeletons Logical Methods in Computer Science computer science - logic in computer science |
| title | Bounding linear head reduction and visible interaction through skeletons |
| title_full | Bounding linear head reduction and visible interaction through skeletons |
| title_fullStr | Bounding linear head reduction and visible interaction through skeletons |
| title_full_unstemmed | Bounding linear head reduction and visible interaction through skeletons |
| title_short | Bounding linear head reduction and visible interaction through skeletons |
| title_sort | bounding linear head reduction and visible interaction through skeletons |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1566/pdf |
| work_keys_str_mv | AT pierreclairambault boundinglinearheadreductionandvisibleinteractionthroughskeletons |