A non-deterministic call-by-need lambda calculus : proving similarity a precongruence by an extension of Howe's method to sharing

Ein nichtdeterministischer Call-by-Need-Lambda-Kalkül : Nachweis der Präkongruenzeigenschaft für Similarity über eine Erweiterung von Howes Methode auf Sharing

  • In this dissertation a non-deterministic lambda-calculus with call-by-need evaluation is treated. Call-by-need means that subexpressions are evaluated at most once and only if their value must be known to compute the overall result. Also called "sharing", this technique is inevitable for an efficient implementation. In the lambda-ND calculus of chapter 3 sharing is represented explicitely by a let-construct. Above, the calculus has function application, lambda abstractions, sequential evaluation and pick for non-deterministic choice. Non-deterministic lambda calculi play a major role as a theoretical foundation for concurrent processes or side-effected input/output. In this work, non-determinism additionally makes visible when sharing is broken. Based on the bisimulation method this work develops a notion of equality which respects sharing. Using bisimulation to establish contextual equivalence requires substitutivity within contexts, i.e., the ability to "replace equals by equals" within every program or term. This property is called congruence or precongruence if it applies to a preorder. The open similarity of chapter 4 represents a new concept, insofar that the usual definition of a bisimulation is impossible in the lambda-ND calculus. So in section 3.2 a further calculus lambda-Approx has to be defined. Section 3.3 contains the proof of the so-called Approximation Theorem which states that the evaluation in lambda-ND and lambda-Approx agrees. The foundation for the non-trivial precongruence proof is set out in chapter 2 where the trailblazing method of Howe is extended to be capable with sharing. By the use of this (extended) method, the Precongruence Theorem proves open similarity to be a precongruence, involving the so-called precongruence candidate relation. Joining with the Approximation Theorem we obtain the Main Theorem which says that open similarity of the lambda-Approx calculus is contained within the contextual preorder of the lambda-ND calculus. However, this inclusion is strict, a property whose non-trivial proof involves the notion of syntactic continuity. Finally, chapter 6 discusses possible extensions of the base calculus such as recursive bindings or case and constructors. As a fundamental study the calculus lambda-ND provides neither of these concepts, since it was intentionally designed to keep the proofs as simple as possible. Section 6.1 illustrates that the addition case and constructors could be accomplished without big hurdles. However, recursive bindings cannot be represented simply by a fixed point combinator like Y, thus further investigations are necessary.
  • Die vorliegende Dissertation behandelt einen nichtdeterministischen Lambda-Kalkül mit sogenannter "call-by-need" Auswertung. Diese Auswertungsstrategie wertet Teilausdrücke nur bei Bedarf aus und verwendet Zwischenergebnisse dabei so weit wie möglich wieder. Eine solche Technik wird auch als "Sharing" bezeichnet und ist für eine effiziente Implementierung unverzichtbar. Im Kalkül Lambda-ND aus Kapitel 3 wird Sharing explizit durch ein let-Konstrukt dargestellt. Darüberhinaus verfügt der Kalkül über Funktionsanwendungen, Abstraktionen mittels Lambda, sequentielle Auswertung über ein seq-Konstrukt und pick für nichtdeterministische Auswahl. Abgesehen von der großen Bedeutung nichtdeterministischer Lambda-Kalküle u.a. als theoretischer Grundlage für nebenläufige Prozesse oder von deklarativer, Seiteneffekt-behafteter Ein-/Ausgabe, wird in diesem Fall durch den Nichtdeterminismus erst deutlich, wann Sharing verletzt ist. In dieser Arbeit wird nun, basierend auf der Methode der Bisimulation, ein Gleichheitsbegriff entwickelt, der Sharing respektiert. Um Bisimulation zum Beweis von kontextueller Gleichheit verwenden zu können, ist Einsetzbarkeit in Kontexte erforderlich, d.h. daß gleiche Terme quasi als Unterprogramme austauschbar sind. Diese Eigenschaft heißt Kongruenz bzw. Präkongruenz, wenn sie eine Präordnung betrifft. Die Open Similarity in Kapitel 4 ist insofern neu, als daß die übliche Definition einer Bisimulation im call-by-need Kalkül Lambda-ND nicht möglich ist und daher in Abschnitt 3.2 ein weiterer Kalkül Lambda-Approx definiert werden muß. Das in Abschnitt 3.3 bewiesene Approximation Theorem stellt die Übereinstimmung der Auswertung in Lambda-ND- und Lambda-Approx-Kalkül her. Die Basis für den Präkongruenzbeweis ist Kapitel 2, in dem die bahnbrechende Methode von Howe, die für eine ganze Klasse von Sprachen anwendbar ist, entsprechend auf Sharing erweitert wird. Open Similarity wird damit im Precongruence Theorem über die Stabilität des sogenannten Präkongruenzkandidaten als Präkongruenz nachgewiesen. Die Verknüpfung mit dem Approximation Theorem ergibt das Main Theorem, welches zeigt, daß die Open Similarity des Lambda-Approx-Kalküls in der kontextuellen Präordnung von Lambda-ND enthalten ist. Diese Inklusion ist jedoch strikt. Der Nachweis dieser Eigenschaft ist nicht trivial und wird in Abschnitt 5.2 über den Begriff der syntaktischen Stetigkeit geführt. Abschließend werden in Kapitel 6 mögliche Erweiterungen behandelt, da der Basiskalkül Lambda-ND als grundlegende Studie weder über Datentypen noch über rekursive Bindungen in seinem let-Konstrukt verfügt, um die Beweisführung nicht unnötig zu verkomplizieren. Die Betrachtungen in Abschnitt 6.1 erscheinen vielversprechend, daß Datentypen, also case und Konstruktoren, ohne größere Schwierigkeiten zum Kalkül hinzugefügt werden können. Für rekursive let-Bindungen hingegen wird in Abschnitt 6.2 gezeigt, daß sie nicht einfach mittels eines Fixpunktkombinators, wie z.B. Y, dargestellt werden können.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Matthias Mann
URN:urn:nbn:de:hebis:30-24661
Referee:Manfred Schmidt-SchaußORCiDGND
Document Type:Doctoral Thesis
Language:English
Date of Publication (online):2006/03/28
Year of first Publication:2005
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Granting Institution:Johann Wolfgang Goethe-Universität
Date of final exam:2005/08/17
Release Date:2006/03/28
Tag:Call-by-Need; Präkongruenz; Similarity; kontextuelle Gleichheit
Call-by-need Lambda Calculus; Contextual Equivalence; Non-determinism; Precongruence; Similarity
GND Keyword:Lambda-Kalkül; Nichtdeterminismus
HeBIS-PPN:176710140
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht