Introduction: Combinatory Logic

Combinatory logic (CL) is based off of things called combinators, which are basically functions. There are two basic "built-in" combinators, S and K, which will be explained later.


CL is left-associative, which means brackets (containing stuff) which are at the far-left of anther pair of brackets containing it can be removed, with its stuff released. For example, something like this:

((a b) c)

Can be reduced to

(a b c)

Where the (a b) is on the far-left of the bigger bracket ((a b) c), so it can be removed.

A much bigger example of left-association (square brackets are explanations):

  ((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j)))   [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j)))     [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j)))       [((g h) i) = (g h i)]
= (a b c (d e f (g h i j)))         [((g h i) j) = (g h i j)]

Brackets can also be reduced when more than one pair wrap around the same objects. Examples:

((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
                        Note that this doesn't reduce to `a b c`, because
                        `(b c)` is not on the left.]


CL has two "built-in" combinators, S and K, which can switch objects (single combinators, or a group of combinators / groups wrapped around brackets) around like so:

K x y = x
S x y z = x z (y z)

Where x, y and z can be stand-ins for anything.

An example of S and K are as follows:

  (S K K) x [x is a stand-in for anything]
= S K K x   [left-associativity]
= K x (K x) [S combinator]
= x         [K combinator]

Another example:

  S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
               where n is the number of "arguments" n is defined to have -
               S takes 3 arguments, so it only works on 3 terms]

The above are examples of normal CL statements, where the statement cannot be evaluated further and achieves an end result in a finite amount of time. There are non-normal statements (which are CL statements that do not terminate and will keep being evaluated forever), but they aren't within the scopes of the challenge and won't need to be covered.

If you want to learn more about CL, read this Wikipedia page.


Your task is to make extra combinators, given the number of arguments, and what it evaluates to as input, which is given like so:

{amount_of_args} = {evaluated}

Where {amount_of_args} is a positive integer equal to the number of args, and {evaluated} consists of:

  • arguments up to the amount of args, with 1 being the first argument, 2 being the second, etcetera.
    • You are guaranteed that argument numbers above the amount of args (so a 4 when {amount_of_args} is only 3) won't appear in {evaluated}.
  • brackets ()

So examples of inputs are:

3 = 2 3 1
4 = 1 (2 (3 4))

The first input is asking for a combinator (say, R) with three arguments (R 1 2 3), which then evaluates into:

R 1 2 3 -> 2 3 1

The second input asks for this (with a combinator name A):

A 1 2 3 4 -> 1 (2 (3 4))

Given the input in this format, you must return a string of S, K and (), which when substituted with a combinator name and run with arguments, returns the same evaluated statement as the {evaluated} block when the command block is substituted back for that combinator name.

The output combinator statement may have its whitespace removed and the outer brackets removed, so something like (S K K (S S)) can be turned into SKK(SS).

If you want to test your program's outputs, @aditsu has made a combinatory logic parser (which includes S, K, I and even other ones like B and C) here.


Since this is a , the aim of this challenge is to achieve the smallest amount of bytes in the output possible, given these 50 test-cases. Please put your results for the 50 test-cases in the answer, or make a pastebin (or something similar) and post a link to that pastebin.

In the event of a tie, the earliest solution wins.


  • Your answer must return CORRECT output - so given an input, it must return the correct output as per the definition in the task.
  • Your answer must output within an hour on a modern laptop for each test case.
  • Any hard-coding of solutions is disallowed. However, you are allowed to hard-code up to 10 combinators.
  • Your program must return the same solution every time for the same input.
  • Your program must return a valid result for any input given, not just test-cases.
  • \$\begingroup\$ How can you make sure that people won't steal combinators found in other answers? \$\endgroup\$ – Fatalize Jan 7 '17 at 15:42
  • \$\begingroup\$ @Fatalize That shouldn't matter too much, as people can take inspiration from other people's answers and build on that to create better answers. \$\endgroup\$ – clismique Jan 8 '17 at 0:34
  • \$\begingroup\$ Speaking of inspiration, I notice that when the desired result does not contain a 1, you can subtract 1 from everything, and then wrap solution for that answer in K(). Example: Solution for 2 -> 1 is K, therefore solution for 3 -> 2 is KK, solution for 4 -> 3 is K(KK) etc. \$\endgroup\$ – Neil Jan 8 '17 at 22:59

