Memoryful GoI
with recursion
Koko Muroya(Univ. Tokyo)

Naohiko Hoshino(Kyoto Univ.)

Ichiro Hasuo(Univ. Tokyo)

LOLA(Kyoto), July 5, 2015

Memoryful
GoI(1)
with recursion
Koko Muroya(Univ. Tokyo)

Naohiko Hoshino(Kyoto Univ.)

Ichiro Hasuo(Univ. Tokyo)

LOLA(Kyoto), July 5, 2015

Memoryful
GoI
(1)
with
recursion(2)
Koko Muroya(Univ. Tokyo)

Naohiko Hoshino(Kyoto Univ.)

Ichiro Hasuo(Univ. Tokyo)

LOLA(Kyoto), July 5, 2015

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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI [Hoshino, —, Hasuo ’14]
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
sound translation around—orfor a statemore
space,
a is thetypeinandb the output
type.
precisely,
aninputedge e.g.
(3) consistsof |N|-many“pipes”
andtransducer
a token goes
through fromthe n-th—and
this is denotedbythenTheobtainedan (effectful)-term isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).

transducers
LPM =L3M N,N L5M

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of

2

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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.
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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)theGeometry of Interaction (GoI)•

semantics of•semantics oflinear logic proofs [Girard ’89],{

functional programming languages“GoI interpretation”•

token machine representation [Mackie ’95]•

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

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x. x + x
x. x + x1

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x. x + x
x. x + x1

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x
x. x + x

31
t5

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x
x. x + x

31
t5

1

q

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x

q

x. x + x

ask (left) x

31
t5

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x

1

x. x + x

ask (left) x

31
t5
answer 1

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x
ask (left) x

x. x + x

1

31
t5
answer 1

ask (right) xq4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x
ask (left) x

x. x + x

1

31
t5
answer 1

ask (right) x
answer 1

1

4

Muroya (U. Tokyo)

Geometry of Interaction (GoI)•

token machine representation of GoI interpretation( x. x + x) 1

x.x.x
x+x
ask (left) x

2

x. x + x

1

31
t5
answer 1

ask (right) x
answer 1
answer 2
4

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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI [Hoshino, —, Hasuo ’14]
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
sound translation around—orfor a statemore
space,
a is thetypeinandb the output
type.
precisely,
aninputedge e.g.
(3) consistsof |N|-many“pipes”
andtransducer
a token goes
through fromthe n-th—and
this is denotedbythenTheobtainedan (effectful)-term isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).

transducers
LPM =L3M N,N L5M

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of

5

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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.
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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)theMemoryful GoI — Input
effectfulterms

CBV λ-terms with algebraic effects

algebraic operations [Plotkin, Power ’01]
transducers

nondeterministic choice M t N• probabilistic choice
M tp N• actions on global states
lookupl (Mv1 , . . . , Mv|Val| ) updatel,v (M )•6

Muroya (U. Tokyo)

Memoryful GoI — Output
effectful
terms

transducers

stream transducers (Mealy machines)(X, c : X ⇥ A ! T (X ⇥ B), x0 2 X) : A _ B

x0

a0 /b1x1

a0 /b2x2

string diagram style

c
7

T =P

x0

B
A

automaton stylea0
Muroya (U. Tokyo)

Memoryful GoI — Output
effectfulterms

stream transducers (Mealy machines)(X, c : X ⇥ A ! T (X ⇥ B), x0 2 X) : A _ B

x0transducers

a0Res(T/b1 ) a0 /b2
x1 sets x2
objects:

automaton styleT =Parrows: transducers modulo
behavioral
equivalence[(X, c : X ⇥ A ! T (X ⇥ B), x0 2 X)]' : A _ B
x0

B

string diagram style

c
A
7

a0
Muroya (U. Tokyo)

Memoryful GoI — Output
effectfulterms

stream transducers (Mealy machines)(X, c : X ⇥ A ! T (X ⇥ B), x0 2 X) : A _ B

T = P (x0 , a0 ) 7 ! {(x1 , b1 ), (x2 , b2 )}transducers

T = S = (1 + ( ) ⇥ S)S

computation with
global states

a0 /b1x1

x0

a0 /b2x2

nondeterministic
computation

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

T =D

x0

a0 /b1
1x1 4
8

a0 /b23
4 x2

probabilistic
computation
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI [Hoshino, —, Hasuo ’14]
effectfulterms

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 and3•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.

of the type Td m x a b:
type

for m
3 t(x,
5 b)
Td Figurem x a1. bSimulation= (x,Resulta) ->sound translation
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
based on Geometryof“pipes”
andtransducer
aInteraction
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 supplevia coalgebraic component
calculus
ment
Recallthat a transducer
is muchlike a p
mentarily use the dynamic algebra notation (g for left and d forin wordFrench,see e.g.Jacobs[9, 11]),for readability
efficiency.
[Barbosa right,’03][Hasuo,’11] andwith
1 The“memory”
here
is almostsynonymous“internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s entrance to and exit
Transducers, Derived and Executed Consider the term P in (1)from a transducer. Specifically, p:[t@x]—with a subterm t0 of twith nondeterministic choice t in it. Its translation to a (three-state,
designated by [t0 ]—means: the token entered to (a copy of) the
nondeterministic) transducer LPM : 3 ⇥ N !• P(3 ⇥ N), after sometransducer Lt0 M, whose current state is x, at its port p. Typical ports
composition operatorsfor software components
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,• (many-sorted) process
calculus[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)
9 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)thetransducers

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)

10

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
11

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)
trace
operator

Tr(C)

