SKI calculus golf: Hello, World!

Question

Background

SKI combinator calculus, or simply SKI calculus, is a system similar to lambda calculus, except that SKI calculus uses a small set of combinators, namely S, K, and I instead of lambda abstraction. Unlike lambda calculus, beta reduction is possible only when a combinator is given enough arguments to reduce.

The three combinators in SKI calculus are defined as follows:

$$ \begin{aligned} S\;x\;y\;z & \overset{S}{\implies} x\;z\;(y\;z) \\ K\;x\;y & \overset{K}{\implies} x \\ I\;x & \overset{I}{\implies} x \end{aligned} $$

For example, the SKI expression \$ e=S(K(S\;I))K \$ is equivalent to the lambda expression \$ λx.λy.y\;x \$, as applying two arguments to \$ e \$ reduces to the desired result:

$$ \begin{aligned} S(K(S\;I))K\;x\;y & \overset{S}{\implies} (K(S\;I)x)(K\;x)y \\ & \overset{K}{\implies} S\;I(K\;x)y \\ & \overset{S}{\implies} (I\;y)(K\;x\;y) \\ & \overset{I,K}{\implies} y\;x \end{aligned} $$

It is known that any lambda expression can be converted to a SKI expression.

A Church numeral is an encoding of natural numbers (including zero) as a lambda expression. The Church encoding of a natural number \$ n \$ is \$ λf. λx. f^n\;x \$ - given a function \$ f \$ and an argument \$ x \$, \$ f \$ repeatedly applied to \$ x \$ \$ n \$ times.

It is possible to construct a lambda expression (and therefore a SKI expression) that performs various arithmetic (e.g. addition, multiplication) in Church encoding. Here are a few examples of Church numerals and Church arithmetic functions: (The given SKI expressions are possibly not minimal.)

$$ \begin{array}{r|r|r} \text{Expr} & \text{Lambda} & \text{SKI} \\ \hline 0 & λf. λx. x & K\;I \\ 1 & λf. λx. f\;x & I \\ 2 & λf. λx. f(f\;x) & S (S (K\;S) K) I \\ \text{Succ} \; n & λn. λf. λx. f(n\;f\;x) & S (S (K\;S) K) \\ m+n & λm. λn. λf. λx. m\;f(n\;f\;x) & S (K\;S) (S (K (S (K\;S) K))) \end{array} $$

It is also possible to represent lists as lambda terms using right-fold encoding. For example, the list of numbers [1, 2, 3] is represented by the lambda term \$λc. λn. c\;1 (c\;2 (c\;3\;n))\$ where each number represents the corresponding Church numeral.

Challenge

Write a SKI expression that evaluates to the string Hello, World!, i.e. the Church list of Church numerals representing the list

[72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]

Scoring and winning criterion

The score is the total number of S, K, and I combinators used. The submission with the lowest score wins.

Here is a Python script to check the correctness and score of your SKI expression.

Answer 1

Score = 192

S(SI(K(S(S(SSI)I))))
(S(SI(K(S(SIS)(KS))))
 (S(SS)I(K(S(SI(K(S(S(SI(K(SS)))(K(KI))))))))
  (S(SI(K(SS(S(K(S(SI)))K))))
   (S(SI(K(S(SI(S(K(SIS)))))))
    (S(SI(K(S(S(S(S(SSI))))K)))
     (S(SI(K(SI(S(S(SS))I))))
      (S(SI(K(SS(S(K(S(SI)))K))))
       (S(SI(K(S(SI(SI(S(K(S(SI)))))))))
        (S(SI(K(S(S(SI(K(SS)))(K(KI))))))
         (S(SI(K(S(SII)(K(SS)))))
          (S(SI(K(K(S(S(S(S(SI)))(KI))))))
           (K(KI)))))))))))))
