This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
(q)~z~...
• ..{q(f)
•..
I {q (f>) ; f > (f )} ...
T
• ..{q(q) }...
T
T •..
{f(f) }.. • • ..{q(f)
}...
T Satz
I und 2 gelten auch fur ALGOL
ALGOL
60-P-G sind nur u n w e s e n t l i c h
60-P-G.
Die Sprachen ALGOL
verschieden,
60-P und
wenn man sich auf Pro-
gramme ohne formale P r o z e d u r a n w e i s u n g e n
beschrMnkt.
liegt in der Methode wie man P r o z e d u r e n
f, die durch formale Prozedur-
anweisungen
(i) aufgerufen w~rden,
mit aktuellen Parametern
In ALGOL 60-P w e r d e n alle aktuellen P a r a m e t e r ~bergeben. ebenfalls
Der U n t e r s c h i e d
In ALGOL 60-P-G w e r d e n die aktuel!en P a r a m e t e r im Moment des Aufrufs ~bergeben,
meter neuer Art
~5 = begin real a; proc q(y);{y(q)};
Aufrufs (i)
proc f(x) ;{r := 2+r; x(f ) }; q (f)
T
end
als ob sie bereits
als der P r o z e d u r i d e n t i f i k a t o r
aktueller Parameter eines v o r a n g e g a n g e n e n
(3)
alter Art
w ~ h r e n d die aktue!len Para-
(2) so betrachtet w e r d e n k~nnen,
vorher ~ b e r g e b e n w o r d e n w~ren,
versorgt.
im Moment des Aufrufs
f als
(3) auftrat.
Beispiel:
[ (2) • . . { f < a > ( q )
}..
T
...{a := 2+a; q(f)}...
T Aus der Wirksamkeit der Parameter neuer Art r~hrt der
Satz 6: ALGOL 60-P-G ist modular;
es gibt ein effektives Verfahren,
das
jedes origina!e Programm in ein formal ~quivalentes modulares umwande!t.
Die Anwendung dieses Verfahrens
~
auf Programm 93 liefert
= beqin proc q(r) ; {proc f<~> (x) ; {f-(x) } ; q(f) ; f (r) }; q (q) end
Hier bekommt nur die Prozedur f einen formalen Begleitparameter Art. Der aktuelle Begleitparameter neuer Art yon f i s t wird im Rumpf von f
r durch f e r s e t z t . ~
f neuer
r. AnschlieSend
und ~w sind offensichtlich
formal ~quivalent.
Satz 7: Die in Satz 5 und 6 genannten Verfahren lassendie Eigenschaften einer Prozedur,
formal erreichbar bzw.
Dabei heiBt eine Prozedur ~ 9' in TE existiert, Rumpf einer rekursiv,
formal rekursiv zu sein, invariant.
in 9 formal erreichbar,
falls ein Programm
dessen innerster erzeugter Block modifizierter
(eventuell modifizierten)
falls Programme ~ ' ~ - - ~ "
Kopie von ~ ist. ~
in T~ existieren,
zeugte Bl6cke modif±zierte R~mpfe von Kopien von ~
heiBt formal
deren innerste er-
sind.
Erst die Einbettung yon ALGOL 60-P in die modulare Sprache ALGOL 60-P-G hat einen durchsichtigen Beweis fur die algorithmische Unl~sbarkeit des Makroprogrammproblems n~gt es n ~ l i c h ,
fHr ALGOL 60-P geliefert
[6] . Wegen Satz 2 ge-
in ALGOL 60-P-G Programme ohne Prozedurschachtelungen
zu betrachten. FHr die Teilsprache ALGOL 60-P-F yon ALGOL 60-P-G derjenigen Programme ohne Parameter alter Art gilt aufgrund des in Satz 6 genannten Verfah-
J0
rens
Satz 8: ALGOL 60-P-F ist modular,
den Makrogrammatiken von M.J.
Die ALGOL 60-P-F-Programme ohne Prozedurschachtelungen scher
k~nnen mitlFi-
[4] identifiziert werden. Deshalb sind das Problem der formal
korrekten ParameterSbergaben und das Makroproqrammproblem 60-P-F algorlthmisch
fSr ALGOL
l~sbar. Wei! die belden Sprachen ALGOL 60-P und
ALGOL 60-P-F Jeweils Randmengen yon ALGOL 60-P-G darstellen, wird ihr gegens~tzliches Verhalten verstMndlich.
5. Zur Imp!ementierun~ von ALGOL 60-P-G Nachteilig
fSr die Implementierung von ALGOL 60-P-G ist zun~chst, dab
bel sukzessivem Anwenden der Kopierregel die aktuellen Parameter unvorhersehbar umfangreich werden kOnnen
(siehe ~ ) ,
so daS sie nicht mehr
wie bei ALGOL 60-P in jeweils elner Zelle Platz finden.
Selbst wenn
ganze AusdrScke wie in ALGOL 60 oder Anwelsungen wie in ALGOL 68 als aktuelle Parameter zugelassen sind, kann man sich auf ALGOL 60-P zurSckzlehen,
indem man "dicke" aktuelle Parameter zu RSmpfen parameter-
loser Prozeduren macht und die Parameter selbst durch die zugeh~rigen Prozeduridentifikatoren nicht weiter.
ersetzt.
Dieser Weg fShrt bei ALGOL 60-P-G
Bei geeigneter Verweistechnik
im Laufzeitkel!er
[I] kann
man aber auch hier alle aktuellen Parameter in jeweils einer Zelle unterbringen. GewShnliche und formale Prozeduranweisungen f(al,.--,a n) bzw.
x(a I,.., san )
seien auf folgende Weise in Maschinencode 8bersetzt: UNT
Gew Proz Anw
bzw.
UNT
x
f
(aI ,
a);
b i'
n
R:
m
an) ;
R~
Form Proz Anw
11
Das Laufzeitunterprogramm 60-P.
In den Speicher
Gew Proz Anw arbeitet ~hnlich wie bei ALGOL
for die neue Inkarnatlon
If von f wird der Reihe
nach eingetragen: !. Der Identifikator statisches Niveau,
f als Repr~sentant
f~r n6tige Merkmale von f wie
statischer Vorg~nger,
Startadresse,
Parameterzahlen
mf und nf, Festspeicherl~nge; 2. die R~ckkehradresse
R;
3. das dynamische
Niveau
~V des dynamischen
4. das dynamische
Niveau
~S des statischen Vorg~ngers
Iv geh~rlgen
statischen Verweiskette
Vorg~ngers
Iv yon If; yon f in der zu
KIv;
5. f~r jeden aktuellen Parameter b i wird eingetragen: a. b i gekoppelt mit dem dynamlschen Prozedur
b. der Inhalt ~er zu b i geh6rigen formaler
Niveau
in K I , falls b i gew~hnllcher Identlflkator
c. die Anfangsadresse
~i der zu b i geh~rigen
Identifikator
Speicherzelle
ist;
in KIv, falls b i
ist; B i von b i gekoppelt mit ~ f a l l s
b i echter Term
ist; 6. mit a i wird wie in 5. verfahren. Das Unterprogramm
Form Proz Anw arbeitet
O. Der Inhalt C ~ ~S der zu x geh~rigen holt. a. C ist Prozeduridentifikator
so:
Speicherzelle
in KIv wird ge-
f. Es folgen die Schritte
1.-4.,6. wie
oben. b. C ist Anfangsadresse
eines echten Terms
C: f
bm> im Hauptteil nach:
der zu ~
geh~rigen Prozedur.
S
Eingetragen
w i ~ der Reihe
1.-3. Wie oben; 4. das dynamische ~S geh~rigen 5. wie oben mit
Niveau
~
des statischen Vorg~ngers
statischen Verweiskette
von f in der zu
K6S;
K6S statt KIv und $S statt ~V;
6. genau wle oben. Die implementierung
der vera!igemeinerten
Sprache
ist also kaum schwie-
riger als die yon ALGOL 60. Hinzu ko~mt, daS Satz 6 einen klaren effektiven Weg bietet,
Prozedurgebirge
vieler Index- oder Displayregister
abzutraqen,
um das Fehlen gen~gend
auszugleichen.
12
Literatur
[I]
Bauer,
F.L., Goos, G.:
Berlin - Heidelberg [2]
Boebert,
W.E.:
Programming: nett. [3]
[4]
Syst.
Ed.: F.L.
Springer
1973.
Fischer,
M.J.:
Ling.
Bauer.
and Autom.
H.: On Correct Procedure
Math.
Wijngaarden,
Languages.
u. Informatik,
Productions.
Report No.
Harvard Univ.,
Parameter T r a n s m i s s i o n
Acta Informatica
2, 110-142
as Open Subroutines. Univ.
d. Saarlandes,
in (1973).
Fachbereich Bericht A 73/04
in Acta Informatica.
A. van, Mailloux,
Report on the Algorithmic
Anschrift
and
- New York:
May 1968.
H.: On Procedures
(1973); erscheint
1968.
in Economics
Translation,
Langmaack,
79 - 218
and Systems Press
Lecture Notes
Mass.
Langmaack,
In: Modular
Ed.: T.O. Bar-
In: A d v a n c e d Course on Software
Cambridge,
Angew.
[7]
Information
System.
Symposium.
Grammars with Macro-like
Higher Programming [6]
1971.
81, 128 - 182, Berlin - Heidelberg
NSF - 22, Math.
[5]
Mass.:
of a National
J.B.: Modularity.
Engineering. Math.
Zweiter Tell.
Springer
Toward a Modular Programminq
Proceedings
Cambridge,
Dennis,
In~ormatik,
- New York:
B.J., Peck, J.E.L.,
Koster,
Language ALGOL 68. Num. Math.
C.H.A.:
14,
(1969).
des Verfassers:
Prof. Dr. Hans Langmaack,
wandte M a t h e m a t i k
und Informatik
der Universit~t
D-66 Saarbrflcken,
Bundesrepub!ik
Deutschland.
Fachbereich
des Saarlandes,
Ange-
ENTSCHEIDBARKEITSPROBLEME
BEI DER OBERSETZUNG VON
PROGR2hMMEN MIT EINPARAMETRIGEN PROZEDUREN
W_~. Lippe
I. Einleitung und Problemstellun ~ Um effiziente Zielprogramme bei der Obersetzung yon Programmen ALGOL~hnlicher Programmiersprachen mit Prozeduren zu erzeugen, folgende Fragen berelts zur ~bersetzungszeit
sollte man
algorithmisch beantworten
k~nnen: i) Hat ein Programm formal korrekte Parameter~bergaben? 2) Ist eine Prozedur formal erreichbar? 3) Ist eine Prozedur formal rekursiv? 4) Ist eine Prozedur stark rekursiv? 5) Hat ein Proqramm die Makro-Programm-Eiqenschaft? F~r ALGOL 60-P sind die Eigenschaften
i)-5) unentscheidbar,
5) f~r ALGOL 60-68, obwohl nur Identifikatoren
ebenso 2)-
als aktuelle Parameter
zugelassen sind [4,5]. Zum Beweis der Unentscheidbarkeit
der formalen Erreichbarkeit von Pro-
zeduren wird in [4] f~r jedes Postsche Korrespondenzsystem L
ein Pro-
gramm ~r mit einer Prozedur ~ 4 effektiv konstruiert,
so dab
dann eine L6sung hat, wenn ~
ist. Es f~llt auf,
in ~r formal erreichbar
dab in n~ nur solche Prozeduranwelsungen nen
ao(al,...,an)
~
genau
auftreten, bei de-
alle formalen Identifikatoren a i paarweise verschieden sind.
Wit nennen nun ein Programm monadisch, wenn f~r die formalen Identifikatoren ai,a j in jeder Prozeduranweisung
ao(al,...,an)
a i = aj ist~
Damit stoSen wir auf die Vermutun@
i: F~r monadische ALGOL 60-P Programn~ist entscheidbar,
ob
eine Prozedur formal errelehbar ist. Diese Vermutung ist dem bekannten Satz von L~wenheim und Skolem
[~]ana-
14
log, welcher besagt, da~ der Pr~dikatenkalk0l
erster Stufe mit nur mo-
nadischen Pr~dikaten entscheidbar ist. Die von Church bewiesene Unentscheidbarkeit des vollen Pr~dikatenkalk01s Unentscheidbarkeit
ALGOL 60-P-Programmen.
Die formalen Identifikatoren entsprechen ge-
wissermaSen den Individuenvariablen, Identifikatoren
erster Stufe entspricht der
der Erreichbarkeit von Prozeduren in generellen
die zusammengefaSten gew~hnlichen
in einer Prozeduranweisung
entsprechen einer Pr~dika-
tenvariablen. Durch ganz ~hnliche Argumentation kommt man zu der
Vermutung
2: FUr ALGOL 60-68-Programme mit endlichen Arten ist entscheidbar,
ob eine Prozedur formal erreichbar ist.
Bislang ist es nicht gelungen, beweisen.
die beiden Vermutungen vollst~ndig zu
FUr Programme, die der Einschr~nkung A unterliegen,
sind die
Vermutungen jedoch richtig, wie wir zeigen werden. Einschr~nkung A: Nur einparametrige Prozeduren und Prozedurschachtelungstiefen ~2 sind zugelassen.
15 2. U berfuhrung in die sprache ALGOL 60-P-G Um die Beweise zu vereinfachen, machen wir ferner die unerhebliche Einschr~nkung, dab es neben Prozedurdeklarationen tionen und neben einparametrigen
keine weiteren Deklara-
Prozeduranweisungen
keine weiteren An-
weisungen geben soll. Programme mit diesen Einschr~nkungen besitzen die allgemeine Form: begin
proc gl(Xl);
{ ~
fll(Yll); :
{ ...... }; Hauptteil yon fll
proc flm I (Ylm I) ; { ..... }; I
Hauptteil von gl
}; proc g2 (x2) ; {proc f21(Y21);
( ..... };
proc f2m 2(y2m2) ; { ..... }; .
}; proc gn(Xn) ; {proc fnl(Ynl);
{ ..... };
®
rp-r-g-qfnm n(ynm n) ; { ..... };
}; • gi(gi ,) ; •
~
Hauptteil des Hauptprogramms (I ~
i,
i'
~ n)
end Es ist klar, dab jedes originale Programm dieser Bauart formal korrekte Parameter~bergaben hat. Betrachten wit nun alle m~glichen Arten von Prozeduranweisungen eines solchen Programms. a) Im Hauptteil des Hauptprogramms k6nnen nur Anweisungen gi(gi ,) stehen (I ~ i,i' ~ n). b) Im Hauptteil der Prozedur gi(i lest) sind folgende Arten von Prozeduranweisungen m~glich: (I ~ i,i' S n;l ~ j,j' ~ m i)
16
c)
gi' (gi '')
fij (gi ")
xi (gi '')
gi' (fij ')
fij (fij ')
xi (fij ~)
gi' (xi)
fij (xi)
xi (xi)
Im Hauptteil der Prozedur fij (i,j fest) sind folgende Arten yon Prozeduranweisungen m~glich: (i ~ i,i', i" < n; 1 _< j,j', j" _< m i) gi' (gi ")
fij' (gi '')
xi (gi ")
Yij (gi '')
gi' (fi9 ")
fij' (fij ")
xi(fij")
Yij (fij ")
gi' (xi)
fij' ( x i )
xi(xi)
Yij (xi)
gi' (Yij)
fij' (Yij)
xi (Ylj)
Yij (Yij)
Um die st6renden Prozedurschachtelungen zu eliminieren, formen wir unser ALGOL 60-P-Programm in ein formal ~quivalentes ALGOL 60-P-G-Pro gramm ohne Prozedurschachtelung um. Es gilt n~mlich folgender Satz: Satz I:
Jedes ALGOL 60-P-Programm kann effektiv in ein formal ~quivalentes ALGOL 60-P-G-Programm ohne Prozedurschachtelung transformiert werden.
F~r die genaue Definition von ALGOL 60-P-G und den Beweis des Satzes siehe [5]. Die allgemeine Form der betrachteten Programme ergibt sich nach der Transformation in ALGOL 60-P-G zu: begin proq gl (Xl) ; { . . . . . }; Haup~teil von gl proc g2(x2) ; { . . . . . };
proc gn(Xn) ; { ..... }; proq fll<Xl>(Yll ) ; { ..... }; • Hauptteil von fll proc flml<Xl>(Ylml);{ ..... }; rp_r~ f21<x2 > (Y21) ;{ ..... };
pr0c f2m2<X2 >(y2m2 ) ; { ..... };
17
proc fnl < Xn>
(Ynl) ; { ..... } ;
proc fnm 2 <Xnb (Ynm n) ;{ ..... }; A I
Hauptteil des [I Hauptprogramms
gi °(gi') ; end
Die entsprechenden Prozeduranweisungen im ALGOL 60-P-G-Programm lauten: a) Im Hauptteil des Hauptprogramms (i ~ i,i' ~ n) : gi(gi ,) b) Im Hauptteil yon gi(i fest; 1 S i,i',i" S n; 1 ~ j,j' S mi) : gi~(gi,,)
fij<xi>(gi,,)
xi(gi,,)
gi, (fij,<xi >) fij<xi>(fijt<xi>)
xi(fij,<xi>)
gi,(xi )
x i (xi)
fij<xi > (x i)
c) Im Hauptteil von fij(i,j fest; 1 _< i,i,i" _< n; 1 < j,j',j" <_ mi) : gi'(gi '')
fij '<xi> (gi I~)
xi (gi ")
Yij (gi ")
gi' (fij"<xi >) fij'<xi>(fij"<xi>)
xi(fiJ"<xi>)
Yij (fij"<xi >)
gi' (xi)
fij '<xi> (xi)
xi (xl)
Yij (xi)
gi' (Yij)
fij '<xi> (Yij)
xi (Yij)
Yij (Yij)
Bei allen Prozeduranweisungen ~(8),die in Programmen~' des Ausf~hrungsbaums T H eines ALGOL 60-P-G-Programms ~ auftreten k~nnen, haben jetzt die Terme a und 8 offenbar die Gestalt: a = fikJk < fik_lJk_l < ... < f i l J l < g i > > °..>>; 8 = fi'k'J'k'
...>
k >~ O, ...>>
; k' >~ O.
Satz 2: F~r al!e Prozeduranweisungen e(B) gilt, dab der unmittelbare Teilterm u.T. des k~rzeren Terms Teilterm des l~ngeren Terms ist. Die Anweisungen e(8) lassen sich somit in Form eines Speicherbandes mit zwei Zustandsk6pfen veranschaulichen, wobei sich mindestens ein Zustandskopf immer am oberen Ende des Speicherbandes befindet. Die Bandinschrift ist hierbei der u.T. des l~ngeren Terms von a und 8.
18
Im linken Zustandskopf befindet sich das Anfangssymbol Zustandskopf das Anfangssymbol
von ~ ,im rechten
von 8 ;z.B. :
rechter Zustandskopf
• fik-lJk-l~''
I linker
ifi'k'J'k' •
Zustandskopf
3.Monadische Programme Wir untersuchen jetzt die monadischen Programme, d.h. solche mit der
Einschr~nkung
B: Bei allen Prozeduranweisungen
s(8) gilt, dab ~ = 8
ist, falls s und 8 formal sind. Diese Forderung bewirkt, dab im Hauptteil von fij(i,j fest) Prozeduranweisungen der Arten xi(Yij) und Yij(xi) nicht erlaubt sind. Mit dieset Einschr~nkung l~Bt sich f~r die Prozeduranweisungen in T n folgender Satz zeigen: Satz 3: FUr alle Prozeduranweisungen ~I
= 1
oder
~Bl = 1
s(8) gilt:
oder
ll~
- ~B~
~ I.
Dies bedeutet, daS fur die Stellung der beiden ZustandskSpfe Band nur folgende Konfigurationen
1....
I
-- -
I~
oder
auf dem
erlaubt sind:
1
I
t
1 ,-o
oder
t fi
I__ .....
{
I ''"
I~ I oder
~
1., •
I~ 1
A
oder
19
oder Ifi'k, J'k,l
Da folgl~h
keine
tigt wird,
liegt es nahe,
Information
fij in ~ Uber regul~re Definition: R =
aus dem Innern des Speicherbandes
die Erreichbarkelt
kanonische
Ein regul~res
Systeme
kanonisches
einer Prozedur
ben~-
gi oder
zu entscheiden.
System
ist ein 4-tupel
( ~ , % , S, ~) mit (i) ~
ist eine endliche,
nicht
leere Menge
( nicht termi-
hale Symbole). (ii) ~ ist eine endliche, nicht Syr~bole) mit ~ n ~ = ~ . (iil)
Sc%~ tionen
} fur
binare
(x,y) &
eines regul~ren
gung von Worten ergibt Definition:
Zu unserem
kanonischen
F~r x,y ~ %~,
~ , ~ e ~[
es existiert
Xl,X2,Yl£~ ~
Sei
Programm
Relation
~ schreiben
sich aus folgender
E konstruleren
auf
~
(Produk-
wir x--~ y)
Systems,
d.h.
die Erzeu-
Definition:
gilt x ~ ------>y u
x2~--~ Yl ~ Mit ~----> bezeichnen wir die transitive
nisches
(terminale
(Startworte).
(iv) ~ ist eine end!iche
Die Arbeitsweise
leere Menge
:
, so dab x = XlX2, y = xlY 1 und reflexive
H~lle von-----~ .
wir nun folgendes
regul~res
kano-
System
~:=
{gi }' 1 S
Die terminalen % := {0,g,f}
i S n, und
Symbole
mit g ~ ~
(fij},
1 ~ i ~ n, i ~ j ~ m i-
kanonischen
Systems
und f £ ~ . Die nicht terminalen
~[ := {(g,u,9,u),(g,u,9,u,L) (f,O,f,u)}
~=
des regul~ren
sind
Symbole
sind
, (g,u,f,O) , (f,O,g,u) , (f,O,f,O) ,(f,u,f,O) ,
mit g,~ 6 ~
;f,{£ ~
und u,O,L ~ ~ u %
drei verschie-
dene Symbole. FUr jede Anweisung wort @
(gi,u,gi,,u)
F~r jede Anweisung
gi(gi,)
des Hauptprogramms
wird genau ein Start-
konstruiert. im Rumpf yon gi werden genau zwei Produktionen
20
konstruiert.
Anweisung~
(gi~u,f,O)
(gi,u,g ,U)
~ (gi' 'u'gi"'U)
gi ' (gi" )
~ (gi''u'gi"'u'L)
gi' (fij '<Xi>)
~--g(gi''u'fij' ,O)
~ ~f (gi' 'u' fij 'O)
gi ' (Xi)
Z~
Z~
(gi''U'g'U)
fij <Xi > (gi")
"g (fij ,O,g~. ,U)
fij<Xi > (fij '<Xi>)
~g (fij 'O' fij ' ,0)
(gi' ,u,f,O)
4~~f (fij 'O'gi" ,u) "f (fij ,O, fij' ,O)
fij<Xi > (Xi)
g~g (fij ,O,g,u)
4~-f (fij ,O, f,u)
Xi (gi" )
Z-- (g,u,gi, ,,O)
~-- (f,O,gi.,u)
Xi (fie '<xi> )
Z~g (g,u, fij , ,0)
~--f(f,u,fij, ,0)
x i (xi)
@~ (g,u,g,u)
~-- (f,O, f,O)
FOr jede Anweisung im Rumpf von fij wird ebenfalls eine endliche Menge yon Produktionen konstrulert(s. Tafel I). Hierbei durchlaufen f,f ~,g ~und y ~u~.In der Matrix stehen die einzelnen Produktionen, wobei das nicht terminale Symbol der linken Seite sich am Kopf jeder Spalte befindet. Hinzu treten noch die Produktionen y (~,u,~,u,L) -- (~,u,~,u,L) @(~,u,~,u,L)
-~ @ ( ~ , u , ~ , u )
mit ~,g ~ ~.
~an kann nun zeigen: Satz 4: Eine Prozedur p in ~ ist genau dann formal erreichbar, falls es ein Startwort s, ein terminales Wort £ und ein nicht terminales Symbol (p,v,y,w) mit v,w 6 {u,Q}ly ~ ~ gibt mit s ~---> t(p,v,y,v). Da letzteres jedoch entschieden werden kann [l]j gilt der Satz 5: Es ist entscheidbar, ob eine Prozedur in einem ALGOL-60-PProgramm mit den Einschr~nkungen A und B formal erreichbar ist.
YiJ (Yij)
Yij (gi") Yij (fij"<xi>)
x i (xi)
xi (fij"<xi>)
xi (gi" )
fij'<xi> (Yij)
fij '<xi> (xi)
gi' (Yij) flj '<xi> (gi") fij '<xi> (fij"<xi >)
(~,O,gi..,u) (~,u,gi. ,u) (y,u, fij . ,O)
(fij' ,O,g,u)
(fij''O'y'u)
(g,utfi9.,O) (g,u,g,u,L)
(g,u,gi. ,u,L)
If 41-" (~,o,K,o) (~,u,~,u)
y~"
(fij' 'O'gi"'u) (fij' 'O' fij" 'O)
(gi' ,u,{,O) (gi' tu,g,u) (gi''u'g'u'L)
(gi''u'gi"'u'L) (gi' 'u'fij"'O)
gi' (gi'') gi' (fij"<xi>)
gi ' (xi)
(fij ,O,g,u)
Anwe i s u n g ~
(fij ,O,f,O)
(fij ,U, f,O)
-M-~ (f,O,gi. ,U) ~-~ (f,O,fij. ,0) ~-- (f,O,f,O)
f~-- (f,O,gi.,U) ~ (f,u,fij.,O) {~-- (f,O,f,O)
(Tafel I)
~ - ({,o,{,o) T~" (~,u,~,u)
~ . ({,o,gi.,u) g~'~ (~,u,gl.,U) y11"~y(Y,U, fij " ,O)
£n - ({,o,{,o)
f~-~f(f,u, fij . ,O)
{~- (~,o,~i,,,u)
(f,O,gi. ,U)
(~,u,~,u)
(~,u,gi..,U) (y,u,fij .,O) (f,O,f,O)
-- (f,O,fij.,U) ~M'~ (f,O,f,O)
g{ ~~f~" ff-~ ~~-~
"J~{- (~,o,g±.,u)
(fij''u'f'O)
(fij.,O,fij..,O) (fij . 'O'y'u)
(fij''O'gi"'u)
~1-" (gi' ,u,f,O)
~'~ (gi' ,u,f,O)
~'~ (fij' 'O'gi"'u) ~q'~ (fij' 'O'gi"'u) ] { ~ ~-- (fij' 'O'fij"'O) 41~- (fij.,O,flj.,O 1 {~ y~'~y(fij. ,O,y,u)IYf~Y f~'f(fij' ,O,f,u) ~'~ (fij''O'f'O) 1 ~I ~-- (flJ''O'f'u)
~-~ (gi''u'f'O)
~f~- (gi,,u,~,u)
-~" (gi' ,u,~,u)
"~ (gi' 'u'gi"'u'L) (gi' 'U'gi"'u'L) ~" (gi' 'u'gi"'u'L) 4~'~ (gi' 'u'fij"'O) ~'~ (gi' 'u'fij"'O) {~-" (gi' 'u'fij' ,O) ~ff~'~ (gi' ,U, ~',o) £'~" (gi' ,U,{,O) f-~-~ (gi' ,U,f,O) fl"
(fij ,O,f,u)
22
4o Programme mit endlichen Arten Im folgenden b e s c h M f t i g e n wir uns an Stelle von ALGOL 60-68 bzw.
60-P mit ALGOL-
ALGOL 60-68-G mit der
Einschr~nkung
C: Alle Identifikatoren von ALGOL
Algorithmen,
besitzen
endliche Arten
im Sinne
68.
die diese E i n s c h r ~ n k u n g
abpr~fen,
werden
in [3] und
[6]
behandelt. Die Annahmen scharf.
am Anfang von 2. zur B e w e i s v e r e i n f a c h u n g
Wir b r a u c h e n
sie aber nur so wenig zu lockern,
gramm von H genau eine weitere D e k l a r a t i o n wir nur e i n p a r a m e t r i g e proc
Bind hier zu
Prozeduren
dab im Hauptpro-
real d zugelassen
zulassen,
ist. Da
haben alle Arten die Form
(proc(... (proc(real))...)).
k--
J ~
n-mal / n Z O Mit der E i n s c h r ~ n k u n g und Yij(Yij)
C schiieBen wir alle A n w e i s u n g e n
aus, da sie nur bei unendlichen
und Ylj auftreten k6nnen. und Yij(xi) bewirken.
erlaubt,
Dagegen
beiden Zustandsk~pfe
die ein A u s e i n a n d e r l a u f e n
enth~it die A n w e i s u n g e n
sungen aus K 2 zur A n w e n d u n g
xi(Yij),
gelangen,
Die Konsequenz
sung der Art xi(Yij) z.B.
K1
Yij(xi) , fij,<xi>(Yij) ,
gilt Satz aus Satz
Solange nur Anwei-
3. Selbst durch Anwei3 nicht unbedin~t
kann nur dann verletzt werden, oder Yij(xi)
C die
ff in zwei Klassen ein:
K 2 enth~lt die ~brigen Anweisungen.
sungen aus K1 werden die K o n s e q u e n z e n letzt.
der beiden Zustandsk~pfe
auf dem Band bewegen kSnnen.
eines Programms
der Arten
von x i
der Arten xi(Yij)
dab wegen der E i n s c h r ~ n k u n g
sich nicht beliebig
Wir teilen die A n w e i s u n g e n
Yij(fij.,<xi>);
DeklaratorbMumen
slnd nun A n w e i s u n q e n
Es l~Bt sich jedoch zeigen,
der Arten xi(x i)
auf ~(~) mit
l~I =
ver-
wenn eine Anwei181 - I folgt
23
Weitere sinken Stets
Anweisungen jediglich
aus K1 verMndern
herunter,
aber resultiert
ist eine Folgerung aus K2 erfolgt, oberen Kopfes fortgefahren Diese
sie ihre Positionen 181 - 1 ~ Max
aus der Einschr~nkung
gilt wiederum
Satz
C. Sobald
3, wobei
nicht,
die K6pfe
tauschen
k~nnen.
(I~'l,18'I)
s 18 I- Dies
nun eine Anweisung
entweder
oder an der Stelle des mittleren
an der Stelle des
Kopfes
oder
"ganz unten"
wird.
anschauliche
Verhaltensweise
keit einer Prozedur Definition:
wobei
s'(8') mit
den Kellerinhalt
dutch
Stack-Systeme
Ein Stack-System (i) ~
legt es nahe,
Erreichbar-
zu entscheiden.
ist ein 4-tupel
ist eine endliche
die formale
S =
( ~ , @ ,S,~) mit
nicht
leere Menge
(nicht terminale
nicht
leere Menge
(terminale
Symbole), (ii) ~ ist eine endliche mit
~ n~ = ~
(iii) S c ~
(Startworte).
(iv) ~ ist eine endliche Formen
Menge von Produktionsregeln
(mit S,S' e~%
i) OAS
--->
; A,B {9;
2) QAS -->
OAS' 0S'
4) QASQ 2 --->
Ol AS'Q2
5) QIASQ2--~
OIS'AO 2
6) QIASBQ2-->
OlABS'Q 2
~Tie bei den regul~ren
kanonischen
Systemen
weise eines
Stack-Systems
mit
Definition:
Wir schreiben
wy~bwy':
eine Produktion ~
falls w,w' ~ ~ ,
wir wieder
Satz 9: Eine Prozedur
falls w 6 ~
Symbol
,Y,Y'6 %']q und in
Y,Y' 6 ~ % ~
Stack-System
~
s~ ein terminales
(p,v,y,w)
(p,v,ytw).
wir die Arbeits-
wir schreiben
~vw ~ w y w
und in ~ eine Produk-
reflexive
mit v,w
H~lle yon ~
konstruieren
p in K ist genau dann formal
in ~ ein Startwort
~iber
existiert.
die transitive
Wie in 2. l~Bt sich zu K ein genschaft
so dab s ~ > t
~
erkl~ren
~y--> Qy' existiert,
tion QIYQ2---~ olY'02 Mit ~-~> bezeichnen
der
Oi,Ql,O 2 Variablen
QABS'
3) QAS --->
minales
Symbole)
.
mit der Ei-
erreichbar,
falls es
Wort t und ein nicht
{u,O} und y £ ~ ~ u { d } g i b t ,
ter-
24
Da letzteres entschieden werden kann
Satz i0: Es ist entscheidbar,
[2] gilt
ob eine Prozedur in einem ALGOL 60-68-
Programm mit den Einschr~nkungen A und C formal erreichbar ist.
Literatur:
[1]
Bichi, J.R.: Regular canonical systems Arch. Math. Logik Grundlagenforschung
[2]
Ginsburg,
S., Greibach S.A.and Harrison, M.A.
Stack automata and compiling,
[3]
Koster, C.H.A.: Feb.
[4]
14(1961),
J. ACM 14,1
143-172
:
(Jan.
1967), 172-201
On infinite modes, ALGOL Bulletin AB 30.3.3,
1969, pp. 61-69
Langmaack,
H.: On correct procedure parameter transmission in
higher programming languages, Acta Informatica, Vol.
[s]
Langmaack, A 73/04,
H.: On procedures
as open subroutines,
2,1973
Bericht
Institut f~r Angew. Math. und Informatik der Univ.
des Saarlandes
[6]
Zosel, M.
: A formal grammar for the representation of modes
and it's application to ALGOL 68, Dissertation Washington,
[7]
Hilbert, D. Ackermann,
W.: Grundz~ge der theoretischen Logik
Springer Verlag 1972
Anschrift des Verfassers: Dipl.-Inform. Fachbereich
Wolfram Lippe
i0
Angewandte Mathematik und Informatik der Universit~t des Saarlandes 66 Saarbr~cken Im Stadtwald
1971, Univ. of
Bericht Nr. TR 71-10-O7
EINE
AXIOMATISCHE VON
STUDIE
ZUR
IDENTIFIKATION
IDENTIFIKATOREN KrUger
F.
1... E i n l e i t u n ~ Die i n P r o g r a m m i e r s p r a c h e n tifikator tion
mehrfach zu v e r e i n b a r e n ,
eines
(in
definierenden
der T e r m i n o l o g i e
Die v o r l i e g e n d e fikation.
Arbeit
gibt ist
es d a b e i ,
zu l a s s e n und m ~ g l i c h s t
intuitive
Betrachtung
einunddenselben
Iden-
das Problem der " I d e n t i f i k a -
durch
e i n angewandtes A u f t r e t e n " solchen
eine axiomatische
gew~hlte A x i o m a t i s i e r u n g
wir eine
schafft
Auftretens
von ALGOL 68) e i n e s
Unser Z i e ]
vortreten Um d i e
vorhandene M S g l i c h k e i t ,
Beschreibung
die n~tigen
allgemein
zu e r l ~ u t e r n
Identifikators. der I d e n t i -
Grundbegriffe
klar
her-
zu f a s s e n . und zu m o t i v i e r e n ,
m i t den z u g r u n d e g e l e g t e n
wollen
Abstraktionen
voranstellen. Der i n t u i t i v e
Sprachgebrauch
ten des I d e n t i f i k a t o r s real
x" - l e g t
x
bereits
ist
finierenden
ein
und einem B e r e i c h sein.
schlie~lich
schen B e r e i c h e n .
partielle Ordnung
Weiter
Deklarationen Grundbegriff
der P r a x i s
mit
einem de-
Zwischen e i n e r Relation
desselben eine
p
Stelle
erfUllt
Identifikators
Relation
y
zwi-
angemessen, d i e s e R e l a t i o n
und aus b e s c h r e i b u n g s t e c h n i s c h e n
soll s
die
Relation
eine Stelle
p
m i t der Ordnung
und s i n d
S P bl A bl X b2 => Der
nahe : M i t einem
GrUnden a l s
als
irre-
vorauszusetzen.
flexiv
also
als vierten
der D e k l a r a t i o n
dieses Auftretens,
verknUpft.
(Enthaltenseins-)
mehrerer
Es s c h e i n t
Grundbegriffe
Stelle
Bereieh
kann e i n e
Die M ~ g l i c h k e i t
verlangt
die
"das angewandte A u f t r e -
im G U l t i g k e i t s b e r e i c h
d i e Wahl d r e i e r
angewandten A u f t r e t e n Auftreten
- etwa d i e Phrase
liegt
Vorgang
der
Identifikation
bl
und
b2
X
vertr~glich
Bereiche,
so s o l l
sein ; gelten
S p b2 . sucht
zu einem
angewandten
Auftreten
ist :
26
eines den
Identifikators "kleinsten"
x
unter
den B e r e i c h e n von D e k l a r a t i o n e n
b e z U g l i c h d e r Ordnung
2~..... Die a x i o m a t i s c h e
sollen
Definition
Bereichsystem
B
und
Definition
ist
Mengen, y B
und
dab g i l t
p
2 : Es s e i e n
X
(B,S,y,p)
e i n Quadrupel
eine irreflexive
X
D c X xB
Uber
und
(xl,bl)
Ord-
s p b A byb'
=> s p b'
S xB
sind,
Ac
Xx S .
in
D
und
= (x2,b2)
Identifikationssys-
Ein ist
e i n Paar
(D,A)
Ein Ele ment ( x , b )
Yon
Auftreten
und
Identifikatoren
(B,S,y,p)
angewandtes Auftreten Yon 3 : (Gleichheit
, wobei
auf
ein Bereichsystem.
fur
(B,S,y,p) partielle
eine Relation
e i n e Menge von
definierendes
Definition
werden:
:
Vs E S V b , b ' E B :
tem
y.
nun f o r m a l i s i e r t
S
nung a u f derart
(Ao)
x
Beschreibung
Diese V o r s t e l l u n g e n 1 : Ein
von
x ,
ein
C D
Element
mit heist
(x,s) E A
x .
A)
<=> x l
:
x2 A b l
= b2
:
x2
:
df (xl,s~)
:
(x2,s2)
<=>
xl
A
s~
s2
df Definition
4 : Es s e i
(D,A)
(B,S,y,p) = df
Lx,b
Definition
FUr
Identifikationssystem
(x,b)
{ b' ~ B :
b'
E D
heiBt
(D,A)
geeignet
~(y,s)EA~1(x,b)CD:
sei
fur
,
x =yAsp
fur
X
wenn g i l t
:
Uber
bA(b'CLx, b =>'~spb')
da~ es zu jedem angewandten A u f t r e t e n
tifikators
identifiziertes
Die I d e n t i f i k a t i o n
Uber
dann
Dieses Axiom f o r d e r t , genau e i n
X
Y b A (x,b ') ~ D},
5 : Ein I d e n t i f i k a t i o n s s y s t e m (B,S,y,p)
(At)
•
ein
definierendes
eines
Auftreten
. Iden-
gibt.
kann d a h e r b e s c h r i e b e n werden d u r c h e i n e F u n k t i o n
27
id
: A÷D
mit id(y,s) id
Das Axiom
(At)
und d i e l a e n t i f i k a t i o n s f u n k t i o n
fe der Zuordnung
L
von T e i ! m e n g e n
von I d e n t i f i k a t o r e n , (1)
.
M
B
(At)
Definfition
Daraus
und d e r
(D,A)
(B,S,y,p) = df
Mx's Die Formel
(I)
ist
lassen
.
zu d e f i n i e r e n d e n
mit
Hil-
Auftreten
~quivalent
zu
angeben, d i e
e i n e an-
a n g e w a n d t e n
~quivalente
Formulierungen
Identifikationssystem
(x,s)EA
{b & B :
Formel
des
ableiten.
ein
FUr
B
sich
Identifikation
6 : Es s e i
formuliert
spb'
von T e i l m e n g e n von
benUtzt.
sind
Formel
noch k u r z e i n e dazu ~ q u i v a l e n t e
dere Zuordnung Auftreten
von
genauer d u r c h d i e
b ' E L x , b => ~
Wir w o l l e n
sei
spb A ( x , b ) E
fur
X
Uber
dann D } .
mit
b ' E Mx, s => m b ' y b .
(2)
D i e s e Behauptung i s t b'EMx, s , folgt
b=>mspb')]
Identifikationsfunktion.
heist
Axioms
= ( x , b ) <=> I x = y A spb A ( b ' E L x , df
so i s t
dann
gekehrt
leicht spb'
b'E Lx, b ,
(2)
d e r Annahme
und i s t spb'
folgt
einzusehen.
und mit
Gilt
(x,b')ED, (i)
also
b'E Lx, b , dann
n~mlich
(I)
und i s t
und aus d e r Annahme der W i d e r s p r u c h
so i s t
b'yb
b ' E Mx, b , m i t
und (2)
b'xb
~spb' (x,b')ED,
also
Gilt
um-
und aus
der W i d e r s p r u c h
b'yb.
3.
Zwei B e i s p i e l e
Wir w o l l e n
i n diesem A b s c h n i t t
das e i n g e f U h r t e Identifikation Als
erstes
fur
die
zwei v e r s c h i e d e n e
A x i o m e n s y s t e m angeben, in verschiedenen
Beispiel
Identifikation
w~hlen w i r
Interpretationen
die zeigen,
fur
w i e das System d i e
Sprachen b e s c h r e i b t . ein
ben~tigten
beliebiges Begriffe
ALGOL 68-Programm, range
und
to c o n t a i n
Die
28
sind
i n der S p r a c h d e f i n i t i o n
tion
ist
gegeben durch
B = Menge d e r
hinreichend
in
(x,r)
~ D
E]]9~ mit plied) rl xr2
<=> r :
rl prz
<=> r~ y r 2
Als
zweites
Die I n t e r p r e t a -
E~Dg~§,
S=B,
contains v
Beispiel
i n einem
riables
formalisiert.
:
rl
,
rl
:
(x,r)
: r ~Qg~§]]]
occurrence
~ A
sei
the defining
S
=
Das l i e f e r t
die
Identifikation
-Programm. folgende
(ap-
von
controlled
(x,s)
fehls, in
{~}),
va-
Ein Z~hlmechanismus o r d n e den im
Interpretation
in
~N
B = m ×(~u
der
x ,
a b l a u f e n d e n Proze~ a u s g e f U h r t e n P r o g r a m m b e f e h l e n f o r t l a u f e n d Z a h l e n zu.
r
r2 .
w~hlen w i r P ~1
bzw.
~ A
i n dem
sei x
s
( x ,) E D
s ei
fur
:
d i e Nummer des Be-
(angewandt)
ALLOCATE - B e f e h l s laufen
natUrliche
des Axiomensystems
x.
n
auftritt, d i e Nummer des
Bis
zum Durch-
des z u g e h ~ r i g e n FREE-Befehls s e i
m = ~ ,
dann werde
m = Nummer des
FREE-
Befehls gesetzt,
(nl,ml
~ y (n2,m2)
<=> nl > n 2 A ml ~ m2 ,
s p<=> n ~ s < m. (Dabei g e l t e
n < ~
fur
alle
Die I d e n t i f i k a t i o n s f u n k t i o n tation
gerade die
Anmerkun~ :
n E IN .) id
beschreibt
An den b e i d e n B e i s p i e l e n
sierung eigentlich
noch n i c h t
streng
Sin n e
Mengen
und
bar
statischen
interpretiert.
fikationssystem
i n der j e w e i l i g e n
Identifikationsvorschriften
B
S
e r k e n n t man, dab u n s e r e F o r m a l i -
genug i s t . werden b i e r
W o l l t e man ganz genau s e i n ,
a l s momentanen
Interpre-
i n den b e i d e n S p r a c h e n .
Ausschnitt
Die im m a t h e m a t i s c h e n dynamische v e r ~ n d e r mUBte man e i n
Identi-
im A b l a u f der P r o g r a m m e l a -
29
boration
auffassen
Folge
durch eine fehlende
und d i e
von d e r a r t i g e n
Genauigkeit
jedoch
Diskussion
der G r u n d b e g r i f f e
te Strenge
verzichtet.
4.
Reduktion
mud es s e i n , Beispiel
einer
Ausschnitten
keinen
EinfluB
hat,
haben w i r
Axiomatisierung
beschreiben.
auf die der
hier
Da d i e s e
beabsichtigte
KUrze h a l b e r
von i n t u i t i v e n
g e w i s s e i n der u n f o r m a l i s i e r t e n
auf
letz-
Vorstellungen
Theorie auftretende
beweisen .
aus den Axiomen zu
Wir w o l l e n
dies
Gesetz-
an einem
vorfUhren.
In gewissen Sprachtypen vorigen
Abschnitt
Grundbegriffe kann
im gesamten P r o g r a m m a b l a u f
yon G r u n d b e g r i f f e n
E i n e der A b s i c h t e n m~igkeiten
Identifikation
S
kann man, wie etwa an dem B e i s p i e l
zu s e h e n ,
B,S,y,p
die
auf
B
ALGOL 68
im
i n das A x i o m e n s y s t e m e i n g e b r a c h t e n und
y
reduzieren.
In
diesen
Sprachen
durch S = B
und
durch
p
spb <=> syb v definiert
werden.
Wir werden d i e s e die M~glichkeit Vorgegeben
sei
Sprachtypen
durch d r e i
der Begriffsreduktion ein
geeignetes
Identifikationsmenge Wir
s = b
X
weitere
mit
konstruieren~
(B,S,T,p)
.
Wie ] e i c h t
das
" s2
ersichtlich,
- kurz wir
ist
klasse
von
werde s,
durch s
"-"
~
-
eine
< = > [VbEB : s l p b df
d i e Menge d e r ~ q u i v a l e n z k l a s s e n Projektion
S
(B,S,y,p)
S von
.
leistet"
Relation
- wie folgt
wie :
<:> s2pb ] .
bezUglich
ausgedrUckt,
ein Repr~sentant
eine
"dasselbe
eine Aquivalenzrelation. in
fur
neuer Axiome e i n B e r e i c h s y s t e m
gesagt
auf
Axiome b e w e i s e n .
(D,A)
~ber einem B e r e i c h s y s t e m
Dazu d e f i n i e r e n sl
dieser
Identifikationssystem
k~nnen nun z u n ~ c h s t ohne H i n z u f ~ g u n g
(B,S,y,~)
Axiome a u s z e i c h n e n und
Hilfe
d.h.
~ .
~ , ~
Es s e i
die
sei
kanonische
die ~quivalenz-
3O
Weiter
definieren
wir
die
Relation
~
auf
~x B :
spb <=> spb . df Diese D e f i n i t i o n i s t
unabh~ngig vom s p e z i e l l e n Repr~sentanten
Lemma i
: (B,S,¥ ~)
i s t ein ~er¢ichsystem.
BeweCs
: Wir mUssen das Axiom ~b
s
von
(AO) v e r i f i z i e r e n :
A bTb' => spb A byb ~ => spb' => spb'
Es sei nun
(D,A)
dasjenige I d e n t i f i k a t i o n s s y s t e m f u r
(B,S,y,~) ,
das gegeben i s t durch : c Xx~ (x,~) E A-<= > [ ~ t e df
Lemma 2 : Das I d e n t i f i k a t i o n s s y s t e m
Beweis
: Wir mUssen das Axiom
dann g i b t net ist,
es
(y,t)
genau e i n
E A,
wobei
(x,b)
E D
es g i b t
genau e i n
(x,b)
S : T = T A (x,t) E A ].
(D,A)
ist
funktion,
sei
~
die
geeignet.
verifizieren.
T = ~,
Sei
und es g i b t ,
da
(y,s) (D,A)
~ A; geeig-
mit
~ D
L x , b => m t p b ~) , mit
x = y A spb A (b~E L x , b => ~ b ~ ) SchlieBlich
Uber
und
(At)
x = y A tpb A ( b ' ¢ d.h.
X
zum System
(D,A)
o
geh~rige
d.h. mit
=> m ~ b ' ) ] . i d ( y , ~ ) = ( x , b ) <:> [ x =y A ~pb A ( b ' ~ L x,b
Identifikations-
~.
31
Lemma 3 : FUr
(y,~)
EA
Der Beweis v e r l ~ u f t
und
~hnlich
(y,s)
tionsfunktion
(B,S,x,p)
weitere
Axiome f u r
= id(y,s)
leicht
.
einsichtig.
e i n e s neuen B e r e i c h s y s t e m s erhalten,
wie d i e
~sES
~bEB : spb
(A3)
Vb~B
~sCS
(A4)
VsES
:
dessen I d e n t i f i k a -
im u r s p r U n g l i c h e n
System.
das vorgegebene B e r e i c h s y s t e m
{b : spb}
ist
wohlgeordnet
(A3)
und
Aufbau von
Wir w o l l e n z e i g e n S
: spb A ( b ' y b = > ~ s p b ' )
(A2)
: Die Axiome
"sinnvollen"
und
i-d(y,~)
ein :
die Begriffsreduktion
B
leistet"
(A2)
Anmerkung nen
Konstruktion
Identifikationssystem
"dasselbe
Wir fUhren nun d r e i
gilt
wie bei Lemma 2 und i s t
Damit haben w i r a l s o durch d i e e i n neues g e e i g n e t e s
E A
B
und
entscheidende
sind S
triviale
verlangen.
aufeinander
y .
Axiome, d i e e i (A4)
ist
die fur
Forderungo
: Unter der V o r a u s s e t z u n g d i e s e r
bijektiv
bzgl.
abbilden
und
Axiome l a s s e n s i c h
~
durch
~x B
durch
y
charakteri-
sieren. Dazu d e f i n i e r e n
wir
eine Relation
T~-b < ~ (unabh~ngig
auf
spb A ( b ' T b = > ~ s p b ' )
vom R e p r ~ s e n t a n t e n )
Lemma 4 :
~
und beweisen
a)
~ES
~IbEB
: ~b
b)
VbEB
~,sES
: T~b
c)
Ist
~b*
,
so g i l t
:
:
s~b <=> b*Tb V b* = b . Beweis
a)
:
Existenz : Sei mit
spb .
sei
b, = b,
s
Repr~sentant von
~.
Wir k o n s t r u i e r e n eine Folge und f a l i s
es ein
b'
Nach ( A ~ ) g i b t es
bEB
F = { b , , b 2 , b s , . . . } c B.
g i b t mit
b'yb n
und
Es
spb' ~ so
32
sei
bn+ 1 = b ~.
]etztes
F
Element
ist
b*.
nicht
FUr
}eer
b*
~ b' Fo]glich
gilt
und
: Seien
spb2 ,
b,yb2
fUhrt bl
b)
wegen
(A4)
ein
und
: b ' T b A spb'
(A4)
mit
wegen
wegen
s~b,
b=yb, s~b2
s~b~
und
s~b2 .
Dann i s t
also
oder
folgt
b2yb,
b,,b2£B
nach
bIyb2 Aus
spb*
~b*.
Eindeutigkeit spb~
und b e s i t z t
gilt
oder
b,
der W i d e r s p r u c h
zum W i d e r s p r u c h
= b2 •
~spb~ ,
mspb2 .
ebenso
Daraus f o l g t
= b2.
Existenz
: folgt
Eindeutigkeit
:
Repr~sentanten b'£ B byb'
und oder
unmittelbar Seien sl
slpb'
(A3) .
sl,s~ES
und
s~
Wegen
b = b'
Umgekehrt z e i g t
aus
mit
gilt
dann
~1~b
In b e i d e n
man genauso
~1~b
gilt F~llen
und
s~pb
und
mb'yb ist
~2~b .
FUr d i e
s2pb .
und m i t
Sei
(A4)
dann aber auch
s2pb'
:
s2pb ~ => s l p b ' Insgesamt
hat man a l s o
fur
alle
slpb' Somit
c)
ist
Es g e l t e
sl
- s2
~b*,
b'E B :
<~=> s 2 p b '
und d a h e r
~I
= ~
•
also spb*
und
byb* =>mspb . Gilt
nun
s~b ,
so auch
spb~
und m i t
(Ad)
folgt
b y b * V b*yb v b* = b o Da
byb*
nach V o r a u s s e t z u n g
a u f den W i d e r s p r u c h
~spb
fUhrt,
nun
folgt
33
folgt
also b*yb v b* : b .
Die u m g e k e h r t e
R i c h t u n g der ~ q u i v a l e n z b e h a u p t u n g
Aufgrund dieses
Lemmas k~nnen w i r
mit der reflexiven
HUIIe
¥refl
nun e i n f a c h yon
¥
ist
S
trivial.
mit
B
und
gleichsetzen.
Die A b b i l d u n g f f(s) ist
:
surjektiv,
: S÷
mit
b <=> [spb A ( b ' T b = > ~ s p b ' ) ] df
und wenn w i r
das neue System
B
(D,~)
aus dem I d e n t i f i k a t i o n s s y s t e m
mit
c (X,B) (x,b) konstruieren, Satz
:
E A <=> [ ~ s ~ S df
so g i l t
Sei (D,A)
= b .
fur
X
schrieben Anschrift
und
kann a l s o (A4)
allein
f(s)
= b A (X,S)E A]
:
~b:r
id(x,b)
(A2) , (A3)
:
FUr d i e
fikationsfunktion
Die I d e n t i f i k a t i o n
und
schlie~lich
f(s)
(D,A)
zum I d e n t i f i k a t i o n s s y s t e m
(B,B,Y,Yrefl) id
gilt
= id(x,s) unter
geh~rige
Identi-
:
der
. Voraussetzung
durch die
Begriffe
B
der Axiome und
¥
be-
werden.
des V e r f a s s e r s
Technischen Universit~t
: Dr.Fred
KrUger,
Mathematisches
Institut
MUnchen, D-8000 MUnchen 2, A r c i s s t r a B e
21.
der
ZUR UBERSETZBARKEIT VON P R O G R A ~ I E R S P R A C H E N H. JURGENSE~
I. Einleitun~ Die erste Anregung zu den folgenden Uberlegungen zur Ubersetzbarkeit yon Programmiersprachen ergab sich aus Diskussionen im Zusammer~ang der Ausstattung des LISP-Systems f~r die ELECTROLOGICA X8 in Kiel mit einem Compiler. Das bis dahin rein interpretativ arbeitende LISPSystem war dem Rechenzentrum der Universit~t Kiel 1968 yon W. van der Poel
0 I~ zur Verf~gung gestellt und 1968-71 von F. Simon 0 6 ~ und dem
Verfasser ES] den Gegebenheiten der Kieler Anlage angepaBt und betr~chtlich erweitert worden.
1971-72 wurde der Compiler von B. Kal-
hoff C6] hergestellt und im wesentlichen im "bootstrap"-Verfahren implementiert. Bekanntlich stehen dem Bau eines Ubersetzers f~r das vollst~ndige LISP einige prinzipielle Hindernisse im Wege; Gblicherweise werden diese dadurch umgangen, da~ die Sprache fGr den Dbersetzer eingeschr~nkt wird [2,6,7,12,14,15] . Ist dieses Vorgehen auch unsch~n, so wgre es noch tragbar, wenn die Einhaltung der Einschr~nkungen zum Zeitpunkt der Ubersetzung, sp~testens aber zum Zeitpunkt der Rechnung GberprGfbar ware; fGr LISP ist dies in einigen F~llen grunds~tzlich u r ~ g lich. Wit wollen diese Aussage im folgenden pr~zisieren. Es wird sich zeigen, da~ die Schwierigkeiten allein auf Akzidenzien yon LISP zurNckzufNhren sind, die die Sprache allerdings erst programmiergerecht machen. Dadurch wird die Frage nach einem generellen Verfshren nahegelegt, mit dessen Hilfe beim Entwurf einer ~hnlich LISP universellen Programmiersprache diese Probleme vermieden werden k~nnten. Insofern sollten im weiteren die aus LISP herangezogenen Beispiele nur als Erl~uterungen der allgemeineren Situation verstanden werden. 2. Spezifische (jedoch behebbare)Probleme
eines LISP-Compilers
Von den bei der Konzeption eines Compilers fGr LISP auftretenden spezifischen Problemen lassen sieh einige unter Verzieht auf Rechengesehwindigkeit vermeiden, andere durch geringfGgige Anderungen in der "Implementationsvorschrift" des EVAL-APPLY-Zyklus [7] beseitigen
35
•
8 • Es handelt , 9sich
mit
,
1
3
•
dabei durchweg um Fragen im Zusammenhang
(I) der Bindung freier Variabler, (2) der Kommunikation zwischen interpretierten compilierten Funktionen
und
und
(3) der m~glichen unterschiedlichen "Typenvereinbarung" (CSET, DEFINE~ DEFPROP, RE~PROP usw.) zum Compilations- und Rechenzeitpunkt.
Im einzelnen vergleiche
man dazu Saunders
~4~
, S. 70 f. Die Schwie-
rigkeiten entstehen, well (I) die in LISP vorgeschriebene Variablenbehandlung eine einfache und effektive Kellerspeicherungstechnik im compilierten Programm verbietet und
(2) die Unsicherheit ~ber die aktuelle "Typenvereinbarung" aufwendige Tests zur Rechenzeit erforderlich macht.
In den bestehenden Cempilern wird meist unter Verzicht auf vollstindige Korrektheit eine LSsung vorgezogen, die sehr viel schnellere Objektprogramme
zuii~t
[6,7,10,12,15~
. Da sich die genannten Problem%
wenn auch unter Effektivit~tsverlusten, beseitigen lassen, wollen wir diese Fragen im folgenden ausklammern und insbesondere in allen Beispielen voraussetzen,
dab eine entsprechend bereinigte
LISP-Version
mit idealem Compiler benutzt wird. 3. Sich selbst ~ndernde Programme Sehr viel komplizierter
als die bisher aufgez~hlten
Probleme
der sich zur Rechenzeit
selbst ~ndernden Programme;
solche Programme
sind in LISP formulierbar, "ALGOL Y" [I~ vorgesehen.
ist das
aber auch z.B. in der Konzeption yon Wir wollen die Frage, wie welt es ~ n s c h e n s -
wert ist, sich selbst ~ndernde Programme zuzulassen, hier nicht diskutieren I). Es kom~t uns vielmehr darauf an, eine Reihe yon Forderungen herauszuarbeiten,
die man an eine Progrsmmiersprache
mit sich
selbst ~ndernden Programmen om~d an ihren Compiler mindestens sollte, um zu erreichen, compilierbar"
da~ alle "compilierbaren"
sind. Dabei lassen wir die Frage der Okonomie
pilers und der Objektprogramme Die Korrektheitsforderung wie m~glich:
f~r den Compiler formulieren wir so schwach
(Interpretation),
eine Funktion zuordnet.
des Com-
vorerst v~llig auger acht.
Es seien LI, L 2 Programmiersprachen,
ij eine Abbildung
stellen
Programme'~orrekt
Ein Compiler
die jedem Programm(text)
p6Lj
(partielle Abbildung)
c: L I --~ L 2 heine korrekt, w e ~ m (I) Quelle(c) in ~! entseheidbar I) Zu allgemeinen Komplexit~tsfragen Buchberger [4] .Zu Realisierungen
und fur j = 1,2 sei
ist
in diesem Zus~mmerahang v~l. f~r ALGOL vgl. ~17,18,19].
56
und
(2) fur alle p@Quelle(c)
gilt:
(a) Quelle(i2(c(p)))--_~
Quelie(i1(P))
~X e Quelle(i2(c(p))): und
(b) Quelle(i2(c(p)))
und
i2(e(p))(x) = il(P)(X)
ist in Quelle(i1(P))
Wir fordern also, da2 die Nicht-Compilierbarkeit
entscheidbar.
eines Programmes zu
einer Fehlermeldung f~hrt (I); wir lassen zu, da2 die durch den Objektcode definierte Funktion Einschr~nkung der durch das urspr~ngliche Programm definierten Funktion ist (2a~ und begn~gen uns damit, da2 wir diesen Unterschied eventuell erst zur Rechenzeit meldungen)
(durch Fehler-
erfahren (2b).
Die sich selbst ~ndernden Programme klassifizieren wir in solche mit expliziter Anderung (z.B. durch Deklaration) und solche mit impliziter Anderung (durch Textsubstitution).
W~hrend erstere einem Compiler
keine prinzipiellen Schwierigkeiten bereiten d~rften, m~ssen b e i d e r zweiten Klasse in der Definition der Semantik der Programmiersprache Vorkehrungen getroffen werden, um eine, worm aueh noch so un~konomische, nicht-triviale
Compilierbarkeit
zu erreichen.
3.1. Explizite Anderungen In LISP k6nnen explizite Programm~nderungen DEF~OP,
zur Rechenzeit
durch
DEFINE r CSET und ~hnliche Fumktionen durchgef~hrt werden.
Statisch entsprechen diesen beispielsweise in ALGOL 60 die Deklarationen. Explizite Programm~nderungen werden allgemein durch Anweisungen zustande k o ~ e n m~ssen, die aus (I) einer Definitions- odor Execute-Anweisung (XEQ), (2) dem Namen des zu definierenden Programmteiles und (3) dem definierenden Ausdruok bestehen. In der Terminologie yon ALGOL 60 k ~ e n grammteile
sicher Prozeduren,
als ~nderbare Pro-
eventuell aber auch Typenvereinbarungen
und Anweisungen mit ~arken in Frage. Beispiel I: DEF~ROP (BI
(L~BDA (...)
(...(DSFPROP (GSNS~) ( . . . ...))
(QUOTS SXP~))
EXPR)
sl
(...)
Ein derartiges Beispiel stellt fiat elm Compiler-orientierte s LISP-
37
System kein Problem dar; dabei ist es gleichgiiltig, ob der Compiler nach der Funktionsdefinition
innerhalb yon BI explizit aufgerufen
wird oder DEFI~OP die Compilation Gbernimmt. Definitionen global wirksam.
In LISP sind DEFPROP-
In Programmiersprachen mit statischer
Blockstruktur entsprechen der Funktion DEFPROP meist die Deklarationen; Neudefinitionen mG~ten also nur lokal wirksam sein. Das Beispiel s~he in einer solchen Sprache etwa folgenderma~en aus: begin ~ t y p e ~ procedure BI (...); begin
begin computed ~ t y p e ~ procedure
(GENSY~.~; ... ) ;
en___dd;
end;
o
end Daraus ergEben sich f~r einen Compiler keine besonderen Schwierigkeiten; selbstverst~ndlich m~Bte er zur Rechenzeit aufrufbar sein; ferner m~Bte er rekursive Aufrufe zulassen, um Deklarationen von (computed procedure, s
innerhalb des den Rmpf einer
defi-
nierenden Textes verarbeiten zu k~nnen. In vielen FEllen k~nnte es erv~dnscht sein, eine in einem ~u~eren Block deklarierte Prozedur in einem inneren Block neu, Wirknng, DEFPROP).
zu definieren
(dies entspr~che
jedoch mit globa!er
der globalen Wirkung yon
Einen sonst idealen Compiler vorausgesetzt,
verhEltnism~Big einfach durch grunds~tzliche nen und Definition erreichenl); z.B.:
lieBe sich dies
Trennung yon Deklaratio-
I) Damit w~rden auch die in manchen Programmiersprachen (wie ALGOL 60) existierenden Unterschiede in der Behandlung yon (identifier~ s als Prozedurnamen und als sonstige Variablen-Namen beseitigt.
38
be~in list L; o
o o a
begin name X; for X & L do declare qomPuted procedure X;
be~in for X @ L d_.odefine computed
~roeedure(X;
...);
o o e
en___dd;
endi
eA
In diesem L~sungsvorschlag ist (~hnlich wie in LISP) nicht einmal mehr die Anzahl der dynamisch definierten Prozeduren statisch festgelegt. An der Compilierbarkeit derartiger zur Rechenzeit explizit ge~nderter Programme ~ndert sich auch nichts, wenn man wie im Beispiel 2 Rekursivit~t zuliBt. Beispiel 2: DEFPROP (A2 (L~BDA
(...) (...(~a ...(B2 . . . ( ~ •..(~...)...)...(@
...)...) ...))
C
EXPR) DEFPROP (B2 (L~,~BDA (...) (...(DEFPROP (QUOTE A2) (...) (QUOTE EXPR))...))
{ ExP FEXPR
A2 ( . . . )
})
39
Die vier Aufrufe yon A2 werden wie folgt bearbeitet: (a) Ursprdngliche Definition von A2. (b) (I) Falls B2 ~[PR ist: Urspr~ngliche Definition von A2. (2) Falls B2 FEXPR ist: In Abh~ngigkeit vom Zeitpunkt der Auswertung in B2; bei mehrfacher Auswertung also eventueli verschieden. (c,d)
Umdefinierte Version yon A2.
Dies ergibt sich fur (a) aus der Festlegung, dab bei Aufruf einer Prozedur F zuerst in F eingetreten wird und dann die aktuellen Parameter bestimmt werden. (bl) aus dem "call-by-value"-Prinzip. (b2) aus dem "call-by-name"-Prinzip. (c,d) aus der Festlegung, dab Arguments nacheinander yon links nach rechts bestimmt werden. (b,c,d) machen auch bei Benutzung eines Compilers keine Schwierigkeiten,
(z.B. in DEFPROP)
falls bei der Berechnung der Argumente
dieser
Aufrufe keine weiteren Anderungen der Definition yon A2 erfolgen (sonst Behandlung entsprechend
(a));
(c,d) sind auch dann unproble-
matiseh, wenn sine andere sinnvolle Reihenfolge
der Argumentsmswertung
festgelegt wird, sofern das Beispiel dann ~berhaupt
ein zul~ssiges
Programm ergibt. Wegen (a) muB v o n einem Compiler-orientierten gefordert werden,
System
da~ Ob~e_kpKo~r~m~e_g~keller% und eventuell von einem
'lgsr~a[e collector" mitbehandelt werden I). 3 ~ 2 - I m p l i z i t e Anderungen Implizite Programminderungen Programmtextes
kommen dadurch zustande,
da~ Teile des
ohne ausdr~ckliche Neudefinition ihrer Einbettung in
den Kontext ausgetauscht werden (z.B. durch Anderung des Textes einer Prozedur ohne erneute Deklaration);
dazu ist notwendig und hinreichend,
dab es mSglich ist~ (I) den Program~text des ausgef~hrten Programmes zur Rechenzeit zu srreichen und
(2) Textst~cke ohne Beeinflussung des Kontextes zu ersetzen.
In LISP erreicht man (I) durch GET bzw. ASSOC oder iquivalente Funktionen oder durch (explizite) Programm~nderungen zur Rechenzeit (in LISP X8 auch durch Einlesen) und
(2) durch RPLACA, RPLACD und abgeleitete Funktionen.
I) Bei LISP ist fur die Kellerung speziell zu beachten, Umdefinition yon A2 in B2 global wirksam ist.
dab die
4O
Geht man davon aus, dab die Operationen wie RPLACA und RPLACD auf Objektcode angewendet ten Programm~nderungen,
werden k~nnen,
nicht
so w~ren diejenigen implizi-
bei denen der zu ~ndernde Text mit GET oder
ASSOC erst nach der Compilation aufgesucht
werden soll, unkritisch,
sofern - wie Gblich - der ursprttugliche Programmtext lierung vergessen werd~n dGrfte
I) .
nach der Compi-
Diese v e r h ~ l t n i s m ~ i g
einfache
L~sung ist jedoch in den Gbrigen F~llen impliziter Anderungen meist nicht anwendbar.
Typiseh ist das folgende
Beis~iel 3: DEFPROP
(D3 (LAA~BDA ( . . . )
(SETQ
V3
(PROG (V3 X3 Y3 . . . )
(LIST
...))
(SETQ X3 (LIST ...)) (SETQ Y3 (LIST ...)) (DEFPROP (QUOTE A3) (LIST (QUOTE L ~ B D A )
V3 (APPEND X3 Y3))
(QUOTE EXPR)) (CSETQ B3 Y3) ® m o
>) EXPR )
D3 ( . . . ) Der k r i t i s c h e P u n k t i n d i e s e m B e i s p i e l i s t , da~ d i e i n D3 neu d e f i n i e r t e F u n k t i o n A3 und d e r Wert v o n B3 das T e x t s t d c k Y3 gemeinsam haben. Die Situation ist folgendermaSen:
f
.......
J
Jede T e x t s u b s t i t u t i o n i n B39 d . h . i n n e r h a l b Y3, i s t g l e i c h z e i t i g eine i m p l i z i t e A n d e r u n g y o n A3. Bei i n t e r p r e t a t i v e m Rechnen w i r d d i e s automatisch ber~cksichtigt. Durch Compilation wird die Textidentit~t yon A3 und B3 jedoch aufgehoben: Anderungen yon B3 wirken sich nicht mehr auf A3 aus. Fdr LISP bedeutet
das: Es gibt Programme,
die in compilierter und
I) Ist die Referenz des Programmes auf seinen Text bereits vor der Compilation im Programmtext realisiert ("zirkulire" S-expression), so kann der Compiler dies schon bemerken u. z.B. mit einer Fehlermeldung reagieren.
41
uncompilierZer
Version verschiedene
Funktionen
gibt keinen korrekten nicht-trivialen Das Beispiel ist jedoch keineswegs LiSP-Version
erseheinen mag;
darstellen;
oder: es
Compiler fdr LISP.
so unnatdrlich,
wie es in seiner
jede sinnvolle Realisierung
tes ders m~Bte etwa das folgende entspreehende Programm zulassen:
des Konzep-
dem Beispiel 3
begin strin~ X3, Y3;
X3: . . . . ; Y3: . . . . ;
be6in computed < t y p e >
~rqcedure
(GENSY~;
CONNECT(X3,Y3) ) ;
end;
end Wir sehen die folgenden zwei M~glichkeiten, beseitigen:
Verbot
3.2.1. Verbot
oder Explizit-Nachen
diese Schwierigkeiten
zu
impliziter Anderungen.
impliziter Anderun~en
Wir sahen, dab es kaum m~glich sein wird, Situationen wie in Beispiel 3 zu vermeiden, wenn man in sin~voller Weise die N~glichkeit zulassen will,
dab sich Programme
Ein Verbot
zur Rechenzeit
impliziter Anderungen
die Textmanipulation
(auch nur explizit)
keine Substitutionsoperationen
dieses ist sicher f~r manche Anwendungen 3.2.2. Explizit-Nachen
indern.
ist also damit gleiehwertig,
daS fdr
erlaubt werdenl);
ziemlich un~konomisch.
im~liziterAnderun~en
Das Problem des Beispiels 3 wird noch dadureh kompliziert,
daS die
inderungen yon B3 wihrend der Ausfdhrung yon A3 stattfinden k~nnen. Zur Zeit des Aufrufs yon A3 liegt also die Interpretation yon A3 als Funktion noeh nicht lest. Dies scheint
inkonsequent,
wenn man berSck-
I) Eine unkritische "Quasi-Substitution" U = (A B C) -->U = (A D C) ist in LIS2 auch ohne RPLACA/R~LACD z.B. mit (L~,~BDA (U D) (LIST (CAR U) D (CADDR U))) m~glich - allerdings mit gr~Serem Zeitund Speicheraufwand.
42
sichtigt,
da~ gleichzeitig normalerweise
die Parameter yon A3 endgGl-
tag ausgewertet werden (dies gilt nicht fur FEXPR's). Abhilfe bringt die folgende Festlegung zur Semantik: Der Prozeduraufruf F(X,Y,...) hat die Wirkung von f(X,Y,...); dabei ist f die durch den Ausdruck (Text) yon F zum Zeitpunkt des Aufrufs definierte Funktion. Die fur z.B. ~eomputed statement,s Festlegung sind evident I). FUr ein Compiler-orientiertes sequenzen:
n~tigen Nodifikationen dieser
System hat das u.a. die folgenden Kon-
(I) Auch nach der Kompilation muB der ursprGngliehe Programmtext
erhalten bleiben;
"Name-Prozedurtext"
die Zuordnung
bzw. "Name - Ausdruck" wird
fur das Programm selbst aufgehoben, fGr den Compiler bestehen;
bleibt aber
GET und ~hnliche Funk-
tionen erreichen den Text also nicht mehr. (2) Substitutionen im ursprGnglichen Programmtext mGssen registriert werden. (3) Vor AusfGhrung eines ProgrammstGckes
(Prozedur,
Anweisung) muB geprGft werden, ob es seit seiner letzten Compilierung ge~ndert wurd~ und eventuell neu compiliert werden. (4) Die verschiedenen Programmversionen im Quelleode und Objekteode mGssen gekellert werden. Ob sieh dies brauchbar durchfGhren l ~ t ,
h~ngt wesentlich v o n d e r
Realisierung von (2) ab. FUr LISP dGrfte das sehr aufwendig sein. 4. Konsequenzen f~r ' LISP Die Forderungen yon 3.2.2. ergeben ungef~hr die folgende gegen ~7~ S. 70-71 ge~nderte Definition der Semantik yon LISp2): I) Interessanterweise reicht also die "copy rule" yon ALGOL 60 fur die Behandlung yon sieh selbst ~ndernden Programmen aus. $.auch 0 2) Nan beaohte die folgenden Eigenschaften von copy fur A r g ~ e n t e , die nicht S-expression sind: (a) Die Identit~t von Listenteilen wird aufgehoben, z.B.
(b) Auf " ~ e i s e n " z.B. fur
ist c o ~
undefiniert
(Pehlermeldungen);
43
evalq,uote[fn;args] = [ get[fn;FEXPR]v get[fn;PSUgR] --> eval[eons[fn;args];NIL]; T --> apply[copy[fn];args;NIL]] a p_p_~[fn;args;a] = [ n u l l [ f n ] -->NIL;
~to~Efn] ~ [ getEfn;SUBR] --> [get[fn;EX~{] /%ehanged[expr] -->
g~t[r~;Exp~]
apply[eopyFexpr];args;a]; T ~ exeeute[subr;args;a]]; --> a p p l y [ c o p y [ e x p r ] ; a r g s ; a ] ;
T --> apply[eopy[edr[sassoe[fn;a;%[[];error[A2]]]]];args;a]];
eq[ear[fn];LABEL]--> apply[oopy[eaddr[fn]];args;oons[eons[cadr[fn]; eaddr[fn]];a]]; eq[ear[fn];FUNARG] --~apply;copy[eadr[fn]];args;eaddr[fn]]; eq[oar[fn];~LMBDA] --> eval[eaddr[fn];noone[pa±r[eadr[fn];args];a]]; T --> apply[eopy[eval[fn;a]];args;a]] evalfform;a] = [ null[form] ~ NIL; numberpiform] --->form; atomIform] --~ [get[form;APVAL] --~carIapval]; T -->cdr[sassoe[form;a;~[[];error[A8]]]]]; eq[car[form];QUOTg] --~ eadr[form]; eq[ear[form];FUNCTION] --~ list!FUNARG;eadrIform];a]; eq[ear[form];COND] --> eveon[edr[formJ;a]; eq[carFform];PR0O] -~ progiedr!form];a]; atom[car[form]] --->[ get[ear[form];SUBR] -~ ! get[ear~form];EXPRJ A ehangedIexprl -~>apply[eopyiexpr]; T --> e x e e u t e [ s u b r ; e v l ± s [ e d r [ f o r m ] ; a ] ; a ] ] ; get[ear[form];FSUBR]---~ a
7
list[edr[form];a];a]; T--~ exeoute[fsubr;edr[form];a]]; get[car[form];EXPR] -~> apply[copy[expr];evlis[cdr[form];a];a]; get[carIform];FEXPR] ~ apply[copy[fexpr];list[edr[form];a];a]; T --> eval[cons[cdr[sassoo[ear[form];a;~[[];error!Ag]]]];
44
Literatur: [i] ALGOL-Bulletin: 21.1 (1965), 22.3.10 (1965). [2] Asai, K., und Inami, Y.: Implementation of LISP-Compilers (japaniseh). J. of the Inform. Processing Soc. of Japan ~, 253-260. Engl. Zusammenfassung in: Inform. Processing in Japan ~,I03 [3]
[4]
[5] [6] [7] [8] [9]
(1969). Berkeley, E.C., und Bobrow, D.G., (Hrsg.): The Progra~ming Language LISP: Its Operation and Applications. MIT Press, Cambridge, Nass., 1967 (3. Aufl.). Buchberger, B., und Roider, B.: A Study on Universal Functions. Inst. f. Numer. ~ath. u. Elektron. Inform.-Verarb., Universit~t Irmsbruck, Bericht Nr. 72-5, 1972. (J~rgensen, H.): LISP X8 - KIEL. Rechenzentrum der Universit~t Kiel, Dokumentation X8.22-I, 1970. Kalhoff, B.: Ein Compiler fur das System LISP 1.5 X8 KIEL. Diplomarbeit, Kiel, 1972. McCarthy, J., und andere (Hrsg.): LISP 1.5 Programmer's Nanual. NIT Press, Cambridge, Nass., 1966 (2. Aufl.). NcCarthy, J.: A New Eval ~unetion. NIT, Project MAC, A.I.Nemo 34. Moses, J.: The function of FUNCTION in LISP. SIGSAN Bull. 15,
13-27 (1970). [10] PDP-6 LISP (LISP 1.6). NIT, Project ~&~C, A.I. Memo 116A (1967). [ii] (van der Poel, W., und andere): PTT LISP-Interpreter voor EL X8. Dokumentation 1967-68. [12] Quam, L.H., und Diffie, W.: Stanford LISP 1.6 Nanual. Stanford Artif. Intellig. Lab., Operating Note 28,7. [13] Sandewall, E.: A Proposed Solution to the FUNARG Problem. Uppsais Univ., Department of Comp. Sc., Rep. 29 (1970). [14] Saunders, R.A.: LISP - On the Programming System. [3], 50-72. [15] Saumders, R.A.: The LISP System for the Q-32 Computer. [3], 220-238 und 290-317. [16] Simon, F.: Sekund~rspeicher in LISP. Diplomarbeit, Kiel, 1970. [17] Buchberger, B.: An Extension of ALGOL 60. Comm. Joint Inst. Nucl. Res. E5-5787, Dubns, 1971. [18] Busse, H.G.: Eine m~gliche Erweiterung der Programmiersprache ALGOL. Elektron. Rechenanl. ~, 81-83 (1966). [19] Kalmar, L.: Ist ALGOL wirklich sine algorithmisehe Sprache? In: D~rr, J., und Hotz, G., (Hrsg.): Automatentheorie und formale Sprachen. Bibl.lnst., Nannheim, 1970. Anschrift des Verfassers: Dr. Helmut J~rgensen, Mathematisches Seminar der Universit~t Kiel, D-2300 Kiel I, OlshausenstraBe 40-60.
fiBER DIE
SYNTAX
I. KUPKA
Summary:
UND
VON
DIALOGSPRACHEN
N. WILSING
A dialog is the interactive analogon of a program. The syntactical
structur of dialogs consisting of free ~nputs and input-dependent outputs is represented by means of a local syntax for describing these units and a global syntax describing their global connection in a dialog. The external form of the input syntax is a hierarchical syntactical partition of the whole set of input words. Considerations on the consistency yield additional conditions for the local syntax. Detailed examples explo~2n the method of syntactically describing conversational languages. I. Synta X und Kontextabhgn$iskeit der Einsaben Die Besehrei~ung von Dialogsprachen erfolgte bislang meist in enger Anlehnung an die Beschreibung von Programmlersprachen, z.B. unter Angabe einer Grammatik so dab die von
G
erzeugte Sprache
L (G)
G,
im wesentlichen die syntaktisch korrek-
ten Eingabezeilen enth~It. Im allgemeinen ist jedoch die syntaktisehe Korrektheit einer Eingabezeile abh~ngig v o n d e r Dialogvergangenheit, d.h. vom aktuellen Zustand des Systempartners. Dabei handelt es sich zun~chst um Kontextabh~ngigkeiten, wie sic auch bei Programmiersprachen fHr Stapelverarbeitung auftreten, etwa im Zusammenhang mit expliziten oder impliziten Deklarationen. Dar~ber hinaus muB man oft mehrere Klassen yon Systemzust~nden unterseheiden, derart dab die Zugeh~rigkeit zu verschiedenen Klassen gleichbedeutend ist mit einer unterschiedlichen Struktur der syntaktisch korrekten Eingaben. Dies ist z.B. der Fall, wenn die Dialogsprache einen sog. Modus der direkten und einen sog. der indirekten AusfHhrung besitzt und der jeweilige Modus vom Zustand abh~ngt. So besteht naeh ErSffnung einer Funktionsdefinition in
APL\360 durch
V F X
ein Zustand der indirekten Ausffihrung
(definition mode), in dem z.B. nieht alle mit
')'
beginnenden Kommandos gegeben
werden dfirfen, siehe Falkoff [2] . Andererseits sind jetzt Verzweigungen mit dem C~TO-Pfeil
' ÷ ' erlaubt, die im Modus direkter Ausffihrung nicht korrekt sind.
Vorprogrammierte Unterbreehungen yon Funktionen oder Prozeduren k~nnen zu Systemzust~nden w~hrend des Dialogs ffihren, in denen die Syntax der korrekten Eingaben zus~tzliehen Einschr~nkungen unterworfen ist oder vSllig neu definiert ist. Nach Aufruf der
APL\360-Funktion
46
VF
D]
0
÷
~+o
V sind z.B. auger der Bet~tigung der Unterbrechungstaste nur solche Eingaben korrekt, die einen Operanden des dyadischen Additionsoperators beschreiben. Naeh Aufruf der Funktion VG
v wird jede Eingabe auBer
OUT
(~bereinander getippt) als Text interpretiert und
wieder ausgegeben. Es liegt also eine vSllig vergnderte syntaktische Situation vor. Das letzte Beispiel zeigt zugleich einen Fall) in dem keine syntaktisch inkorrekten Eingaben auftreten kSnnen. Aber auch sonst spielen die syntaktisch i~korrekten Eingaben im Dialog - anders als syntaktisch inkorrekte Programme im Bereich der Programmierspraehen - eine konstruktive Rolle, indem sie ebenfalls eine Fortsetzung des Dialogs ermSglichen. Eine Ausnahme bilden bier Systeme mit syntaktisch gesteuertem variablem Eingabealphabet wie etwa der Benutzereingaben dient digen Wortmenge
A"
DIALOG, siehe Cameron [1] . Die Syntax
daher allgemein der Unterteilung einer vollstgn-
~ber dem Eingabealphabet
mindestens in einen durch eine Grammatik
A
in syntaktlsche Typen, und zwar
G l erklgrten Tell
II=L(GI) und dessen
Komplement
I = A" - I] . Dabei sind Eingaben aus I ebenso zu verarbeiten, z.B. o o zweeks Erzeugung einer Fehlermeldung oderAufforderung zur Korrektur, wie Eingaben
aus
I 1 . Da alle Eingaben den Systemzustand beeinflussen k~nnen und damit auch
dessen syntaktische Auswirkungen, ergibt sich eine weitere syntaktisehe Unterteilung der Eingaben im Hinblick auf diese Wirkung. Im Modus direkter AusfHhrung (execution mode) haben wit z.B. in
APL\360
die syntaktische Zerlegung
A~ = loV 11 v 12 ) I 1 = L(G|), wobei
12 = L(G2) )
G| die korrekten Eingaben zur unmittelbaren AusfHhrung und
G 2 die modusver-
~ndernden Kopfzeilen von Funktionsdefinitionen beschreibt. Es k~nnen auch syntaktische Unterteilungen auftreten, die durch Grammatiken
G|, G 2 mit
L(G I) ~ L(G 2)
beschrieben werden. Hierauf wird bei der nachfolgenden Analyse der syntaktischen Globalstruktur n~her eingegangen werden. Die so skizzierte Unterteilung von
A" variiert in Abhgngigkeit vom Systemzustand,
wie oben an Beispielen erl~utert. Zu jedem Zustand
S
fassen wir die dutch
Grammatiken beschriebenen Eingaben mittels einer vereinigten Grammatik
G(S)
47
zusammen und definieren als Menge der regulgren Eingaben: Iregul~r (S) = Labgelegt. In einem sp~teren Zustand
Sdirekt im Modus direkter Ausf~rung werde die abgelegte Eingabezeile duroh
einen Aufruf Do
odor mittels einer semantisch dazu ~quivalenten Formulierung zur AusfHhrung gebracht. (Zum Step-Part-Konzept, auf das bier Bezug genommen wird, siehe Smith [~.) Offenbar muS man im Zustand
Sindirekt alle solehen Eingaben als syntaktisch
regul~r ansehen, zu denen es einen auf
Sindirekt mittelbar folgenden Zustand
Sdirekt gibt, in dem diese Eingaben, wenn sie direkt gegeben werden, syntaktisch regul~r sind. Dem kann dureh L (G
(Sindirekt)
)
=
Am
Reehnung getragen werden. In der Praxis w~rde dies die Verschiebung der syntaktischen Analyse auf den Aufrufzeitpunkt, mithin die Abspeieherung ungepr~fter Texte bedeuten. Im Fall e ( G (Sindirekt)) ~
A~
ist eine gr~bere syntaktische Analyse zumEingabezeitpnnkt erforderlich, der eine feinere syntaktische Analyse im Aufrufzeitpunkt folgt. Letztere hat jedoch nichts mehr mit der konkreten Syntax eines Aufrufs wie
Do
zu tun, sondern nur
noch mit der Semantik dieses Aufrufs. Wir bezeichnen Eingaben aus
L(G(Sindirekt))
als formal resulgr, solehe dem Komplement zugehSrigen als formal irresul~r. Beim Aufruf zerf~llt die Menge der formal regul~ren Eingaben entsprechend der Zugeh~rigkeit zu L(G(Sdirekt)) in aktuell resulgre und aktuell i rresulgre. F~r den Benutzer ist bei der Eingabe bereits die Kenntnis der aktuellen Regularit~t wiehtig, fHr das System einzig die formale. Hier haben wir einen Fall, in dem Benutzer und System sich an jeweils verschiedener Syntax orientieren.
48
2. Die syntaktisohe Struktur der Ausgaben Unter Ausgaben sind bei elnem Dialog nlcht nur programmlerte Wertausgaben sondern ganz allgemein alle Ante~le des Systems am Gesamtdialog zu verstehen. Bei den derzeitigen Sprachen findet man unter anderem (Ausgaben hier und im folgenden unterstrichen)
dutch Ausgabebefehle veranlaBte Wertbeschreibungen, Beispiele:
2.]46381 ANSWER = 2.14638!
Anfragen des Systems, Beispiel aus dem Sprachkonzept
VENUS, siehe
MatthewsETJ:
? PLEASE DEFINE WHAT THE VARIABLE "X" = Wiedergabe gespeieherter Zeilen, z.B. zwecks Korrektur durch den Benutzer, Statusmeldungen des Systems, z.B. STOPPED AT LINE 7, sowie Fehlermeldungen. In einem Dialog, in dem auch das System aktiver, wenn auch zumeist deterministisch reagierender Partner ist, etwa im Bereich des "Problem-Solving", mu8 die systemseitige Syntax dieselben internen Objekte besehreiben wie die benutzerseitige. Beide liefern dann externe Abbilder einer gemeinsamen internen abstrakten Syntax im Sinne yon Mc Carthy, siehe [8]. Verschiedenheiten b e i d e r benutzerseitigen Syntax einerseits und der systemseitigen andererselts ergeben sich aus den untersehiedlichen Aufgaben fgr beide Partner. Anders als bei der Eingabe brauchen bei der Ausgabe keine Komplemente berUcksichtigt zu werden. Entsprechend der zugrunde gelegten abstrakten Syntax k~nnen die Ausgaben durch mehrere Grammatiken, etwa eine fur Wertbeschreibungen, elne fur Fehlermeldungen usw., syntaktisch beschrieben und dadurch zu syntaktischen Typen zusammengefa~t werden. Dabei braucht der syntaktische Typ einer Ausgabe nicht eindeutig dureh den Text bestimmt zu sein. Zum Beispiel k~nnte der Text einer Fehlermeldung zugleich der Text eines auszugebenden Strings sein. Eine syntaktische Mehrdeutigkeit anderer Art liegt vor, wenn bei vorgegebenem Systemzustand und vorgegebener Eingabe der syntaktische Typ der Ausgabe nur semantisch determiniert ist. So wird man oft neben Wertbeschreibungen Fehlermeldungen erwarten mUssen, z.B. nach Eingaben wie Type
(sqrt (a + b - c)).
Es kann sein, dab eine Indeterminiertheit bezUglieh des syntaktisehen Typs der Ausgabe durch eine weitere Unterteilung der Eingabesyntax behebbar ist. Wir werden die Konsequenzen hieraus im Zusammenhang mit der syntaktisehen Globalstruktur erSrtern. Die syntaktische Beschreibung der Ausgaben dient sowohl der Orientierung des Benutzers Hber errelchbare bzw. zu erwartende Ausgaben als auch der Festlegung der
49
konkreten Ausgabesituationen ffir den Implementierer° Die Beschreibung des yon den Autoren entwickelten APL-Dialekts
HDL, siehe [4], enth~It z.B. unter anderem fol-
gende Regeln der systemseitigen Syntax ("# " bedeutet "neue Zeile"):