Pure relational arithmetics [Was: How to find the letters?]

Mikael Brockman <mikael@phubuh.org> wrote in message news:<87y8iqwocz.fsf@igloo.phubuh.org>
..
>
> You can't have free variables in math expressions.  If you've
> got R = 5 and you tell Prolog to give you R + 10, it'll just
> change R to 5 and send 5 + 10 to the math guy.  The math guy
> is into maths *only*.  All the searching & backtracking stuff,
> he doesn't want any of it.  Sorry.

I guess it depends on math expressions. It is possible to implement
arithmetics on arbitrary precision binary non-negative integers in
ordinary Prolog. In fact, in a pure subset of Prolog -- without any
use of a cut, var, etc. Addition, multiplication, division with the
remainder become pure relations, which can be used in any mode
whatsoever. For example, we can use the mul(X,Y,Z) relation either to
multiply two numerals X and Y -- or to find all factorizations of
Z. One of the tests does exactly that. We can use such relations to
concisely write loops in the regular Prolog style:

et(L) :- less(I,L), less(J,L), et(I,J,_), fail.
et(_).
?- build(8,L), et(L).

The expression above tries et(I,J,_) for all I and J within the range
[0,8]. The predicate 'less' is defined in the most obvious and
mathematically pleasing way:

% less: N M
% holds if N < M, or
% if exists X>0, N + X = M
less(N,M) :- pos(X), add(N,X,M).

http://pobox.com/~oleg/ftp/Prolog/pure-bin-arithm.prl


The same system has been re-implemented in Kanren, which has fair
disjunctions and conjunctions. We can achieve the total recursive
enumerability of addition and multiplication: e.g, mul(X,Y,Z) recursively
enumerates all of its domain (and do so in the `natural' order).

http://kanren.sf.net
http://cvs.sf.net/viewcvs.py/kanren...-bin-arithm.scm

oleg@pobox.com wrote:
> For example, we can use the mul(X,Y,Z) relation either to
> multiply two numerals X and Y -- or to find all factorizations of
> Z. One of the tests does exactly that. We can use such relations
> to concisely write loops in the regular Prolog style:
>
> et(L) :- less(I,L), less(J,L), et(I,J,_), fail.
> et(_).
> ?- build(8,L), et(L).
>
> The expression above tries et(I,J,_) for all I and J within the
range
> [0,8]. The predicate 'less' is defined in the most obvious and
> mathematically pleasing way:

I'm somewhat  here. You used et\1 first but then go
on and work with et\3. What is "et" supposed to stand for (i
am guessing you don't refer to the small ugly creature who
wanted "phone home" in the 80's).

Also,  if i understand the issue correctly, i could have define
integers by a successor predicate and then play with numbers
as i wished to. BUt that would be rather painfully slow, right?

--

Kindly
Konrad
---------------------------------------------------
May all spammers die an agonizing death; have no burial places;
their souls be chased by demons in Gehenna from one room to
another for all eternity and more.

Sleep - thing used by ineffective people
as a substitute for coffee

Ambition - a poor excuse for not having
enough sense to be lazy
---------------------------------------------------

> et(L) :- less(I,L), less(J,L), et(I,J,_), fail.
> et(_).
> ?- build(8,L), et(L).
> The expression above tries et(I,J,_) for all I and J within the range
> [0,8].
Correction: the range is obviously [0,7]. Sorry.


> I'm somewhat  here. You used et\1 first but then go
> on and work with et\3.

The predicate et/3 does the actual test (of enumerability), that is,
if
X = I, Y = J, mul(X,Y,Z)
succeeds, so does
mul(X,Y,Z), (X = I, Y = J; X = J, Y = I)
for any I and J (instantiated or not). The predicate et/1 is just a
driver that tries the test et/3 for a range of I and J.

> i am guessing you don't refer to the small ugly creature who
> wanted "phone home" in the 80's.

Why is it ugly?

> Also,  if i understand the issue correctly, i could have define
> integers by a successor predicate and then play with numbers
> as i wished to. BUt that would be rather painfully slow, right?
Yes, it is indeed slow.

The tragic thing about this is that relation arithmetic may be the
answer to a whole slew of problems in computer and natural science and
people are so lost they think of relation arithmetic in terms of
relations between standard numbers rather than in terms of relation
numbers.

As Bertrand Russell said:

"I think relation-arithmetic important, not only as an interesting
generalization, but because it supplies a symbolic technique required
for dealing with structure. It has seemed to me that those who are not
familiar with mathematical logic find great difficulty in
understanding what is meant by 'structure', and, owing to this
difficulty, are apt to go astray in attempting to understand the
empirical world. For this reason, if for no other, I am sorry that the
theory of relation-arithmetic has been largely unnoticed."

"My Philosophical Development" by Bertrand Russell