Developer Diary >_

This post is a beginning of a new series with a new tag called "programming languages". I plan to discuss interesting ideas behind programming languages. This post is devoted to a very simple form of calculation system called SKI calculus. SKI calculus was developed by Schoenfinkel in the 1920's. The properties of SKI Calculus was known even before computers were built. Understanding SKI Calculus lays down foudation for understanding more involved modern languages. Let's first see what are the rules of SKI calculus.

Side Note: You can use SKI Calculus Interpreter to experiment with the SKI programs we discuss below!

SKI Rewrite Rules

Like any other calculation system, there are predefined set of rules:

A combinator is a function without free-variables. A function call is written by juxtaposing two expressions. $Ix$ means apply function $I$ to $x$ and the arrow $\to$ represents the calculation step. On the right hand side is the output of compulation which is $x$.

Expressions as binary trees and rules as tree transformations

Paranthesis should be used to represent associativity. Whenever no paranthesis are present assume implicit left associativity. Considering these we can represent expressions as simple binary trees and think rewrite rules as tree transformations. See below:

$\left(Ix\right)\to x$

$I$ takes only one argument and outputs the argument. That's why we called it identity function.

$\left(\right(Kx\left)y\right)\to x$

$K$ takes two arguments and returns the first argument, ignoring the second argument. This means that no matter what the second argument is, the result is always the first argument. Hence, it is called a constant function.

$\left(\right(\left(Sx\right)y\left)z\right)\to \left(xz\right)\left(yz\right)$

$S$ takes in three arguments and apply the first argument (a function) and second argument to the third argument. This is the way to program function calls (applications) and reusing values (make copies). $S$ combines both of them.

Function execution

$S$, $K$, and $I$ are well formed functions they don't execute without required number of arguments.

$I$ needs atleast one argument and it only uses the first argument.

Exmaples function executions:

• $I$ - cannot execute as it expected a single argument.
• $Ixy$ - needs atleast one argument and it only uses the first argument which results $xy$.
• $K$ - cannot execute as it expected two arguments.
• $Kx$ - one argument is not enough, so function holds.
• $Sxy$ - two arguments is not enough, so function holds. We call above and this are partially applied functions.
• $Swxyz$ - More than enough arguments. Only first three arguments used and resutls $wy\left(\mathrm{xy}\right)z$.

Definition of Terms

The terms of the SKI calculus are the smallest set such that

• $S$, $K$, and $I$ are terms
• If $x$ and $y$ are terms,then $\mathrm{xy}$ is a term

CFG for SKI terms

We can derive valid SKI terms using the following simple Context Free Grammar.

$S$, $K$, and $I$ are terminals and $\mathrm{Term}$ is the only non-terminal.

Lets see some computation examples

$SKxy\to \left(Ky\right)\left(xy\right)\to y$ $SIIx\to \left(Ix\right)\left(Ix\right)\to x\left(Ix\right)\to xx$ $\left(SII\right)\left(SII\right)\to \left(I\right(SII\left)\right)\left(I\right(SII\left)\right)$

If you look closely, this example shows a kind of looping which is never-ending loop. Let's see more on looping later on when discussing natural number representation.

Programming with SKI Calculus

To do actual programming we need a way to recurse (form of iteration or looping), conditionls (if-else or branching), and data structures. The last example above is a form of looping of it is non-terminating but not much use in it.

Recursive function calls are little more involved, which calls the function itself again and again.

For example consider following expression: $w=S\left(Kf\right)\left(SII\right)$

Now lets work on function application:

Now this is able to call the function again and again and but it generates never-ending recursive function calls. We will see how to do a fixed number of calls later on under natual numbers discussion.

Branching behavior

We need boolean but, there is no such a thing in SKI Calculus. But we can encode SKI terms intuitively be true and false values. And find combinators for not, and and or boolean operations.

Booleans

Similarly, We can represent false by a function which picks the second of the two argumenets called upon. We can represent true by a function which picks the first of the two argumenets called upon. So:

Now we can intuitively define $T=K$ and $F=SK$. You can now apply these combinators to above and see it works (later on, we will see how to derive them systematically).

Boolean operations

NOT operation

