J operator

In computer science, Peter Landin's J operator is a programming construct that post-composes a lambda expression with the continuation to the current lambda-context. The resulting “function” is first-class and can be passed on to subsequent functions, where if applied it will return its result to the continuation of the function in which it was created.

History

The J operator was created to make labels and jumps a first class value. It was designed to work with the SECD machine with the following extra transitions:

Transition	From	To
J	J:f:S, E, ap:C, D	closure(f,D):S, E, C, D
Closure	closure(f, (S', E', C', D')):x:S, E, ap:C, D	f:x:S', E', ap:C', D'

The J operator originally created what was called a "program closure", consisting of a function called the body and a SECD state called the dump. A program closure is equivalent to composing its body with the dump in continuation form (closure(f,D)(x) = D(f(x)) ).

Simplified description

The J operator composes a function with the continuation of the calling function. That is, the J operator returns a function, which when applied applies the argument of the J operator with the argument of the function, and then forces the function that called the J operator to return that value.

Examples

J(λx.x) is equivalent to a first class return statement. This is because λx.x is the identity function, so when it gets applied it will do nothing to the value given and returns it straight away.

λv.J(λx.x) initially returns the J of λx.x, but that could be used in a surrounding expression to make it re-return a different value.

See also

• Call-with-current-continuation

References

By Landin

• Landin, P. J. (January 1964). "The Mechanical Evaluation of Expressions". Comput. J. 6 (4): 308–320. doi:10.1093/comjnl/6.4.308.
• Landin, P. J. (February 1965). "Correspondence between ALGOL 60 and Church's Lambda-notation: Part I". Comm. ACM. 8 (2): 89–101. doi:10.1145/363744.363749. S2CID 6505810.
• Landin, P. J. (March 1965). "A correspondence between ALGOL 60 and Church's Lambda-notations: Part II". Comm. ACM. 8 (3): 158–167. doi:10.1145/363791.363804. S2CID 15781851.
• Landin, P.J., “A formal description of Algol 60.” Presented at IFIP Working Conf., Baden, Sept. 1964.
• Landin, P.J., “Programming without lmperatives—an Example,” UNIVAC S.P. Research Report (March, 1965)
• Landin, P.J., “Getting Rid of Labels,” UNIVAC S.P. Research Report (July, 1965)
• Landin, P.J., “An Analysis of Assignment in Programming Languages,” UNIVAC S.P. Research Report (September, 1965)
• Landin, P.J., “A Generalization of Jumps and Labels,” math.bas.bg (1998)

By others

• Thielecke, H. (December 1998). "An Introduction to Landin's "A Generalization of Jumps and Labels"" (PDF). Higher-Order and Symbolic Computation. 11 (2): 117–123. doi:10.1023/A:1010060315625. S2CID 1562780.
• Danvy, O.; Millikin, K. (November 2008). Tennent, Robert (ed.). "A Rational Deconstruction of Landin's SECD Machine with the J Operator". Logical Methods in Computer Science. 4 (4:12): 1–67. arXiv:0811.3231. doi:10.2168/LMCS-4(4:12)2008. S2CID 7926360.
• Danvy, O.; Shan, C. C.; Zerny, I. (2009). "J Is for JavaScript: A Direct-Style Correspondence between Algol-Like Languages and JavaScript Using First-Class Continuations" (PDF). Domain-Specific Languages. LNCS. Vol. 5658. pp. 1–19. doi:10.1007/978-3-642-03034-5_1. ISBN 978-3-642-03033-8. Archived from the original (PDF) on 2010-08-18. Retrieved 2009-09-19.