SKombinator

Use S, K, I, or other single letters (a-z, A-Z). Parentheses group; juxtaposition is left-associative (abc=((ab)c)). I is automatically expanded to (S K K).

Evaluation Output

Evaluation results will appear here.

Welcome to SKombinator!

This tool allows you to explore the fascinating world of SK combinator calculus, a foundational system in theoretical computer science.

How to Use

  • Input Expression: Type your SK combinator expression into the text area on the left. Evaluation starts automatically shortly after you stop typing.
    • Use uppercase S and K for the basic combinators.
    • Uppercase I is automatically expanded to (S K K) during parsing.
    • Other single letters (a-z, A-Z, excluding S, K, I) are treated as variables or undefined combinators.
    • Use parentheses () for grouping.
    • Application (juxtaposition) is left-associative: abc is parsed as ((a b) c).
  • Automatic Evaluation: No need to click evaluate! The results update automatically as you type.
  • Layout Toggle: Use the button in the top-right corner to switch between a side-by-side view and a top-bottom view of the input and output panels.

Understanding the Output

  • Evaluation Steps Tab:
    • Shows the step-by-step reduction of the expression.
    • Each step applies one reduction rule (S or K) to the leftmost, outermost possible redex (reducible expression).
    • The part of the expression being reduced in the next step is highlighted with colored backgrounds:
      • S x y z reduces to x z (y z).
      • K x y reduces to x.
    • If the input is invalid (e.g., mismatched parentheses), an Error message will appear here.
    • Evaluation stops when no more S or K rules can be applied (normal form) or after a maximum number of steps (currently 150).
  • Tree Visualization Tab:
    • Displays the Abstract Syntax Tree (AST) for each step of the evaluation.
    • Applications are shown as branches, combinators/variables as leaves.
    • The nodes involved in the redex for that step are highlighted, matching the colors in the "Evaluation Steps" tab.
    • Use the +/- buttons, Ctrl + Mouse Wheel, or Ctrl + +/- keys to zoom in and out. Drag the background (if needed, though scrollbars should appear) to pan.
    • A blue arrow indicates the transformation from one tree state to the next.
  • Help Tab: You are here!

What are SK Combinators?

SK combinator calculus is a system invented by Moses Schönfinkel and Haskell Curry. It's Turing-complete, meaning it can compute anything a regular computer can, using only two fundamental operations (combinators):

  • S combinator: $ S x y z \rightarrow x z (y z) $ (Substitution/Application)
  • K combinator: $ K x y \rightarrow x $ (Constant/Cancellation)

The identity combinator I ($ I x \rightarrow x $) can be defined as $ I = S K K $. This tool automatically makes that substitution for convenience.

Source Code & Disclaimer

You can find the source code for this tool on the GitHub Repository.

Please be advised that the quality of this code or its functionality comes with absolutely no guarantee, as the entire thing was hallucinated into existence by an LLM. Use at your own amusement!