# Introduction


Recently I read the very interesting [Compiling to Categories](http://conal.net/papers/compiling-to-categories/compiling-to-categories.pdf) paper by Conal Elliot.

He presents the idea to compile haskell programs into a expressions of closed cartesian categories by $\lambda$-elimination.

The process applied reminded me of the [bracket abstraction](https://crypto.stanford.edu/~blynn/lambda/sk.html) used when compiling $\lambda$-terms to $SKI$-Combinators.

In this notebook I'm studying this connection.

## bracket abraction in combinatory logic

$\lambda$-terms can be converted to variable free combinator terms with a process called bracket abstraction.
Bracket abstraction $[]$ is defined by the following equations:

\begin{align} 
[\lambda x.x]   & = I \\
[\lambda x.y]   & = Ky \\
[\lambda x.P Q] & = S [\lambda x.P] [\lambda x.Q]
\end{align}

where the combinators $I$, $K$, and $S$ are defined as follows:

\begin{align}
I x & = x \\
K y x & = y \\
S p q x & = (p x) (q x)
\end{align}

In Haskell this combinators could be implemented as follows (we have to use lower case letters as Uppercase first letters are reserved for contructors in Haskell):

```haskell
i :: a -> a
i x = x

k :: a -> b -> a
k y _ = y

s :: (a -> b -> c) -> (a -> b) -> a -> c
s p q x = (p x) (q x)  
```

Once the $\lambda$-terms are compiled to combinator terms, these terms can be interpreted quite efficiently as they don't contain any variables and so no environment-handling is needed.

Combinator terms also allow to apply several more advanced interpretation techniques like graph-reduction, node-sharing, parallel reduction, etc.

## Closed Cartesian Categories







Both $I$ and $K$ are part of the Haskell standard prelude under the names `id` and `const`:

```haskell
-- | Identity function.
id :: a -> a
id x =  x

-- | @const x@ is a unary function which evaluates to @x@ for all inputs.
const :: a -> b -> a
const x _ =  x
```


```haskell
i :: a -> a
i x = x


i 8

```


    8



```haskell

```

14930a7275de4992e1788d8bd11b70e9ecfe56eb
ipynb
Jupyter Notebook
Closed Cartesian Categories and the SKI Combinators.ipynb
thma/lambda-cat
ea0578814b9600011cb770d8a9256a1afcd4d846
Apache-2.0
2021-03-27T14:55:49.000Z
2021-03-27T14:55:49.000Z
Closed Cartesian Categories and the SKI Combinators.ipynb
thma/lambda-cat
ea0578814b9600011cb770d8a9256a1afcd4d846
Apache-2.0
Closed Cartesian Categories and the SKI Combinators.ipynb
thma/lambda-cat
ea0578814b9600011cb770d8a9256a1afcd4d846
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES