PutLink

From OpenCog
Jump to: navigation, search

The PutLink is used to perform assignment of values to variables. It is similar to the assignment operator in procedural programming languages (i.e. the = sign in C++, python and perl). Because OpenCog atoms are not simple variables, but are more general term graphs, the PutLink is more accurately understood as the AtomSpace notation for a beta redex. The PutLink behaves a lot like a beta redex; some differences are discussed below.

The PutLink consists of two parts: an expression with a set of variables in it, followed by a list of values. When the PutLink is executed (e.g. with the cog-execute! function), the variables are replaced by the values, to create a new expression. That is, executing a PutLink performs a beta reduction on it.

The PutLink is typically used for several reasons: to defer the creation (or destruction!) of the target expression until a later time, or to use it with another link that obtains the values dynamically, at run-time. In the second form, it is usually used with a GetLink. In particular, a PutLink can be combined with a GetLink to achieve exactly the same effect as a BindLink. See the GetLink page for details.

The PutLink can be thought of as an imperative version of MemberLink, which is declarative. That is, MemberLink declares a set-membership relation, whereas executing a PutLink makes it so. See the discussion on the SatisfyingSetLink for a worked example. See the link comparison page for additional examples of imperative/declarative duality.

The PutLink also behaves a lot like an EvaluationLink, when it is used with DefinedPredicateNodes. See section below for an example. The PutLink also behaves a lot like an ExecutionOutputLink, when it is used with DefinedSchemaNodes.

Optionally, the variables in a PutLink can be explicitly specified; thus, it is a kind of ScopeLink. By constraining the types of the variables, vs. set of values that will preplace them, the PutLink can be used to perform a kind of filtering on it's arguments.

One can also un-beta-reduce, or un-put expressions, by using the MapLink. That is, the Maplink is dual to the PutLink; it undoes what PutLink does.

Overview

The PutLink has two general forms. The first form allows only one variable; the second form is used when there are two or more variables. The single-variable form is:

 PutLink
    <clause containing a single variable>
    <atom that will replace the variable>

The multi-variable form is similar to the above, except that it uses a ListLink to list all of the values:

 PutLink
    <clause containing multiple variables>
    ListLink
       <atoms that will replace the variables>

The arity of the ListLink must equal the number of variables; the substitution is done in order.

Thus, for example,

  PutLink
     FooBarLink
         SomeAtom "thing-a-ma-bob"
         VariableNode "$x"
     OtherAtom "widget"

when executed (either with the cog-execute! function, or with the pattern matcher), will result in the creation of the following:

   FooBarLink
      SomeAtom "thing-a-ma-bob"
      OtherAtom "widget"

That is, the execution of the PutLink will cause it to be reduced to beta normal form: the VariableNode "$x" will be replaced by the value OtherAtom "widget". That is, the value will be "put" where the variable is. (The above example assumes that the definition of FooBarLink is such that VariableNode "$x" really is a free variable. One cannot "put" values into bound variables.)

A multi-variable example would be:

  PutLink
     FooBarLink
         VariableNode "$y"
         SomeAtom "thing-a-ma-bob"
         VariableNode "$x"
     ListLink
         ANode "foo"
         OtherAtom "widget"

When the above is executed, it would result in:

   FooBarLink
      ANode "foo"
      SomeAtom "thing-a-ma-bob"
      OtherAtom "widget"


If the clause is a LambdaLink, or inherits from LambdaLink, then the variables to be reduced are taken from the lambda variables. If the clause is not a LambdaLink, then the clauses is scanned for all free variables, in left-to-right term order.

If the clause is a LambdaLink, then type-checking is performed, to make sure that the reduction will obey any type restrictions encoded in the lambda.

Value sets

The current implementation of PutLink treats sets as a collection of values, each of which are put into the pattern. Thus, the execution of the following

(cog-execute!
   (PutLink
      (InheritanceLink
         (ConceptNode "color")
         (VariableNode "$v"))
      (SetLink
         (ConceptNode "red")
         (ConceptNode "blue"))))

results in

(SetLink
   (InheritanceLink
      (ConceptNode "color")
      (ConceptNode "red"))
   (InheritanceLink
      (ConceptNode "color")
      (ConceptNode "blue")))

In algebraic terms, one could say that PutLink is distributive over SetLink. Direct use of sets can be avoided by using the proposed DefinedSetNode. This solves the multiple issues that arise from using SetLinks; see the discussion on the SetLink page for details.

