Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5508
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.
URI: http://depositonce.tu-berlin.de/handle/11303/5915
http://dx.doi.org/10.14279/depositonce-5508
Issue Date: 1978
Date Available: 30-Sep-2016
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
Subject(s): semantics
n-graphs
LISP
Church-Rosser
Semantik
Graph-Grammatiken
Church-Rosser-Eigenschaften
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
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:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
padawitz_peter_1978.pdf40,94 MBAdobe PDFThumbnail
View/Open


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