PutLink

From OpenCog
Jump to: navigation, search

The PutLink is used to perform assignment of values to (lambda-bound) 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 a graph, with a set of variables in it. It is followed by a list of values. When the PutLink is executed, with the cog-execute! function, the variables are replaced by the values, to create a new graph. That is, cog-execute! function performs beta reduction on the PutLink. PutLink is a kind of ScopeLink.

The PutLink is typically used for several reasons: to defer the creation (or destruction!) of the target graph 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 is the 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.

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". The above example assumes that the definition of FooBarLink is such that VariableNode "$x" really is a free variable.

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)

Eta conversion

PutLink will automatically eta-convert the values, if needed. Thus:

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

(cog-execute! (Put f g)

will compose f with g, as functions, returning

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

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.

Not quite a true beta-redex

The PutLink is not quite a true beta-redex in the strict sense of lambda calculus. The above section, describing special-case handling for variables, shows one difference: PutLink performs an alpha-conversion instead of a beta-reduction, when given a variable. By contrast, pure lambda calculus would perform the substitution, and then throw away the lambda, leaving the substituted variable free, not bound, in the resulting expression. For atomese, it is more convenient to leave it bound: it is straight-forward to obtain the free expression, if it is desired.

Another difference is that the result of reducing a PutLink always returns a function in prenex normal form. That is, all of the lambda are pulled all the way over to the left. This is done because it "doesn't make sense" to create atoms with lambdas somwhere in the middle of them that are not beta-redexes. Or rather, one can create such things, but they aren't useful; nothing interesting can be done with them, and there is no way to further reduce them. This is because Atomese is not a "flat string" like 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.

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.