Eager Execution in PutLink

[kasimebrahim]

I am working on an atomese representation for asmoses. The representation I have is an atomese program when executed with knob settings as an argument it gives the candidate program.
Here is an atomese representation equivalent to the combo representation [and !and]($a [$b !$b]).

  (DefineLink
    (DefinedSchema "representation")
    (LambdaLink
      (VariableList
        (Variable "$knob-1")
        (Variable "$knob-2"))
      (PutLink
        (GlobNode "$args")
        (CondLink
          (EqualLink
            (Variable "$knob-1")
            (NumberNode 1))
          (AndLink (GlobNode "$args"))
          (EqualLink
            (Variable "$knob-1")
            (NumberNode 1))
          (NotLink (AndLink (GlobNode "$args"))))
        (ListLink
          (PredicateNode "$a")
          (CondLink
            (EqualLink
              (Variable "$knob-2")
              (NumberNode 1))
            (PredicateNode "$b")
            (EqualLink
              (Variable "$knob-2")
              (NumberNode 2))
            (NotLink (PredicateNode "$b")))))))

Now the problem is if I execute the above the program I get is not fully reduced.

(AndLink
  (PredicateNode "$a") 
  (CondLink
    (EqualLink
      (NumberNode "2")
      (NumberNode "1")
    ) 
    (PredicateNode "$b")
    (EqualLink
      (NumberNode "2") 
      (NumberNode "2")
    ) 
    (NotLink
      (PredicateNode "$b")
    )
  )
)

What is going on is ExecutionOutPutLink executes it til it doesn't get executable atom, which in this case is satisfied with the AndLink. So in order to get that CondLink executed we need to add eager execution to PutLink.
Adding something like this in PutLink:do_reduce should fix it.

	if (nameserver().isA(args->get_type(), LIST_LINK))
	{
		HandleSeq seq;
		for (int j = 0; j < args->get_arity(); ++j) {
			Handle arg = args->getOutgoingAtom(j);
			if (nameserver().isA(arg->get_type(), COND_LINK) or
				nameserver().isA(arg->get_type(), PUT_LINK))
				seq.push_back(HandleCast(arg->execute()));
			else seq.push_back(arg);
		}
		args = createLink(seq, LIST_LINK);
	}

If you approve the above fix or if you have other suggestion let me know, I will work on it.
If you have thoughts on the whole representation I will be happy to hear it. here is the link for the code in progress https://github.com/kasimebrahim/asmoses/tree/atomese-representation it has some useless UTests for now.
And of course, since the real representation if far more complected than the above example in order to simplify the construction I had to introduce two types to represent knobs that wrap PutLink and CondLink. The above representation will be this

(PutKnobLink
  (VariableNode "$knob-1") 
  (TypeNode "AndLink")
  (NumberNode "0 1 2") 
  (ListLink
    (PredicateNode "$1") 
    (ConstKnobLink
      (VariableNode "$knob-2") 
      (PredicateNode "$2") 
      (NumberNode "0 1 2")
      (FalseLink ))) 
  (FalseLink ))

[linas]

Let me look at this over the next few days. A lot of work went into removing eager execution everywhere, it would be a shame to put it back in.

[linas]