(S(KS)
 (S(K(S(K(S(KS)K))))
  (S(K(SI))
   (S(KK)
    (S
     (S
      (S
       (SS(S(S(KS)S))(KS))
       (KS))
      (K(S(KS)K)))
     (KI))))))

Try it online!

An attempt to factor out common expressions from the numerals.

Old answer: score = 256

S(SI(K(S(SS)S(S(SI)(K(S(S(KS)K))))I)))
(S(SI(K(S(S(S(S(SIS)(KS)))S)S(S(KS)K)I)))
 (S(SS)I(K(S(SI(K(S(S(K(SSS))(SI))S(S(KS)K)I)))))
  (S(SI(K(S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I)))
   (S(SI(K(SIS(S(SS)K(SSK(S(S(KS)K))))I)))
    (S(SI(K(SS(S(S(SI))S)(K(S(S(KS)K)I)))))
     (S(SI(K(SS(S(SIS))(SSK)(S(S(KS)K))I)))
      (S(SI(K(S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I)))
       (S(SI(K(S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II)))
        (S(SI(K(S(S(K(SSS))(SI))S(S(KS)K)I)))
         (S(SI(K(SIS(S(S(SS)K(S(S(KS)K))))II)))
          (S(SI(K(S(S(SSI))(SSK)(S(S(KS)K))I)))
           (K(KI)))))))))))))
(S(KS)(S(K(S(K(S(KS)K))))(S(K(SI))K)))

Try it online!

How it works

I used a slightly targeted brute-force search to find expressions for the numbers. The basic idea is to loop through all expressions in order of increasing size, apply them to two arguments (with appropriate bounds on the evaluation length and depth), and see if any numbers fall out. For larger sizes, I restricted the search to expressions with S(KS)K (the B combinator) and one or more I at the end, since that seems to find a lot of numbers. Search code is below.

72 = S(SS)S(S(SI)(K(S(S(KS)K))))I
101 = S(S(S(S(SIS)(KS)))S)S(S(KS)K)I
108 = S(S(K(SSS))(SI))S(S(KS)K)I
108 = S(S(K(SSS))(SI))S(S(KS)K)I
111 = S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
44 = SIS(S(SS)K(SSK(S(S(KS)K))))I
32 = SS(S(S(SI))S)(K(S(S(KS)K)I))
87 = SS(S(SIS))(SSK)(S(S(KS)K))I
111 = S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
114 = S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II
108 = S(S(K(SSS))(SI))S(S(KS)K)I
100 = SIS(S(S(SS)K(S(S(KS)K))))II
33 = S(S(SSI))(SSK)(S(S(KS)K))I

To build the list, I used an intermediate list encoding where cons is simpler, then converted to the target encoding:

# pack [x, y, ..., z] = λc. c x (c y (... (c z [])))

square f = S(SS)I(Kf)   # λx. f (f x)
pack [] = K(KI)
pack [n, ...l] = S(SI(Kn))(pack [...l])
pack [n, n, ...l] = square (S(SI(Kn))) (pack [...l])
cons = S(KS)(S(K(S(K(S(KS)K))))(S(K(SI))K))
[...l] = pack [...l] cons

Search code (Rust with rayon and typed_arena)

use rayon::prelude::*;
use std::borrow::Cow::{self, Borrowed, Owned};
use std::cell::Cell;
use std::fmt;
use std::ptr;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering;
use typed_arena::Arena;

const N_BOUND: usize = 115;
const FUEL: u64 = 200;

#[derive(Clone, Copy)]
enum InputNode {
    S,
    K,
    I,
    B,
    App(usize, usize),
}

enum Side {
    Root,
    Left,
    Right { left: usize },
}

struct Input {
    nodes: Vec<(Option<InputNode>, Side)>,
    variables: Vec<usize>,
    apps_left: usize,
    primitives_left: usize,
    size: usize,
}

impl Input {
    fn new(size: usize) -> Input {
        Input {
            nodes: vec![(None, Side::Root)],
            variables: vec![],
            apps_left: size - 1,
            primitives_left: size,
            size,
        }
    }
}

