# Implement SKI combinator calculus

This challenge is to golf an implementation of SKI formal combinator calculus.

# Definition

## Terms

S, K, and I are terms.

If x and y are terms then (xy) is a term.

## Evaluation

The following three steps will be repeated until none of them apply. In these, x, y, and z must be terms.

(Ix) will be replaced by x

((Kx)y) will be replaced by x

(((Sx)y)z) will be replaced by ((xz)(yz))

# Input

A string or array, you do not have to parse the strings in the program.

The input is assumed to be a term.

If the simplification does not terminate, the program should not terminate.

# Examples

(((SI)I)K) should evaluate to (KK) ((((SI)I)K) > ((IK)(IK)) > (K(IK)) > (KK))

The evaluation order is up to you.

This is . Shortest program in bytes wins.

• Are the inputs strings we have to parse, or can we have them in a tree or similar? – xnor Jun 8 at 21:03
• They don't have to be parsed, you can have them in a tree. – nph Jun 8 at 21:04
• Some example please. – Noodle9 Jun 8 at 21:27
• Should we assume the input is a term (i.e. the behavior is unspecified if the input is not a term)? Is a non-strict evaluation order required so that ((KI)(((SI)I)((SI)I))) must terminate, or is such an expression allowed to diverge? – Anders Kaseorg Jun 8 at 22:53
• @nph The point is that ((KI)(((SI)I)((SI)I))) can either be reduced to I with one K step (leading to termination) or to ((KI)(((SI)I)((SI)I))) with one S step (leading to divergence), and you need to specify whether the former is required, the latter is required, or either are allowed. I suggest “either”. See en.wikipedia.org/wiki/Evaluation_strategy. – Anders Kaseorg Jun 8 at 23:23

# Wolfram Language, 63 bytes

#//.{{I,x_}->x,{{K,x_},y_}->x,{{{S,x_},y_},z_}->{{x,z},{y,z}}}&


Try it online!

God, I love pattern matching in Wolfram Language. Represents (xy) as {x,y} (a list of two elements).

Alternatively, if we represent (xy) with x>y, we can do it in 55 bytes.

#//.{I>x_->x,(K>x_)>y_->x,((S>x_)>y_)>z_->(x>z)>(y>z)}&


Try it online!

# perl -p, 135 bytes

1 while s/$$(I)(?<T>[SKI]|\((?&T)(?&T)$$)\)|$$\((K)((?&T))$$(?&T)\)|$$\(\((S)((?&T))$$((?&T))\)((?&T))\)/$1?$2:$3?$4:"(($6$8)($7$8))"/e


Try it online!

Just a regexp applying the three rules. Reads a string from STDIN, applies all the rules until there's nothing to apply, writes the result to STDOUT.

(?<T>[SKI]|$$(?&T)(?&T)$$) is a recursive pattern recognizing a term. The rest of the pattern is just a mechanically translation of the given rules.

