Continuation Semantics Expressed in Algol-68
See L. Allison, A Practical Introduction to Denotational Semantics, CUP, Cambridge Computer Science Texts V23, 1986.
Note proc eee
,
proc ddd
and
proc ccc
in particular.
( print((newline," progch7.a68:Continuation Semantics 19/4/85 L.A.", newline)); #-----------------------------------------------------------------------------# #lexical domains# MODE ALFA = [1:10]CHAR; INT plussy = 0, minussy = 1, timessy = 2, oversy = 3, eqsy = 4, nesy = 5, ltsy = 6, lesy = 7, gtsy = 8, gesy = 9, ident = 10, numeral = 11, ifsy = 12, thensy = 13, elsesy = 14, whilesy = 15, dosy = 16, beginsy = 17, endsy = 18, skipsy = 19, semisy = 20, becomessy = 21, open = 22, close = 23, varsy = 24, constsy = 25, procsy = 26, gotosy = 27, valofsy = 28, resultissy = 29, stopsy = 30, colon = 31, writesy = 32; #-----------------------------------------------------------------------------# #syntactic domains# INT plus = 0, minus = 1, times = 2, over = 3, eq = 4, ne = 5, lt = 6, le = 7, gt = 8, ge = 9, neg = 10; MODE OPR = INT; # = {plus..neg} # MODE BEXP = STRUCT(OPR opr, EXP left,right), # $e $W $e # UEXP = STRUCT(OPR opr, EXP son), # $W $e # VAR = ALFA, # $c # IFEXP= STRUCT(EXP e1, e2, e3); # if $e then $e else $e # MODE EXPNODE = UNION(BEXP, UEXP, VAR, INT, IFEXP, #valof#CMD); MODE EXP = REF EXPNODE; MODE LABEL = INT; MODE ASSIGN = STRUCT(EXP lhs, rhs), # $e:=$e # SEMI = STRUCT(CMD left, right), # $g;$g # IFSTAT = STRUCT(EXP b, CMD gtrue, gfalse),# if $e then $g else $g # WHILES = STRUCT(EXP b, CMD g), # while $e do $g # BLOCK = STRUCT(DEC d, CMD g), # begin $d;$g end # LABCMD = STRUCT(LABEL l, CMD g), # $n:$g # G0T0 = LABEL, # goto $n # ONEEXP = STRUCT(INT tag, EXP e); # resultis $e or write $e # MODE CMDNODE = UNION(ASSIGN, SEMI, IFSTAT, WHILES, BLOCK, #call# ALFA, LABCMD, G0T0, ONEEXP); MODE CMD = REF CMDNODE; MODE VARDEC = ALFA, # var $c # CONSTDEC= STRUCT(ALFA id, EXP e), # const $c=$e # PROCDEC = STRUCT(ALFA id, CMD g), # proc $c=$g # DECLIST = STRUCT(DEC left, right); # $d;$d # MODE DECNODE = UNION(VARDEC, CONSTDEC, PROCDEC, DECLIST); MODE DEC = REF DECNODE; #-------------------------------------------------------------------------# # I/O # LOC INT line no := 1; LOC BOOL end of input := FALSE; print((newline, line no, "->")); OP = =(ALFA a, b)BOOL: (LOC BOOL eq:=TRUE; FOR i TO UPB a WHILE eq DO eq:=a[i]=b[i] OD; eq ); PROC getch = CHAR: (LOC CHAR ch; LOC FILE si:=stand in; PROC gc = CHAR: (LOC FILE si2 := si; PROC eof = (REF FILE f)BOOL: (print((" [EOF]", newline)); ch:="."; end of input := TRUE; GOTO eoflab ); on logical file end(si2, eof); get(si2, ch); print(ch); eoflab: ch ); PROC eol = (REF FILE f)BOOL: (ch:=" "; newline(f); line no +:=1; print((newline, line no, "->")); GOTO eolnlab ); on line end(si, eol); ch:=gc; eolnlab: ch ) # getch #; #-----------------------------------------------------------------------------# LOC CHAR ch:=getch; #current character# LOC INT sy; # current symbol code # LOC ALFA word; # holds characters of a var or ident # LOC INT n; # value if sy=numeral # PROC error = (STRING m)VOID: (print((newline, " error:", m, " lineno=", whole(line no,0), " ch=", ch, " sy=", sy, " n=", n)); IF end of input THEN print(" end of input file") FI; GOTO stop ); PROC check = (INT sym, STRING message)VOID: IF sy=sym THEN insymbol ELSE error(message) FI; PROC insymbol = VOID: (PROC letter = (CHAR ch)BOOL: (ch >= "a" AND ch <= "z") OR (ch >= "A" AND ch <= "Z"); PROC digit = (CHAR ch)BOOL: ch >= "0" AND ch <= "9"; LOC BOOL looked ahead := FALSE; WHILE ch=" " DO ch:=getch OD; # ch~=" " # FOR i FROM LWB word TO UPB word DO word[i]:=" " OD; IF letter(ch) THEN looked ahead := TRUE; word[1]:=ch; ch:=getch; LOC INT l:=1; WHILE letter(ch) OR digit(ch) DO l+:=1; IF l <= UPB word THEN word[l]:=ch FI; ch:=getch OD; IF word=ALFA("i","f"," "," "," "," "," "," "," "," ") THEN sy:=ifsy ELIF word=ALFA("t","h","e","n"," "," "," "," "," "," ") THEN sy:=thensy ELIF word=ALFA("e","l","s","e"," "," "," "," "," "," ") THEN sy:=elsesy ELIF word=ALFA("w","h","i","l","e"," "," "," "," "," ") THEN sy:=whilesy ELIF word=ALFA("d","o"," "," "," "," "," "," "," "," ") THEN sy:=dosy ELIF word=ALFA("b","e","g","i","n"," "," "," "," "," ") THEN sy:=beginsy ELIF word=ALFA("e","n","d"," "," "," "," "," "," "," ") THEN sy:=endsy ELIF word=ALFA("s","k","i","p"," "," "," "," "," "," ") THEN sy:=skipsy ELIF word=ALFA("v","a","r"," "," "," "," "," "," "," ") THEN sy:=varsy ELIF word=ALFA("c","o","n","s","t"," "," "," "," "," ") THEN sy:=constsy ELIF word=ALFA("p","r","o","c"," "," "," "," "," "," ") THEN sy:=procsy ELIF word=ALFA("w","r","i","t","e"," "," "," "," "," ") THEN sy:=writesy ELIF word=ALFA("g","o","t","o"," "," "," "," "," "," ") THEN sy:=gotosy ELIF word=ALFA("r","e","s","u","l","t","i","s"," "," ") THEN sy:=resultissy ELIF word=ALFA("v","a","l","o","f"," "," "," "," "," ") THEN sy:=valofsy ELSE sy:=ident FI ELIF digit(ch) THEN looked ahead := TRUE; n:=0; WHILE digit(ch) DO n:=n*10+ ABS ch - ABS "0"; ch:=getch OD; sy:=numeral ELIF ch=":" THEN ch:=getch; IF ch="=" THEN sy:=becomessy ELSE sy:=colon; looked ahead := TRUE FI ELIF ch=";" THEN sy:=semisy ELIF ch="." THEN sy:=stopsy ELIF ch="(" THEN sy:=open ELIF ch=")" THEN sy:=close ELIF ch="+" THEN sy:=plussy ELIF ch="-" THEN sy:=minussy ELIF ch="*" THEN sy:=timessy ELIF ch="/" THEN sy:=oversy ELIF ch="=" THEN sy:=eqsy ELIF ch="<" THEN # < # ch:=getch; IF ch=">" THEN # ...> # sy:=nesy ELIF ch="=" THEN sy:=lesy ELSE sy:=ltsy; looked ahead:=TRUE FI ELIF ch=">" THEN # > # ch:=getch; IF ch="=" THEN sy:=gesy ELSE sy:=gtsy; looked ahead:=TRUE FI ELSE error("in insymbol") FI; IF NOT looked ahead THEN ch:=getch FI ) # insymbol #; #-----------------------------------------------------------------------------# #syntax# PROC parser = CMD: BEGIN PROC pexp = EXP: ( PROC pexp3 = EXP: IF sy=open THEN insymbol; EXP e:=pexp; check(close, ") "); e ELIF sy=minussy THEN insymbol; HEAP EXPNODE:=UEXP(neg,pexp3) ELIF sy=ident THEN EXP e = HEAP EXPNODE:=word; insymbol; e ELIF sy=numeral THEN EXP e = HEAP EXPNODE:=n; insymbol; e ELIF sy=valofsy THEN insymbol; HEAP EXPNODE := pcmd ELIF sy=ifsy THEN insymbol; EXP e1:=pexp; check(thensy, "then in Conditional expn"); EXP e2:=pexp; check(elsesy, "else in Conditional expn"); EXP e3:=pexp; HEAP EXPNODE := IFEXP(e1, e2, e3) ELSE error("in pexp3"); SKIP FI; PROC pexp2 = EXP: ( LOC EXP e:=pexp3; WHILE sy=timessy OR sy=oversy DO OPR o = IF sy=timessy THEN times ELSE over FI; insymbol; e:= HEAP EXPNODE := BEXP(o, e, pexp3) OD; e ); PROC pexp1 = EXP: ( LOC EXP e := pexp2; WHILE sy=plussy OR sy=minussy DO OPR o = IF sy=plussy THEN plus ELSE minus FI; insymbol; e:=HEAP EXPNODE:=BEXP(o, e, pexp2) OD; e ); IF EXP e=pexp1; sy=eqsy OR sy=nesy OR sy=lesy OR sy=ltsy OR sy=gesy OR sy=gtsy THEN OPR o = IF sy=eqsy THEN eq ELIF sy=nesy THEN ne ELIF sy=lesy THEN le ELIF sy=ltsy THEN lt ELIF sy=gesy THEN ge ELSE gtsy FI; insymbol; HEAP EXPNODE := BEXP(o, e, pexp1) ELSE e FI ) # pexp #; PROC pdec = DEC: ( PROC pdec1 = DEC: IF sy=varsy THEN insymbol; IF sy=ident THEN DEC d=HEAP DECNODE:=word; insymbol; d ELSE error("no ident after var"); SKIP FI ELIF sy=constsy THEN insymbol; IF sy=ident THEN ALFA id=word; insymbol; check(eqsy, "no = after const ident"); HEAP DECNODE := CONSTDEC(id,pexp) ELSE error("no ident after const"); SKIP FI ELIF sy=procsy THEN insymbol; IF sy=ident THEN ALFA id=word; insymbol; check(eqsy,"no = after proc ident"); HEAP DECNODE := PROCDEC(id,pcmd) ELSE error("no id after proc"); SKIP FI ELSE NIL FI; IF sy=varsy OR sy=constsy OR sy=procsy THEN DEC d=pdec1; check(semisy, "no ; after declaration"); HEAP DECNODE := DECLIST(d,pdec) ELSE NIL FI ) # pdec #; PROC pcmd = CMD: IF sy=numeral THEN #labelled# LABEL label=n; insymbol; check(colon, "no : after label"); HEAP CMDNODE := LABCMD(label, pcmd) ELIF sy=ifsy THEN insymbol; EXP b=pexp; check(thensy,"then in parse cmd"); CMD g1=pcmd; check(elsesy,"else in parse cmd"); CMD g2=pcmd; HEAP CMDNODE := IFSTAT(b, g1, g2) ELIF sy=whilesy THEN insymbol; EXP b=pexp; check(dosy,"no do after while"); HEAP CMDNODE := WHILES(b,pcmd) ELIF sy=beginsy THEN PROC pcmd list = CMD: (LOC CMD g:=HEAP CMDNODE := SEMI(NIL,pcmd); WHILE sy=semisy DO insymbol; g:=HEAP CMDNODE := SEMI(g,pcmd) OD; g ); insymbol; DEC d=pdec; CMD blk = HEAP CMDNODE := BLOCK(d, pcmd list); check(endsy, "no end to block"); blk ELIF sy=skipsy THEN insymbol; NIL ELIF sy=resultissy THEN insymbol; HEAP CMDNODE := ONEEXP(resultissy,pexp) ELIF sy=writesy THEN insymbol; HEAP CMDNODE := ONEEXP(writesy,pexp) ELIF sy=gotosy THEN insymbol; CMD g = HEAP CMDNODE := n; insymbol; g ELIF sy=open THEN EXP lhs=pexp; check(becomessy, "no := after expn in pcmd"); HEAP CMDNODE := ASSIGN(lhs, pexp) ELIF sy=ident THEN ALFA id=word; insymbol; IF sy=becomessy THEN insymbol; HEAP CMDNODE := ASSIGN( HEAP EXPNODE := id, pexp) ELSE #a call # HEAP CMDNODE := id FI FI # pcmd #; insymbol; CMD c = pcmd; check(stopsy, "no . at end of program"); c END #parser#; #-----------------------------------------------------------------------------# # semantic domains # MODE EV = UNION( INT, LOCN ), # = Int + Locn # SV = INT, CONT = PROC( INT,STORE)ANS, # = IntxStore -> Ans # KONT = PROC(EV, INT,STORE)ANS, # = Ev -> IntxStore -> Ans # DCONT = PROC(ENV, INT,STORE)ANS; # = Env -> IntxStore -> Ans # MODE DV = EV, # it so happens # LOCN = STRUCT(INT l, dont care); OP = = (LOCN m,n)BOOL: l OF m = l OF n; MODE ANS = UNION( ALFA, REF ANSCELL); # Ans = Int x Ans + {wrong,finish}# MODE ANSCELL=STRUCT(INT v, ANS next); MODE STORE = PROC(LOCN)SV; # = Locn -> Sv # MODE VNV = PROC(ALFA)DV; # Ide -> Dv # MODE PNV = PROC(ALFA,CONT, INT,STORE)ANS; # Ide -> Cont -> IntxStore ->Ans # MODE LNV = PROC(LABEL, INT,STORE)ANS; # Numeral -> IntxStore -> Ans # MODE ENV = STRUCT( VNV vnv, PNV pnv, LNV lnv, KONT kont ); #-----------------------------------------------------------------------------# # semantics # PROC show = (ANS a)VOID: CASE a IN (ALFA w):FOR i TO UPB w DO print(w[i]) OD, (REF ANSCELL r): IF r ISNT NIL THEN print((" ",whole(v OF r,0),",")); show(next OF r) FI ESAC; PROC wrong = (STRING m)ANS: ( print((newline, m, newline)); ALFA("w", "r", "o", "n", "g", " ", " ", " ", " ", " ") ); PROC undefined = VOID: error(" undefined"); PROC eee = (EXP ex, KONT k, ENV e, INT f,STORE s)ANS: ( # : EXP -> KONT -> ENV -> INT x STORE -> ANS # #debug # print(" E["); CASE ex IN (BEXP b):(KONT rhs = (EV v1, INT f,STORE s)ANS: (KONT opr = (EV v2, INT f,STORE s)ANS: k( CASE v1 IN (INT i1):CASE v2 IN (INT i2):IF opr OF b = plus THEN i1+i2 ELIF opr OF b = minus THEN i1-i2 ELIF opr OF b = times THEN i1*i2 ELIF opr OF b = over THEN i1%i2 ELIF opr OF b = ne THEN IF i1=i2 THEN 0 ELSE 1 FI ELIF opr OF b = eq THEN IF i1=i2 THEN 1 ELSE 0 FI ELIF opr OF b = lt THEN IF i1 < i2 THEN 1 ELSE 0 FI ELIF opr OF b = le THEN IF i1 <= i2 THEN 1 ELSE 0 FI ELIF opr OF b = gt THEN IF i1 > i2 THEN 1 ELSE 0 FI ELIF opr OF b = ge THEN IF i1 >= i2 THEN 1 ELSE 0 FI ELSE error(" bad operator");SKIP FI OUT wrong(" int OPR non-int"); SKIP ESAC OUT wrong(" non-int OPR ???"); SKIP ESAC, f,s )# opr #; rrr(right OF b, opr, e, f,s) )# rhs #; #debug# print((" bopr",whole(opr OF b,0) )); rrr(left OF b, rhs, e, f,s) ), (UEXP u):(KONT opr = (EV v, INT f, STORE s)ANS: CASE v IN (INT i): k(-i, f, s) OUT wrong(" - nonInt") ESAC; #debug# print(" -"); rrr(son OF u, opr, e, f,s) ), (VAR v):k( (vnv OF e)(v), f, s), (INT n):k( n, f, s), (IFEXP if):(KONT cond = (EV v, INT f, STORE s)ANS: CASE v IN (INT i): IF i=1 THEN eee(e2 OF if, k, e, f, s) ELSE eee(e3 OF if, k, e, f, s) FI OUT wrong(" CondExp non-int") ESAC; #debug#print(" CondExp"); rrr(e1 OF if, cond, e, f, s) ), (CMD g):(KONT new rnv = (EV v, INT f, STORE s)ANS: # valof $g # k(v, f, s); CONT fail = (INT f, STORE s)ANS: wrong(" fail: fell out of valof"); #debug#print(" valof"); ENV new e=(vnv OF e, pnv OF e, lnv OF e, new rnv); ccc(g, fail, new e, f, s) ) ESAC ) # eee #; PROC lll = (EXP ex, KONT k, ENV e, INT f, STORE s)ANS: ( # EXP -> KONT -> ENV -> INT x STORE -> ANS # #debug# print(" L["); KONT check = (EV v, INT f, STORE s)ANS: CASE v IN (LOCN l): k(l, f, s) OUT wrong(" not left-value") ESAC; eee( ex, check, e, f, s) ) # lll #; PROC rrr = (EXP ex, KONT k, ENV e, INT f, STORE s)ANS: ( # EXP -> KONT -> ENV -> INT x STORE -> ANS # #debug# print(" R["); KONT deref = (EV v, INT f, STORE s)ANS: CASE v IN (INT i): k(i, f, s), (LOCN l): k( s(l), f, s) ESAC; eee( ex, deref, e, f, s) )# rrr #; PROC ddd = (DEC d, DCONT dc, ENV e, INT f, STORE s)ANS: ( # DEC -> DCONT -> ENV -> INT x STORE -> ANS # #debug# print(" D["); IF d IS NIL THEN dc(e, f, s) ELSE CASE d IN (VARDEC vd):(VNV new vnv = (ALFA id)DV: IF id = vd THEN LOCN(f,0) ELSE (vnv OF e)(id) FI; ENV new e = (new vnv, pnv OF e, lnv OF e, kont OF e); #debug# print(( " VAR ", vd[1])); dc( new e, f+1, s) ), (CONSTDEC cd):(KONT update env = (EV v, INT f, STORE s)ANS: ( CASE v IN (INT i):(VNV new vnv = (ALFA id)DV: IF id = id OF cd THEN i ELSE (vnv OF e)(id) FI; ENV new e = (new vnv, pnv OF e, lnv OF e, kont OF e); dc( new e, f, s) ) OUT wrong(" const id=non-int") ESAC ) # update env # ; # debug # print(" CONST"); rrr(e OF cd, update env, e, f, s) ), (PROCDEC pd):(PNV new pnv = (ALFA id, CONT ra, INT f, STORE s)ANS: IF id = id OF pd THEN ccc(g OF pd, ra, new e #recursion#, f, s) ELSE (pnv OF e)(id, ra, f, s) FI; ENV new e = (vnv OF e, new pnv, lnv OF e, kont OF e); #debug#print(" PROC"); dc( new e, f, s) ), (DECLIST l):(DCONT d2 = (ENV e, INT f, STORE s)ANS: ddd(right OF l, dc, e, f, s); #debug#print(" ;"); ddd(left OF l, d2, e, f, s) ) ESAC FI ) # ddd #; PROC ccc = (CMD g, CONT t, ENV e, INT f, STORE s)ANS: ( # : CMD -> CONT -> ENV -> INT x STORE -> ANS # # debug # print( " C[" ); IF g IS NIL #SKIP# THEN t(f,s) ELSE CASE g IN (ASSIGN a):(KONT do rhs = (EV v1, INT f,STORE s)ANS: ( KONT update = (EV v2, INT f,STORE s)ANS: ( CASE v1 IN (LOCN l):CASE v2 IN (SV v):(STORE new s =(LOCN ll)SV: IF ll=l THEN v ELSE s(ll) FI; t(f, new s) ) OUT wrong("try to store bad value") ESAC OUT wrong("try to update non-location") ESAC ); rrr(rhs OF a, update, e, f, s) ); # debug # print(":="); lll(lhs OF a, do rhs, e, f, s) ), (SEMI g1g2):(CONT g2 = (INT f, STORE s)ANS: ccc(right OF g1g2, t, e, f, s); #debug# print(";"); ccc(left OF g1g2, g2, e, f, s) ), (IFSTAT if):(KONT cond = (EV b, INT f,STORE s)ANS: CASE b IN (INT i): ccc(IF i=1 THEN gtrue OF if ELSE gfalse OF if FI, t, e, f, s) OUT wrong("if-cmd, non-int expn") ESAC; #debug#print(" IF"); rrr(b OF if, cond, e, f,s) ), (WHILES w):(KONT cond = (EV b, INT f,STORE s)ANS: ( CONT again = (INT f, STORE s)ANS: ccc(g, t, e, f,s); CASE b IN (INT i): IF i=1 THEN ccc(g OF w, again, e, f,s) ELSE t(f,s) FI OUT wrong("while, non-int expn") ESAC ); #debug# print(" WHILE"); rrr(b OF w, cond, e, f,s) ), (BLOCK b):(DCONT body = (ENV e, INT f,STORE s)ANS: # begin $d;$g end # ( LNV new lnv = (LABEL n, INT f,STORE s)ANS: ( PROC search=(CMD g, CONT t2)ANS: IF g IS NIL THEN (lnv OF e)(n,f,s) ELSE CASE g IN (SEMI g): ( CONT t1=(INT f,STORE s)ANS: ccc(right OF g,t2,new e,f,s); CASE right OF g IN (LABCMD lg):IF n=(l OF lg) THEN ccc(g OF lg,t2,new e,f,s) ELSE search(left OF g,t1) FI OUT search(left OF g, t1) ESAC ) OUT wrong("knotted cmd in block") ESAC FI # search #; #debug# print((" lnv(", whole(n,0), ")" )); search(g OF b, t) )# new lnv#; ENV new e=(vnv OF e, pnv OF e, new lnv, kont OF e); ccc(g OF b, t, new e, f, s) )# body #; #debug# print(( newline," block")); ddd(d OF b, body, e, f,s) ), (ALFA proc):(pnv OF e)(proc, t, f,s), # $r\*<2\*>[procid]$t# (LABCMD l):ccc(g OF l, t, e, f,s), (G0T0 n):(lnv OF e)(n, f,s), # $r[$n] # (ONEEXP eg): # resultis $e or write $e # IF tag OF eg = resultissy THEN rrr( e OF eg, kont OF e, e, f,s) ELIF tag OF eg = writesy THEN KONT do output = (EV v, INT f, STORE s)ANS: CASE v IN (INT i): HEAP ANSCELL := (i, t(f,s)) OUT wrong("write a non-int") ESAC; rrr( e OF eg, do output, e, f,s) ELSE error(" bad tag in ccc< tag,exp>"); SKIP FI ESAC FI ) # ccc #; CONT finish = (INT f, STORE s)ANS: ALFA("f", "i", "n", "i", "s", "h", " ", " ", " ", " "); VNV start vnv = (ALFA a)DV: (undefined; SKIP); PNV start pnv = (ALFA a, CONT ra, INT f, STORE s)ANS: (undefined; SKIP); LNV start lnv = (LABEL l, INT f, STORE s)ANS: (undefined; SKIP); KONT start kont = (EV v, INT f, STORE s)ANS: (undefined; SKIP); ENV start env = (start vnv, start pnv, start lnv, start kont); STORE empty store = (LOCN n)SV: (undefined; SKIP); show( ccc(parser, finish, start env, 0, empty store) ) )