struct InputTerm<'a>(&'a Input, usize);

impl fmt::Display for InputTerm<'_> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        let &InputTerm(input, ix) = self;
        match input.nodes[ix].0 {
            None => write!(fmt, "?"),
            Some(InputNode::S) => write!(fmt, "S"),
            Some(InputNode::K) => write!(fmt, "K"),
            Some(InputNode::I) => write!(fmt, "I"),
            Some(InputNode::B) => write!(fmt, "S(KS)K"),
            Some(InputNode::App(x, y)) => match input.nodes[y].0 {
                Some(InputNode::App(_, _)) | Some(InputNode::B) => {
                    write!(fmt, "{}({})", InputTerm(input, x), InputTerm(input, y))
                }
                _ => write!(fmt, "{}{}", InputTerm(input, x), InputTerm(input, y)),
            },
        }
    }
}

#[derive(Clone, Copy, Debug)]
enum Node<'a> {
    S,
    S1(&'a Cell<Node<'a>>),
    S2(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    K,
    K1(&'a Cell<Node<'a>>),
    I,
    B,
    B1(&'a Cell<Node<'a>>),
    B2(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    F,
    F1(&'a Cell<Node<'a>>),
    N,
    App(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    Ref(&'a Cell<Node<'a>>),
    Input(usize),
}
use Node::*;

struct Evaluator<'a> {
    arena: &'a Arena<Cell<Node<'a>>>,
    input: Input,
    fuel: u64,
}

impl<'a> Evaluator<'a> {
    fn whnf<'b>(&mut self, mut node: &'b Cell<Node<'a>>) -> Option<&'b Cell<Node<'a>>> {
        loop {
            match node.get() {
                S | S1(_) | S2(_, _) | K | K1(_) | I | B | B1(_) | B2(_, _) | F | F1(_) | N => {
                    break
                }
                App(x, y) => match self.apply(x, y)? {
                    Owned(node1) => node.set(node1.get()),
                    Borrowed(node1) => {
                        if !ptr::eq(node, node1) {
                            node.set(Ref(node1));
                        }
                        node = node1;
                    }
                },
                Ref(x) => node = x,
                Input(ix) => {
                    let Input {
                        nodes,
                        variables,
                        primitives_left,
                        apps_left,
                        ..
                    } = &mut self.input;
                    let input_node = if let Some(input_node) = nodes[ix].0 {
                        input_node
                    } else if *primitives_left > *apps_left + 1 || *apps_left == 0 {
                        variables.push(ix);
                        let input_node = InputNode::S;
                        *primitives_left -= 1;
                        nodes[ix].0 = Some(input_node);
                        input_node
                    } else {
                        variables.push(ix);
                        let len = nodes.len();
                        let input_node = InputNode::App(len, len + 1);
                        *apps_left -= 1;
                        nodes.push((None, Side::Left));
                        nodes.push((None, Side::Right { left: len }));
                        nodes[ix].0 = Some(input_node);
                        input_node
                    };
                    node.set(match input_node {
                        InputNode::S => S,
                        InputNode::K => K,
                        InputNode::I => I,
                        InputNode::B => B,
                        InputNode::App(ix0, ix1) => App(
                            self.arena.alloc(Cell::new(Input(ix0))),
                            self.arena.alloc(Cell::new(Input(ix1))),
                        ),
                    });
                }
            };
        }
        Some(node)
    }

    fn apply<'b>(
        &mut self,
        left: &'b Cell<Node<'a>>,
        right: &'a Cell<Node<'a>>,
    ) -> Option<Cow<'a, Cell<Node<'a>>>> {
        if self.fuel == 0 {
            return None;
        }
        self.fuel -= 1;
        match self.whnf(left)?.get() {
            S => Some(Owned(Cell::new(S1(right)))),
            S1(x) => Some(Owned(Cell::new(S2(x, right)))),
            S2(x, y) => {
                let xz = self.apply(x, right)?;
                self.apply(&xz, self.arena.alloc(Cell::new(App(y, right))))
            }
            K => Some(Owned(Cell::new(K1(right)))),
            K1(x) => Some(Borrowed(x)),
            I => Some(Borrowed(right)),
            B => Some(Owned(Cell::new(B1(right)))),
            B1(x) => Some(Owned(Cell::new(B2(x, right)))),
            B2(x, y) => self.apply(x, self.arena.alloc(Cell::new(App(y, right)))),
            F => Some(Owned(Cell::new(F1(right)))),
            F1(_) | N => None,
            App(_, _) | Ref(_) | Input(_) => unreachable!(),
        }
    }

    fn eval_number(&mut self, node: &Cell<Node<'a>>) -> Option<usize> {
        self.fuel = FUEL;
        let node = self.apply(node, self.arena.alloc(Cell::new(F)))?;
        self.fuel = FUEL;
        let node = self.apply(&node, self.arena.alloc(Cell::new(N)))?;
        let mut node = node.as_ref();
        for n in 0..N_BOUND {
            self.fuel = FUEL;
            match self.whnf(node)?.get() {
                N => return Some(n),
                F1(node1) => node = node1,
                _ => break,
            }
        }
        None
    }
}

