List comprehension in Lambda Prolog

Question

I'm using Teyjus for programming in Lambda Prolog. I have this simple lists generator:

type islist int -> list X -> o.

islist N nil
       :- N >= 0.
islist N (H::T)
       :- N >= 0,
          M is N - 1,
          islist M T.

I need to create a predicate that return a list made of all lists generated by islist within a certain bound.

I thought to proceed with Failure driven loop. For the moment I can only print lists generated with the following code:

type loop   int -> o.

loop N
     :- islist N L,
        term_to_string L STR,
        print STR,
        print "\n",
        fail.
loop _.

What I need is to collect these lists not print them (so I need something like a list comprehension). How can I do it?

score 2 · Accepted Answer · answered Dec 13 '20 at 08:59

If you are in Prolog, you can use the setof or bagof built-in operators to do such a collection. These are not available in lambda Prolog. Setof is a natural kind of "higher-order" operator but the proof theory that underlies lambda Prolog (and it's linear logic cousins) do not provide for this kind of feature. It could have been implemented in, for example, Teyjus, but it has not been a priority.

A workaround requires some persistent memory that holds its state across failures. In Prolog, the assert/retract database of clauses can be used. In Teyjus, the only persistence available is the file system. So printing to a file from within a failure-driven loop and then reading back the responses as a list seems to be the only way to do this in the current Teyjus implementation.

score 1 · Answer 2 · answered Jan 10 '23 at 09:29

1

In Prolog (Scryer, SICStus, SWI alike):

?- numlist(0,4,Ns), maplist(length,Ls,Ns).
   Ns = [0,1,2,3,4], Ls = [[],[_A],[_B,_C],[_D,_E,_F],[_G,_H,_I,_J]].

answered Jan 10 '23 at 09:29

false

10,264
13
101
209

List comprehension in Lambda Prolog

2 Answers2