Haskell, score 5017

This combines the dumbest possible algorithm for abstraction elimination ((λx. x) = I; (λx. y) = Ky; (λx. M N) = S(λx. M)(λx. N)) with a peephole optimizer used after every application. The most important optimization rule is S(Kx)(Ky) ↦ K(xy), which stops the algorithm from always blowing up exponentially.

The set of rules is configured as a list of string pairs so it’s easy to play around with new rules. As a special bonus of reusing the input parser for this purpose, S, K, and I are also accepted within the input combinators.

Rules are not applied unconditionally; rather, both the old and new versions are kept, and suboptimal versions are pruned only when their length exceeds that of the best version by more than some constant (currently 3 bytes).

The score is slightly improved by treating I as a fundamental combinator until the output stage rewrites it to SKK. That way KI = K(SKK) can be shortened by 4 bytes to SK on output without confusing the rest of the optimizations.

{-# LANGUAGE ViewPatterns #-}

import qualified Data.IntMap as I
import qualified Data.List.NonEmpty as N
import System.IO

data Term
  = V Int
  | S
  | K
  | I
  | A (N.NonEmpty (Int, Term, Term))
  deriving (Show, Eq, Ord)

parse :: String -> (Term, String)
parse = parseApp . parse1

parseApp :: (Term, String) -> (Term, String)
parseApp (t, ' ':s) = parseApp (t, s)
parseApp (t, "") = (t, "")
parseApp (t, ')':s) = (t, ')' : s)
parseApp (t1, parse1 -> (t2, s)) =
  parseApp (A (pure (appLen (t1, t2), t1, t2)), s)

parse1 :: String -> (Term, String)
parse1 (' ':s) = parse1 s
parse1 ('(':(parse -> (t, ')':s))) = (t, s)
parse1 ('S':s) = (S, s)
parse1 ('K':s) = (K, s)
parse1 ('I':s) = (I, s)
parse1 (lex -> [(i, s)]) = (V (read i), s)

ruleStrings :: [(String, String)]
ruleStrings =
  [ ("1 3(2 3)", "S1 2 3")
  , ("S(K(S(K1)))(S(K(S(K2)))3)", "S(K(S(K(S(K1)2))))3")
  , ("S(K(S(K1)))(S(K2))", "S(K(S(K1)2))")
  , ("S(K1)(K2)", "K(1 2)")
  , ("S(K1)I", "1")
  , ("S(S(K1)2)(K3)", "S(K(S1(K3)))2")
  , ("S(SI1)I", "S(SSK)1")

rules :: [(Term, Term)]
rules = [(a, b) | (parse -> (a, ""), parse -> (b, "")) <- ruleStrings]

len :: Term -> Int
len (V _) = 1
len S = 1
len K = 1
len I = 3
len (A ((l, _, _) N.:| _)) = l

appLen :: (Term, Term) -> Int
appLen (t1, S) = len t1 + 1
appLen (t1, K) = len t1 + 1
appLen (K, I) = 2
appLen (t1, t2) = len t1 + len t2 + 2

notA :: Term -> Bool
notA (A _) = False
notA _ = True

alt :: N.NonEmpty Term -> Term
alt ts =
  head $
  N.filter notA ts ++
  [A (N.nub (a N.:| filter (\(l, _, _) -> l <= minLen + 3) aa))]
    a@(minLen, _, _) N.:| aa =
      N.sort $ do
        A b <- ts

match :: Term -> Term -> I.IntMap Term -> [I.IntMap Term]
match (V i) t m =
  case I.lookup i m of
    Just ((/= t) -> True) -> []
    _ -> [I.insert i t m]
match S S m = [m]
match K K m = [m]
match I I m = [m]
match (A a) (A a') m = do
  (_, t1, t2) <- N.toList a
  (_, t1', t2') <- N.toList a'
  m1 <- match t1 t1' m
  match t2 t2' m1
match _ _ _ = []

sub :: I.IntMap Term -> Term -> Term
sub _ S = S
sub _ K = K
sub _ I = I
sub m (V i) = m I.! i
sub m (A a) =
  alt $ do
    (_, t1, t2) <- a
    pure (sub m t1 & sub m t2)

optimize :: Term -> Term
optimize t = alt $ t N.:| [sub m b | (a, b) <- rules, m <- match a t I.empty]

infixl 5 &

(&) :: Term -> Term -> Term
t1 & t2 = optimize (A (pure (appLen (t1, t2), t1, t2)))

elim :: Int -> Term -> Term
elim n (V ((== n) -> True)) = I
elim n (A a) =
  alt $ do
    (_, t1, t2) <- a
    pure (S & elim n t1 & elim n t2)
elim _ t = K & t

paren :: String -> Bool -> String
paren s True = "(" ++ s ++ ")"
paren s False = s

output :: Term -> Bool -> String
output S = const "S"
output K = const "K"
output I = paren "SKK"
output (V i) = \_ -> show i ++ " "
output (A ((_, K, I) N.:| _)) = paren "SK"
output (A ((_, t1, t2) N.:| _)) = paren (output t1 False ++ output t2 True)

convert :: Int -> Term -> Term
convert 0 t = t
convert n t = convert (n - 1) (elim n t)

process :: String -> String
process (lex -> [(n, lex -> [((`elem` ["=", "->"]) -> True, parse -> (t, ""))])]) =
  output (convert (read n) t) False

main :: IO ()
main = do
  line <- getLine
  putStrLn (process line)
  hFlush stdout

Try it online!


  1. S(KS)K
  2. S(K(SS(KK)))(S(KK)S)
  3. S(K(SS))(S(KK)K)
  4. S(K(SS(KK)))(S(KK)(S(KS)(S(K(S(SKK)))K)))
  5. S(K(S(K(SS(SK)))))(S(K(SS(SK)))(S(SKK)(SKK)))
  6. KK
  7. S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)
  8. S(K(SS(K(S(KK)(S(SKK)(SKK))))))(S(SSK(KS))(S(S(KS)(S(KK)(S(KS)K)))(K(S(K(S(SSK)))K))))
  9. S(K(S(KK)))(S(K(S(S(SKK)(SKK))))K)
  10. SK
  11. S(KS)(S(KK)(S(K(SS))(S(KK)K)))
  12. S(K(SS(K(S(KK)K))))(S(KK)(S(KS)(S(SSK(KS))(S(K(SS))(S(KK)K)))))
  13. S(K(S(K(S(K(SS(KK)))(S(KK)S)))))(S(K(SS(KK)))(S(KK)(S(KS)(S(K(S(SKK)))K))))
  14. S(K(S(K(S(K(SS(KK)))(S(KK)S)))))(S(K(S(SKK)))K)
  15. S(K(S(K(S(KS)K))))(S(KS)K)
  16. S(K(S(KS)K))
  17. S(K(S(K(S(K(SS(K(S(S(KS)(S(KK)(SSK)))(K(S(SKK)(SKK)))))))(S(KK)(S(KS)K))))))(S(K(SS(K(SSK))))(S(KK)(S(KS)(S(KK)(SSK)))))
  18. SSS(KK)
  19. KK
  20. S(KK)(S(KK)(S(S(KS)K)(S(K(S(SKK)))(S(K(S(SKK)))K))))
  21. S(S(KS)(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))
  22. S(KK)
  23. S(KS)(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K)))))
  24. S(K(S(K(S(KS)K))))(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(S(KK)(S(K(SS))(S(KK)K))))
  25. S(KS)(S(KK)(S(KS)K))
  26. S(S(KS)(S(KK)(S(KS)(S(KK)(S(K(S(K(SS(KK)))))(S(KS)(S(KK)(S(SSK(KS))(S(KS)(S(SKK)(SKK)))))))))))(K(S(S(KS)(S(K(S(K(S(KS)(S(K(S(KS)(S(K(S(SKK)))K))))))))(S(K(S(SKK)))K)))(S(K(S(K(S(KK)K))))(S(K(S(SKK)))K))))
  27. S(K(S(K(S(K(SS(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))(S(KK)(S(KS)K))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))
  28. K(S(KK))
  29. S(K(S(K(S(K(S(K(S(KS)K))))(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))K)))))(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(S(KK)(S(K(SS))(S(KK)K))))
  30. S(KK)(S(K(SSS(KK))))
  31. K(SSS(KK))
  32. S(K(SS(K(S(S(KS)(S(KK)(S(KS)K)))(K(S(K(S(SKK)))K))))))(S(KK)(S(KS)(SS(S(S(KS)(S(KK)(S(KS)(S(K(S(KS)(S(KK)(S(KS)K)))))))))(KK))))
  33. S(K(S(K(S(K(S(K(SS(KK)))(S(KK)S)))))))(S(K(SS(K(S(KK)K))))(S(KK)(SSS(KS))))
  34. S(K(S(K(S(KK)K))))
  35. S(K(S(K(S(K(S(K(SS(K(S(K(S(SKK)))K))))(S(KK)(S(KS)(S(KK)(S(K(SS(K(S(K(S(SKK)))K))))(S(KK)(S(K(SS))(S(KK)K)))))))))))))(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K))
  36. S(K(SS(K(S(K(SS(K(S(K(S(SKK)))K))))(S(KK)(S(KS)(SS(S(S(KS)(S(KK)(S(KS)(S(K(S(SKK)))K)))))(KK))))))))(S(KK)(S(KS)(S(KK)(S(K(S(K(S(K(S(K(S(K(SS(KK)))(S(KK)S)))))))))(S(K(SS(KK)))(S(KK)(S(KS)(S(K(S(KS)(S(KK)(S(KS)K))))))))))))
  37. S(KK)(S(K(S(K(S(KK)(S(KK)K)))))(SS(SK)))
  38. K(S(K(SSS(KK))))
  39. S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))(S(KK)(S(KS)K))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))
  40. S(K(S(KK)))(S(KS)(S(KK)(S(K(S(KK)(S(KK)K))))))
  41. S(K(SS(K(S(S(KS)(S(KK)(S(KS)K)))(K(S(K(S(SKK)))K))))))(S(KK)(S(KS)(S(KK)(S(K(S(K(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K))))))(S(K(SS(K(S(KK)(S(K(SS))K)))))(S(KK)(S(K(SS))(S(KK)(S(K(S(K(S(KK)(S(KS)K)))))(S(KS)K))))))))))
  42. S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))(S(KK)(S(KS)K))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))
  43. K(K(K(K(K(S(KK)(S(KK)(S(K(SS(SK)))(SSK))))))))
  44. S(KK)(S(K(S(KK)(S(KK)(S(KK)(S(KK)K))))))
  45. S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(S(K(SS(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))(S(KK)(S(KS)K))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))
  46. S(K(S(K(S(K(S(K(S(K(SS(K(S(K(SS(K(S(K(SS(KK)))(S(KK)(S(KS)(S(K(S(SKK)))K)))))))(S(KK)(S(KS)(S(KK)(S(SSK(KS))(S(K(SS))(S(KK)K))))))))))(S(KK)(S(KS)(S(KK)(S(K(SS(K(S(KK)(S(KS)(S(KK)(S(K(SS(K(S(KK)(S(KS)K)))))(S(KK)(S(K(SS))(S(KK)(S(K(SS(K(S(KK)K))))(S(KK)S))))))))))))(S(KK)(S(K(SS))K))))))))))(S(K(SS(K(S(KK)(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(S(KK)(S(K(SS))(S(KK)K))))))))(S(KK)S))))))(S(K(SS(K(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(S(KK)(S(K(SS))(S(KK)K)))))))(S(KK)(S(KS)(S(KK)(S(K(S(K(S(KS)(S(KK)(S(KS)K))))))(S(KS)(S(KK)(S(K(SS))(S(KK)K)))))))))
  47. S(K(SS(K(SS(S(S(KS)(S(KK)S)))(KK)))))(S(KK)(S(KS)(S(K(S(K(S(KS)(S(KK)(S(KS)(S(KK)(S(K(S(K(S(K(SS(K(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)K))))))(S(KK)(S(K(SS))(S(KK)K)))))))(S(KK)(S(KS)K))))))))))))))(S(K(S(S(KS)(S(KK)(S(K(SS))(S(KK)(S(K(S(K(S(KS)K))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(SS))(S(KK)K)))))))))))))(S(KK)(S(K(S(K(S(KK)(S(KS)(S(KK)(S(K(SS(K(S(KK)(S(KS)K)))))(S(KK)(S(K(SS))K)))))))))(S(KS)(S(KK)(S(K(SS(K(S(KK)K))))(S(KK)(S(KS)(S(SSK(KS))(S(K(SS(KK)))(S(KK)(S(KS)(S(K(S(SKK)))K))))))))))))))))
  48. K(S(K(S(KK)(S(K(S(KK)(S(K(S(KK)(S(KK)K))))))))))
  49. S(KK)(S(K(S(K(S(KK)(S(K(S(K(S(KK)(S(K(S(K(S(KK)(S(K(S(K(S(KK)(S(K(S(KK)))(S(K(S(SKK)))K))))))(S(K(S(SKK)))K))))))(S(K(S(SKK)))K))))))(S(K(S(SKK)))K))))))(S(K(S(SKK)))K))
  50. S(K(S(K(S(K(S(K(S(K(S(KK)))(S(K(SS(K(S(K(S(S(KS)(S(K(S(SKK)))K))))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)K)))))))(S(K(SS(K(S(K(SS))(S(KK)K)))))(S(KK)(S(KS)(S(KK)(S(K(S(K(S(KK)(S(KK)(S(KK)(S(KK)K)))))))(S(K(SS))(S(KK)K)))))))
| improve this answer | |
  • \$\begingroup\$ Would it be possible to make the expressions auto-optimize (eg S (K x) (K y) = K (x y))? \$\endgroup\$ – CalculatorFeline Jun 24 '17 at 19:46
  • \$\begingroup\$ @CalculatorFeline I don’t understand your question; S(Kx)(Ky) is automatically optimized to K(xy). \$\endgroup\$ – Anders Kaseorg Jul 8 '17 at 2:58
  • \$\begingroup\$ Wait, are these expressions represented as partially applied functions or something else? If partially applied functions, then maybe you could do something like my last comment. \$\endgroup\$ – CalculatorFeline Jul 8 '17 at 15:20
  • \$\begingroup\$ @CalculatorFeline The representation looks like, for example, 3=1(2 3) ↦ 2=S(K1)(S(K2)I) ↦ 2=S(K1)2 ↦ 1=S(S(KS)(S(KK)(K1)))I ↦ 1=S(S(KS)(K(K1)))I ↦ 1=S(K(S(K1)))I ↦ 1=S(K(S(K1)))I ↦ 1=S(K1) ↦ S(KS)(S(KK)I) ↦ S(KS)K. As you can see, we have already used the rule S(Kx)(Ky) ↦ K(xy) many times, along with the others I listed in ruleStrings. If we didn’t, the output would be exponentially longer: for this tiny example, we’d have gotten S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK)(SKK)))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(SK))))(S(KK)(SK))) instead of S(KS)K. \$\endgroup\$ – Anders Kaseorg Jul 8 '17 at 21:45

