Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4751
Main Title: Analysis and implementation of hierarchical mutually recursive first class modules
Translated Title: Analyse und Implementierung hierarchischer, gegenseitig rekursiver First-Class Module
Author(s): Rohloff, Judith
Advisor(s): Pepper, Peter
Nestmann, Uwe
Referee(s): Pepper, Peter
Trancón Widemann, Baltasar
Nestmann, Uwe
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Arbeit entwickelt eine neue Methode um zyklisch abhängige, first-class Module in eine call-by-value Sprache zu integrieren. Hierbei wird auf Module mittels dot-Notation zugegriffen und für zyklisch abhängige Module wird keine zusätzliche Syntax benötigt. Im Gegensatz zu anderen call-by-value Sprachen können hier zyklisch abhängige Module ohne Modulkomposition oder “self” Variablen definiert werden. Dieser einfache Mechanismus wird mittels einer Abhängigkeitsanalyse erreicht, welche alle Informationen, die sonst der Programmierer bereitstellen müsste, berechnet. Es wird eine transformationelle Semantik für eine call-by-value Sprache mit hierarchischen, zyklisch abhängigen und first-class Modulen entwickelt. Dafür wird GLang, eine kleine funktionale Sprache, definiert. In GLang wird das Konzept der Gruppen für die Definition von Modulen genutzt. Das Konzept der Gruppen kombiniert dynamische Datenstrukturen mit Aspekten der Modularisierung und der Namensbindung in funktionalen Sprachen. Gruppen sind first-class Values und vereinigen rekursive Definitionen, lexikalisches Scoping, hierarchische Strukturierung von Programmen und dynamisch typisierte Datenstrukturen in einem Konstrukt. Die Probleme, die bei der Kombination von hierarchischen, zyklisch abhängigen und first-class Modulen entstehen, werden zunächst verdeutlicht. Diese Arbeit stellt im Anschluß eine Lösung dieser Probleme vor, welche auf einer neuen Pfadauflösung basiert. Die auf dieser Pfadauflösung basierende Abhängigkeitsanalyse berechnet die Auswertungsreihenfolge aller Definitionen. Diese Auswertungsreihenfolge wird anschließend genutzt um einen GLang-Ausdruck in eine Zwischenrepräsentation zu transformieren. Jede Gruppe wird dabei in eine Komponente transformiert, welche alle Definitionen dieser Gruppe in Abhängigkeitsreihenfolge enthält. Dies stellt sicher, dass Gruppen als Einheit erhalten bleiben. Für die Zwischenrepräsentation wird eine Auswertungsfunktion definiert. Die Transformation zusammen mit der Auswertungsfunktion definiert die Semantik von GLang. Zusätzlich zur Semantik wird die Übersetzung in einen Lambda-Kalkül mit Records und rekursiven let-Ausdrücken entwickelt. Außerdem werden verschiedene Erweiterungen für GLang diskutiert.
This thesis presents a novel way to introduce mutually recursive first-class modules into a call-by-value programming language. In our approach, all modules are accessed through dot-notation without any additional syntax for mutually recursive modules. In contrast to other call-by-value languages, mutually recursive modules can be declared without the use of module composition or a self variable. This simple mechanism is achieved through a dependency analysis. This analysis computes all necessary information, which, in other approaches, must be provided by the programmer. The transformation based denotational semantics of a call-by-value language with first-class, hierarchical and recursive modules is presented. For this purpose, a small functional language - GLang - is defined. GLang uses the notation of Groups, as proposed by Pepper and Hofstedt. Modules merge dynamic data structures with aspects of modularisation and name binding in functional programming languages. Groups are first-class values, which capture recursive definitions, lexical scoping, hierarchical structuring of programs, and dynamically typed data structures in a single construction. This thesis clarifies what problems occur in combining nested, recursive and first-class modules and shows how to solve these problems by a novel path resolution algorithm. This path resolution algorithm is the basis for a dependency analysis which determines the evaluation order for definitions. This evaluation order is used to transform a GLang expression into an intermediate representation. Each Module is transformed into a component which contains all definitions of this Module in dependency order. This ensures that Modules are kept as entities. For the intermediate representation, an evaluation function is provided. The transformation and the evaluation function together define the call-by-value semantics of GLang. Moreover, the compilation into a call-by-value lambda-calculus with records and recursive let-expressions is defined, and we discuss different possibilities to extend GLang.
URI: urn:nbn:de:kobv:83-opus4-72706
http://depositonce.tu-berlin.de/handle/11303/5048
http://dx.doi.org/10.14279/depositonce-4751
Exam Date: 2-Jul-2015
Issue Date: 16-Oct-2015
Date Available: 16-Oct-2015
DDC Class: 005 Computerprogrammierung, Programme, Daten
Subject(s): Zyklisch-abhängige Module
transformationelle Semantik
First-Class Module
Abhängigkeitsanalyse
Mutually-recursive modules
transformational semantics
first-class modules
dependency analysis
call-by-value evaluation
Creative Commons License: https://creativecommons.org/licenses/by/3.0/de/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
rohloff_judith.pdf880.26 kBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.