fn search(found: &[AtomicUsize], mut input: Input) {
    'outer: loop {
        let mut evaluator = Evaluator {
            arena: &Arena::new(),
            input,
            fuel: FUEL,
        };
        let n = evaluator.eval_number(&Cell::new(Input(0)));
        input = evaluator.input;
        if let Some(n) = n {
            if found[n].fetch_min(input.size, Ordering::Relaxed) > input.size {
                println!("{} {} {}", n, input.size, InputTerm(&input, 0));
            }
        }
        loop {
            if let Some(&ix) = input.variables.last() {
                let len = input.nodes.len();
                let node = &mut input.nodes[ix].0;
                match node {
                    None | Some(InputNode::B) => unreachable!(),
                    Some(InputNode::S) => *node = Some(InputNode::K),
                    Some(InputNode::K) => *node = Some(InputNode::I),
                    Some(InputNode::I) => {
                        input.primitives_left += 1;
                        if input.apps_left > 0 {
                            *node = Some(InputNode::App(len, len + 1));
                            input.apps_left -= 1;
                            input.nodes.push((None, Side::Left));
                            input.nodes.push((None, Side::Right { left: len }));
                        } else {
                            *node = None;
                            input.variables.pop();
                            continue;
                        }
                    }
                    &mut Some(InputNode::App(x, y)) => {
                        input.apps_left += 1;
                        *node = None;
                        input.nodes.pop();
                        assert_eq!(y, input.nodes.len());
                        input.nodes.pop();
                        assert_eq!(x, input.nodes.len());
                        input.variables.pop();
                        continue;
                    }
                }
                match &input.nodes[ix] {
                    (Some(InputNode::I), Side::Left) => continue,
                    &(Some(InputNode::K), Side::Right { left: l }) => {
                        if let Some(InputNode::S) = &input.nodes[l].0 {
                            continue;
                        }
                    }
                    _ => (),
                }
                break;
            } else {
                break 'outer;
            }
        }
    }
}