Let $B$ be a Boolean ($T$ or $F$ we chose above)

$\mathrm{not}B=BFT$

OR operation

Let $B$ be a Boolean ($T$ or $F$ we chose above)

$\mathrm{B1}or\mathrm{B2}=\mathrm{B1}T\mathrm{B2}$

AND operation

Let $B$ be a Boolean ($T$ or $F$ we chose above)

Example boolean expression evaluations

Now we can apply the boolean expresion rules we showed above and using $T$ and $F$ encoded as $K$ and $\mathrm{SK}$.

$(notF)andT=\left(FFT\right)TF$ $\to TTF\to T$

$For(notF)=FT\left(FFT\right)$ $\to FTT\to T$

What about conditionals?

Let $B$ be a Boolean ($T$ or $F$ we chose above). Now we can intuitively think of an expression as below:

$ifBthenxelsey=Bxy$

How can we write a combinator for swap using $S$, $K$, and $I$. Seems it is not as easy as the ones could derive right away.

Actually swap can systematically be derived as:

$swap=S\left(K\right(SI\left)\right)\left(S\right(KK\left)I\right)$

By now, it should be clear why it's difficult to guess or intuitively think of one. No worries! There is a systematic way to derive combinators.

Abstraction Algorithem

We need an Abstraction Algorithm $A(\dots )$ that can map the right-hand side to a combinator. We can state mapping functions by reversing the rewrite rules of SKI calculus. The process is to eliminate the variables by replacing them with uses of the combinators $S$, $K$, and $I$.

Consider a function equation of one variable as:

$fx=E$

If we apply function $f$ to argument $x$, the result is $E$.

We want a combinator $A\left(E,x\right)$ that implements $f$. So,

$A\left(E,x\right)x=E$

Note that $A\left(E,x\right)$ doesn't use $x$. We say that we have abstracted $E$ with respect to $x$.

Now, we can see how to abstract out each rule to mappers.

Below are definitions of generalized mappers with none of them using $x$.

• $A\left(x,x\right)=I$
  
  Correctness:
  

  $Ix=x$

• $A\left(E,x\right)=KE$
  if $x$ does not appear in $E$
  
  Correctness:
  

  $\mathrm{KE}x=E$

• $A\left(\mathrm{E1}\mathrm{E2},x\right)=SA\left(\mathrm{E1},x\right)A\left(\mathrm{E2},x\right)$
  
  Correctness:
  

  $SA(\mathrm{E1},x)A(\mathrm{E2},x)x$ $\to \left(A\right(\mathrm{E1},x\left)x\right)\left(A\right(\mathrm{E2},x\left)x\right)$ $\to \mathrm{E1}\left(A\right(\mathrm{E2},x\left)x\right)$ $\to \mathrm{E1}\mathrm{E2}$

Let's try to systematically derive a combinator for 'swap'

$swap(x,y)=(y,x)$

Let's abstract out each argument, one at a time. First we eliminate $y$ which is the last argument. We can eliminate first argument $x$.

Eliminating $y$:

$swapx=A(\mathrm{yx},y)$ $=SA(y,y)A(x,y)$ $=SI\left(Kx\right)$

Eliminating $x$:

$swap=A\left(SI\right(Kx),x)$ $=SA(SI,x)A(\mathrm{Kx},x)$ $=S\left(K\right(SI\left)\right)\left(SA\right(K,x\left)A\right(x,x\left)\right)$ $=S\left(K\right(SI\left)\right)\left(S\right(KK\left)I\right)$

Okay, Abstraction algorithem is a very simple and systematic procedure. But it can become a tedious task to derive one and can be a very long expression as well. We can do something clever to reduce the size of the combinators by trying to further simplify the third abstraction above.

Helper Combinators for Abstract Algorithem

If you look at the third mapper $A\left(\mathrm{E1}\mathrm{E2},x\right)$, we never said $\mathrm{E1}$ or $\mathrm{E2}$ does not include $x$. But we can simplify further when we know if either $\mathrm{E1}$ or $\mathrm{E2}$ contains $x$.

Let's define two new combinators like below:

• $\mathrm{c1}xyz=x\left(yz\right)$
  $\mathrm{c1}$ is a version of $S$ where first argument is constant (means $x$ does not use $z$)
