From Linear Logic to Cyclic Sharing

Title:From Linear Logic to Cyclic Sharing

Authors:Masahito Hasegawa

Conference:Linearity/TLLA 2018

Tags:CPS translation, cyclic lambda calculus, cyclic sharing, Freyd categories, linear lambda calculus, linear logic, monoidal categories, semantics, simply typed lambda calculus and traced monoidal categories

Abstract:

We present a translation from Multiplicative Exponential Linear Logic to a simply-typed lambda calculus with cyclic sharing. This translation is derived from a simple observation on the Int-construction on traced monoidal categories. It turns out that the translation is a mixture of the call-by-name CPS translation and the Geometry of Interaction-based interpretation.

From Linear Logic to Cyclic Sharing

1

3

5

7

9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49

51

53

55

57

59

61

63

65

66

1of66

1

2

3

4