fn main() {
    const MAX: AtomicUsize = AtomicUsize::new(usize::MAX);
    let found = [MAX; N_BOUND];
    for size in 1..10 {
        search(&found, Input::new(size));
    }
    for size in 10.. {
        (0..size - 5).into_par_iter().for_each(|b_depth| {
            for i_depths in 1..1 << (b_depth + 1) {
                let mut input = Input::new(size);
                for i in 0..b_depth + 1 {
                    input.nodes.push((None, Side::Left));
                    input.nodes.push((None, Side::Right { left: 2 * i + 1 }));
                    input.nodes[2 * i].0 = Some(InputNode::App(2 * i + 1, 2 * i + 2));
                    input.apps_left -= 1;
                }
                input.nodes[2 * b_depth + 2].0 = Some(InputNode::B);
                input.apps_left -= 3;
                input.primitives_left -= 4;
                for i_depth in 0..b_depth + 1 {
                    if i_depths & 1 << i_depth != 0 {
                        input.nodes[2 * i_depth + 1].0 = input.nodes[2 * i_depth + 2].0;
                        input.nodes[2 * i_depth + 2].0 = Some(InputNode::I);
                        input.primitives_left -= 1;
                    }
                }
                search(&found, input);
            }
        });
    }
}

Output for all numbers 0, …, 114:

