<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% SOS-Implementierung in Prolog.

% ReprÃ¤sentation von ZustÃ¤nden als Liste von "="-Termen (z.B.: [=(x,2),b=true])
% PrÃ¤dikat zum Nachschlagen in einem Zustand:
lookup([Y=W|_], X, V) :- X = Y, !, V = W.
lookup([_|E]  , X, V) :- lookup(E, X, V).
% Alternativ: lookup([Y=W|E],X,V) :- X=Y -&gt; V=W; lookup(E,X,V).

% PrÃ¤dikat zum Aktualisieren eines Zustand:
% update(Sigma,X,V,Sigma1) entspricht "Sigma1 = Sigma[X/V]"
update([]         , X, V, [X=V] ).
update([Y=W|Sigma], X, V, Sigma1) :- X = Y -&gt; Sigma1 = [X=V|Sigma]; update(Sigma, X, V, Sigma2), Sigma1 = [Y=W|Sigma2].

% Auswertung von AusdrÃ¼cken nach den Regeln der natÃ¼rlichen Semantik:
% eval(Sigma,E,V) enspricht "Sigma |- E : V"
eval(_    , N    , N) :- number(N).
eval(Sigma, X    , V) :- atom(X), lookup(Sigma, X, V).
eval(Sigma, E1+E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), V is V1 + V2.
eval(Sigma, E1-E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), V is V1 - V2.
eval(Sigma, E1*E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), V is V1 * V2.
eval(Sigma, E1&lt;E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), (V1 &lt; V2 -&gt; V = true; V = false).
eval(Sigma, E1&gt;E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), (V1 &gt; V2 -&gt; V = true; V = false).
eval(Sigma, E1=E2, V) :- eval(Sigma,E1,V1), eval(Sigma,E2,V2), (V1 = V2 -&gt; V = true; V = false).

% Berechnungsschritte nach Regeln der SOS:
% step(S1,Sigma1,S2,Sigma2) entspricht "&lt;S1,Sigma1&gt; -&gt; &lt;S2,Sigma2&gt;"
step((X=E)      , Sigma, skip, SigmaV) :- eval(Sigma, E, V), update(Sigma,X,V,SigmaV).
step(if(E,S1,S2), Sigma, S   , Sigma ) :- eval(Sigma, E, V), (V -&gt; S = S1; S = S2).
% Alternativ:
% step(if(E,S1,S2), Sigma, S1, Sigma) :- eval(Sigma, E, true).
% step(if(E,S1,S2), Sigma, S2, Sigma) :- eval(Sigma, E, false).
step(while(E,_) , Sigma, skip, Sigma) :- eval(Sigma, E, false).
step(while(E,S) , Sigma, (S; while(E,S)), Sigma) :- eval(Sigma, E, true).
step((skip; S)  , Sigma, S, Sigma).
step((S1;S)     , Sigma, (S2;S), Sigma2) :- step(S1, Sigma, S2, Sigma2).

% DruchfÃ¼hren einer Berechnung:
% exec(S, Sigma, FinalSigma) entspricht "&lt;S, Sigma&gt; -&gt; ... -&gt; &lt;skip, FinalSigma&gt;""
exec(skip, Sigma, Sigma     ).
exec(S   , Sigma, FinalSigma) :- step(S, Sigma, S2, Sigma2), exec(S2, Sigma2, FinalSigma).

% Beispiel: Berechnung der FakultÃ¤t einer Variable n
% ?- P = (p=1; while(n&gt;0, (p=p*n; n=n-1))), exec(P, [n=6], R).
</pre></body></html>