Mogensen–Scott encoding
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, Scott encoding is a way to represent (recursive) data types in the
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
. Church encoding performs a similar function. The data and operators form a mathematical structure which is embedded in the lambda calculus. Whereas Church encoding starts with representations of the basic data types, and builds up from it, Scott encoding starts from the simplest method to compose algebraic data types. Mogensen–Scott encoding extends and slightly modifies Scott encoding by applying the encoding to Metaprogramming. This encoding allows the representation of
lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
terms, as data, to be operated on by a meta program.


History

Scott encoding appears first in a set of unpublished lecture notes by
Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, Ca ...
whose first citation occurs in the book ''Combinatorial Logic, Volume II''.
Michel Parigot Michel may refer to: * Michel (name), a given name or surname of French origin (and list of people with the name) * Míchel (nickname), a nickname (a list of people with the nickname, mainly Spanish footballers) * Míchel (footballer, born 1963), ...
gave a logical interpretation of and strongly normalizing recursor for Scott-encoded numerals, referring to them as the "Stack type" representation of numbers. Torben Mogensen later extended Scott encoding for the encoding of Lambda terms as data.


Discussion

Lambda calculus allows data to be stored as parameters to a function that does not yet have all the parameters required for application. For example, : ((\lambda x_1 \ldots x_n.\lambda c.c\ x_1 \ldots x_n)\ v_1 \ldots v_n)\ f May be thought of as a record or struct where the fields x_1 \ldots x_n have been initialized with the values v_1 \ldots v_n . These values may then be accessed by applying the term to a function ''f''. This reduces to, : f\ v_1 \ldots v_n ''c'' may represent a constructor for an algebraic data type in functional languages such as Haskell. Now suppose there are ''N'' constructors, each with A_i arguments; :\begin \text & \text & \text \\ \hline ((\lambda x_1 \ldots x_.\lambda c_1 \ldots c_N.c_1\ x_1 \ldots x_)\ v_1 \ldots v_) & f_1 \ldots f_N & f_1\ v_1 \ldots v_ \\ ((\lambda x_1 \ldots x_.\lambda c_1 \ldots c_N.c_2\ x_1 \ldots x_)\ v_1 \ldots v_) & f_1 \ldots f_N & f_2\ v_1 \ldots v_ \\ \vdots & \vdots & \vdots \\ ((\lambda x_1 \ldots x_.\lambda c_1 \ldots c_N.c_N\ x_1 \ldots x_)\ v_1 \ldots v_) & f_1 \ldots f_N & f_N\ v_1 \ldots v_ \end Each constructor selects a different function from the function parameters f_1 \ldots f_N . This provides branching in the process flow, based on the constructor. Each constructor may have a different
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
(number of parameters). If the constructors have no parameters then the set of constructors acts like an ''enum''; a type with a fixed number of values. If the constructors have parameters, recursive data structures may be constructed.


Definition

Let ''D'' be a datatype with ''N'' constructors, \_^N, such that constructor c_i has
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
A_i.


Scott encoding

The Scott encoding of constructor c_i of the data type ''D'' is : \lambda x_1 \ldots x_ . \lambda c_1 \ldots c_N . c_i\ x_1 \ldots x_


Mogensen–Scott encoding

Mogensen extends Scott encoding to encode any untyped lambda term as data. This allows a lambda term to be represented as data, within a Lambda calculus meta program. The meta function ''mse'' converts a lambda term into the corresponding data representation of the lambda term; :\begin \operatorname & = \lambda a, b, c.a\ x \\ \operatorname \ N& = \lambda a, b, c.b\ \operatorname \operatorname \\ \operatorname lambda x . M& = \lambda a, b, c.c\ (\lambda x.\operatorname \\ \end The "lambda term" is represented as a tagged union with three cases: * Constructor ''a'' - a variable (
arity Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
1, not recursive) * Constructor ''b'' - function application (arity 2, recursive in both arguments), * Constructor ''c'' - lambda-abstraction (arity 1, recursive). For example, : \begin \operatorname lambda x.f\ (x\ x)\ \lambda a, b, c.c\ (\lambda x.\operatorname \ (x\ x)\\ \lambda a, b, c.c\ (\lambda x.\lambda a, b, c.b\ \operatorname \operatorname \ x\\ \lambda a, b, c.c\ (\lambda x.\lambda a, b, c.b\ (\lambda a, b, c.a\ f)\ \operatorname \ x\\ \lambda a, b, c.c\ (\lambda x.\lambda a, b, c.b\ (\lambda a, b, c.a\ f)\ (\lambda a, b, c.b\ \operatorname \operatorname )\\ \lambda a, b, c.c\ (\lambda x.\lambda a, b, c.b\ (\lambda a, b, c.a\ f)\ (\lambda a, b, c.b\ (\lambda a, b, c.a\ x)\ (\lambda a, b, c.a\ x))) \end


Comparison to the Church encoding

The Scott encoding coincides with the Church encoding for booleans. Church encoding of pairs may be generalized to arbitrary data types by encoding c_i of ''D'' above as : \lambda x_1 \ldots x_ . \lambda c_1 \ldots c_N . c_i (x_1 c_1 \ldots c_N) \ldots (x_ c_1 \ldots c_N) compare this to the Mogensen Scott encoding, : \lambda x_1 \ldots x_ . \lambda c_1 \ldots c_N . c_i x_1 \ldots x_ With this generalization, the Scott and Church encodings coincide on all enumerated datatypes (such as the boolean datatype) because each constructor is a constant (no parameters). Concerning the practicality of using either the Church or Scott encoding for programming, there is a symmetric trade-off: Church-encoded numerals support a constant-time addition operation and have no better than a linear-time predecessor operation; Scott-encoded numerals support a constant-time predecessor operation and have no better than a linear-time addition operation.


Type definitions

Church-encoded data and operations on them are typable in
system F System F (also polymorphic lambda calculus or second-order lambda calculus) is a typed lambda calculus that introduces, to simply typed lambda calculus, a mechanism of universal quantification over types. System F formalizes parametric polymorph ...
, as are Scott-encoded data and operations. However, the encoding is significantly more complicated. The type of the Scott encoding of the natural numbers is the positive recursive type: : \mu X. \forall R. R \to (X \to R) \to R Full recursive types are not part of System F, but positive recursive types can are expressible in System F via the encoding: : \mu X: G = \forall X: ((G \to X) \to X) Combining these twos fact yields the System F type of the Scott encoding: : \forall X. (((\forall R. R \to (X \to R) \to R) \to X) \to X) This can be contrasted with the type of the Church encoding: : \forall X. X \to (X \to X) \to X The Church encoding is a second-order type, but the Scott encoding is fourth-order!


See also

* Church encoding *
System F System F (also polymorphic lambda calculus or second-order lambda calculus) is a typed lambda calculus that introduces, to simply typed lambda calculus, a mechanism of universal quantification over types. System F formalizes parametric polymorph ...
*
Lambda cube In mathematical logic and type theory, the λ-cube (also written lambda cube) is a framework introduced by Henk Barendregt to investigate the different dimensions in which the calculus of constructions is a generalization of the simply typed ...


Notes


References

*Stump, A. (2009)
Directly reflective meta-programming
''Higher-Order and Symbolic Computation, 22'', 115-144. *Mogensen, T.Æ. (1992)
Efficient Self-Interpretations in lambda Calculus
''J. Funct. Program., 2'', 345-363. {{DEFAULTSORT:Mogensen-Scott encoding Lambda calculus