Please use this identifier to cite or link to this item:
Main Title: Operationelle und funktionale Semantik von Σ-Graphen mit Anwendungen auf LISP
Author(s): Padawitz, Peter
Type: Research Paper
Language Code: de
Abstract: Previous studies of operational versus functional semantics of symbolic expressions mostly have been confined to treelike expressions and evaluation by "simplification" and substitution of recursive definitions for function symbols. In order to drop these restrictions we introduce Σ-graphs and Σ-grammars to represent expressions and evaluation rules, respectively. Functional semantics of Σ-graphs is defined as an extension of Scott's fixed point semantics of flow diagrams. We prove that derivations via a Σ-grammar P preserve the functional semantics of Σ-graphs if the underlying "semantic algebra" satisfies the equations given by P. To get an operational semantics of a Σ-graph G relative to a Σ-grammar P derivations of G via P must yield a unique normal form. Therefore sufficient conditions for a weak Church-Rosser property of Σ-grammars are formulated and proved for some classes of such grammars. Applying these results to the programming language LISP we show that the evaluation rules of a LISP interpreter are compatible with the semantics of LISP and weak Church-Rosser where garbage collection is included.
Issue Date: 1978
Date Available: 30-Sep-2016
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): semantics
Series: Bericht / Technische Universität Berlin, Fachbereich 20, Informatik
Series Number: 78,23
Notes: Dieser Bericht ist im Wortlaut identisch mit: Peter Padawitz, Church-Rosser-Eigenschaften von Graph-Grammatiken und Anwendungen auf die Semantik von LISP, Diplomarbeit 1978.
Appears in Collections:Fak. 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
padawitz_peter_1978.pdf40.94 MBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons