Can factorial be encoded in the Kappa-calculus with fixed point operator?

Question

Suppose we have a $\kappa$-calculus with operator $fix$, that could be used to transform function with type $(1 \rightarrow a) \rightarrow a$ to a value of type $1 \rightarrow a$. We use a normal reduction strategy.

We'd like to represent factorial function in such a system. The problem is that whatever function we're trying to find a fixed point of, when we apply the function to its fixpoint, there's no way to determine whether we need to use the value of argument $x$ or not. There's no "counter" to base our solution on.

$fix (\kappa{}x. \cdots) = (\kappa{}x. \cdots) (fix (\kappa{}x. \cdots))$

In $\lambda$-calculus we could run $fix (\lambda f. \lambda x.\cdots)$ and terminate depending on the value of $x$.

1. How to prove that $\kappa$-calculus with fixed point operator cannot really represent a factorial function?
2. How could we extend $\kappa$-calculus to make it Turing-complete, leaving space for its translation into generalized arrows?

Answer 1

The bare $\kappa$-calculus does not permit defining factorial, even when extended with a fixed point operator. However, this answer deserves some unpacking.

1. The fixed point operator you give is not well-formed according to the grammar of types in the $\kappa$-calculus. Note that the grammar of types does not contain the function space $\tau \Rightarrow \tau'$ -- this is because the $\kappa$-calculus is a language of first-order functions. An expression has a type $\tau_1 \to \tau_2$, to indicate that it is an expression of type $\tau_2$, whose free variables are typed by $\tau_1$.

   The proper typing for a fixed point operator would be roughly something like: $$ \frac{\Gamma, x:1 \to \tau \vdash e : 1 \to \tau} {\Gamma \vdash \mu x:1 \to \tau. e : 1 \to \tau} $$

2. Once you've fixed this, you still can't define a factorial.

   The plain $\kappa$-calculus does not have sums or natural numbers as a base type. As a result, you can't write branching programs, and so you cannot define interesting recursive functions. If you added natural numbers and their iterator, you could define a factorial function. Hasegawa actually gives factorial as an example in his paper on the $\kappa$-calculus, in a calculus augmented with a basic natural number type.

   However, you might wonder why you are able to define factorial in the pure lambda calculus, even though it has no apparent control structures. The reason is that the interaction of fixed points and recursion gives you a "universal type" (i.e., a type $V$ such that $V$ is isomorphic to $V \to V$), and this lets you encode any datatype as a subset (more accurately, a retract) of it.

   In more syntactic terms, you can write the Y combinator (i.e., Curry's paradox) in any language with (a) higher-order functions, (b) recursion, and (c) the ability to use each variable more than once in a program. Since the basic $\kappa$-calculus lacks (a), adding even an unrestricted fixed point operator does not make it Turing-complete!

Answer 2

Not good with proofs but can answer number 2.

First of all it isn't necessary to use a complicated compilation scheme, you can just use PHOAS or a tagless final style directly.

class Category k => Terminal k where
     bang :: k a ()
class Terminal k => Kappa k where
     kappa :: (k () a -> k b c) -> k (a, b) c
     lift :: k () a -> k b (a, b)

I literally find this nowhere but there's a dual zeta calculus that composed with the Kappa calculus gives you a full lambda calculus

http://www.kurims.kyoto-u.ac.jp/~hassei/papers/ctcs95.html

class Terminal k => Zeta k where
    zeta :: (k () a -> k b c) -> k b (a -> c)
    pass :: k () a -> k (a -> b) b

class (Kappa k, Zeta k) => Lambda k

The dual constructions are literally just the same things but in the opposite category

class Category k => Initial k where
    absurd :: k Void a
class Initial k => Sum k where
     label :: (k a Void -> k c b) -> k c (a + b)
     jump :: k a Void -> k (a + b) b
class Initial k => Coexponential k where
     cozeta :: (k a Void -> k b c) -> k (b -< c) a
     compass :: k a Void -> k b (a -< b)
class (Sum K, Coexponential k) => Colambda k

• would be a type synonym for Either probably. -< would have to be a phantom type

You would want to add Sum into the mix but not Coexponential which is basically just as powerful as exponentials but just really really strange.

Incidentally, you can't exactly really usefully have both exponentials and coexponentials in a programming language unless you have some sort of linear type system or something, not sure of the precise details.

Sum + Kappa is still not Turing complete IIRC.

If you had a Fixpoint type that is equivalent in power to a Fixpoint operater IIRC.

But I'm not sure that works without exponentials.