Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe (In)Efficiency of Interaction
218
0
0.0
(
0
)
Added by
Gabriele Vanoni
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Evaluating higher-order functional programs through abstract machines inspired by the geometry of the interaction is known to induce $textit{space}$ efficiencies, the price being $textit{time}$ performances often poorer than those obtainable with traditional, environment-based, abstract machines. Although families of lambda-terms for which the former is exponentially less efficient than the latter do exist, it is currently unknown how emph{general} this phenomenon is, and how far the inefficiencies can go, in the worst case. We answer these questions formulating four different well-known abstract machines inside a common definitional framework, this way being able to give sharp results about the relative time efficiencies. We also prove that non-idempotent intersection type theories are able to precisely reflect the time performances of the interactive abstract machine, this way showing that its time-inefficiency ultimately descends from the presence of higher-order types.
rate research
Read More
This volume contains the proceedings of ICE20, the 13th Interaction and Concurrency Experience, which was held online on the 19th of June 2020, as a satellite event of DisCoTec20. The ICE workshop series features a distinguishing review and selection procedure, allowing PC members to interact anonymously with authors. As in the past 12 editions, this interaction considerably improved the accuracy of the feedback from the reviewers and the quality of accepted papers, and offered the basis for lively discussion during the workshop. The 2020 edition of ICE included double blind reviewing of original research papers, in order to increase fairness and avoid bias in reviewing. Each paper was reviewed by three PC members, and altogether 5 papers were accepted for publication - plus 5 oral presentations which are not part of this volume. We were proud to host 2 invited talks, by Cinzia Di Giusto and Karoliina Lehtinen. The abstracts of these talks are included in this volume together with the regular papers. The fin
The original paper on Mixed Sessions introduce the side A of the tape: there is an encoding of classical sessions into mixed sessions. Here we present side B: there is a translation of (a subset of) mixed sessions into classical session types. We prove that the translation is a minimal encoding, according to the criteria put forward by Kouzapas, Perez, and Yoshida.
Single-pass instruction sequences under execution are considered to produce behaviours to be controlled by some execution environment. Threads as considered in thread algebra model such behaviours: upon each action performed by a thread, a reply from its execution environment determines how the thread proceeds. Threads in turn can be looked upon as producing processes as considered in process algebra. We show that, by apposite choice of basic instructions, all processes that can only be in a finite number of states can be produced by single-pass instruction sequences.
The possibility of translating logic programs into functional ones has long been a subject of investigation. Common to the many approaches is that the original logic program, in order to be translated, needs to be well-moded and this has led to the common understanding that these programs can be considered to be the ``functional part of logic programs. As a consequence of this it has become widely accepted that ``complex logical variables, the possibility of a dynamic selection rule, and general properties of non-well-moded programs are exclusive features of logic programs. This is not quite true, as some of these features are naturally found in lazy functional languages. We readdress the old question of what features are exclusive to the logic programming paradigm by defining a simple translation applicable to a wider range of logic programs, and demonstrate that the current circumscription is unreasonably restrictive.
In this article, we give an overview of our project on higher-order program verification based on HFL (higher-order fixpoint logic) model checking. After a brief introduction to HFL, we explain how it can be applied to program verification, and summarize the current status of the project.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
