Mogensen–Scott encoding¶

Mogensen–Scott encoding represents constructor data as functions that select a matching handler and expose immediate fields.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13440
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Functional Programming, Lambda Calculus → Computer Science & Software Engineering
Aliases: Scott Encoding

Core Idea¶

A Scott-style encoding turns a value of an algebraic data type into a lambda term that awaits one handler per constructor. When applied to those handlers, the value chooses the handler matching its own constructor and passes that constructor's immediate fields. It is case analysis expressed through function application rather than a primitive case operator. In the special lambda-term setting, Torben Mogensen used the same constructor-dispatch idea, together with higher-order abstract syntax for binding, to represent lambda programs as data inside the lambda calculus itself.^[1]^[2]

The naming needs care: Scott-style encodings were not invented whole by Mogensen. The compound label describes a family of handler-dispatch encodings and Mogensen's notable application to lambda syntax. The important discriminator from a Church-style representation of recursive data is that the recursive child is handed to the branch as a child, rather than automatically pre-folded into a result.^[1]^[3]

Structural Signature¶

Sig role-phrases:

Constructor family: a finite set of alternatives, each with a specified number of fields.
Encoded value: a function expecting one handler for each alternative.
Selected handler: the branch corresponding to the value's constructor.
Immediate fields: original constructor arguments supplied to that handler, including unprocessed recursive children.
External recursor: an additional function or fixed point when the consumer needs to traverse the whole structure rather than inspect one layer.^[1]^[2]

For Foo a | Bar | Baz b c, Ben Lynn's worked Scott encoding makes Foo a select the first handler and give it a, Bar select the second with no fields, and Baz b c select the third with b,c. The constructor alternative is carried by which handler is invoked, not by a separate machine-level tag. It is also why a branch for every constructor must be supplied to eliminate a value.^[2]

What It Is Not¶

It is not simply “any function representing data.” Church numerals, for example, apply a step function repeatedly as an iterator; a Scott successor packages the predecessor value as an immediate field. Neither name guarantees a real-machine speed advantage in every compiler or evaluation strategy. A claim of constant-time predecessor here means a bounded number of head beta-reductions to expose the stored predecessor; it is not a claim about allocation, normalization of arbitrary arguments, or full-program running time.^[2]^[3]

Nor does encoding a syntax tree automatically interpret it. Mogensen defines an encoding schema for variables, applications and abstractions and separately builds a self-interpreter using recursion. Applying a syntax code to handlers can distinguish its outer constructor; evaluating the encoded program requires more work. Confusing quotation with evaluation would erase the paper's main construction.^[1]

Scope of Application¶

In pure lambda calculus, there are only abstraction and application, so algebraic variants can be represented by choosing among handler arguments. Mogensen's 1992 paper gives a general signature construction, then specializes it to lambda terms. A variable code selects a variable handler with that variable; an application code selects an application handler with codes for function and argument; an abstraction code selects an abstraction handler with a host-language lambda that binds its variable. This last field is not just a raw name string: higher-order abstract syntax uses lambda binding itself to express scope.^[1]

The author then constructs a self-interpreter for the representation. His paper states that the representation grows linearly with original term size and that testing, decomposition and building are local operations needing only a few beta reductions. Those are results about this formal representation and its described cost model. They should not be copied as an unqualified benchmark for every implementation called “Scott encoding.”^[1]

Clarity¶

Let Zero = λz s.z and Succ n = λz s.s n, with z the zero branch and s the successor branch. Define pred = λn.n Zero (λp.p). On Zero, the zero branch returns Zero. On Succ q, the successor branch is applied to the stored q, and the identity handler returns q. The calculation is direct case elimination. No traversal through every earlier numeral is involved just to expose that one field.^[2]

Now distinguish a whole fold. To compute a result that depends recursively on every predecessor, the Scott value supplies only the next child; some recursive procedure must call itself on that child. Church-style data can encode the fold itself. This is a tradeoff in what the representation offers directly, not a claim that one is categorically superior for every operation.^[2]^[3]

Manages Complexity¶

The handler view turns a potentially opaque lambda term into a predictable data interface: count constructors; give one handler for each; read the fields supplied to the chosen handler. For a list, the empty case selects a base handler and the cons case passes head and tail. For a numeral, successor passes its predecessor. For a lambda program, application passes codes for its two subterms. All are the same dispatch skeleton, but their fields and downstream algorithms differ.^[2]^[1]

Mogensen's representation separates three questions often merged: how to quote a term, how to inspect its outer constructor, and how to interpret or reduce the quoted term. His paper's self-interpreter needs a fixed point for recursive traversal. A case dispatcher can select the application branch without thereby applying the represented function to its represented argument.^[1]

Abstract Reasoning¶

The counterfactual test exposes the identity. Remove the constructor family, and there is no set of handlers to select from. Keep the family but replace the raw recursive field with the fold result produced by each nested value, and the representation has shifted toward Church-style eliminators. Keep raw fields but require an external primitive case, and one may have an ordinary algebraic data type rather than its lambda-only encoding. The distinguishing relation is therefore not just “functional data” but constructor-indexed dispatch with immediate-field delivery.^[1]^[2]

The cost claim follows the same boundary. pred (Succ q) can reach q in a fixed number of beta steps because the constructor placed it directly in a handler argument. A complete transformation of a structure of length n cannot generally be made constant merely by this packaging; it must visit the relevant nodes. “Constant-time deconstruction” and “constant-time recursion” are different propositions.^[2]