0 2 KI
1 1 I
2 6 S(S(KS)K)I
3 9 S(K(SS(S(SS)I)))K
4 9 SII(S(S(KS)K)I)
5 11 S(S(SS)S)S(S(KS)K)I
6 11 SII(SSS(S(KS)K))I
7 13 S(SI)S(SSK(S(S(KS)K)))I
8 12 S(S(KS)S)I(S(S(KS)K))I
9 12 SII(SS(K(S(S(KS)K))))I
10 13 SI(SS)(SSK(S(S(KS)K)))I
11 13 S(SS)S(SSK(S(S(KS)K)))I
12 11 S(S(SI))I(S(S(KS)K))I
13 12 S(S(SS)I)I(S(S(KS)K))I
14 13 SS(SS)(SSK)(S(S(KS)K))I
15 14 S(SI)(S(SSK(S(S(KS)K))))II
16 10 S(S(SI))(S(S(KS)K))I
17 14 S(SS(K(S(S(SI)))))S(S(KS)K)I
18 13 SS(SS)(SS)(K(S(S(KS)K)))I
19 15 SS(SS(SS)(SS))(K(S(S(KS)K)))I
20 12 S(S(SIS))I(S(S(KS)K))I
21 14 S(SSK)(S(SIS))(S(S(KS)K))I
22 13 S(SSI(SSS))S(S(KS)K)I
23 13 S(S(SI))(SSK)(S(S(KS)K))I
24 14 S(S(S(S(SS))K))I(S(S(KS)K))I
25 13 SS(S(SSK)S)(S(S(KS)K))I
26 14 S(S(SS)S)(SS(KI))(S(KS)K)I
27 12 SSS(SS)(K(S(S(KS)K)))I
28 14 SS(SSS(SS))(K(S(S(KS)K)))I
29 14 S(S(S(S(SI))I))S(S(KS)K)II
30 15 S(S(SS(S(SS)K)))S(S(KS)K)II
31 14 SIS(S(SII)(K(S(S(KS)K))))I
32 14 SS(S(S(SI))S)(K(S(S(KS)K)I))
33 14 S(S(SSI))(SSK)(S(S(KS)K))I
34 15 SI(S(SS))(S(SSK))(S(S(KS)K))I
35 15 S(S(SI))(S(SSS)K)(S(S(KS)K))I
36 12 SI(SI)(SSS(S(KS)K))I
37 14 SII(S(S(SS)S)S(S(KS)K))I
38 16 S(S(S(S(S(K(SSK))))I))S(S(KS)K)I
39 12 SSS(SSS)S(S(KS)K)I
40 13 S(S(S(SSI))S)S(S(KS)K)I
41 15 S(SS(S(S(SSI))S))S(S(KS)K)I
42 13 S(S(SS(KI)))I(S(S(KS)K))I
43 15 SI(SIS)(S(SI)(K(S(S(KS)K))))I
44 16 SIS(S(SS)K(SSK(S(S(KS)K))))I
45 15 S(S(S(SI)))(SSS)(K(S(S(KS)K)))I
46 16 S(SI)(S(S(SSS)K(S(S(KS)K))))II
47 16 S(S(SIK))S(SSK(S(S(KS)K)))II
48 16 S(SS(S(S(S(SS)I))))K(S(S(KS)K))I
49 15 SS(S(S(SS))(SSK))(S(S(KS)K))I
50 14 SSS(S(S(SI))S(S(KS)K))II
51 15 S(SS(SS))I(SSK(S(S(KS)K)))I
52 15 SSS(SSI(S(K(S(S(KS)K)))))II
53 17 SS(S(SS(SS))I)(SSK(S(S(KS)K)))I
54 13 S(SI)S(SS)(K(S(S(KS)K)))I
55 15 SS(S(SI)S(SS))(K(S(S(KS)K)))I
56 13 S(S(SS)(SSS))S(S(KS)K)I
57 15 S(SS(S(SS)(SSS)))S(S(KS)K)I
58 17 SSS(S(S(S(SIK))))(K(K(S(S(KS)K))))I
59 18 S(S(S(S(SIS(S(SS))K)))S)S(S(KS)K)I
60 17 S(SS(SS(KI)))(SSK)(S(S(KS)K))II
61 14 S(S(S(S(SS)I))S)S(S(KS)K)I
62 16 S(SS(S(S(S(SS)I))S))S(S(KS)K)I
63 15 S(SS)S(SI(SSK(S(S(KS)K))))I
64 13 S(SSS)S(K(S(S(KS)K)I))I
65 15 S(SS)K(S(SS)S(K(S(S(KS)K))))I
66 16 S(SS(S(S(S(SIS)))))K(S(S(KS)K))I
67 16 S(S(S(S(S(SS))I)))S(K(S(S(KS)K)))I
68 15 SIS(S(SSS(K(S(S(KS)K)))))II
69 18 SS(SI(K(SI)))(SS(SSK)(S(S(KS)K)))I
70 17 S(S(S(S(S(SI)(S(KS)))))S)S(S(KS)K)I
71 18 SIS(S(S(SSK))(S(SI)S)(S(KS)K))II
72 14 S(SS)S(S(SI)(K(S(S(KS)K))))I
73 16 SS(S(SI)(SS)(SS))(K(S(S(KS)K)))I
74 15 S(S(SI)(S(SSS)S))S(S(KS)K)I
75 17 S(SS(S(SI)(S(SSS)S)))S(S(KS)K)I
76 16 SS(SSS)(S(SIK))(K(S(S(KS)K)))I
77 17 S(SS(SI(SI)))(SSK)(S(S(KS)K))II
78 18 S(SI)(S(S(SI)I)S)(SI(K(S(S(KS)K))))I
79 17 S(S(S(SI(KK))))S(SSK(S(S(KS)K)))I
80 14 S(SIS)(S(SI)I)(S(S(KS)K))I
81 12 SIS(SS(K(S(S(KS)K))))I
82 16 SS(S(K(SIS))(SS))(K(S(S(KS)K)))I
83 16 S(S(SSI)(S(KS)S))K(S(S(KS)K))I
84 15 SIS(SSK(SI(K(S(S(KS)K)))))I
85 14 S(S(S(SS)I)I)I(S(S(KS)K))I
86 15 S(SS)S(SS(K(K(S(S(KS)K)))))II
87 15 SS(S(SIS))(SSK)(S(S(KS)K))I
88 15 S(SI)(S(S(SSK))I)(S(S(KS)K))I
89 17 SI(S(SSI)K)(S(SI)(K(S(S(KS)K))))I
90 16 SI(S(SI))(S(SSS)K(S(S(KS)K)))I
91 15 S(SIS)(S(SSK)I)(S(S(KS)K))I
92 15 SI(S(SIS))(SSK(S(S(KS)K)))I
93 18 S(SI)S(SIS(S(K(SSK(S(S(KS)K))))))I
94 17 SS(SI(S(SIS)))(SSK(S(S(KS)K)))I
95 18 S(S(S(S(S(SI)))S)S)(SIS)(S(KS)K)II
96 16 SIS(S(S(SSI)(K(S(S(KS)K)))))II
97 16 S(S(S(SS)I))(SSS)(K(S(S(KS)K)))I
98 15 S(SS)(SSS)(SI(K(S(S(KS)K))))I
99 16 S(SI)S(SIK(SSK(S(S(KS)K))))I
100 15 SIS(S(S(SS)K(S(S(KS)K))))II
101 16 S(S(S(S(SIS)(KS)))S)S(S(KS)K)I
102 17 S(SI(S(SS)))S(SI(K(S(S(KS)K))))II
103 15 S(S(SI)S(SS(KS)))S(S(KS)K)I
104 15 SIS(SSI(S(K(S(S(KS)K)))))II
105 17 S(S(S(S(S(SSS)))K))S(K(S(S(KS)K)))I
106 17 S(S(S(S(S(SS(KI)))I))S)S(S(KS)K)I
107 19 S(S(SSS(SIS))(S(SI)))S(K(S(S(KS)K)))I
108 14 S(S(K(SSS))(SI))S(S(KS)K)I
109 16 SSS(S(S(SSK))(K(S(S(KS)K))))II
110 16 SSK(S(SSS(K(S(S(KS)K)))))III
111 17 S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
112 16 S(SSS)(S(S(S(SS))S)S)(S(KS)K)I
113 18 S(SS(S(S(S(S(K(S(SI))))))S))S(S(KS)K)I
114 18 S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II

