A lyric filtering, with naked Prolog

[haijinSk]

I was inspired by Markus @triska

As I'm a Prolog beginner, and not only Prolog beginner, I would say, the realm of programming itself is something I'm only starting to explore...

So, often I have crazy ideas in my head, like: how to do the numeric filtering, but without clpz library. With naked Prolog, so to speak, how can I make a truly relational filtering program, working in "two-way" mode (like with clpz), at least to some extent... The relational mode means without standard built-in operators: is/2 and friends. Without standard modulo, minus and comparison operator. Is it possible?

The code works only with the basic numbers 0..9 and 10 (why not). I'm not a math person, but, I think, the code might be extended (not by me) to work with arbitrary natural numbers, except, represented like this: 5 = [5], 112 = [1,1,2] as the user-input format; if I want to use only the "naked" Prolog, and I wanted. Yes, in a small 0..9 domain, I could define directly what is even or odd number: without my lists of ones... And indeed, direct defining is the magic. Prolog asks us to define...

Of course, I love clpz library. Beside the declarative arithmetic, many problems, nightmares using classical computer science methods, are suddenly only few declarative lines of code, with the clpz. I love every library and design decision that makes Scryer a more declarative, relational/bidirectional and easy to use Prolog system.

Too, I like the notion (Marc Denecker/recently with David S. Warren) that Prolog is basically a language of (inductive) definitions. Inductive definitions allows bottom-up reasoning, in a good way. Like: Dear category theory, Prolog has a cool constructive math build in, by definition, by the constructive :-. Like: Bottom-up thinking in Prolog considered beneficial, especially for beginners: in this view, for instance, recursion is not a concept to think with, it's only a concrete mechanism used to evaluate inductive definitions top-down. But we can think iteratively: building (with our predicates, independently of problem decomposition) a set (a relation is a set, a set of tuples with the desired property) in a bottom-up way. Like: Programming and proving that your program is correct at the same time. Unfortunately, I'm afraid, my filtering example is not a good example of that methodology.

Brutally inefficient, quick and dirty and useless, call it a kindergarten programming, it is (sometimes I want to touch some CS and programming basics with my own hands, the most simple things); it's only my crazy thought experiment after all, or my MacGuffin. But I hope, it's fully "definitional", even somewhat inductive, in a lyric sense... Or, maybe not.

Thank you.

n_1s(0,[]).
n_1s(1,[1]).
n_1s(2,[1,1]).
n_1s(3,[1,1,1]).
n_1s(4,[1,1,1,1]).
n_1s(5,[1,1,1,1,1]).
n_1s(6,[1,1,1,1,1,1]).
n_1s(7,[1,1,1,1,1,1,1]).
n_1s(8,[1,1,1,1,1,1,1,1]).
n_1s(9,[1,1,1,1,1,1,1,1,1]).
n_1s(10,[1,1,1,1,1,1,1,1,1,1]).

nums_odds_evens([],[],[]).
nums_odds_evens([N|Rest],[N|Os],Es) :- odd(N), nums_odds_evens(Rest,Os,Es).
nums_odds_evens([N|Rest],Os,[N|Es]) :- even(N), nums_odds_evens(Rest,Os,Es).

odd(N) :- n_1s(N,Ones), odd1s(Ones).
even(N) :- n_1s(N,Ones), even1s(Ones).

even1s([]).
even1s([1,1|Os]) :- even1s(Os).

odd1s([1]).
odd1s([1,1|Os]) :- odd1s(Os).

?- nums_odds_evens([0,1,2,3,4,5,6,7,8,9,10],Os,Es).
   Os = [1,3,5,7,9], Es = [0,2,4,6,8,10]
;  false.

?- length(Ns,3),nums_odds_evens(Ns,Os,Es).
   Ns = [1,1,1], Os = [1,1,1], Es = []