( (
c

C

( (
A

B
B

c
A

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

c

F

=

A

B

B

C

c
c
c

A

A

A

=

Tr

↵({Ci }i2I )

F(C)

C

B

lifted algebraic
operation

countable copy
operatorA···"
a0 /b1
x1

x0

⇤

"

a0 /b2 a0 /b01
y1
x2

y0

a0 /b02y2(↵: I-ary algebraic operation)
12

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)
trace
operator

Tr(C)

( (
2

A

=

q

x. x + x

B
c
A

( (

q

C

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

c

F

C

=

A

B

B

c

Tr

↵({Ci }i2I )

F(C)

C

B

lifted algebraic
operation

countable copy
operator

B
c

1
cc

A

1

···
q

A

A

A

1

"
a0 /b1
x1

x0

⇤

"

a0 /b2 a0 /b01
y1
x2

y0

a0 /b02y2(↵: I-ary algebraic operation)
12

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (component calculus)
trace
operator

Tr(C)

( (
c

C

( (
A

B
B

c
A

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

c

F

=

A

B

B

C

c
c
c

A

A

A

=

Tr

↵({Ci }i2I )

F(C)

C

B

lifted algebraic
operation

countable copy
operatorA···"
a0 /b1
x1

x0

⇤

"

a0 /b2 a0 /b01
y1
x2

y0

a0 /b02y2(↵: I-ary algebraic operation)
12

Muroya (U. Tokyo)

Memoryful GoI — Translation
Def. (translation L ` M : ⌧ M)

For a type judgement L ` M : ⌧ M ( = x1 : ⌧1 , . . . , xn : ⌧n )we inductively define{n

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

13.

Muroya (U. Tokyo)

ner

e
o
at

⌧
-

d

Memoryful GoI — Translation
L ` xi : ⌧i M =Def. (translation L ` M : ⌧ M)

...
u

d

d
...

L ` x : .M :! ⌧M =

L ,x :h` M : ⌧M
...

d0

v

...

d0

...
e

c

c

...

L ` M N : ⌧M =

L `M:

! ⌧M

2

x. x + x

L `N: M

...

e0

c0

q 1

q

1

1 q

c0
...

L ` rec(f :! ⌧, x : ). M :! ⌧M =

14

Muroya (U. Tokyo)L ` rec(f :! ⌧, x : ). M :! ⌧M =

Memoryful GoI — Translationc0udDef. (translation L ` M : ⌧ M)h ...

L ` xi : ⌧i M =w ... w

h

d

...

1
! ⌧, x :wci` M : ⌧M
...

w

0
0
w
w
0
v . . .d

...

d
...

i
L ,f :

w0 . . . w0

...

d0

...

d0

1
... ...
...

L ` op+ (M1 , . . . , Mar(op) ) : ⌧ M =L ` x : .M :! ⌧M =L ` op () : ⌧ M =op00

L ` M1 : ⌧ M
...

...

op+
. . . L ` Mar(op) : ⌧ M...

... ...

...
w

w

w0

w0

...

...

15
Figure 3. inductive definition ofthetranslation
L M
e
c
c

Muroya (U. Tokyo)

...

...

...

Memoryful GoI — Translation
c0

c0

c0

c0

Def. (translation L ` M : ⌧ M)

...

...

L ` n : natM =

h

w

w

w0

w0

kn

...

...

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

h

w

w0

w0

sum

h

...

(if x 6⌘ y)...

c

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

w

w

w

w0

w0

sum
c0

...

Figure 5. inductive definition of the 16translation L M

Muroya (U. Tokyo)

’s
d
ont
r,
a
d

theory given in [6]. The latter is (an almost full fragment of)
the Moggi’s equational theory of computational -calculus,
extended by algebraic operations, arithmetic primitives andrecursion.

Memoryful GoI — Translation

Theorem III.3 (soundness of L M). For closed terms M and Nof the base type nat, ` M = N : nat implies L` M : natM 'L` N : natM.

behavioral
equivalence
For simplicity we have restricted to algebraic
operations
withaccommodating
countable
arities is straightfor•finite(almostarities;
full fragmentof) Moggi’s equations
forcomputationalward(much lambda-calculus
like in [5], [10]). On top of soundness, we expect• equations for algebraic operations
n adequacy to hold too, against the operational semantics in [6].
M tM =M
Extension of our implementation tool TtT with recursion isE[opr(M1 , . . . , Mn )] = opr(E[M1 ], . . . , E[Mn ])future work, too.

ne

( x. M ) (N1 t N2 ) = ( x. M ) N1 t ( x. M ) N2

B. The Categorical Model

The translation L M extended with recursion (Def. III.2) is
17
Muroya (U. Tokyo)
backed up by a categorical model, too—this fact underlies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]:Answern --->|parts:---dd<42,5>
TtT Compiler
and TtT Simulator.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
the translation· ·implements
· N
N
N
--->
L `|WeM : ---⌧express
M = dd<42,5>atransducer(witheffect T ) as a Haskell prog
` M : ⌧Just
M
Result: 5 / LState:(Rightthe(*))
of the typeNTdN m· ·x· a
N b:

Memoryful GoI [Hoshino, —, Hasuo ’14]

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 can
answerdifferently.
what•cute 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.

{

effectful
terms

type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
sound translation around—orfor a statemore
space,
a is thetypeinandb the output
type.
precisely,
aninputedge e.g.
(3) consistsof |N|-many“pipes”
andtransducer
a token goes
through fromthe n-th—and
this is denotedbythenTheobtainedan (effectful)-term isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s
entrance to and exit
B
Cfrom a transducer. Specifically, p:[t@x]—with a subterm t0 of t
Transducers, Derived and Executed Consider the term P in (1)BdBto (a copy of) theD [t0 ]—means:
B by
B
···
with nondeterministic choice t in it. Its translation to a (three-state,
Bthe token
designatedentered↵cc···B· cj p.
nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somecctransducerc Lt0 M,d whose
current state
is x,· · ·atciits· ·port
Typical portscmanual simplifications, is depicted below (manually).
C (aAtop-levelA x (an answer toinclude:AQuery
query) and AAnswer
C A
the previous query on x; see Fig. 2, lines A
24 and 44). Similarly,
A[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)
18 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)thetransducers

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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).

transducers
LPM =L3M N,N L5M

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of

19

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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.
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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)the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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).

transducers
LPM =L3M N,N L5M

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of

19

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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.
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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)the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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

transducers
L3M N,N L5M

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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.
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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)thefix(F ) = F (F (F (· · · )))Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).
LPM =1 The word “memory” here is almost synonymous with “internal states”

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of19

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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s entrance to and exit
Transducers, Derived and Executed Consider the term P in (1)from a transducer. Specifically, p:[t@x]—with a subterm t0 of twith nondeterministic choice t in it. Its translation to a (three-state,
designated by [t0 ]—means: the token entered to (a copy of) the
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).
q
include: Query (a top-level query) and Answer x (an answer to1
the previous query on x; see Fig. 2, lines 24 and 44). Similarly,[t@x]:p means the token departed from the port p.
2
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 pureq .
functions like h : N + N ! N + N) is found in [8]. As we notedq1(3)19 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)thetransducers

fix(F ) = F (F (F (· · · )))x. x + x

1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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via coalgebraic component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s entrance to and exit
Transducers, Derived and Executed Consider the term P in (1)from a transducer. Specifically, p:[t@x]—with a subterm t0 of twith nondeterministic choice t in it. Its translation to a (three-state,
designated by [t0 ]—means: the token entered to (a copy of) the
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).
q
include: Query (a top-level query) and Answer x (an answer to1
the previous query on x; see Fig. 2, lines 24 and 44). Similarly,[t@x]:p means the token departed from the port p.
2
The latter class of expressions like h; k_3; h on Fig. 1, linecc 3 are referredc to as bookkeeping.
5
and
phi
on
Fig.
2,
line
For
cpy
sum
L3M
L5M
h
LPM =
N,N
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 pureq .
functions like h : N + N ! N + N) is found in [8]. As we notedq1(3)19 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)thetransducers

