The Denotational Semantics of Programming Languages
R.D. Tennent
draft 2019-04-13
0. Introduction
This note is about a concurrent logic programming language and its rhizomic pattern-theoretic semantics.
These are introduced or revived in this note:
σCP = Stochastic Concurrent Prolog
RPT = Rhizomic Pattern Theory
RhiPE = Rhizomic Pattern[-theoretic] Environment
Earlier notes:
35. Calideas – species 0.1.1
48. Rhizomatic programming
71. σCP – Stochastic Concurrent Prolog
78. A σCP formulation of the path integral
1. σCP
See [71,78] above.
The form of the clause is
Head :- Guard | Probability / Body.
Here the convention of capitalized lexical units for logical variables is reverted to.
2. Rhizomic pattern theory (RPT)
Rhizomic pattern theory is a variant of pattern theory which replaces static components (configurations) of Grenander’s pattern theory (see [33,35,48] above) with dynamic ones, in which (diagrammatically) [see pictures below for examples]
- generators = circles (with identifiers inside)
- bonds are either of type
stream (of values) = small circles (ids outside)
unitary (a single value = small boxes
with identifiers outside - all connections (between generators and bonds) are directed arrows
- a bond has (at most) one input, but can have multiple outputs (the bond relation is equality)
- There a a grammar whereby
- each generator can be replaced by a collection of generators (thus the configuration structure is dynamic)
- a generator can split into other generators
- a generator with unitary bonds is temporary, as are unitary bonds themselves
Rhizomic pattern configurations have a biological flavor: molecules (terms) flowing through (directed) filaments connecting nodes (generators, predicates) via bonds (steam or unitary logical variables).
3. RhiPE (for σCP)
σCP | RPT | |
predicates | generators | |
logical variables (streams*, unitary) | bonds | |
terms | bond values | |
programs | (dynamic) configurations |
* [X|Xs]
4. Coin toss examples
// Fair toss …
toss([○|Xs]) :- 0.5 / toss(Xs).
toss([●|Xs]) :- 0.5 / toss(Xs).
prints([X|Xs]) :- print(X) | prints(Xs?).
:- toss(Xs),prints(Xs?).
see Figure 1, top
// … but the ‘toss’ process can run unbounded before a ‘orint’, so …
toss([○|Xs], [ok|OKs]) :- 0.5 / toss(Xs,OKs?).
toss([●|Xs], [ok|OKs]) :- 0.5 / toss(Xs,OKs?).
prints([X|Xs],OKs) :- print(X), OKs=[ok|OKs1] | prints(Xs?,OKs1).
// alternatively
prints([X|Xs],[ok|OKs]) :- print(X) | prints(Xs?,OKs).
:- toss(Xs,[ok|OKs]),prints(Xs?,OKs).
see Figure 1, bottom
// Here, the probabilities are changing …
toss([○|Xs], [ok(P)|OKs]) :- P? / toss(Xs,OKs?).
toss([●|Xs], [ok(P)|OKs]) :- Q is 1.0-P | Q? / toss(Xs,OKs?).
prints([○|Xs],[ok(0.6)|OKs]) :- print(○) | prints(Xs?,OKs).
prints([●|Xs],[ok(0.4)|OKs]) :- print(●) | prints(Xs?,OKs).
:- toss(Xs,[ok(0.5)|OKs]),prints(Xs?,OKs).
5. (Stochastic) processes and fields
Examples:
inv(B4?,B1),inv(B1?,B2),inv(B2?,B3),inv(B3?,B1),
B1=[○|_],B2=[●|_],B3=[○|_],B4=[●|_]
inv([○|Xs], [_,●|Ys]) :- inv(Xs?,Ys).
inv([●|Xs], [_,○|Ys]) :- inv(Xs?,Ys).
see Figure 2
vs.
inv([X|Xs], [_,Y}Ys]) :- flip(X?,Y), inv(Xs?,Ys).
flip(○,●).
flip(●,○).
see Figure 3
// add probabilities to make a percolation model
inv([○|Xs], [_,●|Ys]) :- 0.3 / inv(Xs,Ys).
inv([●|Xs], [_,○|Ys]) :- 0.7 / inv(Xs,Ys).
inv([○|Xs], [_,○|Ys]) :- 0.4 / inv(Xs,Ys).
inv([●|Xs], [_,●|Ys]) :- 0.6 /inv(Xs,Ys).
// create a percolation circle
perc_circle(N) :- perc_circle(N.B,B), B = [○|_]
perc_circle(0,B,B).
perc_circle(N,B_in,B_out) :-
N>0, N1 is N-1 | perc_circle(N1,B_in,B_out1), inv(B_out1,B_out).
:- perc_circle(5).
see Figure 4
// 2×2 lattice percolation
// ○ 0
// ● 1
lattice2x2([X|Xs],[Y|Ys], [_,X1|X1s],[_,Y1|Y1s]) :-
perc2to2(X?,Y?,X1,X2), perc(Xs?,Ys?,X1s,Y1s).
perc2to2(○,○,○,○) :- 0.2 / true.
perc2to2(○,○,○,●) :- 0.2 / true.
perc2to2(○,○,●,○) :- 0.3 / true.
perc2to2(○,○,●,●) :- 0.3 / true.
perc2to2(○,●,○,○) :- 0.1 / true.
perc2to2(○,●,○,●) :- 0.5 / true.
perc2to2(○,●,●,○) :- 0.2 / true.
perc2to2(○,●,●,●) :- 0.2 / true.
perc2to2(●,●,○,○) :- 0.1 / true.
perc2to2(●,●,○,●) :- 0.2 / true.
perc2to2(●,●,●,○) :- 0.1 / true.
perc2to2(●,●,●,●) :- 0.6 / true.
Figure 1 (to-be-redrawn: tbr)
Figure 2 (tbr)
Figure 3 (tbr)
Figure 4 (tbr)