;  Ns = [1,1,3], Os = [1,1,3], Es = []
;  Ns = [1,1,5], Os = [1,1,5], Es = []
;  Ns = [1,1,7], Os = [1,1,7], Es = []
;  Ns = [1,1,9], Os = [1,1,9], Es = []
;  Ns = [1,1,0], Os = [1,1], Es = [0]
;  Ns = [1,1,2], Os = [1,1], Es = [2]
;  Ns = [1,1,4], Os = [1,1], Es = [4]
;  Ns = [1,1,6], Os = [1,1], Es = [6]
;  Ns = [1,1,8], Os = [1,1], Es = [8]
;  Ns = [1,1,10], Os = [1,1], Es = [10]
;  Ns = [1,3,1], Os = [1,3,1], Es = []
;  Ns = [1,3,3], Os = [1,3,3], Es = []
;  Ns = [1,3,5], Os = [1,3,5], Es = []
;  Ns = [1,3,7], Os = [1,3,7], Es = []
;  Ns = [1,3,9], Os = [1,3,9], Es = []
;  Ns = [1,3,0], Os = [1,3], Es = [0]
;  Ns = [1,3,2], Os = [1,3], Es = [2]
;  Ns = [1,3,4], Os = [1,3], Es = [4]
;  Ns = [1,3,6], Os = [1,3], Es = [6]
;  Ns = [1,3,8], Os = [1,3], Es = [8]
;  Ns = [1,3,10], Os = [1,3], Es = [10]
;  Ns = [1,5,1], Os = [1,5,1], Es = []
;  Ns = [1,5,3], Os = [1,5,3], Es = []
;  Ns = [1,5,5], Os = [1,5,5], Es = []
;  Ns = [1,5,7], Os = [1,5,7], Es = []
;  Ns = [1,5,9], Os = [1,5,9], Es = []
;  Ns = [1,5,0], Os = [1,5], Es = [0]
;  Ns = [1,5,2], Os = [1,5], Es = [2]
;  Ns = [1,5,4], Os = [1,5], Es = [4]
;  ... .

[hurufu]

You can define natural numbers using classic successor function:

nat(0).
nat(succ(X)) :- nat(X).

And then you can start building on that notion, for example you can define odd and even numbers:

nat_even(0).
nat_even(succ(succ(X))) :- nat_even(X).

nat_odd(succ(X)) :- nat_even(X).

Of course you then need to accept that succ(succ(succ(0))) is three, but if you insist on using digits (1,2,3...), you will need to define some mapping from the successor notation to Arabic numerals.

[UWN]

odd1s([1|Os]) :- even1s(Os).

And as to successor arithmetics, the functor s/1 is more commonly used.

[haijinSk]

Thank you for the suggestions. My newest "lyric code" is not so naked Prolog: I'm using length/2 as the key component, and append/3:

% Warning: Don't try this at home! Especially with numbers not small enough...

nums_odds_evens([],[],[]).
nums_odds_evens([N|Ns],Os,[N|Es]) :- even(N), nums_odds_evens(Ns,Os,Es).
nums_odds_evens([N|Ns],[N|Os],Es) :- odd(N), nums_odds_evens(Ns,Os,Es).

even(N) :- length(Ls,N), append(Is,Is,Ls).

odd(N) :- length([_|Ls],N), append(Is,Is,Ls).

With length/2 I don't need write definitions for converting and building a number representation, append/3 for the "modulo" part. With brutally inefficient "numbers are lists" as a starting point, this code simplification has an additional computational cost, I suspect.

At the end of the day, it was a mistaken, out of topic experiment/attempt (not using clpz struggling with not using is/2 and mod/2) of a naive beginner.

Nevertheless, I think, I like experimenting with Prolog; though, at a "simple/basic" level.

Thank you.

[haijinSk]

PS: As a bonus or by-product, then, thinking/writing about the relational filtering, I also "discovered" my own version of a (wannabe) relational addition, but I edited/removed it from my comment (or the whole comment) then:

% A hand-made, relational/bidirectional addition outside of clpz, almost... 
% if bidirectional, then the name "add" is not a good one.

add(N1,N2,Sum) :- 
  length(N1s,N1),
  length(N2_1s,N2),
  append(N1s,N2_1s,Sum1s),
  length(Sum1s,Sum).

The "addition" example. Again, don't try it at home...

?- add(123,X,1234).
   X = 1111
;  ... .

---

And today, accidentally, via reading something about Prolog on Softpanorama, I've found:

"Pure, Declarative, and Constructive Arithmetic Relations (Declarative Pearl)"

https://okmij.org/ftp/Prolog/Arithm/arithm.pdf

https://okmij.org/ftp/Prolog/Arithm/

[hurufu]

Thanks for a link to a cool paper.

[UWN]

Consider the following failure-slice:

add(N1,N2,Sum) :- 
  length(N1s,N1),
  length(N2_1s,N2), false,
  append(N1s,N2_1s,Sum1s),
  length(Sum1s,Sum).

If this does not terminate, then also your original program does not terminate (universally).

[haijinSk]

Thank you very much for this suggestion/hint/advice!!!

I didn't want to use "lower-level" things I don't know much about (consequences for a relational programming), like var/1, but for now:

% Now, I think, it might be tried at home, but again: with numbers small enough...

add(N1,N2,Sum) :-  
  \+ var(Sum),
  length(Sum1s,Sum),
  append(N1s,N2_1s,Sum1s),
  length(N1s,N1),
  length(N2_1s,N2).

add(N1,N2,Sum) :-   
  var(Sum),
  length(N1s,N1),
  length(N2_1s,N2),
  append(N1s,N2_1s,Sum1s),
  length(Sum1s,Sum).