Eliminate MapLink

[linas]

MapLink does not seem to serve any useful purpose. This issue proposes eliminating it, and/or debating reaoson why it should stay (and be improved/changed) Some background comments about it.:

• MapLink was originally proposed as a way to "not search the whole atomspace" but this is misleading: GetLink already doesn't search the whole atomspace; it only pretends that it does. So MapLink offrs no real perf benefit over GetLink.
• An early idea was that MapLink potentially allows you to build pipelines ... but so does GetLink. So this is no advantage.
• Turns out SetLink is a bad idea .. see the wiki page for SetLink, and also Stop using SetLink for search results! #1502. I want to replace all users of SetLink by MemberLink.

[ngeiswei]

@linas, how to make GetLink not search the whole atomspace?

[linas]

GetLink already "doesn't search the whole atomspace". it only seems to, conceptually. In practice, it searches only a tiny portion of it. Some examples (copied from #2202)

(MemberLink (Concept "a") (Concept "my set"))
(MemberLink (Concept "b") (Concept "my set"))

(cog-execute! (Get (And
   (PresentLink (MemberLink (Variable "x") (Concept "my set")))
   (Evaluation (GroundedPredicate "scm:filter") (Variable "x")))
)))

which searches ONLY the members of "my set".

Even better:

(cog-execute! (Bind
   (And
      (PresentLink (MemberLink (Variable "x") (Concept "my set")))
      (Evaluation (GroundedPredicate "scm:filter") (Variable "x")))  )
   (MemberLink  (Variable "x") (Concept "the next stage set"))))

which is a processing pipeline: accepts "my-set" as input, and places results into "the next stage set". BTW, I use AnchorNode for this (i.e. (Anchor "my set") instead of (Concept "my set")) - anchors are a cleaner more obvious drop-off/pick-up points. I suggest everyone could use them for organizing stages of a processing pipeline.

Processing pipelines could be even further improved, e.g. #1750 and/or #1507

[ngeiswei]

Ah, as long as it is efficient it's OK, which I'm not entirely sure of, but maybe it's another issue.

[vsbogd]

It is question for both this issue and issue #1502.

For example query "get all baskets which contain only red balls" can be written as:

(cog-execute! (Get
  (Variable "basket")
  (And
    (Inheritance (Variable "basket") (Concept "basket"))
    (Equal
      (Set)
      (Get (Variable "ball") (And 
        (Member (Variable "ball") (Variable "basket")) 
        (Absent (Evaluation (Predicate "is-red") (Variable "ball")) )
      ))
    )
  )
))

But this query relies on inner GetLink returns SetLink and outer GetLink searchs in results.
@linas, how would you rewrite this example without intermediate SetLink?

[linas]

There's a way to do that -- two ways, actually. One way is to realize that you are doing implicitly chaining, and acknowledge that, and just be explicit about it. The other way is to include the anchor for member as part of the search pattern. I'd like to provide a longer detailed answer to this, to make this clear, but can't right now, distracted with other things :-/

[vsbogd]

If I understand second way properly you are proposing adding Anchors to mark all "not red" balls? But then I need to cleanup these Anchors after query.

I don't understand the first way, what do you mean by explicit chaining?

[ngeiswei]

I wonder if that issue isn't fundamentally related to the notion of https://en.wikipedia.org/wiki/Continuation (which is a bit above my head frankly).

[linas]

@vsbogd if this has actual, direct impact on your work, I can take some time provide a detailed answer; right now, I have other urgent bugs which seem more important that I want to get to. I mean, you have good questions that deserve detailed examples, but I'm overwhelmed at the moment.

@ngeiswei that particular wikipedia article is a classic example of "you won't understand it unless you already know it", it's more or less a terrible article. There's actually a very simple way to explain continuations: They're just like C++ objects. Or rather, C++ objects with just one anonymous method. When you call a continuation, it "magically" remembers internal state the same way that a C++ instance "remembers" internal state. Here is the (slightly buggy) C++ version of the example in that article:

