Apologies for splitting the thread, but I thought it'd be easier to read this way.

This comment addresses your concerns about me writing the program I wanted Louise to generate. I like to see background knowledge ("BK", e.g. shorter/2) as a library of sub-programs from which the learner can select the ones necessary to compose a target program. The example above is trivial because I've defined a BK predicate that is necessary and sufficient to learn, so the learner was indeed served the solution "on a plate".

However, as I said in my previous comment, Louise can learn its own background knowledge. This can be done by predicate invention, or more simply, by incrementally learning necessary sub-programs.

Below is a problem definition and learning session that first learns length/2 (renamed llength/2 to avoid name clashes with the built-in) and shorter/2 from list and numeric function primitives, before using the learned predicates as BK for ordered/2. Like I say in my previous comment, it's a little larger than the previous one:

  ?- list_mil_problem([llength/2,shorter/2,ordered/3]).
  Positive examples
  -----------------
  llength([],0).
  llength([a],s(0)).
  shorter([a],[b,c]).
  shorter([1,2],[3,4,5]).
  ordered([a],[b,c],[d,e,f]).
  
  Negative examples
  -----------------
  :-ordered([a],[b],[c]).
  :-ordered([a,b,c],[a,b],[c]).
  
  Background knowledge
  --------------------
  tail/2:
  tail([A|B],B).
  
  p/2:
  p(s(A),A).
  
  s/2:
  s(A,s(A)).
  
  Metarules
  ---------
  abduce metarule 'P(X,Y)'.
  list_rec_func metarule 'P(x,y):- Q(x,z),R(y,u),P(z,u)'.
  list_comp metarule 'P(x,y):- Q(x,z), R(y,u), S(z,u)'.
  triadic_chain metarule 'P(x,z,y):- Q(x,z), R(z,y)'.
  true.

  ?- time(learn_dynamic([llength/2,shorter/2,ordered/3])).
  llength([],0).
  llength(A,B):-tail(A,C),p(B,D),llength(C,D).
  shorter(A,B):-llength(A,C),llength(B,D),s(C,D).
  ordered(A,B,C):-shorter(A,B),shorter(B,C).
  % 20,928 inferences, 0.000 CPU in 0.007 seconds (0% CPU, Infinite Lips)
  true.

The BK for this problem consists of tail/2, similar to "car" in Lisp (i.e. matches the head of a list) and the pair of p/2 and s/2, that act as "dereferencers" to Peano number functions. These are bog-standard Prolog programs and useful whenever a target program must manipulate a list, or perform numerical reasoning. In other words, they're pretty much generic, like a standard library of sorts.

I've added the full source of the experiment file for the learning task on pastebin. It includes a few more detailed comments and a set of constraints to clean up the learned hypothesis, mostly for aesthetic reasons:

https://pastebin.com/nPYFKKpx

Of course this is still a toy problem and we know the solution. But I hope it demonstrates the principle. On the other hand, you'd still not be able to solve this with alternative approaches, e.g. I see that the benchmark suite you pointed to is used for genetic programming. I'm also not aware of neural approaches that build programs incrementally, from a couple of examples of each sub-program.

That is to say, this is a toy problem for ILP. For other approaches it's unsolvable.