Compiling Effectful
Terms to Transducers
Prototype Implementation ofMemoryful Geometry of Interaction

Koko Muroya
Toshiki Kataoka
Ichiro Hasuo(Dept. CS, Univ. Tokyo)

Naohiko Hoshino(RIMS, Kyoto Univ.)

LOLA (Vienna), July 13, 2014

Compiling Effectful
TtT!
Terms to Transducers(“Terms to Transducers”)

Prototype Implementation ofMemoryful Geometry of Interaction

Koko Muroya
Toshiki Kataoka
Ichiro Hasuo(Dept. CS, Univ. Tokyo)

Naohiko Hoshino(RIMS, Kyoto Univ.)

LOLA (Vienna), July 13, 2014

---- n resumptions.
--->. Therefor
seecoproducte.g. [5]),types
but also
becausecompilation(basedcomposinglylike bit= 1 the+ 1—callfor special
stand for a certain natur
nal semantics)
construction.
Theby
current
interpretation
thatisiscorrect
far frombytrivial.
One solution
soOur
Tool TtT use
Thisisdynama prelmentarily
theiveslicesthen[9],form
whicha basis
can beofthoughtof as an compilers.
additionaltT willsuch practicalof right,
memoryful
GoI. Our
toolin
French,seee.g.
on proof
dayer
reasonis: it’snets.
simply a lot of fun to“Terms
see higher-orderto Transducers”
Transducers”—andis implem
In
Fig.
1,
betweenm
exampleofthelimitationsof“memoryless
GoI”
manmputation in action—or GoI at work. We hope theparts: TtT Compiler and TtT S
inpresenceofcomputational
effects.
Considerthecallexpressions like Query:[be convinced by the following examples.
TtT Compiler implements
aluation of the term
The ones like the former
We express a transducer (wits,
DerivedandExecuted
Consider
the
term
P
in
(1)
from
a
transducer.
Speci
P = ( x : nat. x + x) (3 t 5) : nat(1)of the
type
Td
m
x
a
b:
terms
0

Our Tool TtT

erministic choice t in it. Its translation to a (three-state,ubtermtransducer
3 t 5 returns
5 nondeterministically.
Obvinistic)
LPM3: or
3⇥
N
!
P(3
⇥
N),
after
some
TtT
Compilerrm is expected
to yield 6 below
or 10 (butnot 8). However theplifications,is depicted(manually).

nterpretation can yield 8 too: in the interaction betweens x. x + x and 3 t 5, the value of the latter is queriedhich the subterm 3t 5 can answer differently. Here whatsome memory mechanism that allows the subterm 3t5
L3M N,N
L5Mit has made,h
Mr the= choicethat
andsumto stick tocpy
it.

ul” GoI Motivated by a similar (but more complinical challenge we encountered in the semantics of a.

(3)s a string diagram in the traced monoidal category of; the box L3M N,N L5M in (3)TtT
is theSimulator(equivalence class of)er (2), after suitably encoding messages like q or 3 asbers. The diagram (3) can be identified with a proof net
2
construction.” Specifically: notice a horizontal axis ofdesignated by [t ]—metype
Td m xLt0aM, bwhose= cu(xtransducer
include:Query(a top-le
where
m is theHaskellmona
previousx
forthea statespace, querya is theon
inpu[t@x]:pmeansobtained
the token
The transducerflatterclass of inexa
ecutedTheby TtT
Simulator,
5
and
phi
on
Fig.
2,
lin
ment
is
recorded.
Recallthattransducers
example, h; k_3; h me
1 The word “memory” here is alm
node and then an h nod
stick
to the former
functionslikesohas: toNdisting+N
before, these bookkeepinin a proof net; therefore
token. From line 1 to 4 imuch like in the dynamic
Let us discuss effect(U. Tokyo)
as depicted Muroya
by thelines

Overviewterms← λ-terms with algebraic effects

TtT Compiler ← memoryful GoI[Hoshino, —, Hasuo CSL-LICS ’14]
transducers← stream transducers

TtT Simulator
simulation
result3

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

semantics of linear logic proof [Girard ’89],•

semantics of functional programming•

token machine presentation [Mackie ’95]
“GoI implementation”!

•

compilation techniques and implementations•[Mackie ’95] [Pinto ’01] [Ghica ’07]

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ 0

succ

0
cut

5

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ 0

succ

0

succ

cut

q

0

succ

cut

0

cut

q

q

token machine semantics

succ

0
succ

cut

0

succ

cut

0

cut

1

0

5

succ

0

cut
0

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ

0

proof net style

cut

succ

0

string diagram stylein traced monoidal category
6

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ

0

proof net style

cut

succ

0

string diagram stylein traced monoidal categoryq
6

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ

0

proof net style

cut

q

succ

0

string diagram stylein traced monoidal category
6

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ

0

proof net style

cut

０

succ

0

string diagram stylein traced monoidal category
6

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine presentation [Mackie ’95]
succ

0

proof net style

cut

１

succ

0

string diagram stylein traced monoidal category
6

Muroya (U. Tokyo)

GoI is “memoryless”•

advantage: simplicity•

challenges

succ

•

additive connectives &,•computational effects

70

Muroya (U. Tokyo)

GoI is “memoryless”•

advantage: simplicity•

challenges

succ

•

additive connectives &,•computational effects

70

additive slices!
[Laurent ’01]

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here what
memory mechanism that allows the subterm 3t5
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similar
hallenge we encountered in the semantics of a

8

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type
The transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a trans

1 The word “memory” here is almost syn

stick to the former so as to distinguish fro

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm 3t5
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similar
hallenge we encountered in the semantics of a
q

8

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a trans

1 The word “memory” here is almost syn

stick to the former so as to distinguish fro

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xq
memory mechanismthat allows the subterm
ask3t5(left) x
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similar
hallenge we encountered in the semantics of a

8

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a trans

1 The word “memory” here is almost syn

stick to the former so as to distinguish fro

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ x3
memory mechanism that allows
the subterm
ask3t5(left) x
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similar
hallenge we encountered in the semantics of a

8

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish froq8

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a
5

8

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro
answer 5

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additionalof memoryful GoI. Our tool is ca
n proof nets.
Transducers”—and is implemented
ple of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that8 it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro
answer 5

answer 8
8

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additional
memoryful
GoI!tool is caof memoryful
GoI. Ourn proof nets.
[Hoshino, —, Hasuo!
Transducers”—andis implemented
ple of the limitations of “memoryless GoI” manCSL-LICS ’14]
parts:
TtT
Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callTtT Compiler implements the traon of the term
We express a transducer (with the e( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that8 it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro
answer 5

answer 8
8

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additional
memoryful
GoI!tool is caof memoryful
GoI. Ourn proof nets.
[Hoshino, —, Hasuo!
Transducers”—andis implemented
ple of the limitations of “memoryless GoI” manCSL-LICS ’14]
parts:
TtT
Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callThu., July 17
TtT Compiler implements
the traon of the term
11:45
- the eWe express a transducer(with( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

m 3 t 5 returns 3 or 5 nondeterministically. Obvixpected to yield 6 or 10 (but not 8). However thetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that8 it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a

type

Td m x a b=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro
answer 5

answer 8
8

Muroya (U. Tokyo)

nical novelty is systematic use of cos to the use of GoI, too. For example, it is longfor composing transducers, formul
munity that additive connectives in linear logic—
composing resumptions.
roduct types like bit = 1 + 1—call for special
etation that is far from trivial. One solution by soOur Tool TtT This is a preliminarces [9], which can be thought of as an additional
memoryful
GoI!tool is caof memoryful
GoI. Ourn proof nets.
[Hoshino, —, Hasuo!
Transducers”—andis implemented
ple of the limitations of “memoryless GoI” manCSL-LICS ’14]
parts:
TtT
Compiler and TtT Simula•challenge:
computational
effects
sence of computational effects. Consider the callThu., July 17
TtT Compiler implements
the traon of the term
11:45
- the eWe express a transducer(with( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

GoI is “memoryless”

idea:
equip
each
node
with
m 3 t 5 returns 3 or 5 nondeterministically. Obvitype Td m x a b“memory”
xpected to yield 6 or 10 (but not 8). Howeverthetation can yield 8 too: in the interaction between
x + x and 3 t 5, the value of the latter is queried
e subterm 3t 5 can answer differently. Here x.x
what+ xmemory mechanism that allows the subterm
ask3t5(left) x
hoice that8 it has made, and to stick to it.

x.x +3 t(but
5 more complioI Motivatedby xa similarask (right) x
hallenge we encountered in the semantics of a=(x, a)

where m is the Haskell monad thatfor a state space, a is the input type3The
t 5transducer obtained from aecuted by TtT Simulator, in a metic
ment is recorded. Recall that a transanswer 3
1 The word “memory” here is almost syn
stick to the former so as to distinguish fro
answer 5

answer 8
8

Muroya (U. Tokyo)

Memoryful GoI — Input
λ-terms with algebraic effects

terms

algebraic operations [Plotkin, Power ’03]
transducers!

nondeterministic choice• probabilistic choice• action on global state•

9

Muroya (U. Tokyo)

Memoryful GoI — Output
stream transducers (Mealy machines)
terms

transducersc

C = (X, X ⇥ A ! T (X ⇥ B), x0 2 X)
a0 /b1x1

x0

a0 /b2x2

string diagram stylec10(T = P)x0

B
A

automaton stylea0
Muroya (U. Tokyo)

Memoryful GoI — Output
stream transducers (Mealy machines)
terms

c

C = (X, X ⇥ A ! T (X ⇥ B), x0 2 X)

transducerscx0

a0 /b1
x1

x0

proof net style

10(T = P)

string diagram stylecA

automaton style

x0

B

a0

a0 /b2x2

a0
Muroya (U. Tokyo)

Memoryful GoI — Output
stream transducers (Mealy machines)
terms

c

C = (X, X ⇥ A ! T (X ⇥ B), x0 2 X)
T = P (x0 , a0 ) 7 ! {(x1 , b1 ), (x2 , b2 )}transducers

a0 /b1
x1

T =D

x0

a0 /b2x2

nondeterministic!
computation

(x1 , b1 ) 7! 1/4,
(x0 , a0 ) 7 !
(x2 , b2 ) 7! 3/4,
x0

a0 /b1
1
x1 4

a0 /b23
4 x2

11probabilistic!
computation
Muroya (U. Tokyo)

Memoryful GoI — Translation
terms

•

idea: resumptions + categorical GoI••[Abramsky, Haghverdi, Scott ’02]

use coalgebraic component calculus!

transducers[Barbosa ’03] [Hasuo, Jacobs ’11]•

composition operations for software components!

•(many-sorted) process calculus

12

Muroya (U. Tokyo)

Memoryful GoI — Translation
1. introduce component calculus over transducers!
!

2. define interpretation inductively L ` t : ⌧ M!

L ` t s: ⌧M= L ` t:!

) ⌧M • L ` s: M

3. prove soundness of interpretation L ` t : ⌧ M
13Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)
C

D

C

Tr(C)

D

↵({Ci }i2I )

F(C)

B

C
d

B
c

B
c

A

D
d

B

C

A

B

c
C

A

A

c
c
c

···

B
B
↵
· · · ci · · · cj · · ·AAA(↵: I-ary algebraic operation)

14

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)
sequential
compositionC

parallelcomposition

D

C

1
1 0
10
X,
X,
X ⇥ Y,ccd@Y ⇥ B !
A @X ⇥ A !
T (X ⇥ B),A···
T (Y ⇥ C),A @X ⇥ A ! T (X ⇥ B),A = @x0 2 X(x0 , y0 ) 2 X ⇥ Y
x0 2 Xy0 2 Y0

1 0

Y,(x0 , y0 )a1 /c1

a2 /c2(x1 , y1 ) (x2 , y2 )

C y0
d
B x0
c

a1 /b1

0D

1
X ⇥ Y,d@Y ⇥ C !
A···
T (Y ⇥ D),A = @(x0 , y0 ) 2 X ⇥ Y
y0 2 Y(x0 , y0 )Y,

c1 /d1(x1 , y0 ) (x0 , y1 )10

B x 0 D y0
c
d
A

C

A
15

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)

algebraiceffect!-modality
application

Tr(C)
C

B

( (
c

C

( (
A

B
B

c
A

C

B

c

F

=

A

B

=

Tr

↵({Ci }i2I )

F(C)

c
c
c

A

···

B
B
↵
· · · ci · · · cj · · ·AAA(↵: I-ary algebraic operation)

16

Muroya (U. Tokyo)

Memoryful GoI — Translation
1. introduce component calculus over transducers
!

B

C
d

B
c

B

!

c

A

D
d

B

C

A

B

c

A

cc
C

A

c

···

B
B
↵
· · · ci · · · cj · · ·AAA

2. define interpretation inductively L ` t : ⌧ M!

L ` t s: ⌧M= L ` t:!

) ⌧M • L ` s: M

3. prove soundness of interpretation L ` t : ⌧ M
17Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (interpretation L ` t : ⌧ M)
For a type judgement` t : ⌧ ( = x1 : ⌧1 , . . . , xn : ⌧n ),we inductively define
n

!

{

!

L ` t: ⌧M =N N ··· N
L ` t: ⌧M
N N ··· N

18.

Muroya (U. Tokyo)

In this section we first introduce the syntax (including
syste(c(x , n))(s) = the(x , typeLs(`)M(n),s),(c(x , n))(s)= (x we, LmM(n),s).
Lx : ⌧ , · · · , x by
: ⌧ the` x : ⌧operationalM=
followed
semantics (§3.2). Thenin §3.3
discusso
Initially, the S-transducer drf looks up the global stateespecially the reason for the diﬀerence fromthe calculus in (Selinger ahaves as an S-transducer Ls(`)M. At the same time, the SdrfHoq,
stores theincluding
value s(`) locallysome
using its internal
state. T
where
w : N !we; and
w : ; ! N aresome
unique Set-morphisms,
In§3.4
establish
propertiesonsafety
p
drf
looks
up
its
internalstate:
ifaninternal
state
is
x
,
and h : N + N ! N + N is
h . Here h is from Section 6, andbehaves following LnM without referring to global states.
wsubstitution,
and w are from weakeningof the GoIreduction
situation in Section
4.2.4. progress.
subject
andWe interpret ` ` := n : unit by an S-transducer
The combinator h corresponds to the unit of the monad .
w

1

1

n

n

i

···

h

i

w

0

w

w

0

0

w

w

w

···

w

`

s(`)

m

m

0

Memoryful GoI — Translation
···

0

S

···

S

`

S

L ` t : ⌧ M)
Def. For(interpretation` t : ⌧ ) and ` s : ⌧ , we define L ` t s : M by
···

c

n

`

0

e

`

c

asg`,n = ({xrun , xdone }, c0 , xrun ) : N _ N

where the SetS -morphism c0 on {xrun , xdone } ⇥ N is g

(c0 (xrun , m))(s) = (xdone , L1M(m), s[n/`])0where we write e for u (1 ⇥···N), e0 for (>N ⇥ N) v, c for(c(xdone , m))(s) = (xdone , L1M(m), s).
0u ( 3.1.
⇥ N)L Syntax(v(uN)M v. Here we omit`t:⌧)+M u) ( L⇥`s:⌧`+t sv): andM =c Lforsome obvious bijections like N ⇥··· (N + N) ⇠= N ⇥ N + N ⇥ N. Initially, ({xrun , xdone }, c0 , xrun ) updates a global state,after, ({xrun , xdone }, c0 , xrun ) does nothing. We note t
These S-transducers are from dereliction and0 contraction
of
the
c
c0
right handof
sideHoqcan be any
GoI interpretation of a con
Definition
3.1(Typesof
Hoq).
Thethetypes
are:
GoI situation given in Section 4.2.4. We enotethat the component0
For example, the GoI interpretation of the following p
cpy consists of c and c0 .
···intuitionistic logic
For , x : ⌧ ` t : , we define L ` x : ⌧. t : ⌧ ) M by
Q = ( x : nat. x + (` := 3); x) (! `) : nat

A, B

::=

d

A)B
n-qbit | ! A |! A ! B | ⊤linear| A logic"B |A+B ,···dwith conventions qbit :≡ 1-qbit and···L ` x : ⌧. t : ⌧ ) M =hbit :≡ ⊤ +L ,x:⌧ `t: M

Here n ∈ N is a natural number.
···
d0

···

d0

whereDefinitiond and d0 are S-transducers
from N to
N Hoq).
given by d The=
3.2(Terms
of
terms
of
Hoq
are:
19
0
Muroya (U. Tokyo)u (u ⇥ N) F v v and d = u F u (v ⇥ N) v. They are from`t:⌧is an applicatio
followed by co( = x1 : ⌧1 , · · · , xn : ⌧n ),we inductively define an S-transducer

Memoryful GoI — Translation
L ` t : ⌧ M : N⌦(n+1) _ N⌦(n+1)

where N⌦(n+1) is the (n+1)-fold tensor product of N, i.e., (n+1)fold direct sum of N. First, we give GoI interpretation of constants,t : ⌧ M) and the lambda abstraction. We
variables, theLterm`application
Def. (interpretationinterpret natural numbers, summation and variables as follows:w

L ` n : natM =

···

w

kn

h

w0

w0
···
w

L , x : nat, y : nat ` x + y : natM =

h

···

w

sum
w0

···

w0

w

i 1
···

Lx1 : ⌧1 , · · · , xn : ⌧n ` xi : ⌧i M =

h
w0

w
···
···

w0

w
w0

w
···

w0

···

where w0 : N !S ; and w : ; !S N are unique SetS -morphisms,
and h : N + N ! N + N is
h20 . Here h is from Section 6, and0

GoI interpreta
and N be cou
algebraic oper
on , which indrf

called genericassignment ` :simplicity, we
location ` and
We interpre

drL ` t + s : natM = L ` ( xy : nat. x + y) t s : natM···

F (N ⌦ · · · ⌦where the Set(

Initially, the S
haves as an Sdrf ` stores thedrf ` looks up
Muroya(U. Tokyo)
behavesfollow

Memoryful GoI — Translation
1. introduce component calculus over transducers
!

B

C
d

B
c

B

!

c

A

D
d

B

C

A

B

c

cc
C

c

A

A

···

B
B
↵
· · · ci · · · cj · · ·AAA

2. define interpretation inductively L ` t : ⌧ Mn{!

L ` t: ⌧M =!

N N ··· N
L ` t: ⌧M
N N ··· N

3. prove soundness of interpretation L ` t : ⌧ M
21Muroya (U. Tokyo)

3. The categorical interpretation of a closed term t of a type ⌧ bijectively corresponds to an equivalence class of a partial equivalence relation J⌧ K where J⌧ K is the categorical interpretationof the type ⌧ . We choose a Res(T )-morphism on N that represents the equivalence class, and then, we extract a T -transducer
LtM : N _ N that represents the Res(T )-morphism on N.

5

3. sumhhn,

Memoryful GoI — Translation

4. k3 a5. sumThm. (soundness)lgebraicve them:d proofs

ilize thecategory
the SKa precise
s. Since
considerPer(T ).
undness

As a whL( xy :
that the Ginteracti
computeWe call the T -transducer LtM GoI interpretation of a term t.
We extracted GoI interpretation so that the next theorem holds.
Theorem 6.2 (Soundness). For closed terms t and s of type ⌧ ,• If t ⇡ s, then ([LtM], [LsM]) 2J⌧ K.

• If t ⇡ s and ⌧ is the base type nat, then LtM 'T
N,N LsM.

where [LtM] is the Res(T )-morphism represented by LtM, and wewrite t ⇡ s when the equation holds in the extension of thecomputational lambda calculus. For example, we havev (3 t 5) ⇡ v 3 t v 5,3t5t3⇡3t5⇡5t3

for any value v when the extension of the computational lambda
calculus has nondeterminism.

7.

GoI Interpretation of Algebraic Effects

7.1

Memoryless GoI Interpretation
22

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)transducers

resumptions

[ [

B

B

c
A

c

A

behavioral!
equivalence

23

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)transducers

resumptions

[ [

B

B

c
A

c

A

behavioral!
equivalence

GoI situation

23✓(Res(T ), ;, , Tr),F, J0 , J0 , J0 u, J0 v◆

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)transducers

resumptions

[ [

B

B

c
A

c

A

behavioral!
equivalence

C
d

B
c

B
c

A

D
d

B

C

A

c
C

A

GoI situation✓(Res(T ), ;, , Tr),F, J0 , J0 , J0 u, J0 v

B
cc

23

A

c

···

◆

:N+N⇠
=N:
u:N⇥N⇠=N:v
Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)
resumptions
GoI situation✓(Res(T ), ;, , Tr),F, J0 , J0 , J0 u, J0 v◆

partial equivalence relations (per’s)
on resumptions
cartesian closed category Per(T )categorical GoI!
[Abramsky,!
Haghverdi, Scott ’02]!
realizability

24

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)
resumptions
GoI situation✓(Res(T ), ;, , Tr),F, J0 , J0 , J0 u, J0 v◆

partial equivalence relations (per’s)
on resumptions
cartesian closed category Per(T )monadon Per(T )categorical GoI!
[Abramsky,!
Haghverdi, Scott ’02]!
realizability

24

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)partial equivalence relations (per’s)transducers resumptions
on resumptions
cartesian closed category Per(T )monad on Per(T )denotationalsemantics

J` t : ⌧ K = equivalence class ofJ⌧ K 2 Per(T )25

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)partial equivalence relations (per’s)transducers resumptions
on resumptions
cartesian closed category Per(T )monad on Per(T )denotationalsemantics

L` t : ⌧ M

J` t : ⌧ K = equivalence class ofJ⌧ K 2 Per(T )25

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)partial equivalence relations (per’s)transducers resumptions
on resumptions
cartesian closed category Per(T )monad on Per(T )denotationalsemantics

L` t : ⌧ M

J` t : ⌧ K = equivalence class ofJ⌧ K 2 Per(T )25

Muroya (U. Tokyo)

Memoryful GoI — Translation
proof (soundness)partial equivalence relations (per’s)transducers resumptions
on resumptions
cartesian closed category Per(T )monad on Per(T )denotationalsemantics

L` t : ⌧ M

J` t : ⌧ K = equivalence class ofJ⌧ K 2 Per(T )25

Muroya (U. Tokyo)

specific; currently
it supports
the powerset
monad (nondeterminof simplicity:
it allows
us to analyze
complicatedhigher-order 34ism) and the distribution monad (probability).
computation in the elementary terms of nodes and edges in graphs 5(or: TtT
linksasandedges in proof
The samenature,a Prototype
We nets).
emphasizethat what
ourhowever,tool TtT posescur- 6certainlimitations
use of use
GoI,whatsoever:too. For example,
long 7
rentlydoes is oftonothepractical
after all it istranslatesinan-term—that
may connectives
well be simply
expressed
as 8
known
theeffectfulcommunitythat additivein linearlogic—
Haskell program—to
anotherthat is way
more 9and asimilarly
coproduct types
likeHaskell
bit =program
1 + 1—callfor special
10complicated
and
runs
more
slowly.
Neverthelesswebelieve
thisiscare in GoI interpretation that is far from trivial. One solution by so-11
a worthwhile
venture,the following
three reasons.
calledadditive slices[9],forwhich
can be thoughtof as an additional12
The
first
reasonistheoretical:
ourmemoryful
GoI framework 13“memory” layer on proof nets.
in [8] seems to be a useful theoretical tool that gives us in- 14
Anotherexample of the limitations of “memoryless GoI” mansights into higher-order computation with effects. Automating the 15
ifestsitself in presenceof computational
effects.
the call-16
translation—that
is painfullycomplicatedwhenConsider
done by hand—by-valueevaluationof theterm
17will hencemeet sometheoreticians’
needs.

+-.gory C------>
withdd<42,137>
suitable additional
structures. What we do in [8] is| |Query:[ [3]|_|5 @ * ]category| |as C theh;k_3; h of resumptions, i.e. transducers modulo a suitequivalence.
This in fact is already done in [2]: our te| |behavioral[ [3]|_|5@ * ]:Answer| |nical ---dd<42,3>---> use of component calculi—those cal
novelty
is systematic| |for [composing[3|_|5] @ transducers,
Just (Left (*))]:Answerin coalgebraic terms—
formulated| | ---- dd<42,3> --->
composing resumptions.
| Result: 3 / State: Just (Left (*))‘-.
---- dd<42,137> --->Our
Tool
TtT This is a preliminary report on the implementa|
Query:[ 3|_|[5] @ * ]Our tool is called TtT—short for “Term|of memoryfulh; k_5; GoI.
himplemented in Haskell. It consists of|Transducers”—and[ 3|_|[5] @ * is]:Answer|parts:---dd<42,5> --->
TtT Compiler
and TtT Simulator.
B|C [TtT[3|_|5]@ Just(Right (*))]:Answer
Compiler
implements
the translation
sketched in the ab| d ---- Bdd<42,5>--->
B·
D transducer (with
B T )Bas a Haskell prog
B the· · effectWe express↵
Result:5c / aState:
Just(Right
(*))
c
c ···
··· c
cc

Memoryful GoI — Summary
terms

18
The second
speculative
P = reason( xis: nat.
x + x)but(3practical:t 5) : wenatwish to fol-(1)low the path of [3, 4, 10, 11] and use memoryful GoI as a compilawhere
subtermto3hardware.
t 5 returns
3 orcase
5 nondeterministically.
Obvitionthe
technique
In ourthis will specifically mean
to thetaketerm
hardwarethat natively
supportsthe(but
effectandHowevercompilingously
is expected
to yield
6 or 10
notT ,8).
thewith T -algebraic
it. Doingfor emerging
comusual -terms
GoI interpretation
caneffects
yield 8to too:in thesointeraction
betweenputing paradigms
probabilistic
andvaluequantumprogrammingwill
the subterms
x. x +likex and
3 t 5, theof thelatter is queried
havepractical
impacts—not
only
becauseprograms Herewill exetwice,
to bigwhich
the subterm
3t 5 cananswerdifferently.
whatcute faster(seememory
e.g. [5]),mechanism
but also because
the compilation(basedis needed
is somethat allows
the subterm
3t5
on denotational semantics) is correct by construction. The current
to remember the choice that it has made, and to stick to it.
toy tool of TtT will then form a basis of such practical compilers.
The thirdGoI
reasonMotivatedis: it’s simplyof fun (butto seemore
higher-order“Memoryful”
by aalotsimilarcomplieffectful
computation
in weaction—or
GoI atinwork.
We hope thecated)
technical
challenge
encountered
the semantics
of areader will be convinced by the following examples.

B the type Tdd m x a b:
of
c

type
A

A

C

A

C

c

A

i

A

···

j

A

for m
3 t(x,
5 b)
Td Figurem x a1. bSimulation= (x,Result
a) ->
A

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
for a statemore
space,
a is thetypeinandb the output
type.
around—or
precisely,
aninputedge e.g.
(3) consistsof |N|-many“pipes”
andtransducer
a token goes
through fromthe n-th—and
this is denotedbythenTheobtainedan (effectful)-term is---n --->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedby TtT
Simulator,
in a meticulous
way where
every
stand
forisarecorded.
certain natural
number.
We howeverhere
chose
to supplement
Recallthat a transducer
is muchlike a p

use coalgebraic component calculus

transducers{

mentarily use the dynamic algebra notation (g for left and d forright,
in wordFrench,see e.g. here
[9, 11]),for readability
andwithefficiency.
1 The“memory”
is almostsynonymous“internal states”
In
Fig.
1,
betweenmovements
---n
--->
of
the
token are ef
stick to the former so as tondistinguish from states as a computational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former
for the token’s entrance to and exit··· N
N N stand` t : ⌧ M = Specifically, p:[t@x]—with a subterm t0 of t
Transducers, Derived and Executed Consider the term P in (1)from La transducer.
L ` t: ⌧Mwith nondeterministic choice t in it. Its translation to a (three-state,
designated by [t0 ]—means: the token entered to (a copy of) the
N N ··· N
nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after sometransducer Lt0 M, whose
current state is x, at its port p. Typical ports
manual simplifications, is depicted below (manually).
include: Query (a top-level query) and Answer x (an answer tothe previous query on x; see Fig. 2, lines 24 and 44). Similarly,[t@x]:p means the token departed from the port p.
The latter class of expressions like h; k_3; h on Fig. 1, line
5 and phi on Fig. 2, line 3 are referred to as bookkeeping. For
cpy
sum
h
LPM = L3M N,N L5M
example, h; k_3; h means the token traversed an h node, a k3
node and then an h node. The definition of these nodes (as purefunctions like h : N + N ! N + N) is found in [8]. As we noted.
(3)
26 before, these bookkeeping nodes correspond to logical connectives
MuroyaThe figure is a string diagram in the traced monoidal category of
in a proof net; therefore they change the number
carried(U.
byTokyo)thetion of the token; a state transition of a token machine
hence is correct by construction and compositional. The cons
ovement of the token, from one position to another. Ittion of the denotational model relies on the categorical axioma
hat the underlying proof net—the “graph” on which thetion of GoI by Abramsky, Haghverdi and Scott [1, 2]: it allow
s around—is static and remains unchanged.
to derive a Cartesian closed category from a traced monoidal
moryless nature of GoI is a big advantage in view
“Termsto CTransducers”
gorywith suitable additional structures. What we do in [8] is
ty: it allows us to analyze complicated higher-order
as C the category of resumptions, i.e. transducers modulo a sui
n in the elementary terms of nodes and edges in graphs
behavioral equivalence. This in fact is already done in [2]: ourd edges in proof nets). The same nature, however, poses
nical novelty is systematic use of component calculi—those catations to the use of GoI, too. For example, it is longfor composing transducers, formulated in coalgebraic term
e community that additive connectives in linear logic—
composing resumptions.
ly coproduct types like bit = 1 + 1—call for special
interpretation that is far from trivial. One solution by soOur Tool TtT This is a preliminary report on the implement
ive slices [9], which can be thought of as an additionalof memoryful GoI. Our tool is called TtT—short for “Termayer on proof nets.
Transducers”—and is implemented in Haskell. It consists o
example of the limitations of “memoryless GoI” manparts: TtT Compiler and TtT Simulator.
in presence of computational effects. Consider the callTtT Compiler implements the translation sketched in the aaluation of the term
We express a transducer (with the effect T ) as a Haskell pro
P = ( x : nat. x + x) (3 t 5) : nat(1)of the type Td m x a b:

Our Tool TtT

λ-terms witheffects

terms

TtT Compiler

memoryful GoI

transducers

ubterm 3 t 5 returns 3 or 5 nondeterministically. Obvirm is expected to yield 6 or 10 (but not 8). However thenterpretation can yield 8 too: in the interaction betweens x. x + x and 3 t 5, the value of the latter is queriedhich the subterm 3t 5 can answer differently. Here whatsome memory mechanism that allows the subterm 3t5
r the choice that it has made, and to stick to it.

ul” GoI Motivated by a similar (but more complinical challenge we encountered in the semantics of a

Haskell programtype

Td m x a b=(x, a) -> m (x, b)

where m is the Haskell monad that corresponds to T , x is thefor a state space, a is the input type and b the output type.
The transducer obtained from an (effectful) -term is theecuted by TtT Simulator, in a meticulous way where every mment is recorded. Recall that a transducer here is much like a

TtT Simulator

simulation
stick to the former so as to distinguish from states as a computational e
result1 The word “memory” here is almost synonymous with “internal states

27

Muroya (U. Tokyo)

4526 6,lines
that
6, 8, 8,10 as possible(duplica-weyields8, 8,
10 yields
as possible
outcomes(duplicaInstead
ofoutcomes
pictorial presentation,onof 8 isfinal
due todifferent
statesofTtT
theSimulatortransducer).
withand observe its dyna
different
statesof the final
transducer).

lation result of LPM for P in (1) consists o
Our
Tool
TtT
—
Demonstration
mulation
Resultspresent actual
simulation
forsuccessfu
sims We present
actualWe
simulation
results
forassimand 10
possibleresults
outcomes,for+ f11)in( Fig.
x. 3 t2.5) w
writtenas 3|_|5in Fig. 1;( x.inx)
1thein1;termFig.
er terms:
3t5, written
asand
3|_|5
Fig.
and(2.(f. fx.0 x)

secondNondetExample = Apply,137>--->dd<42,137> --->---(Abst "f" $ sumLambda
idOne = Apply
threeOrFive= [3|_|5](Apply (Variable "f") (Const 0))|_|5]@ Nothing]
Query:[@ (AbstNothing]"x" $ Variable"x")(Apply (Variable "f") (Const 1))
Oplus (Const 3) (Const 5))
42,137>--->dd<42,137> (Const-.
------> 1)(Abst "x" $ Oplus (Const 3) (Const 5))[3]|_|5@ * ] [3]|_|5 @ * ]|Query:[;| hh; k_3; h
5| @ * ]:Answer[ [3]|_|5 @ * ]:Answer
42,3>
--->
|
---- dd<42,3> --->@| Just(Left (*))]:Answer[ [3|_|5]@ Just(Left (*)) ]:Answer,3>---> dd<42,3> --->
| ---tate:
Just3 (Left(*))Just (Left (*))
Result:/ State:42,137>--->-.
---- dd<42,137> --->
3|_|[5]@*]|
Query:[ 3|_|[5] @ * ];| hh; k_5; h] @ * ]:Answer|[ 3|_|[5] @ * ]:Answer 28
42,5> --->
Muroya (U. Tokyo)

4526 6,lines
that
6, 8, 8,10 as possible(duplica-weyields8, 8,
10 yields
as possible
outcomes(duplicaInstead
ofoutcomes
pictorial presentation,onof 8 isfinal
due todifferent
statesofTtT
theSimulatortransducer).
withand observe its dyna
different
statesof the final
transducer).

lation result of LPM for P in (1) consists o
Our
Tool
TtT
—
Demonstration
mulation
Resultspresent actual
simulation
forsuccessfu
sims We present
actualWe
simulation
results
forassimand 10
possibleresults
outcomes,for+ f11)in( Fig.
x. 3 t2.5) w
writtenas 3|_|5in Fig. 1;( x.inx)
1thein1;termFig.
er terms:
3t5, written
asand
3|_|5
Fig.
and(2.(f. fx.0 x),137>--->dd<42,137> --->---|_|5]@ Nothing]
Query:[[3|_|5]@ Nothing ]42,137>--->dd<42,137> --->-.
---[3]|_|5@ * ] [3]|_|5 @ * ]|Query:[;| hh; k_3; h
5| @ * ]:Answer[ [3]|_|5 @ * ]:Answer
42,3>
--->
|
---- dd<42,3> --->@| Just(Left (*))]:Answer[ [3|_|5]@ Just(Left (*)) ]:Answer,3>---> dd<42,3> --->
| ---tate:
Just3 (Left(*))Just (Left (*))
Result:/ State:42,137>--->-.
---- dd<42,137> --->
3|_|[5]@*]|
Query:[ 3|_|[5] @ * ];| hh; k_5; h] @ * ]:Answer|[ 3|_|[5] @ * ]:Answer 29
42,5> --->of 4526 lines that yields 6, 8, 8, 10 as possible outcomes (duplication of 8 is due to different final states of the transducer).

Simulation Results We present actual simulation results for simpler terms: 3t5, written as 3|_|5 in Fig. 1; and ( x. x) 1 in Fig. 2.

1
2
3
4

1
2
3
4
5
6
7
8
9

10
11
12
13
14
15
16
17
18

.
---- dd<42,137> --->|
Query:[ [3|_|5] @ Nothing ]+-.
---- dd<42,137> --->| |Query:[ [3]|_|5 @ * ]| |h; k_3; h| |[ [3]|_|5 @ * ]:Answer| |---- dd<42,3> --->
| | [ [3|_|5] @ Just (Left (*)) ]:Answer| | ---- dd<42,3> --->| Result: 3 / State: Just (Left (*))‘-.
---- dd<42,137> --->|
Query:[ 3|_|[5] @ * ]|h; k_5; h|[ 3|_|[5] @ * ]:Answer|---- dd<42,5> --->
| [ [3|_|5] @ Just (Right (*)) ]:Answer| ---- dd<42,5> --->
Result: 5 / State: Just (Right (*))

5
6
7
8
9

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Figure 1. Simulation Result for 3 t 5

The convention is as follows. A token carries a natural number naround—or more precisely, an edge e.g. in (3) consists of |N|-many“pipes” and a token goes through the n-th—and this is denoted by---- n --->. Therefore expressions like dd<42,137> in Fig. 1
stand for a certain natural number. We however chose to supplementarily use the dynamic algebra notation (g for left and d forright, in French, see e.g. [9, 11]), for readability and efficiency.
In Fig. 1, between movements ---- n ---> of the token are
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s entrance to and exitfrom a transducer. Specifically, p:[t@x]—with a subterm t0 of t
designated by [t0 ]—means: the token entered to (a copy of) thetransducer Lt0 M, whose current state is x, at its port p. Typical ports
include: Query (a top-level query) and Answer x (an answer tothe previous query on x; see Fig. 2, lines 24 and 44). Similarly,[t@x]:p means the token departed from the port p.

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

---- dd<42,137> --->
Query:[ [(\x.x) 1] @ ({_: *}, *) ]phi---- gdd<42,137> --->
Query:[ [\x.x] 1 @ {_: *} ]h
[ [\x.x] 1 @ {_: *} ]:Answer---- dgdd<42,137> --->
psi; psi; phi---- gdd<42,137> --->
Query:[ (\x.x) [1] @ * ]h[ (\x.x) [1] @ * ]:Answer---- dgdd<42,137> --->
psi; e; phi; phi---- dd<0,gdd<42,137>> --->
Query:[ [\x.x] 1 @ {_: *} ]
h; v
0 {
psi
---- dd<42,137> --->
Query:[ (\x.[x]) 1 @ * ]h[ (\x.[x]) 1 @ * ]:Query x---- <42,137> --->
phi
} 0
u; h
[ [\x.x] 1 @ {_: *} ]:Answer---- dd<0,d<42,137>> --->
psi; psi; e’; phi---- dd<42,137> --->
Query:[ (\x.x) [1] @ * ]h; k_1; h[ (\x.x) [1] @ * ]:Answer---- dd<42,1> --->
psi; e; phi; phi---- dd<0,d<42,1>> --->
Query:[ [\x.x] 1 @ {_: *} ]
h; v
0 {
psi
---- <42,1> --->
Answer x:[ (\x.[x]) 1 @ * ]h[ (\x.[x]) 1 @ * ]:Answer---- dd<42,1> --->
phi
} 0
u; h
[ [\x.x] 1 @ {_: *} ]:Answer---- dd<0,gdd<42,1>> --->
psi; psi; e’; phi---- dgdd<42,1> --->
Query:[ (\x.x) [1] @ * ]h[ (\x.x) [1] @ * ]:Answer---- gdd<42,1> --->
psi; phi; phi---- dgdd<42,1> --->
Query:[ [\x.x] 1 @ {_: *} ]h
[ [\x.x] 1 @ {_: *} ]:Answer---- gdd<42,1> --->psi
[ [(\x.x) 1] @ ({_: *}, *) ]:Answer---- dd<42,1> --->
Result: 1 / State: ({_: *}, *)Finally let us speak about making |N|-many copies of a transducer—
which interprets the ! modality that is implicit in the Girard
translation A ! B = ! A ( B. The bookkeeping functionv : N ! N ⇥ N in Fig. 2, line 18, splits |N|-many pipes into
|N| · |N|-many pipes; and lines 19 and 27 mean the token went
to the 0-th bunch of pipes, i.e., to the 0-th copy of the transducer[ (\x.[x]) 1 @ * ]. The state {_: *} that occur e.g. on line
17 stands for the function N ! 1, n 7! *, meaning that the state of
every copy of the transducer is the unique one *.

Acknowledgments

aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa

Thank are due to Ugo Dal Lago, Claudia Faggian, Dan Ghica andAkira Yoshimizu for useful discussions, and to the anonymous referees for useful comments. K.M. and I.H. are supported by Grantsin-Aid for Young Scientists (A) No. 24680001, JSPS; T.K. is supported by Grant-in-Aid for JSPS Fellows; and N.H. is supported by
Grants-in-Aid for Young Scientists (B) No. 26730004, JSPS.

References[1] S. Abramsky. Retracing some paths in process algebra. In CONCUR,
pages 1–17, 1996.
[2] S. Abramsky, E. Haghverdi, and P. Scott. Geometry of interaction andlinear combinatory algebras. Math. Struct. in Comp. Sci., 12:625–665,
2002.
[3] O. Fredriksson and D. R. Ghica. Seamless distributed computing fromthe geometry of interaction. In C. Palamidessi and M. D. Ryan, editors,
Trustworthy Global Computing, volume 8191 of Lecture Notes in
Computer Science, pages 34–48. Springer Berlin Heidelberg, 2013.
[4] D. R. Ghica. Geometry of synthesis: a structured approach to VLSI
design. In M. Hofmann and M. Felleisen, editors, POPL, pages 363–
375. ACM, 2007. ISBN 1-59593-575-4.
[5] D. R. Ghica, A. I. Smith, and S. Singh. Geometry of synthesis
IV: compiling affine recursion into static hardware. In M. M. T.
Chakravarty, Z. Hu, and O. Danvy, editors, ICFP, pages 221–233.
ACM, 2011. ISBN 978-1-4503-0865-6.

[6] J.-Y. Girard. Geometry of interaction 1: Interpretation of system F. In
S. V. R. Ferro, C. Bonotto and A. Zanardo, editors, Logic Colloquium’88 Proceedings of the Colloquium held in Padova, volume 127 ofStudies in Logic and the Foundations of Mathematics, pages 221–260.
Elsevier, 1989.
[7] I. Hasuo and N. Hoshino. Semantics of higher-order quantum computation via geometry of interaction. In LICS, pages 237–246, 2011.
[8] N. Hoshino, K. Muroya, and I. Hasuo. Memoryful geometry ofinteraction: From coalgebraic components to algebraic effects. In
CSL-LICS, 2014. To appear.
[9] O. Laurent. A token machine for full geometry of interaction. In
TLCA, pages 283–297, 2001.
[10] I. Mackie. The geometry of interaction machine. In R. K. Cytron
and P. Lee, editors, POPL, pages 198–208. ACM Press, 1995. ISBN
0-89791-692-1.
[11] J. S. Pinto. Implantation Parallèle avec la Logique Linéaire (Applications des Réseaux d’Interaction et de la Géométrie de l’Interaction).
PhD thesis, École Polytechnique, 2001. Main text in English.
[12] G. Plotkin and J. Power. Algebraic operations and generic effects.
Applied Categorical Structures, 11(1):69–94, 2003.

(4,526 lines)

Figure 2. Simulation Result for ( x. x) 1

Muroya (U. Tokyo)

Our Tool TtT

30

Muroya (U. Tokyo)

Our Tool TtT•

currently no practical use

30

Muroya (U. Tokyo)

Our Tool TtT•

currently no practical use•

nevertheless worthwhile•

helpful for studying higher-order effectful computations••

showing dynamics of token(speculative) basis of compiler for effectful computations•

following [Mackie ’95] [Pinto ’01] [Ghica ’07]

30

Muroya (U. Tokyo)

Our Tool TtT•

currently no practical use•

nevertheless worthwhile•

helpful for studying higher-order effectful computations••(speculative) basis of compiler for effectful computations••

showing dynamics of token

following [Mackie ’95] [Pinto ’01] [Ghica ’07]

fun to see GoI at work!
30

Muroya (U. Tokyo)