int (*the-continuation)(void) = nullptr;    // function pointer
class test {
    int i;   // private member
    int call-cc(void)  {    //private method 
           *the-continuation = test::call-cc;    // set function pointer to this method
           i++; // increment
    }
public:
    test() {    // constructor
          i = 0; 
           *the-continuation = test::call-cc;   // clobber function pointer
      }
};

new test;   // memleak!
printf ("its %d\n", (*the-continuation)());
printf ("its %d\n", (*the-continuation)());
int (*another-continuation)(void) = the-continuation;
new test;   // memleak!!
printf ("its %d\n", (*the-continuation)());
printf ("its %d\n", (*another-continuation)());
printf ("its %d\n", (*the-continuation)());

The only "bug" in the above is that function pointers and method pointers in C++ can't be mixed the way I mixed them, so you would need to glom this up with extra syntax to make it actually work. But that is all that the first example is doing.

Continuations are just objects with a single anonymous method. There's a bit more; its a Zen-master story:

Young Buddhist acolyte:  
      "Master! Master! I finally understand continuations!"
      "They are a poor-man's object!"
Master hits him on the head: 
      "You understand nothing!"
Months later, the acolyte returns and says:  
       "Master! I finally understand objects!"
       "They are a poor-man's continuation!"
Master replies:
       "Now you understand."

Once you get it, continuations are actually simpler, easier, nicer and more powerful than objects, but for starters, just think of them as anonymous objects with a single anonymous method (because that is what they are).

[linas]

Well, I messed that up. Its actually "closures are a poor-man's object". Continuations are more like a go-to statement into an object. Or actually, even more like a come-from statement in an object: https://en.wikipedia.org/wiki/COMEFROM Whatever. you do certainly need to grok closures in scheme (its not hard); continuations are .. less structured and uglier as a result.

[amebel]

@ngeiswei see http://community.schemewiki.org/?call-with-current-continuation

[ngeiswei]

Thanks guys, I understand what is a continuation now, in principle at least (which is different from having practical experience with it).

[vsbogd]

@linas, there is no urgency, so please answer when you have time.

[linas]

@vsbogd you asked:

If I understand second way properly you are proposing adding Anchors to mark all "not red" balls? But then I need to cleanup these Anchors after query.

Yes, this is a problem. It's roughly equal to having to clean up SetLinks. Both can be done by performing searches in child atomspaces, and then popping when done (cog-push-atomspace) and (cog-pop-atomspace) although you have to be careful to not make your search results disappear after the pop!

The push-pop solution has the advantage of being thread-safe; you can have two different searches running at the same time, using the same Anchor, without each one polluting the Anchor with results from the other one.

Without the push-pop, the use of AnchorNode is NOT thread-safe; this line of reasoning lead to #1750 - a publish/subscribe system, so that the results of the first search are seen only by those who are subscribed to get them.

[linas]

@vsbogd you asked:

get all baskets which contain only red balls

This is a very interesting and challenging question. It is making me contemplate implementing a ForAllLink to complement the PresentLink (which is just ExistsLink by a different name). I think I know how to do this, now, and will give it a whirl.

what do you mean by explicit chaining?

Chaining is the wrong word. I'm not sure what the right word is. I meant "just basic expansion". Since this issue is wayyy off topic, already, it won't hurt to post a solution. It's done in two steps: first, find all baskets containing balls that are not red. Second, find baskets which aren't one of those.

This is a sequential running of two term re-writing steps.

The first search pollutes the atomspace with (Member (Variable "basket") (Concept "baskets-with-non-red balls")) this is needed because, without this, the second rule cannot run. Thus the need for push/pop of atomspaces.

BTW, one way to think of this is that the (cog-push-atomspace) creates a new "Kripke frame". So that's good. The bad news is that, when using Kripke frames, one typically wants to actually keep the very last one (viz throw away the earlier atomspaces) and one also wants them to be confluent (merge the contents of two different atomspaces that were pushed for two different reasons) Right now we cannot do either. But that's because right now, we don't have any problems that needs Kripke frames as a solution. Just FYI.