Dynamically generated value sets

PutLink can be used with any other link that dynamically generates new atoms, such as ExecutionOutputLinks or GetLinks. Thus, for example, it can be combined with GetLink as follows:

PutLink
   FooBarLink
       SomeAtom "thing-a-ma-bob"
       VariableNode "$x"
   GetLink
       WhizzyLink
           SomeAtom "widget"
           VariableNode "$x"

Executing the above will cause a thing-a-ma-bob to created for every widget in the atomspace. The above is entirely equivalent to the BindLink below.

BindLink
   WhizzyLink
       SomeAtom "widget"
       VariableNode "$x"
   FooBarLink
       SomeAtom "thing-a-ma-bob"
       VariableNode "$x"

Atom deletion

The PutLink can be used to defer deletion to a later time. Thus, for example:

  PutLink
     DeleteLink
         FooBarLink
             SomeAtom "thing-a-ma-bob"
             VariableNode "$x"
     OtherAtom "widget"

targets

   FooBarLink
      SomeAtom "thing-a-ma-bob"
      OtherAtom "widget"

for deletion. Executing the PutLink with cog-execute! will cause it to be deleted, if it exists. The values to be deleted can be dynamically generated with the GetLink or the ExecutionOutputLink, as well.

Filtering

The PutLink performs a type-check when substituting values for variables; when the type of the value does not match the type of the variable, then the substitution silently fails. This can be used to implement filtering. Thus, for example, the following PutLink, when executed, will return only the ConceptNodes:

  (PutLink
     (TypedVariableLink        ;; a variable declaration
        (VariableNode "%x")
        (TypeNode "ConceptNode"))
     (VariableNode "%x")       ;; body of the put
     (SetLink                  ;; values to place into the body
        (NumberNode "42")
        (ConceptNode "foo")
        (SchemaNode "finagle")
        (ConceptNode "bar")))

This can be executed with the cog-execute! function. It works today. It will return:

(SetLink
   (ConceptNode "foo")
   (ConceptNode "bar"))

Equivalently, the following will work as well:

  (PutLink
     (LambdaLink
        (TypedVariableLink
          (VariableNode "%x")
          (TypeNode "ConceptNode"))
        (VariableNode "%x"))
     (SetLink
        (NumberNode "42")
        (ConceptNode "foo")
        (SchemaNode "finagle")
        (ConceptNode "bar")))

A more sophisticated filtering proposal is defined below, as well as on the FilterLink page.

Defined schemas

PutLinks can be used with DefineLinks. For example, one can define a schema for "colored things":

DefineLink
   DefinedSchemaNode "colored things"
   InheritanceLink
      Conceptnode "color"
      VariableNode Y

In the above, the variable Y should be considered to be bound, a part of the definition of "colored things". it might be better to make this binding explicit:

DefineLink
   DefinedSchemaNode "colored things"
   LambdaLink
      Variablenode Y
      InheritanceLink
         Conceptnode "color"
         VariableNode Y

Then, executing

PutLink
   DefinedSchemaNode "colored things"
   ConceptNode "green"

will cause

InheritanceLink
   Conceptnode "color"
   ConceptNode "green"

to be created.

Defined predicates

When a PutLink is used with a DefinedPredicateNode, it behaves much like an EvaluationLink.

That is,

PutLink
   DefinedPredicate "Do Something"
   ListLink
      Atom A
      Atom B

works more or less the same way as

EvaluationLink
   DefinedPredicate "Do Something"
   ListLink
      Atom A
      Atom B

This is perhaps confusing, and could use some work.

Functions

PutLink also works with pointless functions. For example:

(cog-execute! (Put (Plus) (List (Number 2) (Number 2))))

returns

(Number 4)

while

(cog-execute! (Put (Plus (Number 38)) (List (Number 2) (Number 2))))

returns

(Number 42)

Function composition

PutLink can be used to compose functions. Consider, for example, a function f taking three arguments (X, Y and Z, below), and a function g that outputs a list of three values.

(define f (Lambda 
   (VariableList (Variable "X") (Variable "Y") (Variable "Z"))
   (Inheritance (Variable "Z")(Variable "X"))))

(define g (Lambda (Variable "W")
   (List (Concept "animal") (Concept "foobar") (Variable "W"))))

The function g can be composed with f, because the output of g matches the required input for f. The composition can be done by executing