Answer 2

5844 SKIs

The Baseline

In order to respect your scrolling fingers, I won't copy & paste it here. The 5,844 score is the SKI count; it doesn't even include all the parentheses. But please do try it online!

Generating Lambda Calculus

def church_numeral(n):
    return r'(\f.\x. '+'f('*n +'x'+ ')'*n+')'

def church_list(lst):
    acc = r'\c.\n.'
    for l in lst:
        acc+='(c '+l+' '
    acc+='n'+')'*len(lst)
    return acc

def church_numeral_list(lst):
    nums = [church_numeral(l) for l in lst]
    return church_list(nums)

print(church_numeral_list([72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]))

• The function church_numeral generates a number of the form: \f. \x. f (f (f x)).

• The function church_list generates a list of the form: \c. \n. c 0 (c 1 (c 2 n) which is precisely the format a right-fold list takes as per Wikipedia.

• The function church_numeral_list just converts the numbers to Church numerals and sends them over to be list-churchified.

If anyone would like to strategically compile the lambda calculus to SKI, here's a link to the output on TIO. The lambda calculus it generates is totally naive; it doesn't attempt to optimize anything, as you can tell.

Compiling to SKI

This part was super hacky. I used the intermediate form generated by this site– the first lambda2ski compiler I could find. That site is actually a compiler from the lambda calculus into WebAssembly, which seems totally out of left field!

That's why the output I used was just the intermediate form which the site luckily spits outs as well. There may be more efficient compilers, I don't know. Even still, there was one more issue, the output — I mean intermediate form — also used the B & C combinators. Those took me a while to find, but eventually I found their translation into SKI here on good ol' Wikipedia.

So just two more lines of code left:

B = "S(KS)K"
C = "S(S(K(S(KS)K))S)(KK)"
ski = ski.replace('B', B)
ski = ski.replace('C', C)

A bad bug

Just kidding! There's a bug in the very last step. And there are no SKI interpreters to help you out. Just Bubbler's TIO link which spits out nasty and nonsensical python errors at you. Or maybe it seems to do run fine, only to output <function <lambda> at 0xmadbadhex>.

Can you spot it?

The B & C combinators need to be wrapped in parentheses. So it should really be:

B = "(S(KS)K)"
C = "(S(S(K(S(KS)K))S)(KK))"
ski = ski.replace('B', B)
ski = ski.replace('C', C)

And now you've built your very own hello-world app in SKI and successfully deployed it to TIO!