Here's the sequence-of-two-rewrite-rules solution:

(use-modules (opencog) (opencog exec))

(Inheritance (Concept "reds basket") (Concept "basket"))
(Inheritance (Concept "reds&greens basket") (Concept "basket"))
(Inheritance (Concept "yellows basket") (Concept "basket"))

(Member (Concept "red ball") (Concept "reds basket"))
(Member (Concept "red ball too") (Concept "reds basket"))
(Member (Concept "red ball also") (Concept "reds basket"))
(Member (Concept "red ball") (Concept "reds&greens basket"))
(Member (Concept "red ball too") (Concept "reds&greens basket"))
(Member (Concept "green ball") (Concept "reds&greens basket"))
(Member (Concept "yellow ball") (Concept "yellows basket"))

(Evaluation (Predicate "is red") (Concept "red ball"))
(Evaluation (Predicate "is red") (Concept "red ball too"))
(Evaluation (Predicate "is red") (Concept "red ball also"))

(Evaluation (Predicate "is green") (Concept "green ball"))
(Evaluation (Predicate "is yellow") (Concept "yellow ball"))

(define baskets-with-non-red-balls
(Bind
   (VariableList
      (TypedVariable (Variable "basket") (Type 'ConceptNode))
      (TypedVariable (Variable "ball") (Type 'ConceptNode))
   )
   (And
      (Inheritance (Variable "basket") (Concept "basket"))
      (Member (Variable "ball") (Variable "basket"))
      (Absent (Evaluation (Predicate "is red")  (Variable "ball")))
   )
   (Member (Variable "basket") (Concept "baskets-with-non-red balls")))
)
(cog-execute! baskets-with-non-red-balls)

(define red-baskets
   (Get
      (TypedVariable (Variable "basket") (Type 'ConceptNode))
      (And
         (Inheritance (Variable "basket") (Concept "basket"))
         (Absent (Member (Variable "basket")
            (Concept "baskets-with-non-red balls"))))))

(cog-execute! red-baskets)

[linas]

Once there's an itch, I want to scratch it. As of pull req #2288 there is now an AlwaysLink that solves the red-balls-in-basket query in one shot. It was pretty easy to implement (but only cause I already know the pattern matcher internals) It is not clear if a NeverLink is also needed (because "not always" is "sometimes")

@vsbogd you are invited to cook up more complex examples. Your ball-in-basket example also had the general flavor of a set-intersection type problem, and I imagine that there are other similar queries that are currently awkward, hard to express. We should look at them.

[vsbogd]

Hi @linas, AlwaysLink works nicely thank you. I will think about it and If I will find something interesting I will publish it.

BTW, I found another way to re-write this query via SatisfactionLink which is:

(cog-execute! 
  (Get (Variable "basket")
  (And
    (Inheritance (Variable "basket") (Concept "basket"))
    (NotLink (SatisfactionLink (Variable "ball") 
        (And 
          (Member (Variable "ball") (Variable "basket")) 
          (Absent (Evaluation (Predicate "is red") (Variable "ball")) )
     ))
    )
  )
))

[linas]

I enshrined the not..exists...absent variant in examples/pattern-matcher/always.scm

Reading it feels like reading some textbook in set theory, where you have to mentally parse these long expressions "not and exists or equals and not always greater..." hard for humans to do.

The goal with all of these is that, in the long run, some other algo (PLN, moses, maybe even VQA?) are generating these queries and launching them ... so we need to make it easy for these other algos to run these things.

[linas]

Closing. Won't-fix. They're actually useful. I renamed MapLink to FilterLink and will be extending it's abilities shortly. It seems to be of the right form for performing transformations on streams of data. The old MapLink only accepted and returned SetLinks -- the new one will accept any kind of set or vector or stream, and in particular, the QueueValue. Work is underway; i need this for streamlining the language-learning code. See https://github.com/opencog/atomspace/tree/master/opencog/object-atomese for details