LambdaLink and ScopeLink

From OpenCog
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.

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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://api.formulasearchengine.com/v1/":): {\displaystyle \sum_n f(n) ,\qquad \int f(x) dx ,\qquad \forall y f(y) ,\qquad \exists z f(z)}

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.

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.).

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 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"

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).