SASL : Implementierung einer rein funktionalen Programmiersprache mit Lazy Evaluation

Abstract

Dieser Report beschreibt eine Implementierung von SASL in Lisp, die auf Variablenabstraktion und Kombinatorgraph-Reduktion beruht. Nach einer Einführung in SASL schildert ein Kapitel über Variablenabstraktion ausführlich, wie aus SASL-Programmen effektive Kombinatorausdrücke erzeugt werden, einschließlich der Behandlung von lokalen Definitionen, mehrzeiligen Funktionsdefinitionen mit Fallunterscheidung durch Patternmatching sowie von ZF-Mengennotation. Zur Auswertung der so erzeugten Kombinatorgraphen wird die konkrete Implementierung einer effizienten Reduktions-maschine vorgestellt.

This report presents an implementation of SASL in Lisp which uses abstraction of variables and reduction of combinator graphs. Following an introduction to SASL a section shows in detail how SASL programs can be translated into compact combinator graphs, with special emphasis on the methods used to deal with local definitions, function definitions that spread over several lines making use of pattern matching for case selection, and with ZF-set notation. The second part of the report gives a detailed account of the concrete implementation of an efficient algorithm for the reduction of combinator graphs.