LambdaLink and ScopeLink
LambdaLink and ScopeLink are two closely-related Section 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 never be used directly; rather, it is useful as a base class for a large variety of other link types. It is a "private atom type". By contrast, LambdaLinks are ideal for declaring user-defined custom functions!
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.
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.
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.
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)))))
(cog-execute! (ExecutionOutputLink (DefinedSchemaNode "x+y*10") (ListLink (NumberNode "2") (NumberNode "4"))))
(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.
LambdaLink VariableList VariableNode "$X" VariableNode "$Y" EvaluationLink PredicateNode "like_to_do_with" ListLink VariableNode "$X" ConceptNode "play" VariableNode "$Y"
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).
Consider the Lambda
(LambdaLink (VariableList (TypedVariable (Variable "$x") (TypeNode 'ConceptNode)) (TypedVariable (Variable "$y") (TypeNode 'ConceptNode))) (FooBarBodyLink ...))
It obviously has the type signature
(ArrowLink (VariableList (TypeNode 'ConceptNode) (TypeNode 'ConceptNode)) (TypeNode 'FooBarBodyLink))
That is, it takes two inputs, and generates one output. This can be expressed in a more general fashion as
(ConnectorSeq (Connector (TypeNode 'ConceptNode) (DirectionNode "input")) (Connector (TypeNode 'ConceptNode) (DirectionNode "input")) (Connector (TypeNode 'FooBarBodyLink) (DirectionNode "output")))
This is more general, because there may be other directions besides "input" and "output", and the kinds of possible joints between different connectors can come in a rainbow of styles.