actually, after a quick look, why do you need the put link at all? It appears to serve no purpose whatsoever. Just manually plug the CondLink into the $args (for which you used a glob node for some reason -- glob nodes don't really make sense with put links anyway. (well, they sort-of do, but I don't think that's been implemented at all). )

Again, just perform the reduction by hand, so that you have a lambda link, and that's it, nothing more to do .. ...

[kasimebrahim]

Thanks @linas.

why do you need the put link at all?

The reason is as you know the ListLink inside the PutLink is continuously changing until the representation is fully constructed. The first change is we might add more arguments and sub-programs(sub-representations) in the ListLink, such as $c and [or !or nil]($a $b) respectively. The second is we want to recursively expand each argument, such as $a could change in to [$a !$a nil] which is done with CondLink in atomese. So if we substitute the content of the ListLink into the PutLink and remove the PutLink we will have to do all the above changes in every substitution making the representation construction very slow and very complicated.

for which you used a glob node for some reason -- glob nodes don't really make sense with put links anyway. (well, they sort-of do, but I don't think that's been implemented at all).

Similarly I used GlobNode because the number of arguments changes dynamically as the representation construction goes. So I didn't want to track every argument. And Glob is supported and tested with PutLink.

Again, just perform the reduction by hand, so that you have a lambda link, and that's it, nothing more to do .. ..

I dont understand that one could you explain it a bit?

[linas]

There's some misunderstanding.

the ListLink inside the PutLink is continuously changing

That is impossible -- atoms are immutable, and once they've been created, they can never be changed again. They can only be deleted. So everything inside of that PutLink is 100% static, and can never change. Ever. Its frozen, once and for all.

just perform the reduction by hand,
I dont understand

Beta reduction is algorithmic, mechanical. Just perform those steps with pencil and paper. You only need to do it once, because the Atoms are immutable, so you can never get any result other than that one result.

From what I can tell, the Lambda that you wrote is equivalent to this (although, in this form, there seem to be problems... its not well-formed)

(define args (list       ; this is just a scheme list, a scheme define.
  (PredicateNode "$a")
  (CondLink
    (EqualLink
      (Variable "$knob-2")
      (NumberNode 1))
    (PredicateNode "$b")
    (EqualLink
      (Variable "$knob-2")
      (NumberNode 2))
    (NotLink (PredicateNode "$b")))))

(LambdaLink
   (VariableList
      (Variable "$knob-1")
      (Variable "$knob-2"))
   (CondLink
      (EqualLink
         (Variable "$knob-1")
         (NumberNode 1))
      (AndLink 
         args
         (EqualLink
            (Variable "$knob-1")
            (NumberNode 1))
       (NotLink (AndLink args)))))

[linas]

(although, in this form, there seem to be problems... its not well-formed)

... I see what you are doing there. I think there are some minor typos in the expression, I think what you actually wanted was this:

(define the-expr
  (AndLink
    (PredicateNode "$a")
    (CondLink
      (EqualLink (Variable "$knob-2") (NumberNode 1))
      (PredicateNode "$b")
      (NotLink (PredicateNode "$b")))))

(LambdaLink
   (VariableList
      (Variable "$knob-1")
      (Variable "$knob-2"))
   (CondLink
      (EqualLink (Variable "$knob-1") (NumberNode 1))
      the-expr
      (NotLink the-expr)))

Now it's clear -- there are two knobs. Each knob either repeats, or negates the expression.

[kasimebrahim]

That is impossible -- atoms are immutable

That is correct. let me rephrase. It is not changed it is recreated. Based on whether a new knob could result in higher|equal complexity value after reduction is applied, we recreate a new atomese with the new knob.

there are two knobs. Each knob either repeats, or negates the expression.

that is correct.

[linas]

that is correct.

So, is the last thing that I wrote -- is that what you wanted, or did you want something else?

[kasimebrahim]

Let me have another look and I will get back.

In general this is what I am working on if we have (And $a $b) as our initial exampler. we do the following steps to create a representation from it.

We start from the AndLink and
1/ first we take all arguments and we generate a set of sub-programs from them.
i:e {(Or $a $b), (Or !$a !$b), $a, $b}
2/ for every sub-program in our set

• we insert the sub-program to the out going set of AndLink giving us (And $a $b (Or $a $b))
• if complexity(reduct((And $a $b (Or $a $b)))) > complexity(reduct(<our exampler>))
  then we create a knob giving us (And $a $b ([Or !Or nil] $a $b)) other wise we leave it as it was (And $a $b)

finally we recurse through the out going set of the AndLink from the result, which would be some thing like (And $a $b ([Or !Or nil] $a $b) ...), and that would be our exampler.
and if it is a node we wrap it withAnd or Or and we do the above steps on it.

[kasimebrahim]

@linas, so I thought about the above solution. As of my current understanding I can't use that at least with c++, since it requires some kind of meta-programing (because I will need more of that define as I go further down the outgoingsets). I think I could use DefineLink if redefining were allowed. But I might be wrong I will experiment more tomorrow and will ask you further questions.

[linas]

OK, well, you are missing one important step: actually using the resulting tree. That is, picking some knob values, and running the tree over a table of inputs. There are two ways to do this.

One way:

• plug in knob values, creating a (smaller) tree without knobs. Then evaluate that smaller tree against all of your input tables.

The other way:

• Run the tree (the one with knobs in it) over all of your input tables, using some specific knob settings as you do this.

These have different performance profiles. Fist one has:

• CPU total = CPU(create knob-less tree) + CPU(run smaller knobless tree over data)

The second has

• CPU total = CPU(run knobby-tree over data).

It is always the case that CPU(run knobby-tree over data) > CPU(run knobless tree over data) and it is always the case that CPU(create knob-less tree)==large.

So the first way is much slower if your data tables are small. But if the data is huge, then the cost of building the knob-less tree is worth it. If I remember correctly, moses does the first. Not sure.

The first way is more complicated - requires more code to write. ...

[kasimebrahim]

Yes, that is the last and the important part. As you said moses uses the first. On the new atomese representation though we can use the second way.

Since the representation is a program that takes knob settings, for now to get the candidate program(with out the knobs) what we do is just execute it with the knob settings(instance).

And in asmoses to evaluate programs with the input tables first we populate the input table in the atomspace as Values[actually this is done once just after the moses problem type is identified], Then we just call the atomese interpreter on the candidate program. So if we can move the as-moses atomese interpreter to atomspace(gracefully) we can perform both processes in just one execution step.

[linas]

OK, so: The lambda I gave you. it creates the simplified tree. Try it.

(use-modules (opencog) (opencog exec))
(define the-expr
  (AndLink
    (PredicateNode "$a")
    (CondLink
      (EqualLink (Variable "$knob-2") (NumberNode 1))
      (PredicateNode "$b")
      (NotLink (PredicateNode "$b")))))

(DefineLink
   (DefinedSchema "rep")
   (LambdaLink
      (VariableList
         (Variable "$knob-1")
         (Variable "$knob-2"))
      (CondLink
         (EqualLink (Variable "$knob-1") (NumberNode 1))
         the-expr
         (NotLink the-expr))))

(cog-execute!
   (Put (DefinedSchema "rep") (List (Number 1) (Number 0))))

Ooops -- looks like there's a bug in CondLink: (I'll try to fix shortly after posting this) I get:

(AndLink
   (PredicateNode "$a")
   (CondLink
      (EqualLink
         (NumberNode "0")
         (NumberNode "1")
      )
      (PredicateNode "$b")
      (NotLink
         (PredicateNode "$b")
      )
   )
)

so just take that, execute it a second time (for now, till bug is fixed) and that is now your simplified tree. So simplification is .. not that hard.

After the second simplification I get:

(define x (cog-execute!
   (Put (DefinedSchema "rep") (List (Number 1) (Number 0))))
)
scheme@(guile-user)> (cog-execute! x)
$4 = (AndLink
   (PredicateNode "$a")
   (NotLink
      (PredicateNode "$b")
   )
)

[linas]

OK, Just fixed the CondLink so that the double-execute is not needed. Pull req shortly.

Can you describe how/where the table is stored? Were you planning to use ValueOfLink to run the table through the tree?

[kasimebrahim]

@linas, With a few changes on my representation code and your fix on the condlink I managed to remove the PutLink. I now have a fully working representation. Thanks for the help!

Can you describe how/where the table is stored?

For table based problems in table_problem_base [table-problems.cc] there is a common_setup method which handles loading input data files, so here we added a code if 'atomese-port' flag is on populate the atomspace with the Itable and CTable.

so what populate_atomspace.cc does is, it creates Predicate or Schema nodes for every feature and it adds the value of the column of the table to the node with a static value or compressed_value key.

So at the time of fitness evaluation we add the program to the atomspace and call the as-moses interpreter. So this has also enabled as to memoize the interpretation. A program or a subprogram won't get interpreted twice.

Were you planning to use ValueOfLink to run the table through the tree?

We didn't thought of using ValueOfLink or at least I didn't. That might help us if we want to have a single execution to get the candidate and evaluate at the same time.

[linas]

I didn't quite get it...

adds the value of the column of the table to the node with a static value

I guess it adds a FloatValue, which can hold an arbitrary-length sequence of floats? BTW, could you change the name of the key to something else, like "moses table key" or "moses column key" or something like that? just calling it "value" will lead to trouble (especially since its a key...)

So at the time of fitness evaluation we add the program to the atomspace and call the as-moses interpreter.

Well, :-) you don't need to do that, any more. The whole point of FloatValue and ValueOf is that you can do stuff like this:

 (GreaterThan
    (ValueOf (Predicate "column A") (Predicate "moses column key"))
    (Plus
         (ValueOf (Predicate "column B") (Predicate "moses column key"))
         (ValueOf (Predicate "column C") (Predicate "moses column key"))))

which should return a column of 0's and 1's, whenever A>B+C row by row. The PlusLink, etc were designed to replace the moses interpreter. They mostly work. Even reduct works .. so for example

(cog-execute!
    (Plus (Number 1) 
        (Times (Variable $x) (Number 2) (Number 0.5))
        Number -1)))

should correctly reduce to exactly just (Variable $x). Many (most??) of the reduct rules are in the atomspace, already. I'll fix whatever bugs you find. I'm not sure I want to volunteer to write new reduct rules, though...

[linas]

Closing, see #66