Sum of solution lengths: 12945 8508 5872

Haskell code that takes input lines from stdin and doesn't care if the separator is = or ->:

data E=S|K|V Int|A E E deriving Eq

instance Show E where
  showsPrec _ S = showChar 'S'
  showsPrec _ K = showChar 'K'
  showsPrec _ (V i) = shows i
  showsPrec p (A e f) = showParen (p>0) $ showsPrec 0 e . showsPrec 1 f

type SRead a = String -> (a,String) -- a simpler variation of ReadS

parse :: String -> E
parse s = let (e,"")=parseList (s++")") in e
parseList :: SRead E
parseList s = let (l,s')=parseL s in (foldl1 A l,s')
parseL :: SRead [E]
parseL (c:s) | c==' ' = parseL s
             | c==')' = ([],s)
parseL s = let (p,s')=parseExp s; (l,s'')=parseL s' in (p:l,s'')
parseExp :: SRead E
parseExp ('(':s) = parseList s
parseExp s = let [(n,s')]=reads s in (V n,s')

k e = A K e
s e f = A (A S e) f
i = s K K
s3 e f g = A (s e f) g
sk = A S K
ssk e f = A (s3 S K e) f

n `invars` (A e f) = n `invars` e || n `invars` f
n `invars` (V m)   = n==m
_ `invars` _       = False

comb (A e f) = comb e && comb f
comb (V _)   = False
comb _       = True

abstract _ (A (A S K) _) = sk
abstract n e | not (n `invars` e) = k e
abstract n (A e (V _)) | not (n `invars` e) = e
abstract n (A (A (V i) e) (V j)) | n==i && n==j =
                                   abstract n (ssk (V i) e)
abstract n (A e (A f g)) | comb e && comb f =
                                   abstract n (s3 (abstract n e) f g)
abstract n (A (A e f) g) | comb e && comb g =
                                   abstract n (s3 e (abstract n g) f)
abstract n (A (A e f) (A g h)) | comb e && comb g && f==h =
                                   abstract n (s3 e g f)
abstract n (A e f) = s (abstract n e) (abstract n f)
abstract n _ = i

abstractAll 0 e = e
abstractAll n e = abstractAll (n-1) $ abstract n e

parseLine :: String -> (Int,E)
parseLine s = let [(n,s')] = reads s
                  s''=dropWhile(`elem` " =->") s'
              in (n, parse s'')

solveLine :: String -> E
solveLine s = let (n,e) = parseLine s in abstractAll n e

main = interact $ unlines . map (show . solveLine) . lines

It implements the improved bracket abstraction from section 3.2 of John Tromp: Binary Lambda Calculus and Combinatory Logic which is linked to from the Wikipedia article on combinatory logic. The most useful special cases only use the S combinator to suffle subterms around in order to avoid deep nesting of variables. The case that checks for equality of some subterms is not needed for any of the test cases. While there is no special case for handling the W combinator (see Peter's answer), the rules work together to find the shorter SS(SK) expression. (I first made a mistake by trying to optimize away the inner calls to abstract, then this W optimization did not happen and the overall result was 16 bytes longer.)

And here are the results from the test cases:

| improve this answer | |

8486 using S, K, I, W


The standard algorithm (as described e.g. in chapter 18 of To Mock a Mockingbird) uses four cases, corresponding to the combinators S, K, I = SKK, and simple left-association. I think this is what Christian's answer implements. This is sufficient, but not necessarily optimal, and since we're allowed to hard-code up to 10 combinators it leaves 7 options.

Other well-known combinatorial combinators are

B x y z = x (y z)
C x y z = x z y
W x y = x y y

which, together with K, make a complete basis. In SK these are

B = S (K S) K
C = S (S (K (S (K S) K)) S) (K K)
W = S S (S K)

and the SKI rules derive those same expressions for B and C, but for W they derive S S (K (S K K)). I therefore chose to implement W as a special case.

Program (CJam)

e# A tests whether argument is an array

e# F "flattens" an expression by removing unnecessary parentheses, although if the expression is a primitive
e# it actually wraps it in an array
  e# A primitive is already flat, so we only need to process arrays
      e# Stack: ... index elt
      e# First recurse to see how far that simplifies the element
      e# If it's an array...
        e# ... we can drop a level of nesting if either it's the first one (since combinator application
        e# is left-associative) or if it's a one-element array
          e# The tricky bit is that it might be a string, so we can't just use ~


e# Parse line of input
"->=()"" [[[]"er']+~
e# Eliminate the appropriate variables in reverse order. E eliminates the variable currently stored in V.
  e# Flatten current expression

  e# Identify cases; X holds the eXpression and is guaranteed to be non-primitive
    XVa=                  e# [V]
    Xe_V&!                e# case V-free expression
    X)_A0{V=}?\e_V&!*     e# case array with exactly one V, which is the last element
    X_e_Ve=~)>[VV]=X,2>*  e# case array with exactly two Vs, which are the last two elements
  e# Corresponding combinators
    {;"SKK"}              e# I
    {['K\]}               e# K
    {);}                  e# X (less that final V)
    {););['S 'S "SK"]\a+} e# W special-cased as SS(SK) because the general-case algorithm derives SS(K(SKK))
    {['S\)E\E\]}          e# S (catch-all case)

e# Format for output


Online test suite

Generated outputs:

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.