LambdaLink and ScopeLink

From OpenCog
(Redirected from ScopeLink)
Jump to: navigation, search

LambdaLink and ScopeLink are two closely-related Link types used for binding and scoping variables. The LambdaLink implements a minimal form of lambda abstraction in atomese, while the ScopeLink captures the idea of variable binding for knowledge representation.

ScopeLink should almost never be used directly; rather, it is useful as a base class for a large variety of other link types.

Overview

The LambdaLink can be understood as the OpenCog analog of the lambda of lambda calculus and functional programming. It can be thought of as a "function declaration": a list of variables followed by a "function body" in which those variables appear. In particular, LambdaLinks are meant to allow beta-reduction: the substitution of values for the bound variables. Because OpenCog is typed, the LambdaLink also has the effect of defining a signature. The actual beta reduction is typically performed by either a PutLink or an ExecutionOutputLink.

The ScopeLink can be understood as mechanism for binding variables when representing factual statements or assertions. It is a generalization of the concept of "sum over variable", "integral over variable" in calculus, and of "for all", "there exists" in logic. Each of these symbols scope a variable to a function body. So, for example,

all scope a variable in such a way that it is no longer "free" in the expression.

One way to understand the difference between the two is by analogy to C/C++:

  • A lambda-bound variable is like a C/C++ function argument. Lambda-bound variables are used for passing function argument values.
  • A scoped variable is like a C/C++ block-scope variable. They are used only inside the block scope; they cannot be accessed outside of that block.
  • A free variable is like a C/C++ global variable (or also like a block-scope variable used in a nested smaller block): it is "free" in the smaller block, although it is bound or scoped in a larger block (which would be the global block, for true global variables.).

The two forms behave differently with respect to the concept of beta-reduction. The LambdaLink allows free and unconstrained beta-reduction: one can substitute any value for any variable in a LambdaLink. By contrast, the ScopeLink only allows for beta-reductions that are equivalent to a change-of-variable. For example, in the expresion , one can replace the variable n by some other variable name, e.g. the variable m, without changing the meaning of the sum. This is an example of alpha-conversion; changing variable names has no effect. One cannot replace the variable n by the constant 42: the expression is incoherent nonsense. In integral calculus, one can take an expression such as and perform a change-of-variable, and replace x by some other function , as long as one also replaces dx by g'(y) dy

Both LambdaLink and ScopeLink have the same general structure: a variable declaration, followed by a body. The variables may be typed, using the TypeNode and TypedVariableLink. The variable declaration is optional; if it is absent, then any free variables in the expression are implicitly bound/scoped by these links.

Counter-intuitively, LambdaLink is currently not the base class for any other link type. It's standard, intended usage is to provide the definition for the body of a DefinedSchemaNode.

ScopeLink is the base class for GetLink, BindLink, ForAllLink and ThereExistsLink; anything that uses variables, but cannot be composed as functions.

Both link types respect QuoteLink and UnquoteLink: quoted variables are not really variables; they are constants.

The C++ implementation of these links pre-computes the list of bound variables in the constructor. It correctly handles quoting, and etc. Various convenience methods are provided for working with those variables, including performing type checks, etc.

Definition

The structure of ScopeLink and LambdaLink is given by:

  ScopeLink | LambdaLink
      [ VariableNode | TypedVariableLink | VariableList ]
      <expression>

The bracket [...] indicates that the variable declarations are optional; if there is no explicit variable definition, then all free variables occurring within the expression become bound. By default, the bound variables have no type restrictions on them, unless the variables are explicitly typed with TypedVariableLink.

ScopeLinks must always be in prenex normal form. That is, the <expression> cannot contain any ScopeLink's or LambdaLink's inside of it. The reason for this restriction is that ScopeLinks are used to define search patterns, via GetLink and BindLink, where only prenex forms make any sense.

Examples

The following defines a schema (procedure) that multiplies y by 10 and then adds x.

(DefineLink
  (DefinedSchemaNode "x+y*10")
  (LambdaLink
     (VariableList
        (VariableNode "$X")
        (VariableNode "$Y"))
     (PlusLink
        (VariableNode "$X")
        (TimesLink
           (VariableNode "$Y")
           (NumberNode 10)))))

It can be explictly evaluated, using either ExecutionOutputLink or PutLink. In either case, the same value is returned.

(cog-execute!
  (ExecutionOutputLink
     (DefinedSchemaNode "x+y*10")
     (ListLink
        (NumberNode "2")
        (NumberNode "4"))))

Equivalently,

(cog-execute!
  (PutLink
     (DefinedSchemaNode "x+y*10")
     (ListLink
        (NumberNode "2")
        (NumberNode "4"))))

The above actually work and give the correct results in the current code base.

The following defines a predicate expressing that $X likes to play with $Y. It is a predicate because the result of evaluating an EvaluationLink is always a truth value.

  LambdaLink
      VariableList
          VariableNode "$X"
          VariableNode "$Y"
      EvaluationLink
          PredicateNode "like_to_do_with"
          ListLink
              VariableNode "$X"
              ConceptNode "play"
              VariableNode "$Y"

In other words, LambdaLink's can be used to define "functions" that "return" either atoms or values, in general.

Limitations

The current implementation of LambdaLink does NOT support closures. There is also no support for message dispatch. Both of these would be needed, if one wanted to implement object-oriented programming in atomese. The reason for these limitations are:

  • Atomese was originally intended to be a language for knowledge representation: that is, a way of encoding facts and hypothesis, in a machine-readable way, such that the knowledge could be manipulated and data-mined.
  • In order to represent ideas such as "for all" and "there exists", it is convenient to introduce the notion of scope, via the ScopeLink.
  • It seems to be useful to introduce a notion of lambda abstraction, or rather, an unsophisticated, simplistic form of lambda abstraction.
  • Atomese is not, and was never intended to be a programming language with which humans will write "code" by hand. Rather, it is a language that computer algorithms, such as term rewriting systems and rule engines would be able to manipulate. It is a language designed for easy self-introspection.
  • As a runtime, atomese has horrible performance: it is many thousands of times slower than a native compiled language. That is OK, because atomese was not meant to be a runtime; rather, it is meant for knowledge representation and self-introspection.

So far, there has not been any need to support closures, nor for methods (messages). If these two were supported, then it would be possible to use the LambdaLink to create an object constructor, and thus, to do object-oriented programming in atomese. A sketch of how this can be done may be found here: "From Functions To Objects", Mark S. Miller; first section of "Capability-based Financial Instruments" (2000).