Church encodings implemented in Java 8. Includes natural numbers and arithmetic, booleans, conditionals, recursion, and a demonstration using the factorial function.

church.java

package church;

import java.util.function.Function;
import java.util.function.Supplier;
import java.util.function.UnaryOperator;

import org.junit.Test;


public class church {
   @Test
   public void testChurchArithmetic() {
      final ChurchNumeral zero = ChurchNumeral.ZERO;
      final ChurchNumeral one = ChurchNumeral.increment.apply(zero);
      final ChurchNumeral two = ChurchNumeral.increment.apply(one);
      final ChurchNumeral three = ChurchNumeral.increment.apply(two);
      final ChurchNumeral four = ChurchNumeral.increment.apply(three);

      assert ChurchNumeral.churchToInt(four) == 4;
      assert ChurchNumeral.churchToInt(ChurchNumeral.multiply.apply(three).apply(four)) == 12;
      assert ChurchNumeral.churchToInt(ChurchNumeral.add.apply(three).apply(four)) == 7;
      assert ChurchNumeral.churchToInt(ChurchNumeral.addInc.apply(three).apply(four)) == 7;
      assert ChurchNumeral.churchToInt(ChurchNumeral.exp.apply(three).apply(four)) == 81;
   }

   @Test
   public void testChurchBooleans() {
      assert ChurchBoolean.churchToBool(ChurchBoolean.TRUE);
      assert !ChurchBoolean.churchToBool(ChurchBoolean.FALSE);
   }

   @Test
   public void testChurchPairs() {
      final ChurchPair pair = ChurchPair.cons(true).apply(false);
      assert ChurchPair.<Boolean> car(pair);
      assert !ChurchPair.<Boolean> cdr(pair);
   }

   @Test
   public void testDecrement() {
      final ChurchNumeral zero = ChurchNumeral.ZERO;
      final ChurchNumeral one = ChurchNumeral.increment.apply(zero);
      final ChurchNumeral two = ChurchNumeral.increment.apply(one);
      final ChurchNumeral three = ChurchNumeral.increment.apply(two);
      final ChurchNumeral four = ChurchNumeral.increment.apply(three);

      assert ChurchNumeral.churchToInt(ChurchNumeral.decrement.apply(four)) == 3;
      assert ChurchNumeral.churchToInt(ChurchNumeral.decrement.apply(three)) == 2;
   }

   @Test
   public void testFactorial() {
      final ChurchNumeral zero = ChurchNumeral.ZERO;
      final ChurchNumeral one = ChurchNumeral.increment.apply(zero);
      final ChurchNumeral two = ChurchNumeral.increment.apply(one);
      final ChurchNumeral three = ChurchNumeral.increment.apply(two);
      final ChurchNumeral four = ChurchNumeral.increment.apply(three);

      assert ChurchNumeral.churchToInt(ChurchNumeral.factorial.apply(four)) == 24;
   }

   @FunctionalInterface
   private interface ChurchNumeralT<T> extends ChurchNumeral {
      @SuppressWarnings({ "rawtypes", "unchecked" })
      @Override
      default <U> UnaryOperator<U> apply(UnaryOperator<U> f) {
         return ((ChurchNumeralT)this).tapply(f);
      }

      UnaryOperator<T> tapply(UnaryOperator<T> f);
   }

   public interface ChurchNumeral {

      <T> UnaryOperator<T> apply(UnaryOperator<T> f);

      static int churchToInt(ChurchNumeral n) {
         return n.<Integer> apply(s -> s + 1).apply(0);
      }

      static UnaryOperator<ChurchNumeral> increment =
         n -> (ChurchNumeralT<?>)f -> x -> f.apply(n.apply(f).apply(x));

      static ChurchNumeral ZERO = (ChurchNumeralT<?>)f -> x -> x;
      static ChurchNumeral ONE = ChurchNumeral.increment.apply(ChurchNumeral.ZERO);

      static Function<ChurchNumeral, UnaryOperator<ChurchNumeral>> multiply =
         n -> m -> (ChurchNumeralT<?>)f -> x -> m.apply(n.apply(f)).apply(x);

