Non-termination without loops, iteration or recursion: Omega in Javascript

Related pages:

Javascript is a great vehicle for teaching functional programming techniques and the λ-calculus. The λ-calculus, which forms the theoretical basis for programming languages like Lisp and Scheme, is also present in Javascript thanks to its support for anonymous functions.

At first glance, anonymous functions seem like merely a syntactic convenience. This article demonstrates otherwise by creating a non-terminating program entirely out of anonymous functions. In the functional programming community, this expression is known as ω (omega).

The program ω is made up of two functions which each take one argument. Each of these functions applies the argument to it itself. Omega is then the application of one of these functions to the other:

Trying to evaluate this code fragment will hang the browser until it decides to terminate the script:

[omega-result]

The means by which ω achieves non-termination is self-application, and self-application turns out to be the theoretical source of power for the computational universality of the λ-calculus. (Self-application creates a number of issues needing careful handling for logical theories based on the λ-calculus, but these aren't a concern when the λ-calculus is used as the basis of a programming language.) More specifically, self-application allows the construction of fixed combinators, such as the Y combinator, and these permit the construction of recursive functions without explicit support for recursion. I've also created an article demonstrating the Y combinator and showing how it can be used for memoizing recursive functions.

matt.might.net is powered by linode | legal information