• −1 byte: $$\(\(\({3} – Anders Kaseorg Jun 8 at 22:49 • Or −40 bytes. – Anders Kaseorg Jun 8 at 23:25 # Retina 0.8.2, 171 bytes {T()<> <<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>) <<17<47> <<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+> 1 <I((\w|(<)|(?<-3>>))+)> 1 T<>()  Try it online! Explanation: {  Repeat the transformations until there are no more available. T()<> T<>()  Temporarily switch ()s with <>s to avoid having to quote numerous ()s. <<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>) <<17<47>  Process S operations. (The last capture includes the trailing > in order to avoid repeating it in the replacement.) <<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+> 1  Process K operations. <I((\w|(<)|(?<-3>>))+)> 1  Process I operations. The (\w|(<)|(?<-[N]>>))+ construct is an example of a .NET regex balancing group. It tries to match characters, but it's only allowed to match >s if it's already seen the same number of <s. (N needs to be replaced with the number of the (<) capturing group. As written it fails if the <>s aren't balanced correctly, but you can use conditional regex to check for that.) # 05AB1E, 92 bytes ΔDŒʒ„)(©S¢Ë}ʒÁ®Å?y®S¢O_~}©vy"(Iÿ)"y:}®ãvy"((Kÿ)ÿ)"yθ:}®3ãvy"(((Sÿ)ÿ)ÿ)"yĆ1.I"((ÿÿ)(ÿÿ))":  05AB1E has no regex, so uses a brute-force approach using all valid substrings. Because of this, it's extremely slow for larger test cases. Executes in the order (Ix)((Kx)y)(((Sx)y)z). Explanation: Δ # Continue until the result no longer changes: D # Duplicate the current string # (will use the implicit input-string in the first iteration) Œ # Take all its substrings ʒ # Filter those substrings by: „)( # Push ")(" © # Store it in variable ® (without popping) S # Convert it to a list of characters: [")","("] ¢ # Count each in the substring Ë # Check that the counts are equal for both }ʒ # After the filter: filter once more: Á # Rotate the substring once towards the left ® # Push string ")(" from variable ® Å? # Check if the rotated substring starts with this y # Push the substring again ®S¢ # Count the [")","("] again O_ # Check that the sum of both counts is 0 ~ # Check if either of the two was truthy }© # After the filter: store it in variable ® (without popping) v # Loop over each valid substring: y # Push the substring "(Iÿ)" # Push this string, with the ÿ automatically filled with # the substring y # Push the substring again : # Replace all "(Ia)" with "a" }® # After the loop: push the list of valid substrings again ã # Take all pairs of valid substrings v # Loop over these pairs: y # Pop and push the pair separated to the stack "((Kÿ)ÿ)" # Push this string, with the ÿ automatically filled again yθ # Pop and push only the last substring of the pair: [a,b] → b : # Replace all "((Kb)a)" with "b" }® # After the loop: push the list of valid substrings again 3ã # Take all triplets of valid substrings this time v # Loop each each triplet: y # Pop and push the triplet separated to the stack "(((Sÿ)ÿ)ÿ)" # Push this string, with the ÿ automatically filled again y # Push the current triplet again Ć # Enclose; append its own head: [a,b,c] → [a,b,c,a] 1.I # Get the 0-based 1st permutation: [a,b,c,a] → [a,b,a,c]  # Pop and push the quartet separated to the stack "((ÿÿ)(ÿÿ))" # Push this string, with the ÿ automatically filled again : # Replace all "(((Sc)b)a)" with "((ca)(ba))" # (after which the result is output implicitly)  # Haskell, 83 bytes data T=S|K|I|T:T e(x:y)=e x!e y e x=x I!x=x K:x!_=x S:x:y!z=x!z!(y!z) x!y=x:y  Try it online! # C (gcc), 666616518483 476 bytes Who doesn't love classy, Arthur Whitney-styled code? No regular expressions involved, only clever parsing and evaluation. PS: Yes, obviously, a few bytes can be shaved off, but for the artistic style of the obfuscated code, I'll keep them. Also for the byte count :p. Also, this code utilizes undefined behaviour in hope that nothing will break (hopefully). @ceilingcat insisted on golfing it down from 666 bytes, so here is the golfed version: #define J putchar #define H O->a #define G H->a #define K O->b typedef struct x{struct x*a,*b;int q;}Y;Y*O;z=1;A(q){O=calloc(6,4);O->q=q;}h(Y*O){Y*u;O=H&&H->q==2?z=K:H&&G&&G->q==1?z=H->b:H&&G&&G->a&&!G->a->q?u=A(3),(u->a=A(3))->a=G->b,(u->b=A(3))->a=H->b,u->a->b=u->b->b=K,z=u:(O->q==3?H=h(H),K=h(K):0,O);}r(x){Y*O;x=getchar()-73;x=x+33?A(x?x!=10:2):!getchar(K=r(H=r(O=A(3))))+O;}q(Y*O){O&&J(O->q["SKI "],O->q-3||J(41,q(K),q(H),J(40)));}main(){Y*O=r();for(;z;O=h(O))z=0;q(O);}  Try it online! # sed, 89 :1;s|(I\(.$$)|\1|g;t1;s|((K$$.$$).)|\1|g;t1;s|(((S$$.$$)$$.$$)$$.$$)|((\1\3)(\2\3))|g;t1
`