• $\mathrm{c2}xyz=\left(xz\right)y$
  $\mathrm{c2}$ is a version of $S$ where second argument is constant (means $y$ does not use $z$)

Okay now we can think about mappers using them:

• $A(\mathrm{E1E2},x)=\mathrm{c1}\mathrm{E1}A(\mathrm{E2},x)$
  where $\mathrm{E1}$ does not use $x$
• $A(\mathrm{E1E2},x)=\mathrm{c2}A(\mathrm{E1},x)\mathrm{E2}$
  where $\mathrm{E2}$ does not use $x$
• $A\left(\mathrm{E1}\mathrm{E2},x\right)=SA\left(\mathrm{E1},x\right)A\left(\mathrm{E2},x\right)$
  This general case can be applied without knowing specifics about $\mathrm{E1}$ or $\mathrm{E2}$

Now let's use abstraction algorithem to derive combinators for $\mathrm{c1}$ and $\mathrm{c2}$ in terms of $S$, $K$ and $I$:

Deriving c1

$\mathrm{c1}xyz=x\left(yz\right)$

$\mathrm{c1}xy=A(x(yz),z)$ $=SA(x,z)A(yz,z)$ $=S\left(Kx\right)\left(SA\right(yz\left)A\right(z,z\left)\right)$ $=S\left(Kx\right)(S(Ky\left)I\right)$

Observe below,

$S\left(Ky\right)Iw$ $\to \left(\right(Ky\left)w\right)\left(Iw\right)$ $\to yw$

Therefore,

$S\left(Ky\right)I=y$

So, now we can write,

$\mathrm{c1}xy=S\left(Kx\right)y$

Then we get,

$\mathrm{c1}x=S\left(Kx\right)$

Then,

$\mathrm{c1}=A\left(S\right(Kx),x)$ $=SA(S,x)A(Kx,x)$ $=S\left(KS\right)(SA(K,x)A(x,x\left)\right)$ $=S\left(KS\right)\left(S\right(KK\left)I\right)$

Observe below,

$\left(S\right(KK\left)I\right)w=\left(\right(KK\left)w\right)\left(Iw\right)$ $=Kw$

Therefore,

$S\left(KK\right)I=K$

Finally, we can write,

$\mathrm{c1}=S\left(KS\right)K$

Deriving c2

$\mathrm{c2}xyz=\left(xz\right)y$

Note that for the derivation of $\mathrm{c2}$ we can use $\mathrm{c1}$ combinator directly.

$\mathrm{c2}xy=A\left(\right(xz)y,z)$ $=SA(xz,z)A(y,z)$ $=S(\mathrm{c1}xA(z,z\left)\right)\left(Ky\right)$ $=S\left(\mathrm{c1}xI\right)\left(Ky\right)$