fix(F ) = F (F (F (· · · )))x. x + x

1···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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via extended coalgebraic
component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
The ones like the former stand for the token’s entrance to and exit
Transducers, Derived and Executed Consider the term P in (1)from a transducer. Specifically, p:[t@x]—with a subterm t0 of twith nondeterministic choice t in it. Its translation to a (three-state,
designated by [t0 ]—means: the token entered to (a copy of) the
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).
q
include: Query (a top-level query) and Answer x (an answer to1
the previous query on x; see Fig. 2, lines 24 and 44). Similarly,[t@x]:p means the token departed from the port p.
2
The latter class of expressions like h; k_3; h on Fig. 1, linecc 3 are referredc to as bookkeeping.
5
and
phi
on
Fig.
2,
line
For
cpy
sum
L3M
L5M
h
LPM =
N,N
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 pureq .
functions like h : N + N ! N + N) is found in [8]. As we notedq1(3)20 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)thetransducers

fix(F ) = F (F (F (· · · )))x. x + x

1···

Memoryful GoI with recursion
Def. (component calculus over transducers)
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

c
c
c

A

A
sequential
composition

parallelcomposition

B
B↵· · · ci · · · cj · · ·
A

A

A

trace
operator(↵: I-ary algebraic operation)

countable copy
operator
21···

lifted algebraic
operation
Muroya (U. Tokyo)

Memoryful GoI with recursion
Def. (extended component calculus)

i2I

Ci

“fixed point”
operatorcountable
parallelcomposition

Fix(C)
N⇥A

A

