Refine
Year of publication
Document Type
- Diploma Thesis (9)
- Doctoral Thesis (5)
Has Fulltext
- yes (14)
Is part of the Bibliography
- no (14)
Keywords
- Contextual Equivalence (2)
- Lambda-Kalkül (2)
- BMRT (1)
- BRDF (1)
- BTF (1)
- Beleuchtungsmodell (1)
- Call-by-Need (1)
- Call-by-need Lambda Calculus (1)
- Ein-Ausgabe ; Funktionale Programmiersprache ; Lambda-Kalkül ; Nichtdeterminismus ; Operationale Semantik ; Programmtransformation (1)
- Funktionale Programmiersprache (1)
Institute
- Informatik (13)
- Informatik und Mathematik (1)
Die Implementation der Striktheits-Analyse, die im Zuge dieser Arbeit vorgenommen wurde, stellt eine effiziente Approximation der abstrakten Reduktion mit Pfadanalyse dar. Durch die G#-Maschine, ein neues, auf der G-Maschine basierendes Maschinenmodell, wurde die verwendete Methode systematisch dargelegt. Die große Ähnlichkeit mit der G-Maschin, die in unserer Implementation beibehalten werden konnte, zeigt, wie natürlich die verwendete Methode der Reduktion in funktionalen Programmiersprachen entspricht. Obwohl die Umsetzung mehr Wert auf Nachvollziehbarkeit, als auf Effizienz legt, zeigt sie, daß die Methode der abstrakten Reduktion mit Pfadanalyse auch in einer funktionalen Implementierung durchaus alltagstauglich ist und Striktheits-Information findet, die Umsetzungen anderer Methoden nicht finden. Es bestehen Möglichkeiten zur Optimierung u. a. von Programmteilen, die für jede simulierte G#-Maschinen-Anweisung ausgeführt werden. Bei vorsichtiger Einschätzung erscheint eine Halbierung der Laufzeit mit vertretbarem Aufwand erreichbar.
Funktionale Programmiersprachen weisen viele Eigenschaften auf, die zur modernen Softwareentwicklung benotigt werden: Zuverlässigkeit, Modularisierung, Wiederverwendbarkeit und Verifizierbarkeit. Als schwer vereinbar mit diesen Sprachen stellte sich die Einbettung von Seiteneffekten in diese Sprachen heraus. Nach einigen mehr oder weniger gescheiterten Ansätzen hat sich mittlerweile fur die nichtstrikte funktionale Sprache Haskell der monadische Ansatz durchgesetzt, bei dem die Seiteneffekte geschickt verpackt werden, so dass zumindest IO-behaftete Teile eines Haskell-Programms dem klassischen imperativen Programmierstil ähneln. S. Peyton Jones bringt dieses in [Pey01, Seite 3] auf den Punkt, indem er schreibt "...Haskell is the world's finest imperative programming language." Dies ist einerseits vorteilhaft, denn die klassischen Programmiertechniken können angewendet werden, andererseits bedeutet dies auch eine Rückkehr zu altbekannten Problemen in diesen Sprachen: Der Programmcode wird unverständlicher, die Wiederverwendbarkeit von Code verschlechtert sich, Änderungen im Programm sind aufwendig. Zudem erscheint die monadische Programmierung teilweise umständlich. Deshalb wurde im Zuge der Entwicklung in fast jede Implementierung von Haskell ein Konstrukt eingebaut, dass von monadischem IO zu direktem IO führt. Da dieses nicht mit dem bisherigen Ansatz vereinbar schien, wird es als "unsafe" bezeichnet, die entsprechende Funktion heißt "unsafePerformIO". Zahlreiche Anwendungen benutzten diese Funktion, teilweise scheint die Verwendung zumindest aus Effizienzgründen unabdingbar. Allerdings ist die Frage, wann dieses verwendet werden darf, d.h. so angewendet wird, dass es nicht "unsicher" ist, nur unzureichend geklärt. Das Zitat in Abbildung 1.1 gibt wenig Aufschluss über die korrekte Anwendung, zumal immer wieder Diskussionen entstehen, ob die Verwendung von unsafePerformIO in diesem oder jenem Spezialfall korrekt ist.
The number of multilingual texts in the World Wide Web (WWW) is increasing dramatically and a multilingual economic zone like the European Union (EU) requires the availability of multilingual Natural Language Processing (NLP) tools. Due to a rapid development of NLP tools, many lexical, syntactic, semantic and other linguistic features have been used in different NLP applications. However, there are some situations where these features can not be used due the application type or unavailability of NLP resources for some of the languages. That is why an application that is intended to handle multilingual texts must have features that are not dependent on a particular language and specific linguistic tools. In this thesis, we will focus on two such applications: text readability and source and translation classification.
In this thesis, we provide 18 features that are not only suitable for both applications, but are also language and linguistic tools independent. In order to build a readability classifier, we use texts from three different languages: English, German and Bangla. Our proposed features achieve a classification accuracy that is comparable with a classifier using 40 linguistic features. The readability classifier achieves a classification F-score of 74.21% on the English Wikipedia corpus, an F-score of 75.47% on the English textbook corpus, an F-score of 86.46% on the Bangla textbook corpus and an F-score of 86.26% on the German GEO/GEOLino corpus.
We used more than two million sentence pairs from 21 European languages in order to build the source and translation classifier. The classifier using the same eighteen features achieves a classification accuracy of 86.63%. We also used the same features to build a classifier that classifies translated texts based on their origin. The classifier achieves classification accuracy of 75% for texts from 10 European languages. In this thesis, we also provide four different corpora, three for text readability analysis and one for corpus based translation studies.
Space optimizations in deterministic and concurrent call-by-need functional programming languages
(2020)
In this thesis the space consumption and runtime of lazy-evaluating functional programming languages are analyzed.
The typed and extended lambda-calculi LRP and CHF* as core languages for Haskell and Concurrent Haskell are used. For each LRP and CHF* compatible abstract machines are introduced.
Too lower the distortion of space measurement a classical implementable garbage collector is applied after each LRP reduction step. Die size of expressions and the space measure spmax as maximal size of all garbage-free expressions during an LRP-evaluation, are defined.
Program-Transformations are considered as code-to-code transformations. The notions Space Improvement and Space Equivalence as properties of transformations are defined. A Space Improvement does neither change the semantics nor it increases the needed space consumption, for a space equivalence the space consumption is required to remain the same. Several transformations are shown as Space Improvements and Equivalences.
An abstract machine for space measurements is introduced. An implementation of this machine is used for more complex space- and runtime-analyses.
Total Garbage Collection replaces subexpressions by a non-terminating constant with size zero, if the overall termination is not affected. Thereby the notion of improvement is more independent from the used garbage collector.
Analogous to Space Improvements and Equivalences the notions Total Space Improvement and Total Space Equivalence are defined, which use Total Garbage Collection during the space measurement. Several Total Space Improvements and Equivalences are shown.
Space measures for CHF* are defined, that are compatible to the space measure of LRP. An algorithm with sort-complexity is developed, that calculates the required space of independent processes that all start and end together. If a constant amount of synchronization restrictions is added and a constant number of processors is used, the runtime is polynomial, if arbitrary synchronizations are used, then the problem is NP-complete.
Abstract machines for space- and time-analyses in CHF* are developed and implementations of these are used for space and runtime analyses.
Ziel dieser Arbeit war es, ein System zu entwickeln, mit dem Sätze von Reduktionsdiagrammen auf ihre Vollständigkeit überprüft werden können. Das System sollte in der puren, funktionalen Programmiersprache Haskell realisiert werden und speziell auf einen nichtdeterministischen Kalkül mit Konstruktoren, einem case-Konstrukt und einem rekursiven let- Ausdruck (letrec) ausgerichtet sein. Dazu wurde in Kapitel 2 der lambda-Kalkül und funktionale Programmiersprachen eingeführt, um die Entwicklung der Kalküle lambda-nd und lambda-nd,rec zu motivieren. Die Basis-Kalküle lambda-nd und lamda-nd,rec wurden in Kapitel 3 bezüglich ihrer Sprachdefinition und Reduktionsregeln vorgestellt. Die Implementierung der beiden Kalküle und der Parser für die verwendete Kernsprache wurden ebenso angegeben wie die Mechanismen zur Markierung und Reduktion der Terme. Die Unterscheidung eines reduzierbaren Terms in NO- und internen Redex, sowie deren Erkennung wurde in diesem Kapitel besonders herausgestellt, da sie die Grundlage für die zu validierenden Reduktionsdiagramme darstellt. Damit ist der Grundstock für diese Arbeit gelegt worden. In Kapitel 4 haben wir kurz Methoden vorgestellt, die lamda-Kalkülen und deren Derivate eine Bedeutung zuzumessen versuchen, um Programme oder Terme miteinander vergleichen zu können. Also nicht nur ihre Termstruktur, sondern ihr Verhalten zu vergleichen. Dabei ist festgestellt worden, daß für nichtdeterministische Kalküle nur eine Methode verfügbar ist, und zwar die der kontextuellen Äquivalenz. Da wir gängige Programmtransformationen dahingehend überprüfen wollten, ob sie der kontextuellen Äquivalenz genügen, also nicht die Auswertung oder das Ergebnis derselben verändern, haben wir ein Kontext-Lemma vorgestellt. Mit Hilfe des Kontext-Lemmas ist es uns möglich gewesen, die Gültigkeit von Beweisen in Reduktionskontexten auf beliebige Kontexte auszudehnen. Für die eigentlichen Beweise werden Reduktionsdiagramme benötigt, die Reduktionsfolgen in verschiedener Weise umstellen. Wir haben die Reduktionsdiagramme ebenfalls in Kapitel 4 definiert. Die Reduktionsdiagramme müssen an jeder Stelle einer Reduktionsfolge anwendbar sein, da sonst die Äquivalenz-Beweise nicht möglich sind. D. h. es müßte bewiesen werden, daß mindestens ein Reduktionsdiagramm einer definierten Menge von Reduktionsdiagrammen für jeden Term und jede seiner Reduktionsfolgen anwendbar ist. Der naive Weg wäre, alle Terme und seine Reduktionsfolgen dahingehend zu überprüfen. Da dies jedoch nicht möglich ist, haben wir uns dazu entschlossen so viele Terme wie möglich zu untersuchen, nicht um die Vollständigkeit der Diagramme zu beweisen, sondern um zu zeigen, daß auf viele verschiedenartige Terme Reduktionsdiagramme erfolgreich angewendet werden können. Die Generierung der Terme haben wir in Kapitel 5 ausführlich dargestellt. In Kapitel 6 haben wir die Sprache zur Darstellung von Reduktionsdiagrammen und die Implementierung der Diagramm-Validierung beschrieben. Weiterhin haben wir ein Verfahren vorgestellt, mit dem wir fehlende Diagramme für Terme suchen und meist auch finden können. Das gesamte System haben wir so aufgebaut, daß eine große Menge an Termen generiert wird, für die Diagramme anwendbar sein müssen. Wenn keines der Diagramme auf einen Term anwendbar ist, also nicht validiert werden kann, dann wird ein passendes Diagramm gesucht. Mit Hilfe des entwickelten Systems Jonah sind in Kapitel 7 verschiedene Programmtransformationen dahingehend überprüft worden, ob die angegebenen Reduktionsdiagramme für große Mengen von Termen gültig sind. Dabei ist als Ergebnis herausgekommen, daß ein vollständiger Satz an Reduktionsdiagrammen für die (cp)-Reduktion nur sehr schwer zu finden ist. Selbst neu hinzugefügte Transformationen, die dabei helfen sollten, die Schwierigkeiten zu umgehen, konnten nicht verwendet werden, da es uns ebenfalls nicht möglich gewesen ist, für sie vollständige Diagrammsätze zu finden. Daraufhin haben wir den Basis-Kalkül zweimal erweitert, um die Schwierigkeiten der (cp)-Diagramme in den Griff zu bekommen. Aber auch diese Ansätze haben kein zufriedenstellendes Ergebnis geliefert. Als positives Ergebnis dieser Arbeit kann aber festgestellt werden, daß das System Jonah bei der Entwicklung nichtdeterministischer Kalküle auf Basis von lambda-Kalkülen eine sehr gute Hilfestellung sein kann, auch wenn es nicht zum vollständigen Beweis der Gültigkeit von Reduktionsdiagrammen dienen kann.
In Abschnitt 4.1 wurden Algebren auf Mengen und Relationen vorgestellt. Desweitern wurde in Abschnitt 4.2 eine zu ALC erweiterte terminologische Wissensrepräsentationssprache ALCX definiert und gezeigt, daß die in Abschnitt 4.1 vorgestellten Algebren zur Festlegung der odell-theoretischen Semantik der Sprache ALCX benutzt werden können. Als Ergebnis einer derartigen Festlegung kann jeder terminologische Ausdruck direkt mit einem algebraischen Term assoziiert werden. Desweitern können alle in den Algebren aufgeführten universellen Identitäten in semantisch äquivalente terminologische Identitäten überführt werden. Eine mittels ALCX repräsentierte Wissensbasis ist in meinem Programm mit Hilfe der in der funktionalen Programmiersprache Gofer (Version 2.28) gegebenen Möglichkeiten formuliert. Mein Programm bietet durch Simplifizierung von Anfrageausdrücken eine optimierte Lösung des aus dem Bereich der Wissensrepräsentation bekannten Retrieval-Problems. Die Simplifizierung von Anfrageausdrücken wird in meinem Programm erzielt, indem in den oben genannten Algebren erfüllte universelle Identitäten als Simplifikationshilfsmittel benutzt werden. Die in den Algebren aufgeführten universellen Identitäten bestehen stets aus zwei äquivalenten Termen, für die eine unterschiedliche Anzahl von Reduktionsschritten zur Evaluierung benötigt werden. Es existieren universelle Identitäten, bei denen unabhängig von den Instanzen der Argumentterme ein Term gegenüber einem anderen Term effizienter auswertbar ist. Bei diesen universellen Identitäten kann eine Simplifikation von einem Term zu einem anderen Term immer unproblematisch realisiert werden. Es gibt jedoch auch universelle Identitäten, bei denen die Unabhängigkeit von den Instanzen der Argumentterme nicht gegeben ist. In diesen Fällen wird ein von der Wissensbasis abhängiges Komplexitätsabschätzungsverfahren eingesetzt, um den effizienter auswertbaren Term von zwei an einer universellen Identität beteiligten Termen zu ermitteln. Daß die Simplifikation eines Anfrageausdrucks große Einsparungen bei dessen Auswertung nach sich ziehen kann, wurde an verschiedenen Beispielen in Abschnitt 5.4.4 gezeigt. Über eine weitere Möglichkeit, die zum Simplifizieren von Anfrageausdrucken verwendet werden kann, wurde in Abschnitt 5.4.5 berichtet. Die Genauigkeit der Komplexitätsabschätzung kann erhöht werden, indem das Komplexitätsabschätzungsverfahren erweitert wird. So kann beispielsweise die Komplexität der Funktion "oder" genauer abgeschätzt werden, indem für zu vereinigende Mengen überprüft wird, ob Teilmengenbeziehungen vorhanden sind. Durch eine genauere Abschätzung der Mächtigkeit entstehender Vereinigungsmengen wird die Komplexitätsabschätzung insgesamt in ihrer Genauigkeit gesteigert. Eine Änderung der Instanzen meiner terminologischen Datenbank erfordert eine Änderung des Skripts meines Programms. Indem die Instanzen-Daten in einer veränderlichen Datenbank festgehalten würden, könnte hier Abhilfe geschaffen werden. Dies könnte im Rahmen der Erstellung einer benutzterfreundlichen Ein- und Ausgabe-Schnittstelle realisiert werden.
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.
In dieser Diplomarbeit wurde zunächst eine Einführung in das Gebiet der Unifikationstheorie gegeben, um dann zum Teilgebiet des Kontextmatchings zu kommen. Dieses wurde in das Gesamtgebiet der Unifikation eingeordnet. In Anlehnung an [Schm2003] wurde die Komplexität einiger Einschränkungen des Kontextmatchings betrachtet. Insbesondere wurde ein Algorithmus zur Lösung linearer Kontextmatchingprobleme in polynomieller Zeit vorgestellt. Es folgte die Einführung des Transformationsalgorithmus aus [Schm2003] zur Lösung allgemeiner Kontextmatchingprobleme, wobei nach und nach verbesserte Transformationsregeln für einzelne spezielle Problemsituationen vorgestellt wurden. Über [Schm2003] hinausgehend wurden die Regeln Split: Korrespondierende Lochpfade und Konstantenelimination vorgestellt. Im Rahmen der Diplomarbeit wurden die genannten Algorithmen in der funktionalen Programmiersprache Haskell implementiert, wobei auf eine einfache Erweiterbarkeit um neue Transformationsregeln sowie alternative Heuristiken zur Auswahl der in einem Schritt anzuwendenden Transformationsregel geachtet wurde. Die Implementierung (und damit auch die in ihr implementierten Algorithmen) wurde mit Hilfe von zufällig erzeugten Termen auf ihre Leistungsfähigkeit getestet. Hauptaugenmerk lag dabei darauf, inwiefern sich Regeln, die über die Basisregeln aus Tabelle 3.4.1 hinausgehen, positiv auf die Anzahl der Transformationsschritte auswirken. Das Ergebnis ist beeindruckend: durch die Einführung komplexerer Transformationsregeln ließen sich in unseren Testfällen bis zu 87% der Transformationsschritte einsparen, im Durchschnitt immerhin noch 83%. Speziell komplexere Kontextmatchingprobleme mit einer größeren Anzahl an Kontextvariablen profitieren hiervon. Insbesondere die Erkennung korrespondierender Positionen in Verbindung mit der Regel Split führte zu erheblichen Verbesserungen. Die implementierten Algorithmen zur Erkennung korrespondierender Positionen stellen teilweise nur ein notwendiges Kriterium für die Existenz korrespondierender Löcher dar. Dies kann zu fehlerhaften Erkennungen solcher Positionen führen. Wie sich in unseren Tests zeigte, scheint das jedoch kein gravierendes Problem zu sein, da die entsprechenden Split- Transformationen ohnehin äußerst sparsam eingesetzt werden.
Wir haben ein Softwaresystem entwickelt, das in der Lage ist, Beschreibungen von Termersetzungssystemen höherer Ordnung, deren Reduktionsregeln auf einer strukturellen operationalen Semantik basieren, einzulesen und zu interpretieren. Das System ist dabei fähig, Reduktionskontexte für die Redexsuche zu benutzen, die entweder vom Benutzer definiert werden können oder automatisch anhand der strikten Positionen berechnet werden. Außerdem dürfen Kontexte und spezielle Definitionen für Term-Mengen, die wir Domains nennen, in den Reduktionsregeln verwendet werden. Mit dem resultierenden Reduktionssystem-Format können wir somit nicht nur den „lazy“ Lambda-Kalkül, den Call-by-Value Lambda-Kalkül und verwandte, um Konstruktoren und Fallunterscheidungen erweiterte Kalküle, wie die in Kapitel 4 vorgestellten Kernsprachen KFP und PCF, darstellen, sondern auch den (in Abschnitt 4.3 vorgestellten) Call-by-Need Lambda-Kalkül, welcher sich durch die Verwendung von Kontexten innerhalb der Regeln deutlich von den anderen Kalkülen abhebt. Allerdings hält sich der Call-by-Need Lambda-Kalkül damit nicht an das in Kapitel 5 vorgestellte GDSOS-Format, das u.a. sicherstellt, dass Bisimulation eine Kongruenz ist. Wir haben dabei in Abschnitt 5.3.3 bewiesen, dass sich ein GDSOS-Reduktionssystem in ein äquivalentes strukturiertes Auswertungssystem nach Howe übersetzen lässt. Unser System ist in der Lage, die GDSOS-Bedingungen zu prüfen und gibt eine Warnung aus, falls eine der nötigen Bedingungen nicht erfüllt ist (wobei aus dieser auch gleich der Grund des Verstoßes hervorgeht). Wie wir gesehen haben, ist unser System nicht nur befähigt, die einzelnen Reduktionsschritte für kleinere Bespiele ordnungsgemäß auszuführen, sondern es ist durchaus in der Lage, auch aufwendigere KFP-Ausdrücke, wie in unserem Quicksort- Beispiel, auszuwerten.
