The SKI combinator calculus in D's type system. Inspired by https://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/

ski.d

/*
  The SKI combinator calculus in D's type system
  Inspired by https://michid.wordpress.com/2010/01/29/scala-alias-level-encoding-of-the-ski-calculus/
 */

interface Term {
  alias ap(X: Term) = Term;
  alias eval = Term;
}

// The S combinator
interface S : Term {
  alias ap(X: Term) = S1!X;
  alias eval = S;
}

interface S1(X: Term) : Term {
  alias ap(Y: Term) = S2!(X, Y);
  alias eval = S1!X;
}

interface S2(X: Term, Y: Term) : Term {
  alias ap(Z: Term) = S3!(X, Y, Z);
  alias eval = S2!(X, Y);
}

interface S3(X: Term, Y: Term, Z: Term) : Term {
  alias ap(V: Term) = eval.ap!V;
  alias eval = X.ap!(Z).ap!(Y.ap!Z).eval;
}

// The K combinator
interface K : Term {
  alias ap(X: Term) = K1!X;
  alias eval = K;
}

interface K1(X: Term) : Term {
  alias ap(Y: Term) = K2!(X, Y);
  alias eval = K1!X;
}

interface K2(X: Term, Y: Term) : Term {
  alias ap(Z: Term) = eval.ap!Z;
  alias eval = X.eval;
}
   
// The I combinator
interface I : Term {
  alias ap(X: Term) = I1!X;
  alias eval = I;
}

interface I1(X: Term) : Term {
  alias ap(Y: Term) = eval.ap!Y;
  alias eval = X.eval;
}

interface c : Term {
  alias ap(X: Term) = c;
  alias eval = c;
}

interface d : Term {
  alias ap(X: Term) = d;
  alias eval = d;
}

interface e : Term {
  alias ap(X: Term) = e;
  alias eval = e;
}

class Equals(X: Y, Y: X) {}

void EqualsDump(X: Equals!(Y, Z), Y, Z)() {
  writeln(aliasid(Y));
  writeln(aliasid(Z));
}

import std.stdio;

void main() {
  // Ic -> c
  Equals!(I.ap!(c).eval, c) Ic_c;

  // Kcd -> c
  Equals!(K.ap!(c).ap!(d).eval, c) Kcd_c;

  // KKcde -> d
  Equals!(K.ap!(K).ap!(c).ap!(d).ap!(e).eval, d) KKcde_d;

  // SIIIc -> Ic
  Equals!(S.ap!(I).ap!(I).ap!(I).ap!(c).eval, c) SIIIc_Ic;

  // SKKc -> Ic
  Equals!(S.ap!(K).ap!(K).ap!(c).eval, c) SKKc_Ic;

  // SIIKc -> KKc
  Equals!(S.ap!(I).ap!(I).ap!(K).ap!(c).eval, K.ap!(K).ap!(c).eval) SKKc_KKc;

  // SIKKc -> K(KK)c
  Equals!(S.ap!(I).ap!(K).ap!(K).ap!(c).eval, K.ap!(K.ap!(K)).ap!(c).eval) SIKKc_K0KK0c;

  // SIKIc -> KIc
  Equals!(S.ap!(I).ap!(K).ap!(I).ap!(c).eval, K.ap!(I).ap!(c).eval) SIKIc_KIc;

  // SKIc -> Ic
  Equals!(S.ap!(K).ap!(I).ap!(c).eval, c) SKIc_Ic;

  // R = S(K(SI))K  (reverse)
  alias R = S.ap!(K.ap!(S.ap!(I))).ap!(K);
  Equals!(R.ap!(c).ap!(d).eval, d.ap!(c).eval) Rcd_dc;


  // b(a) = S(Ka)(SII)
  alias b(a: Term) = S.ap!(K.ap!(a)).ap!(S.ap!(I).ap!(I));

  interface A0 : Term {
    alias ap(x: Term) = c;
    alias eval = A0;
  }
  
  interface A1 : Term {
    alias ap(x: Term) = x.ap!(A0).eval;
    alias eval = A1;
  }

  interface A2 : Term {
    alias ap(x: Term) = x.ap!(A1).eval;
    alias eval = A2;
  }


/*
  // These below codes can't pass the compailation because of too many recursive expansion.
  // error with NN1 is
  // Error: template instance ski.I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(I1!(S2!(K1!(S2!(K1!(S1!(I)), K)), S2!(I, I)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) recursive expansion
  // These below code might run if D compiler accept guge recursive expansion of template instance.

  // Single iteration
  alias NN1 = b!(R).ap!(b!(R)).ap!(A0);
  Equals!(NN1.eval, c) NN1_c;

  // Double iteration
  alias NN2 = b!(R).ap!(b!(R)).ap!(A1);
  Equals!(NN2.eval, c) NN2_c;

  // Triple iteration
  alias NN3 = b!(R).ap!(b!(R)).ap!(A2);
  Equals!(NN3.eval, c) NN3_c;


  interface An : Term {
    alias ap(x: Term) = x.ap!(An).eval;
    alias eval = An;
  }
  
  // Infinite iteration: Smashes scalac's stack
  alias NNn = b!(R).ap!(b!(R)).ap!(An);
  Equals!(NNn.eval, c) NNn_c;
 */
}