# 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 '20 at 21:03
• Some example please. Jun 8 '20 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? Jun 8 '20 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. Jun 8 '20 at 23:23
• @user Outputting a function would give you no way to distinguish between terms like I and ((SK)K), which behave the same way as functions but are different formal terms according to the specification. Aug 24 '20 at 21:53

# Seed, 59255909 5890 bytes

112 454589265847615306392798371150868941185478173773114477799564999108299456271639608935231513022776287832169539139030305614982810812517498775300490082993668394081853118827424324680483930252479178912170382051619623446321480070977903088483201405923237338736733045701202032658549057148741443040831657737494410468780563941406417621523125299414038178600484145424465141212821402474602587759871115433130071157202419955878988531751042638978281084885656577124199893992297220594246775547971011993876657174034110776607444390867194303611291345805455706478215512150414242378973689595111161387131118943758988075182082759033642723387857122595187338850784874097521822851953277293644018138492307288851421003371217891107265259184442792711632901926492683256660812509944531473832442150415710333032389848374170750957512067980434176779059629590678502838862313718843012100388720238322267576244874317397797751771730549548536334784699165271031061970419147383967567393495633325352027978908696297734869839897974223409966395297644383154098218581137346568324823045017985950607000959131770446942498812407921393476300400514378035091204429931461058441380346709949939653672072709159094287637392759406779970591265050936984276520813829646200162116578122791712804292807168864566743926404900399432671206644817643936598187943307644068614587766977369590161315546014669709900683650050671370290255915890928965739795170533442567013533074550855743862653328866130381141543920032698780393878547547477723940935219022328003543633456487371259775680023283545170304985610592884834055648061932546044270218157026321454767685241406089318071456215033397545832882667222474227164419303809193175438912289560520871643744838052035001071126632372577008530919555565773424820763256408788465335585120827724050147991521431564649021655683528508618364248647779788845290157533250456363931575427175614357525848744220511199930375285371146657469264361384847354819237450690770868245037791073713218174155651466950722514098393901264402559105104607244482960815553476392931783154559406736164508941225610469139699671606051743842834815978316389831657603947583379665686027107259763079401958868014422468983428063204947981403315480812065282899526082195556714001190472884952694606881811958681546103476420391037432273482783545306524008162467755209092895031586783239185683431801803846206792395439436125865421233214331347734305323117009265968765111148207854951678815072036545686126071643226523979150989289792917436970730779603712474782865554019927951514737172864249515833232617761891685366123762264587440421739117658317575386657624166840011044392816727974221041590403176483547359472151493349229643021444660425857896370444717347722770162001271254542315803704090578352136329874536765186082188066475786812985526726059435947445496251668573141997200713913938863005600193252450674622149708980023145884353439035971867257691367305542167818476978738678525502873091350111215661477328726072674543530344272922676114578262954991864915892018117690764541896792256929162111925169780076720047700936825370566931525206071864966407235136727748138924517541498187905517996789645523235539704836304656890034613118115553357348865891254493501729463767641371479411556885484879979731350456918194851699976524573639339627645314237253015600757062123821505101147291776066203134403965729458150026679083957626780409220064898475575693488372310267729199642920709626464830131536910728497813727475348538985232597710740724798498172264879853350830403160789379477061159933229449153330871441267496280269990054009767804416183275901115302474179975044412536713819176008412032841038743957265585572080549379423740730975865106043262464389314181446637082850847738738498775588031910419257144656438237616227140174941271492166969241696570436758025663918159366989937279459172468512691021000738161290459477545578144401495570541604035937115958512864644777656235066028923696886901496549011493783645904875442080437544115448712597110749654652225658785298887555703075334386409712570677239256772072451457433929620102956919469781422524094777336772075237289298599679731529350180926652125863859838770307477577778943314678392955358259166012482047391429637802764614730320858352931272899229785593240097550804558623317317614657388148918726080520567799494901729911183400243057228717201883524099466135911901198225318508539805168784073042357339548913694008912765025798785238423445594266796964780050275763980567051596441028150542187543016783481379751707226044025696424221431055020838543842878956428531020177366790245393052536841789573293787730498934931374698799530673049515080383753074389734382436341010573153631947301143375292859890428594303212308428920875952899028171431382958118935301253915066322519447341617735393810028944087881424470797051080032684752781168166380344868289064907981591303051844183769560048408396746815262473697088348197693336948369159878364726814460681776784639943371045714706599940976542993625726402315752771769458405262931514105075819860046332219279460190256092944303518902850244549346068557061451395104054450064940994554215410195913951564377864071186254089557106527996972712942736869114468757569066509332901970013168293365394160495270235848752522733638301152861909743462189640128638159526139624942001714641343424480241004257904603548698904866941477465539837445283432971955083741529614146998357681685672311233177798926670821445288159977480956564360169495030412618874353402269234885302568814458987382927649197142099133541101416844549824060597733853956528739401736513461241162705083603010719688298277076508265423036086678140294125900903766981959055374466454505572227492014633980967216506036444099222328156878458657114084530068585424843387925451225414636323667618149027784116461560620852462455851520996459492183055695661531005660727956356213597259737765789774713691079631438817987929700912695679140345866298644393144192921454830326865244823989930205963299006093120867129586814919013554461985611547291274703042962578553969287


