Affordable Access

Publisher Website

Token-Passing Nets: Call-by-Need for Free

Authors
Journal
Electronic Notes in Theoretical Computer Science
1571-0661
Publisher
Elsevier
Publication Date
Volume
135
Issue
3
Identifiers
DOI: 10.1016/j.entcs.2005.09.027
Keywords
  • λ-Calculus
  • Call-By-Name
  • Call-By-Value
  • Interaction Net
Disciplines
  • Philosophy

Abstract

Abstract Recently, encodings in interaction nets of the call-by-name and call-by-value strategies of the λ-calculus have been proposed. The purpose of these encodings was to bridge the gap between interaction nets and traditional abstract machines, which are both used to provide lower-level specifications of strategies of the λ-calculus, but in radically different ways. The strength of these encodings is their simplicity, which comes from the simple idea of introducing an explicit syntactic object to represent the flow of evaluation. In particular, no artifact to represent boxes is needed. However, these encodings purposefully follow as closely as possible the implemented strategies, call-by-name and call-by-value, hence do not benefit from the ability of interaction nets to easily represent sharing. The aim of this note is to show that sharing can indeed be achieved without adding any structure. We thus present the call-by-need strategy following the same philosophy, which is indeed not any more complicated than call-by-name. This continues the task of bridging the gap between interaction nets and abstract machines, thus pushing forward a more uniform framework for implementations of the λ-calculus.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Token-passing Nets for Functional Languages

on Electronic Notes in Theoretica... Jan 01, 2008

Nets with tokens which carry data

on Fundamenta Informaticae Jan 01, 2008
More articles like this..