(

Fix

c1

A1

B2
c2

A2

N⇥A

A

=

B1

(

c

···

A
A
c

A

c

c

···

A
22

Muroya (U. Tokyo)

Memoryful GoI with recursion
Def. (extended component calculus)

i2I“fixed point”
operatorcountable
parallelcomposition

Ci

Fix(C)
N⇥A

A

(

Fix

c1

A1

B2
c2

A2

N⇥A

A

=

B1

(

c

···
c

A
c

c

···

A
c

A

c

c

···

A
22

Muroya (U. Tokyo)

“Fixed point” operator
Lem. ( Fix as a fixed point operator)
A
A

(

Fix

A

c

N⇥A

(

A

A

=

c

N⇥A

c

c

A

=:

···

Fix(c)

A

A

N⇥A

A

satisfiesc

Fix(c)AA'

Fix(c)

.

A

N⇥A
23

Muroya (U. Tokyo)

“Fixed point” operator
Lem. (two styles of “implementation”)
AuN⇥A
Fix(c)
v

N⇥A

A
u

'

N⇥A

N2 ⇥ A

c

c
N⇥A

v

c

c

...

Girard styleN2 ⇥ A

A

A
A

'

c0
A
u
N⇥A

N⇥A

d

c

N⇥A
u
N2 ⇥ AN2 ⇥ A

v

v

c

d0

A

A

Mackie style
A

N⇥A

A

24

Muroya (U. Tokyo)

“Fixed point” operator
Lem. (domain-theoretic characterization of Fix )Under the assumption that
• SetT is a Cppo-enriched category with Cppo-enriched (countable) cotuplings• compositions T of SetT is strict in the restricted form: f T ? = ? and? T (⌘Y g) = ? hold for any f : X ! T Y and g : X ! Y in Set• premonoidal structures X ⌦strict for any X in Set,⌦ X of SetT is locally continuous andit holds that:25

Muroya (U. Tokyo)

“Fixed point” operator
Lem. (domain-theoretic characterization of Fix )
A

A

(

Fix

c

N⇥A

(=

N⇥A

A

A
c

c

is a supremum of an !-chain

···

c

A
A

A

A

A

A

A

A

A

?

?

?

···

E

c
A

?

?

···

A

A

E

c
A

c

?

···

E ···

A

where (X, c : X ⇥ A ! T (X ⇥ B), x0 2 X) E (Y, c : Y ⇥ A ! T (Y ⇥ B), y0 2 Y )def.

(=) X = Y ^ x = y ^ c v d in SetT (X ⇥ A, X ⇥ B)
26

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
recursionThe
firstreasonistheoretical:
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.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
implements
the translation| ---- dd<42,5> --->We express
transducer
effect T ) as a Haskell prog
Result:5 / aState:
Just (with(Rightthe(*))

Memoryful GoI with recursion
effectfulterms

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 can
answerdifferently.
what•cute 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.

of the type Td m x a b:
type

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

where
m is the isHaskell
monad
thatcarries
corresponds
T , x isnthe t
The convention
as follows.
A tokena naturaltonumber
translation
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 isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via extended coalgebraic
component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.

Transducers, Derived and Executed Consider the term P in (1)with nondeterministic choice t in it. Its translation to a (three-state,nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somemanual simplifications, is depicted below (manually).

transducers
LPM =L3M N,N L5M

h

sum

cpy

.

(3)

The figure is a string diagram in the traced monoidal category of

27

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
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 aAtransducer. Specifically, p:[t@x]—with a subterm t0 of tA
designatedby [t0 ]—means: the token entered to (a copy of) thecc ···transducer
Lt0cM, whose
current state is x, at its port p. Typical portsA
include: Query (a top-level query) and Answer x (an answer toAthe 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
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
before, these bookkeeping nodes correspond to logical connectives
Muroyain a proof net; therefore they change the number
carried(U.
byTokyo)theMemoryful GoI — Translation
Def. (translation L ` M : ⌧ M)

For a type judgement L ` M : ⌧ M ( = x1 : ⌧1 , . . . , xn : ⌧n )we inductively define{n

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

28.

Muroya (U. Tokyo)

ner

e
o
at

⌧
-

d

Memoryful GoI — Translation
L ` xi : ⌧i M =Def. (translation L ` M : ⌧ M)

...
u

d

d
...

L ` x : .M :! ⌧M =

L ,x :h` M : ⌧M
...

d0

v

...

d0

...
e

c

c

...

L ` M N : ⌧M =

L `M:

! ⌧M

2

x. x + x

L `N: M

...

e0

c0

q 1

q

1

1 q

c0
...

L ` rec(f :! ⌧, x : ). M :! ⌧M =

29

Muroya (U. Tokyo)L ` rec(f :! ⌧, x : ). M :! ⌧M =

Memoryful GoI — Translationc0udDef. (translation L ` M : ⌧ M)h ...

L ` xi : ⌧i M =w ... w

h

d

...

1
! ⌧, x :wci` M : ⌧M
...

w

0
0
w
w
0
v . . .d

...

d
...

i
L ,f :

w0 . . . w0

...

d0

...

d0

1
... ...
...

L ` op+ (M1 , . . . , Mar(op) ) : ⌧ M =L ` x : .M :! ⌧M =L ` op () : ⌧ M =op00

L ` M1 : ⌧ M
...

...

op+
. . . L ` Mar(op) : ⌧ M...

... ...

...
w

w

w0

w0

...

...

30
Figure 3. inductive definition ofthetranslation
L M
e
c
c

Muroya (U. Tokyo)

...

...

...

Memoryful GoI — Translation
c0

c0

c0

c0

Def. (translation L ` M : ⌧ M)

...

...

L ` n : natM =

h

w

w

w0

w0

kn

...

...

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

h

w

w0

w0

sum

h

...

(if x 6⌘ y)...

c

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

w

w

w

w0

w0

sum
c0

...

Figure 5. inductive definition of the 31
translation L M

Muroya (U. Tokyo)

...

L ` M N : ⌧M =

L `M:

! ⌧M

L `N: M

Memoryful GoI with recursion...

Def. (translation L ` M : ⌧ M)
L ` rec(f :! ⌧, x : ). M :

e0

c0

c0
...

! ⌧M =
c0

Mackie style

u

d

...
d
...

A
c0
A
u
N⇥A

N⇥A

d

v

A
c

d

c

N⇥A
u
N2 ⇥ Av

N2 ⇥ A
N⇥A

d0

h
A

A

L ,f :! ⌧, x :v

d0` M : ⌧M
...

c

d0

...

d0

A

... ...

32

...

op+

...

Muroya (U. Tokyo)

’s
d
ont
r,
a
d

theory given in [6]. The latter is (an almost full fragment of)
the Moggi’s equational theory of computational -calculus,
extended by algebraic operations, arithmetic primitives andrecursion.

Memoryful GoI — Translation

Theorem III.3 (soundness of L M). For closed terms M and Nof the base type nat, ` M = N : nat implies L` M : natM 'L` N : natM.

behavioral
equivalence
For simplicity we have restricted to algebraic
operations
withaccommodating
countable
arities is straightfor•finite(almostarities;
full fragmentof) Moggi’s equations
forcomputationalward(much lambda-calculus
like in [5], [10]). On top of soundness, we expect• equations for algebraic operations
n adequacy to hold too, against the operational semantics in [6].
M tM =M
Extension of our implementation tool TtT with recursion isE[opr(M1 , . . . , Mn )] = opr(E[M1 ], . . . , E[Mn ])future work, too.

ne

( x. M ) (N1 t N2 ) = ( x. M ) N1 t ( x. M ) N2

B. The Categorical Model

The translation L M extended with recursion (Def. III.2) is33
Muroya (U. Tokyo)
backed up by a categorical model, too—this fact underlies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
recursionThe
firstreasonistheoretical:
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]:Answern --->|parts:---dd<42,5>
TtT Compiler
and TtT Simulator.
| [TtT[3|_|5]@ Just(Right (*))]:Answer sketched in the abCompiler
the translation· ·implements
· N
N
N
--->
L `|WeM : ---⌧express
M = dd<42,5>atransducer(witheffect T ) as a Haskell prog
` M : ⌧Just
M
Result: 5 / LState:(Rightthe(*))
Aof the typeNTdN m· ·x· a
N b:

Memoryful GoI recursion

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 can
answerdifferently.
what•cute 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.

{

effectful
terms

type

A

for cm3 t(x,c5
cb)
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
sound translation around—orfor a statemore
space,
a is thetypeinandb the output
type.
precisely,
aninputedge e.g.
(3) consistsof |N|-many“pipes”
andtransducer
a token goes
through fromthe n-th—and
this is denotedbythenTheobtainedan (effectful)-term isbased on Geometry---nof--->.
Therefore
expressions
like dd<42,137>
in Fig.
1 mo
ecutedbyInteraction
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
mentarilyusethedynamic
algebranotation
(g
for
left
and
d
for
via extended coalgebraic
component
calculus
right, in French, see e.g. [9, 11]), for readability and efficiency.
A

1 The word “memory” here is almost synonymous with “internal states”

In Fig.
1, former
between----fromn --->
token are ef
stick
to thesomovements
as to distinguishstates ofas athecomputational
expressions like Query:[ [3|_|5] @ Nothing ] and h; k_3; h.
BCThe ones like the former stand for the token’s entrance to and exit
0BdB
D a transducer.
B from
B p:[t@x]—with
Transducers, Derived and Executed Consider the term P in (1)···Specifically,asubterm
t
of t
B
↵
0
c
cby [t ]—means:·the· · ci token···
cdesignatedBdwith nondeterministic choice t in it. Its translation to a (three-state,· · · cj enteredto (a copy of) thecc0
nondeterministic) transducer LPM : 3 ⇥ N ! P(3 ⇥ N), after somec
A Lt M, Cwhose
isAx, at its port p. Typical ports
C
A transducerA
A current state
manual simplifications, is depicted below (manually).
include: Query (a top-level query)and Answer x (an answer toAA
the 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)
34 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)thetransducers

ExamplesL( x.x) (3 t0.4 5)M =35

Muroya (U. Tokyo)

ExamplesL( x.x) (3 t0.4 5)M =35

Muroya (U. Tokyo)

ExamplesL(rec(f, x).f x) 0M =36

Muroya (U. Tokyo)

Examplescase(inl1,1 (⇤) t inr1,1 (⇤), y.1, z.f x)

L(rec(f, x).if true t false then 1 else f x) 0M =37

Muroya (U. Tokyo)

of simplicity: it allows us to analyze complicated higher-ordercomputation in the elementary terms of nodes and edges in graphs(or: links and edges in proof nets). The same nature, however, posescertain limitations to the use of GoI, too. For example, it is longknown in the community that additive connectives in linear logic—
and similarly coproduct types like bit = 1 + 1—call for special
care in GoI interpretation that is far from trivial. One solution by socalled additive slices [9], which can be thought of as an additional
recursion“memory” layer on proof nets.
Another example of the limitations of “memoryless GoI” manifests itself in presence of computational effects. Consider the callby-value evaluation of the term

gory C with suitable additional structures. What we do in [8] is
as C the category of resumptions, i.e. transducers modulo a suit
behavioral equivalence. This in fact is already done in [2]: our tenical novelty is systematic use of component calculi—those cal
for composing transducers, formulated in coalgebraic terms—
composing resumptions.

Memoryful GoI recursionP=( x : nat. x + x) (3 t 5)

: nat

(1)

where the subterm 3 t 5 returns 3 or 5 nondeterministically. Obviously the term is expected to yield 6 or 10 (but not 8). However theusual GoI interpretation can yield 8 too: in the interaction between
the subterms x. x + x and 3 t 5, the value of the latter is queried
twice, to which the subterm 3t• 5 can answer differently. Here whatis needed is some memory mechanism that allows the subterm 3t5
to remember the choice that •it has made, and to stick to it.

{

effectfulterms

Our Tool TtT This is a preliminary report on the implementa
of memoryful GoI. Our tool is called TtT—short for “TermnTransducers”—andis implemented in Haskell. It consists ofparts: TtT N
Compiler
N · · · and
N TtT Simulator.
` M : ⌧M =TtT Compiler
the translation sketched in the ab
L ` Mimplements: ⌧M
We expressN a Ntransducer(with the effect T ) as a Haskell prog··· N
Aof the type Td m x a b:

L

type

Td m x a b

A

=

c
cb)
(x, a) -> cm (x,···Awhere m is the Haskell monad that corresponds to T , x is the tsound (& adequate) translation
for a state space, a is the input type and b the output type.
The transducer obtained from an (effectful) -term is thenbased on GeometryofbyInteraction
ecutedTtT Simulator, in a meticulous way where every moment is recorded. Recall that a transducer here is much like a p
via extended coalgebraic component calculus“Memoryful” GoI Motivated by a similar (but more complicated) technical challenge we encountered in the semantics of aA

1 The word “memory” here is almost synonymous with “internal states”

stick to the former so as to distinguish from states as a computational ef
B

C
d

B
c

B

transducers

c
A

38

A

D
d

B

C

A

B

c

cc
C

A

c

···

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

Muroya (U. Tokyo)

of simplicity: it allows us to analyze complicated higher-ordercomputation in the elementary terms of nodes and edges in graphs(or: links and edges in proof nets). The same nature, however, posescertain limitations to the use of GoI, too. For example, it is longknown in the community that additive connectives in linear logic—
and similarly coproduct types like bit = 1 + 1—call for special
care in GoI interpretation that is far from trivial. One solution by socalled additive slices [9], which can be thought of as an additional
recursion“memory” layer on proof nets.
Another example of the limitations of “memoryless GoI” manifests itself in presence of computational effects. Consider the callby-value evaluation of the term

gory C with suitable additional structures. What we do in [8] is
as C the category of resumptions, i.e. transducers modulo a suit
behavioral equivalence. This in fact is already done in [2]: our tenical novelty is systematic use of component calculi—those cal
for composing transducers, formulated in coalgebraic terms—
composing resumptions.

Memoryful GoI recursionP=( x : nat. x + x) (3 t 5)

: nat

(1)

where the subterm 3 t 5 returns 3 or 5 nondeterministically. Obviously the term is expected to yield 6 or 10 (but not 8). However theusual GoI interpretation can yield 8 too: in the interaction between
the subterms x. x + x and 3 t 5, the value of the latter is queried
twice, to which the subterm 3t• 5 can answer differently. Here whatis needed is some memory mechanism that allows the subterm 3t5
to remember the choice that •it has made, and to stick to it.

{

effectfulterms

Our Tool TtT This is a preliminary report on the implementa
of memoryful GoI. Our tool is called TtT—short for “TermnTransducers”—andis implemented in Haskell. It consists ofparts: TtT N
Compiler
N · · · and
N TtT Simulator.
` M : ⌧M =TtT Compiler
the translation sketched in the ab
L ` Mimplements: ⌧M
We expressN a Ntransducer(with the effect T ) as a Haskell prog··· N
Aof the type Td m x a b:

L

type

Td m x a b

A

=

c
cb)
(x, a) -> cm (x,···Awhere m is the Haskell monad that corresponds to T , x is the tsound (& adequate) translation
for a state space, a is the input type and b the output type.
The transducer obtained from an (effectful) -term is thenbased on GeometryofbyInteraction
ecutedTtT Simulator, in a meticulous way where every moment is recorded. Recall that a transducer here is much like a p
via extended coalgebraic component calculus“Memoryful” GoI Motivated by a similar (but more complicated) technical challenge we encountered in the semantics of aA

1 The word “memory” here is almost synonymous with “internal states”

stick to the former so as to distinguish from states as a computational ef
B

C
d

B
c

B

transducers

c
A

38

A

D
d

B

C

A

B

c

cc
C

A

c

···

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

Muroya (U. Tokyo)