$\mathrm{c2}x=A\left(S\right(\mathrm{c1}xI\left)\right(Ky),y)$ $=SA\left(S\right(\mathrm{c1}xI),y)A(Ky,y)$ $=S\left(K\right(S\left(\mathrm{c1}xI\right)\left)\right(\mathrm{c1}KA(y,y))$ $=S\left(K\right(S\left(\mathrm{c1}xI\right)\left)\right(\mathrm{c1}KI)$

$\mathrm{c2}=A(S(K(S(\mathrm{c1}xI\left)\right))(\mathrm{c1}KI),x)$ $=SA(S(K(S(\mathrm{c1}xI\left)\right)),x)A(\mathrm{c1}KI,x)$ $=S(\mathrm{c1}SA(K(S(\mathrm{c1}xI),x)\left)\right(K\left(\mathrm{c1}KI\right))$ $=S(\mathrm{c1}S(\mathrm{c1}KA(S(\mathrm{c1}xI),x)\left)\right)(K(\mathrm{c1}KI\left)\right)$ $=S(\mathrm{c1}S(\mathrm{c1}K(\mathrm{c1}SA(\mathrm{c1}xI,x\left)\right)\left)\right)(K(\mathrm{c1}KI\left)\right)$ $=S(\mathrm{c1}S(\mathrm{c1}K(\mathrm{c1}S(SA(\mathrm{c1}x,x)A(I,x)\left)\right)\left)\right)(K(\mathrm{c1}KI\left)\right)$ $=S(\mathrm{c1}S(\mathrm{c1}K(\mathrm{c1}S(S(\mathrm{c1}\mathrm{c1}A(x,x\left)\right)\left(KI\right)\left)\right)\left)\right)(K(\mathrm{c1}KI\left)\right)$ $=S(\mathrm{c1}S(\mathrm{c1}K(\mathrm{c1}S(S\left(\mathrm{c1}\mathrm{c1}I\right)\left(KI\right)\left)\right)\left)\right)(K(\mathrm{c1}KI\left)\right)$

Think how long $\mathrm{c2}$ would be if we didn't use the $\mathrm{c1}$ combinator.

Let's again derive 'swap' but this time using the helpers

$\mathrm{swap}xy=yx$

$\mathrm{swap}x=A(yx,y)$ $=\mathrm{c2}A(y,y)x$ $=\mathrm{c2}Ix$

$\mathrm{swap}=A(\mathrm{c2}Ix,x)$ $=\mathrm{c1}\left(\mathrm{c2}I\right)A(x,x)$ $=\mathrm{c1}\left(\mathrm{c2}I\right)I$

Great!! it's in a very short form thanks to $\mathrm{c1}$ and $\mathrm{c2}$.

Introducing Abstract Data Type: Pairs

Let's see how we can represent a simple abstract data structure now. Suppose we want to have a data structure called pair where we can access the first and second elements by specifying it as an argument as below:

$\mathrm{pair}xy\mathrm{first}=x$

$\mathrm{pair}xy\mathrm{second}=y$

Remember how we use $T$ and $F$ to handle if-then-else above. We can choose:

$\mathrm{first}=T$ $\mathrm{second}=F$

Then we can state:

$\mathrm{pair}xyz=zxy$

Let's abstract out $\mathrm{pair}$ combinator now:

$\mathrm{pair}xyz=zxy$

$\mathrm{pair}xy=A(zxy,z)$ $=\mathrm{c2}A(zx,z)y$ $=\mathrm{c2}(\mathrm{c2}A(z,z\left)x\right)y$ $=\mathrm{c2}\left(\mathrm{c2}Ix\right)y$

$\mathrm{pair}x=A(\mathrm{c2}(\mathrm{c2}Ix)y,y)$ $=\mathrm{c1}(\mathrm{c2}(\mathrm{c2}Ix\left)\right)A(y,y)$ $=\mathrm{c1}(\mathrm{c2}(\mathrm{c2}Ix\left)\right)I$

$\mathrm{pair}=A(\mathrm{c1}(\mathrm{c2}\left(\mathrm{c2}Ix\right))I,x)$ $=\mathrm{c2}A(\mathrm{c1}(\mathrm{c2}\left(\mathrm{c2}Ix\right)),x)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}A(\mathrm{c2}\left(\mathrm{c2}Ix\right),x\left)\right)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}(\mathrm{c1}\mathrm{c2}A(\mathrm{c2}Ix,x)\left)\right)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}(\mathrm{c1}\mathrm{c2}(\mathrm{c1}(\mathrm{c2}I)A(x,x\left)\right)\left)\right)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}(\mathrm{c1}\mathrm{c2}(\mathrm{c1}(\mathrm{c2}I\left)I\right)\left)\right)I$

SKI is a language with higher-order functions (functions that take functions as arguments and return functions as results). For example following are higher-order functions:

• $\mathrm{swap}x$

  can read as swap with $x$. You can give an argument function $z$ and get the output function $zx$ which is the opposite of as it was before (apply $x$ to $z$)

• $\mathrm{pair}B\mathrm{or}$

  pair of functions. You can input $T$ to get function $B$ or input $F$ to get function $\mathrm{or}$

Natural Numbers

Remember how we got the boolean true and false values. Boolean are actually encoded using $S$, $K$, and $I$. What we can try to get natural numbers is the same. We need to encode each number starting from zero. We can think of a combinator that does apply a function $n$ times to another as the natural number $n$. Let's find that combinator that applies it's first argument $n$ times to its second argument as below:

$$nfx=f^n\left(x\right)$$

Note $0fx=x$ when $0=SK$

$0fx=\left(SK\right)fx$ $\to \left(Kx\right)\left(fx\right)$ $\to x$

We can find a combinator succ (successive application) as below:

$\mathrm{succ}nfx=f\left(nfx\right)$ where $\mathrm{succ}=S(S(KS\left)K\right)$

Correctness:

$\mathrm{succ}nfx=S(S(KS\left)K\right)nfx$ $\to (S(KS\left)Kf\right)\left(nf\right)x$ $\to \left(KSf\right)\left(Kf\right)\left(nf\right)x$ $\to S\left(Kf\right)\left(nf\right)x$ $\to \left(\right(Kf\left)x\right)\left(\right(nf\left)x\right)$ $\to f\left(nfx\right)$

Therefore:

$\mathrm{succ}0fx=f\left(0fx\right)$ $=f\left(x\right)$

We can define $\mathrm{one}$ as:

$\mathrm{one}=\mathrm{succ}0$

$\mathrm{one}fx=f\left(x\right)$

Now apply $\mathrm{succ}$ to $\mathrm{one}fx$:

$\mathrm{succ}\mathrm{one}fx=f\left(\mathrm{one}fx\right)$ $=f(f(x\left)\right)$

So we can write:

$\mathrm{two}=\mathrm{succ}\mathrm{one}$

Just to be clear, once again let's apply $\mathrm{succ}$ to $\mathrm{two}fx$:

$\mathrm{succ}\mathrm{two}fx=f\left(\mathrm{two}fx\right)$ $=f(f(f\left(x\right)\left)\right)$

So we can write:

$\mathrm{three}=\mathrm{succ}\mathrm{two}$

$\mathrm{three}fx=f(f(f\left(x\right)\left)\right)$

Now it's clear that we can express n th natural numbers in the form of:

$$n={\mathrm{succ}}^n\left(0\right)$$

Nutual numbers in SKI Calculus have built-in iteration as we see above.

Addition and Multiplication

Now we can think about addition using $\mathrm{succ}$ and $nfx$:

$addxy=x\mathrm{succ}y$

Most importantly $x$ and $y$ are any natural numbers we derive above. We can read the right hand side like apply $\mathrm{succ}$ combinator $x$ times to $y$. We are adding 1 at a time to y, x many times to get (x+y) encoded in $S$, $K$ and $I$. Great, now we can abstract out $\mathrm{add}$ as a combinator:

$\mathrm{add}xy=x\mathrm{succ}y$

$\mathrm{add}x=A(x\mathrm{succ}y,y)$ $=\mathrm{c1}(x\mathrm{succ})A(y,y)$ $=\mathrm{c1}(x\mathrm{succ})I$

$\mathrm{add}=A(\mathrm{c1}(x\mathrm{succ})I,x)$ $=\mathrm{c2}A(\mathrm{c1}(x\mathrm{succ}),x)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}A(x\mathrm{succ},x\left)\right)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}(\mathrm{c2}A(x,x)\mathrm{succ}\left)\right)I$ $=\mathrm{c2}(\mathrm{c1}\mathrm{c1}(\mathrm{c2}I\mathrm{succ}\left)\right)I$

Similarly using the application of $nfx$, muliplication can be expressed in terms of addition as below:

$\mathrm{mul}xy=x\left(\mathrm{add}y\right)0$

We can read it as do add y, x many times starting from 0. You can abstract out mul as we did for add, but I won't do it here since it's almost same.

Now let's see how to write some arithmetic expression in SKI Calculus. Note numbers in below are SKI encoded natural numbers and * and + represent $\mathrm{mul}$ and $\mathrm{add}$ combinators shown above.

We can express (3x4)+5 in SKI calculus as below:

We began by introducing SKI Calculus, then explored conditionals, abstract data types like pairs, and derived natural numbers and simple arithmetic operations. That wraps up this blog post. I hope you've gained some new insights. Also, I'd like to express my gratitude to Alex Aiken for sharing the lecture notes publicly. This entire post is based on my understanding of his lecture slides.

Looking forward to seeing you in a new post! Bye!