Try it online!

Made possible thanks to Abigail's perl answer. Inspired by HighlyRadioactive's comment.

Last iteration was golfed with bx5.

• What the... this is real...
– null
Aug 21 '20 at 1:17
• Now, do this in Malbolge.
– user96495
Aug 22 '20 at 3:04
• Challenge accepted, but let me finish my work first ;) Aug 22 '20 at 9:08
• This is wrong for the same reason as user89655’s answer; namely, it fails to simplify, e.g., ((K(SS))S) to (SS). (In the rules, x, y, and z are terms; they don’t have to be single characters.) Aug 24 '20 at 7:02
• @AndersKaseorg fixed; it hurt many bytes but should work correctly now. Aug 24 '20 at 17:43

# 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!

• Now, do this in Seed.
– null
Aug 20 '20 at 9:09

# 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!

• Basic -1. Alternatively, save more with // instead of >: 45 bytes
– att
Aug 25 '20 at 20:39

# 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} Jun 8 '20 at 22:49 • Or −40 bytes. Jun 8 '20 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.) # Rust Macros, 480 441 bytes macro_rules!s{({I(t:tt)+}s:tt)=>{s![{(t)+}s]};({Kx:tty:tt(t:tt)*}s:tt)=>{s![{x(t)*}s]};({Sx:tty:ttz:tt(t:tt)*}s:tt)=>{s![{xz(yz)(t)*}s]};({((c:tt)*)(t:tt)*}{(r:tt)*})=>{s![{(c)*}{{(t)*}(r)*}]};({(c:tt)*}{{(t:tt)*}(s:tt)*})=>{s![{(c)*(t)*}{(s)*}]};({(c:tt)*}{})=>{concat!((s![c]),*)};(((t:tt)*))=>{concat!("(",s!((t)*),")")};(t:tt)=>{stringify!(t)};((t:tt)*)=>{s![{(t)*}{}]};}  Try it online! The macro takes in tokens and spits out a string literal. Input is in a flattened, left-associative format as seen on Wikipedia. Make sure there is some whitespace between combinators when using it. ungolfed: macro_rules! ski { ({I (t:tt)+} s:tt) => {ski![ {(t)+} s]}; ({K x:tt y:tt (t:tt)*} s:tt) => {ski![ {x (t)*}s] }; ({S x:tt y:tt z:tt (t:tt)*} s:tt) => {ski![ {x z (y z) (t)*} s ]}; ({((c:tt)*) (t:tt)+}{(r:tt)*}) => {ski![ {(c)+} {{(t)*} (r)*} ]}; ({(c:tt)*} { {(t:tt)*} (s:tt)* }) =>{ski![ { (c)* (t)* } {(s)*} ]}; ({(c:tt)*} {}) => {concat!((ski![c]),*)}; (((t:tt)*)) => {concat!("(", ski!((t)*), ")")}; ( t:tt) =>{stringify!(t)}; ((t:tt)*) => {ski![ {(t)*} {}]}; }  Macros declared with macro_rules perform substitution based on rules similar to a regex-based substitution. The general strategy is here is an execution stack, where the instructions are being stored and executed, and a call stack, which is a stack of execution stacks and is used to traverse into functions created with (). Rule number ten serves as the entry point to the macro, matching on all inputs and setting up the call and execution stacks in the form {instructions}{}. Note that matched pairs of brackets count as a single token, and closing brackets stop greedy matches. Rule one implements the I combinator. It matches when the call stack is I followed by one or more instructions. It simply passes on all the matched instructions. Rule two implements the K combinator. It behaves similarly to I but uses two arguments instead of one. Rule three is the same but for S. Rule four implements traversing into parentheses by pushing the instructions remaining on the execution stack after the parentheses onto the call stack, and replacing the call stack with the instructions in the parentheses. Rule five catches an edge case by stopping infinite recursion when there are no instructions after the parentheses. was made redundant by an earlier bug fix and removed. Rule six is when the execution stack can't be simplified and there are more instructions on the call stack, the instructions in the top execution stack on the call stack are concatenated on the bottom of the main execution stack. Rule seven is when the execution stack can't be simplified and the call stack is empty. Here all the tokens are split, fed back into this macro for stringification, and concatenated. Rule eight is where I say I lied because parenthesized groups need further evaluation because that strategy I had above evaluated these groups lazily. This rule simply feeds the instructions in the parentheses back into the original macro and concatenates parentheses around the results. Rule nine is our terminal rule, where the tokens passed in are stringified and returned. Assuming the recursion limit is removed and rustc gets unlimited memory this is a proof of turing completeness for rust's macro system (not the only one- rust's macros are trivially ℒ-hard, a macro that binds an inputted  can create and execute arbitrary macros). A playground link that lets you view the ungolfed macro's expansion steps is below. Playground # 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)  # Scala 3 (compile-time), 113 bytes type A=AnyKind type S[X[a<:A]<:[b<:A]=>>A]=[Y[z<:A]]=>>[Z<:A]=>>X[Z][Y[Z]] type K[X<:A]=[Y<:A]=>>X type I[X<:A]=X  Try it in Scastie It works at compile time and it doesn't exactly return a value (you can check it with =:= or other mechanisms), but Dotty's type system is Turing-complete (Scala 2's too, actually). Pretty straightforward - it uses higher-kinded types and curried type lambdas like functions. Ungolfed (and modified slightly for clarity): type S = [X <: [a <: AnyKind] =>> [b <: AnyKind] =>> AnyKind] =>> //X is a type lambda with 2 parameters (curried) and returning a type of any kind [Y[z <: AnyKind]] =>> //Y is a type lambda taking one parameter and returning a type of any kind [Z <: AnyKind] //Z is a type of any kind =>> X[Z][Y[Z]] //The result of Skyz, as defined in the question type K = [X <: AnyKind] =>> [Y <: AnyKind] =>> X type I = [X <: AnyKind] =>> X  SIIK or (((SI)I)K) would be written as S[I][I][K]. ### With match types, 200 bytes final class S final class K final class I type R[T]=T match{case(((S,x),y),z)=>R[((x,z),(y,z))]case((K,x),y)=>R[x]case(I,x)=>R[x]case(a,b)=>R[a]match{casea=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}  Thanks to @HTNW on SO for helping me with this Try it in Scastie A term (xy) is represented as the tuple (x,y). ### Using literal types, 164 bytes type R[T]=T match{case((('S',x),y),z)=>R[((x,z),(y,z))]case(('K',x),y)=>R[x]case('I',x)=>R[x]case(a,b)=>R[a]match{casea=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}  Try it in Scastie This one uses literal-based singleton types (the Chars 'S', 'K', and 'I'). ### Slightly unethical version, 158 bytes type R[T]=T match{case(((0,x),y),z)=>R[((x,z),(y,z))]case((1,x),y)=>R[x]case(2,x)=>R[x]case(a,b)=>R[a]match{casea=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}  Same approach as above, but this time, S is the singleton type of 0, K is 1, and I is 2. Try it in Scastie # Wolfram Language, 44 bytes s[a_][b_][c_]:=b@c//a@c;k[a_][b_]:=a;i@a_:=a  This defines them as actual functions in Wolfram, so s[i][i][k] returns k[k], etc. Try it online! • -6 bytes – att Aug 29 at 6:02 # KamilaLisp, 137 bytes (defmacro f(x)(match x((a b c)(S a b c)[(tie a c b c)/ 2])((a b)(K a b)a)(a(I a)a)((a b)(a b)(tie(f a)(f b)))(x)))(def g (iterate /= f))  Ungolfed: ;; SKI calculus implementation using KamilaLisp macros (defmacro ski (x) (match x ((a b c) (S a b c) [(tie a c b c) / 2]) ((a b) (K a b) a) ((a) (I a) a) ((a b) (a b) (tie (ski a) (ski b))) (x) )) ;; iterate /= => fixed point (def ski-red (iterate /= ski)) ;; an example expression (println@ski-red '(S I I K))  # sed, 89 :1;s|(I\(.$$)|\1|g;t1;s|((K$$.$$).)|\1|g;t1;s|(((S$$.$$)$$.$$)$$.$$)|((\1\3)(\2\3))|g;t1

• This is wrong because it fails to simplify, e.g., ((K(SS))S) to (SS). (In the rules, x, y, and z are terms; they don’t have to be single characters.) Aug 24 '20 at 7:00

data T=S|K|I|T:$T e(x:$y)=e x!e y
K:$x!_=x S:$x:$y!z=x!z!(y!z) x!y=x:$y
`