(cog-execute! (Put f g)

The returned function is

(Lambda (Variable "W") (Inheritance (Variable "W") (Concept "animal")))

Note that the variable W remains bound in the final expression; viz. the result of composing two functions is again a function. This from the standard notion of beta-reduction in lambda calculus; strictly speaking, function composition is a beta reduction followed by an eta conversion.

Alpha conversion

PutLink performs an alpha-conversion, instead of a beta-conversion, when the composition involves variables. This means that PutLink is not quite like a beta-redex in lambda calculus. So, for example:

(define X (Variable "X"))
(define Y (Variable "Y"))
(define Z (Variable "Z"))
(define W (Variable "W"))
(define f (Lambda
    (VariableList X Y W Z)
    (And
        (Inheritance X Y)
        (Inheritance W Z))))

(define d (List X Y Y Z))
(cog-execute! (Put f d)

will return

(Lambda
    (VariableList X Y Z)
    (And
        (Inheritance X Y)
        (Inheritance Y Z))))

so that the W variable was alpha-converted to a Y. Note that d resembles a "diagonal morphism", and that this resemblance can be increased by explicitly writing

(define d (Lambda (VariableList X Y Z) (List X Y Y Z)))

which will yield the same result as the earlier example. In this example, d is a function that takes three arguments, and returns four; that is why it can be composed with f, which is expecting four arguments.

Comparison to a beta-redex

The PutLink is similar to, but not the same as a pure beta-redex in the strict sense of ordinary lambda calculus. There are several reasons for this, driven by the fact that atomese is not lambda calculus, and that it has a rich type system. Differences include:

  • When supplied with functions, PutLink performs function composition (as described above), returning a function. This can be thought of as a beta reduction followed by an eta reduction.
  • When the values to be "put" into variables are themselves variables, PutLink performs alpha conversion, renaming the variables to the new names. That is, an alpha conversion is done in this case, instead of a beta reduction.
  • When the values to be "put" into variables are any link type that derives from the PrenexLink type, the result will be converted into prenex normal form. That is, any declarations of bound variables are pulled to the outermost level ("all the way to the left"). This is done a a convenience: it "doesn't make sense" to create atoms with variable bindings somewhere in the middle. The technical (theoretical) underpinning for this is that Atomese does not consist of "flat strings", as in lambda calculus; a lambda in the middle of a long string can always act on it's neighbor to the right; but in Atomese, one has tree-graphs, and there might not be a sibling "to the right" of a lambda. Thus, prenex normal form is the form that naturally "makes sense" in Atomese; other expressions are possible, but usually have no natural or obvious interpretation.

Chaining

There is an unimplemented extension to PutLink that would support chaining in a simpler fashion. This would define

Put A B C D

to mean

Put A
  Put B
    Put C D

so that C and D are composed first, and then the result is composed into B, and then the result composed into A.

Advanced filtering (pattern matching)

This section describes an unimplemented proposal or idea. A minor variation of this idea is described in FilterLink.

A slight modification of the PutLink syntax would alow it to act as a filter, or as a simple pattern matcher, acting on a set of values, rather than pattern matching on all of the atomspace. Thus, for example, in the current definition (given above)

PutLink
  LambdaLink
     VariableList
        Variable $x
        Variable $y
     Body...
  ListLink
     Atom A
     Atom B

would cause a substitution of $x -> A and $y -> B to be made in the body. In this proposal, the variable declaration is replaced by an arbitrary pattern that must be matched, to extract the variables, for example:

PutLink
  LambdaLink
     EvaluationLink  ;; this is acting like a signature
        PredicateNode "foo"
        ListLink
           Variable $x
           Variable $y
     Body...
  EvaluationLink
     PredicateNode "foo"
     ListLink
        Atom A
        Atom B

Just as above, the substitution of $x -> A and $y -> B is to be made in the body. The point here is that $x and $y were identified by means of the initial pattern. The pattern could also be used as a selector, to reject bad matches. Thus, for example:

PutLink
  LambdaLink
     EvaluationLink
        PredicateNode "foo"
        ListLink
           Variable $x
           Variable $y
     Body...
  SetLink
     EvaluationLink
        PredicateNode "foo"
        ListLink
           Atom A
           Atom B
     EvaluationLink
        PredicateNode "bar"
        ListLink
           Atom C
           Atom D

would extract the values of A and B from the "foo" clause, but ignore the "bar" clause, because it does not match the input filter. In this formulation, the PutLink behave a lot like a BindLink, except that a BindLink searches the entire atomspace, whereas, in the above, the search would be limited to the set.