Knowledge Transfer¶

The representation pattern transfers among finite-constructor types if their constructor arities and handler order are explicit. A new type with an additional constructor needs an additional handler in every elimination. The general pattern does not automatically settle how binding should be represented in a program syntax tree; Mogensen's higher-order abstraction is an additional domain-specific choice that handles the lambda calculus's variable scope.^[1]^[2]

The transfer limit is equally important. A typed language may impose type constraints not visible in the untyped lambda equations, and an evaluator's cost model may differ from beta-step accounting. Applying the compound name to every tagged union or every functional fold would confuse the very distinctions the examples show.^[1]^[3]

Examples¶

Scott Peano predecessor. Ben Lynn's construction gives Zero = λz s.z and Succ q = λz s.s q. Applying pred = λn.n Zero (λp.p) to Succ (Succ Zero) selects the successor handler and returns the stored Succ Zero; applying it to Zero selects the zero handler and returns Zero. Mapped back: constructors = Zero/Succ; encoded value = the two-handler numeral; selected handler = zero result or identity; immediate field = the predecessor numeral q; external recursor = unnecessary for this one-step operation, though needed for a whole-number fold. This is a symbolic beta-reduction, not a timed machine benchmark.^[2]
Mogensen's code for λx.xx. The 1992 original paper expands this particular term on p. 348. Its outer abstraction code selects handler c and passes a host lambda binding x; the body xx selects application handler b, with two variable codes that each select a and pass x. The encoded children are passed as codes, not executed at dispatch time. Mapped back: constructors = variable/application/abstraction; encoded value = the nested handler-selecting lambda term; selected handler = c at the root, b in the body, a at each variable; immediate fields = bound-body function and subterm codes; external recursor = Mogensen's separately defined self-interpreter for evaluating the represented program. The paper gives the expansion, so this is not an invented interpreter trace.^[1]

Structural Tensions¶

One-step access versus built-in fold. Scott-style dispatch readily exposes a constructor's child and makes operations such as predecessor or list tail a local case. For whole-structure recursion, the consumer must supply a recursive traversal, often through a fixed point in untyped lambda calculus. Church-style data packages folding behavior more directly, but its recursive result is not the same as an unprocessed child for one-step deconstruction. Diagnostic: is the task selecting a field at the head, or recursively aggregating the whole value? The sources support this representational tradeoff, not a universal implementation winner.^[2]^[3]

Structural–Framed Character¶

The handler/constructor relation is formally structural, but its significance is framed by the chosen calculus, evaluation strategy and the computational task. “Immediate” is a reduction-level property, not an observer-independent time unit. The vocabulary originated in lambda-calculus representation and traveled to compiler expositions and metaprogramming because those settings preserve constructor alternatives and elimination by application. Importing it into arbitrary higher-order code without a finite constructor family would be mere resemblance, not recognition of the pattern. Its character: a formal data-representation scheme with portable dispatch equations and domain-specific cost and binding interpretations.^[1]^[2]

Structural Core vs. Domain Accent¶

The portable skeleton is value-as-function selecting one of k handlers and passing the fields of exactly one constructor. The domain-bound mechanism is lambda-term encoding; Mogensen's version adds higher-order representation of binders and a separate self-interpreter. The named entry fails the prime bar because its identity depends on lambda calculus, constructor encoding and a precise Church/Scott distinction. Its live genus is Encoding and Decoding; a separate prime about “dispatch to a handler” would need unlike-domain evidence and would lose the beta-reduction and binding claims that make this entry substantive.^[1]^[2]

This entry is a kind of Encoding And Decoding.

Strict parent: Encoding And Decoding. Mogensen–Scott represents constructor values as lambda terms with handler-based elimination; most encodings do not have this mechanism. No exact live Scott-encoding intermediate was found. The edge does not attribute every Scott encoding to Mogensen or assume recursive children are pre-folded.

Relationships to Other Abstractions¶

Current abstraction Mogensen–Scott encoding Domain-specific

Parents (1) — more general patterns this builds on

Mogensen–Scott encoding is a kind of Encoding And Decoding Prime

Mogensen–Scott is a constructor encoding.

Hierarchy path (1) — routes to 1 parentless root

Mogensen–Scott encoding → Encoding And Decoding → Transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

Mogensen–Scott encoding sits in a sparse region of the domain-specific corpus (76^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Type Systems & Functional Constructs (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Church numerals or a Church-encoded recursive fold.^[2]^[3]
Primitive tagged unions in a host language, though they can implement analogous case semantics.
Quoted lambda syntax that is already evaluated simply because it is represented.^[1]
Universal constant wall-clock complexity claims for every evaluator.

References¶

[1] Torben Æ. Mogensen, “Efficient Self-Interpretation in Lambda Calculus,” Journal of Functional Programming 2(3) (1992), 345–364, original publisher PDF, especially pp. 347–349, §§2–3. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o

[2] Ben Lynn, “The Scott encoding,” Compilers, original worked technical exposition, ADT and “Booleans, Numbers, Lists” sections. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o

[3] Jan Martin Jansen, “Programming in the λ-Calculus: From Church to Scott and Back,” The Beauty of Functional Code (2013), 168–180, original publisher abstract supporting the representational contrast; full chapter not relied on for detailed formulas. registry ↩a ↩b ↩c ↩d ↩e ↩f