Skip to main content
4 of 7
fixed ambiguity in reduction steps
ThreeFx
  • 1.5k
  • 9
  • 22

Combinator quines

#Background#

You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:

(S I I (S I I))

You notice that when trying to reduce it to its normal form, it reduces to itself after three steps:

(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

You are determined to find other expressions which share this trait and begin to work on this immediately.

Rules

  • You may use any combination of the following combinators:

      B f g x = f (g x)
      C f x y = f y x
      I x     = x
      K x y   = x
      S f g x = f x (g x)
      W f x   = f x x
    
  • Application is left associative, which means that (S K K) is actually ((S K) K).

  • A reduction is minimal there is no other order of reduction steps which uses fewer steps. Example: if x has reduction y, then the correct minimal reduction of (W f x) is:

      (W f x)
      = (W f y) (1)
      = f y y   (2)
    

    and not

      (W f x)
      = f x x   (1)
      = f y x   (2)
      = f y y   (3) 
    
  • Standard loopholes apply.

Task

We define the cycle of an expression to be the minimal number of reductions in between two same expressions.

Your task is to find the expression, with length < 100, which produces the longest cycle.

Scoring

Your score will be determined by the length of the cycle of your expression. If two people's expression have the same cycle, the answer which uses fewer combinators wins. If they both use the same number of combinators, the earlier answer wins.

Good luck and have fun!

ThreeFx
  • 1.5k
  • 9
  • 22