LambdaLink and ScopeLink

From OpenCog
Jump to: navigation, search

LambdaLink and ScopeLink are two closely-related Link types used for binding and scoping variables. One way to understand the difference beween 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, but also like a block-scope variable used in a nested smaller block: it looks "free" in the smaller block, but is bound or scoped in the larger block.

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.

The LambdaLink can also be understood as the OpenCog analog of the lambda of lambda calculus and of the corresponding concept in 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 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. Note, in particular, that beta-reduction is not allowed in a ScopeLink, as it "doesn't make sense", any more than it would in the above examples. One cannot "compose" the above, the way one can compose functions. Note that scoped variables can be typed: in the above examples, n is an integer, x a real number, y and z elements of a set.

Counter-intuitively, LambdaLink is currently not the base class for any other link type. It's standard 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.

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"