User loginNavigation 
The Two Dualities of Computation: Negative and Fractional Types
The Two Dualities of Computation: Negative and Fractional Types
Abstract Every functional programmer knows about sum and product types, a+b and a*b respectively. Negative and fractional types, ab and a/b respectively, are much less known and their computational interpretation is unfamiliar and often complicated. We show that in a programming model in which information is preserved (such as the model introduced in our recent paper on Information Effects), these types have particularly natural computational interpretations. Intuitively, values of negative types are values that flow â€œbackwardsâ€ to satisfy demands and values of fractional types are values that impose constraints on their context. The combination of these negative and fractional types enables greater flexibility in programming by breaking global invariants into local ones that can be autonomously satisfied by a subcomputation. Theoretically, these types give rise to two function spaces and to two notions of continuations, suggesting that the previously observed duality of computation conflated two orthogonal notions: an additive duality that corresponds to backtracking and a multiplicative duality that corresponds to constraint propagation. By Greg Buchholz at 20140521 16:59  LtU Forum  previous forum topic  next forum topic  other blogs  4159 reads

Browse archivesActive forum topicsNew forum topics

Recent comments
9 hours 18 min ago
10 hours 37 min ago
11 hours 2 sec ago
14 hours 30 min ago
20 hours 22 min ago
20 hours 29 min ago
22 hours 23 min ago
1 day 7 hours ago
2 days 3 hours ago
2 days 13 hours ago