Getting all key-value pairs out of a dict using bagof/3 fails, but succeeds with findall/3

Help!
1

Probably something borderline:

I have here some test code where retrieval of all key-value pairs from a Dict works with findall/3, but fails with bagof/3. I have tried a few ways to do it, commented out here, but the one currently commented in should work as I see it. Instead, bagof/3 just fills the bag with a single solution:

:- begin_tests(dicts).

   empty_dict(foo{}).
   nonempty_dict(foo{x:alpha, y:bravo, z:charlie}).
   
   bagof_call(Value,Dict,Key) :- (Value = Dict.Key).

   % Using bagof/3 to get all key-value pairs out of a dict
   
   test(test01_get_all_content_using_bagof, [true(T)]) :-
      nonempty_dict(Dict),
      % bagof(Key-Value, Value = Dict.get(Key), Bag),           % NO
      % bagof(Key-Value, get_dict_ex(Key,Dict,Value), Bag),     % NOT FOUND
      % bagof(Key-Value, bagof_call(Value,Dict,Key), Bag),      % YES
      % bagof(Key-Value, get_dict(Key,Dict,Value), Bag),        % YES      
      bagof(Key-Value, (Value = Dict.Key), Bag),                % NO
      keysort(Bag,SortedBag),
      T = (SortedBag == [x-alpha, y-bravo, z-charlie]).

   % Using findall/3 to get all key-value pairs out of a dict
   
   test(test02_get_all_content_using_findall, [true(T)]) :-
      nonempty_dict(Dict),      
      % findall(Key-Value, Value = Dict.get(Key), Bag),        % YES
      % findall(Key-Value, get_dict_ex(Key,Dict,Value), Bag),  % NOT FOUND      
      % findall(Key-Value, get_dict(Key,Dict,Value), Bag),     % YES
      findall(Key-Value, (Value = Dict.Key), Bag),             % YES
      keysort(Bag,SortedBag),
      T = (SortedBag == [x-alpha, y-bravo, z-charlie]).
     
:- end_tests(dicts).

rt(dicts) :- run_tests(dicts).
1 Like
2

I think this is because the Value = Dict.Key expands into something with intermediate variables that aren’t qualified in the bagof, but findall will qualify event those intermediate variables.

Oh actually, it looks like a dict inside a findall just gets expanded incorrectly:

test_get_bag(Dict, Bag) :-
    bagof(Key-Value, (Value = Dict.Key), Bag).

?- listing(test_get_bag).
test_get_bag(A, E) :-
    '.'(A, B, D),
    bagof(B-C, C=D, E).


test_get_findall(Dict, Bag) :-
    findall(Key-Value, (Value = Dict.Key), Bag).

?- listing(test_get_findall).
test_get_findall(Dict, Bag) :-
    findall(Key-Value,
            ( '.'(Dict, Key, A),
              Value=A
            ),
            Bag).

I guess if bagof did get expanded correctly, then my above comment would be the cause (i.e. the A variable we see in the findall needs to be existentially qualified to work with bagof).

1 Like
4

Pushed a fix (4ee28abda5e826a3d98791cd588d7ff7ac885e3a) for this. Also automatically adds the intermediate variables to the existential variable set.

4 Likes
5

Wow, that’s some quick turnaround :ok_hand:

7

It is likely that there are more corner cases. Given an untyped language with code-is-data this stuff is hard to get correct for all corner cases.

1 Like
8

The developer will have to make things clear to himself/herself by adding helper predicates in any case before drifting off into complexity like Aguirre on a float.

Programming … it’s all about staying in P. But it’s mainly about human cognitive limits.

1 Like
9

Please explain. :confused:

10

I assume dtonhofer means “staying in the complexity class of P (vs NP)”

1 Like
11

It is just a pithy way to say that all of Computer Science would collapse and we would all be out of a job if we were able to not care about optimizations. Actually, the guys from the electronics lab would be able to do it all by themselves.

Finagling with sorting algorithms for example is all about keeping space and time (and energy) requirements at (low) powers of a polynomial in the size of the problem.

And of course, writing complex problems hits another limit relatively rapidly: humans can’t write programs very well. 7 chunks held in short-term memory is lousy. If your compiler has bugs that will only become apparent in highly complex, imbricated code, you may well be safe! Unless you let a student loose, because he/she is still unaware of cognitive limits and still free of the reflexes that makes one avoid those particular minefields.

You may be aware of this related fun read by Scott Aaronson: https://www.scottaaronson.com/papers/npcomplete.pdf

12

Nice, it notes holographic bound.