Fun3

Fun3

Paradigm(s)	functional, combinatory logic
Designed by	User:AndrewBayly
Appeared in	2026
Type system	untyped
Memory system	graph reduction (no variables)
Computational class	Turing complete (as a calculus; see Computational class)
Reference implementation	single-file HTML/JS interpreter
Influenced by	SKI combinator calculus, Fun2
File extension(s)	.js

Fun3 is an esoteric programming language by User:AndrewBayly, the third in a series of languages (after Fun and Fun2) built on the same conceit: a dialect of JavaScript in which an entire program is a single nested function call, and every parameter is itself a function call. Where Fun turned out to be highly imperative and Fun2 achieved a functional style by building an S-expression tree and interpreting it with a small Lisp, Fun3 drops the intermediate interpreter altogether. Its programs build a tree of SKI combinators directly out of nested calls, then reduce the whole tree with a single final call. The fit is close to exact: SKI calculus has no variables or binding forms to represent, so it collapses into JavaScript's own call syntax with nothing left over.

Design

A Fun3 program is a single expression of the form CALL(...). The library consists of six functions:

• S(), K(), I() — return the corresponding combinator.
• APP(a, b) — returns a deferred application node representing a applied to b.
• CALL(a) — forces the tree built from nested APP calls down to a normal form.
• PRINT(x) — forces its argument, checks whether it behaves as a Church numeral by probing it with a successor function and zero, prints the result if so, and returns its argument unchanged (so it can be dropped anywhere in a tree without affecting the computation).

Because SKI terms have no data type beyond functions, PRINT's numeral detection is a heuristic (duck typing), not a type check.

The reference implementation reduces terms lazily: applications are built as deferred thunks and only forced when something actually calls them as a function. This distinction matters more than it first appears — an early version of the interpreter forced both branches of the S-rule (S x y z = x z (y z)) eagerly, which meant K could never actually protect a divergent argument from being evaluated, since the divergent computation had already run by the time K had a chance to discard it. Only a properly deferred second branch gives the reduction genuine normal-order semantics.

Examples

Identity via SKK

CALL(PRINT(APP(APP(APP(S(), K()), K()), someChurchNumeral)))

S K K is extensionally equal to I; applying it to a numeral built from S/K/I and printing the result is used as a basic structural correctness check.

A Church numeral built from S, K, I

CALL(PRINT(APP(APP(S(), APP(APP(S(), APP(K(), S())), K())), APP(APP(S(), APP(APP(S(), APP(K(), S())), K())), APP(APP(S(), APP(APP(S(), APP(K(), S())), K())), APP(K(), I()))))))

Builds the numeral 3 using SUCC = S (S (K S) K) and ZERO = K I, applying SUCC three times. Because Fun3 has no variables, any subterm used more than once — like SUCC here — must be written out in full at each occurrence; there is no way to name and reuse it. Programs are consequently expected to be generated rather than hand-written for anything beyond small demonstrations.

Unbounded recursion via the Y combinator

A Y combinator applied to a successor function with no base case recurses without end, and is used to demonstrate genuine unbounded recursion (as opposed to bare self-application) hitting the implementation's resource limit rather than a designed halting condition.

Computational class

SKI combinator calculus is Turing complete; S and K alone suffice, since I is derivable as S K K. Any untyped lambda calculus term can be mechanically translated into an equivalent SK term via bracket abstraction, and untyped lambda calculus is Turing complete.

The reference implementation is Turing complete only in the "modulo resources" sense that applies to any concrete interpreter, and notably carries two independent, non-interchangeable limits rather than one:

1. A configurable step counter on the reduction loop, which is a purely practical safety valve and bounds divergence that manifests as flat, repeated iteration.
2. The host JavaScript engine's own call stack, which is architectural rather than practical: genuine SKI divergence (e.g. an omega term applied to itself, or the Y-combinator example above) reduces via nested calls into the interpreter's own forcing function rather than flat iteration, and so hits this ceiling directly. Removing the step counter entirely does not allow such terms to run any longer; they still fail immediately via a native stack-overflow error.

Closing the second gap would require rewriting the interpreter's core reduction step as an explicit, heap-allocated trampoline rather than relying on the host language's own call stack for recursion depth — a real rewrite rather than a configuration change, and one the reference implementation does not attempt.

See also

• SKI combinator calculus
• Combinatory logic
• Unlambda
• Iota