      static Function<ChurchNumeral, UnaryOperator<ChurchNumeral>> add =
         n -> m -> (ChurchNumeralT<?>)f -> x -> m.apply(f).apply(n.apply(f).apply(x));

      static Function<ChurchNumeral, UnaryOperator<ChurchNumeral>> addInc =
         n -> m -> m.apply(ChurchNumeral.increment).apply(n);

      static Function<ChurchNumeral, Function<ChurchNumeral, ChurchNumeral>> exp =
         n -> m -> m.apply(ChurchNumeral.multiply.apply(n))
            .apply(ChurchNumeral.ONE);

      // decrement uses church pairs
      static UnaryOperator<ChurchNumeral> decrement =
         n -> ChurchPair.car(n.apply(ChurchPair.shift)
            .apply(ChurchPair.cons(ChurchNumeral.ZERO).apply(ChurchNumeral.ZERO)));

      static Function<ChurchNumeral, ChurchBoolean> isZero =
         n -> n.apply((UnaryOperator<ChurchBoolean>)a -> ChurchBoolean.FALSE)
            .apply(ChurchBoolean.TRUE);

      static Function<ChurchNumeral, ChurchNumeral> factorial = YCombinator.Y(
         f -> n -> (ChurchNumeral)ChurchBoolean.ifte(ChurchNumeral.isZero.apply(n))
            .apply(() -> ChurchNumeral.ONE)
            .apply(() -> ChurchNumeral.multiply.apply(n)
               .apply(f.apply(ChurchNumeral.decrement.apply(n)))));
   }

   @FunctionalInterface
   private interface ChurchBooleanT<T> extends ChurchBoolean {
      @SuppressWarnings({ "rawtypes", "unchecked" })
      @Override
      default <U> UnaryOperator<U> apply(U f) {
         return ((ChurchBooleanT)this).tapply(f);
      }

      UnaryOperator<T> tapply(T f);
   }

   public interface ChurchBoolean {
      <T> UnaryOperator<T> apply(T f);

      public static final ChurchBoolean TRUE = (ChurchBooleanT<?>)t -> f -> t;

      public static final ChurchBoolean FALSE = (ChurchBooleanT<?>)t -> f -> f;

      public static Boolean churchToBool(ChurchBoolean b) {
         return b.apply(true).apply(false);
      }

      public static <T> Function<Supplier<T>, Function<Supplier<T>, T>> ifte(ChurchBoolean b) {
         return t -> e -> b.apply(t).apply(e).get();
      }
   }

   private interface ChurchPairT<T> extends ChurchPair {
      @SuppressWarnings({ "rawtypes", "unchecked" })
      @Override
      default <U> U apply(Function<U, UnaryOperator<U>> selector) {
         return (U)((ChurchPairT)this).tapply(selector);
      }

      T tapply(Function<T, UnaryOperator<T>> selector);
   }


   public interface ChurchPair {
      <T> T apply(Function<T, UnaryOperator<T>> selector);

      static <T> Function<T, ChurchPair> cons(T x) {
         return y -> (ChurchPairT<T>)(s -> s.apply(x).apply(y));
      }

      static <T> T car(ChurchPair t) {
         return t.apply(a -> d -> a);
      }

      static <T> T cdr(ChurchPair t) {
         return t.apply(a -> d -> d);
      }

      static Function<ChurchNumeral, ChurchPair> selfAndInc =
         x -> ChurchPair.cons(x).apply(ChurchNumeral.increment.apply(x));

      static UnaryOperator<ChurchPair> shift =
         p -> ChurchPair.selfAndInc.apply(ChurchPair.cdr(p));
   }

   public interface YCombinator {
      interface RecursiveFunction<F> extends Function<RecursiveFunction<F>, F> {
      }

      public static <A, B> Function<A, B> Y(Function<Function<A, B>, Function<A, B>> f) {
         final RecursiveFunction<Function<A, B>> r = w -> f.apply(x -> w.apply(w).apply(x));
         return r.apply(r);
      }
   }
}