Subject: Re: [SWIPL] problem

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 4 Mar 2002 14:31:54 +1300 (NZDT)

"dhruv malik" <[email-masked]>
sent us a copy of some exercises.  It is not clear to me _why_
this was done, as there appeared to be no question about these
exercises.  It looks uncommonly like a homework problem, and
Netiquette frowns on asking people to do your homework for you.

	 from Computational Intelligence by david pool Ex3.10 pg 108
	
	Q) Use a binary representation of natural numbers,where a number 
	is either one,b(N,zero), or b(N,one),where
	
It is important to be aware that there are two rival definitions
of "natural number".  For myself, I prefer the set theory version:
 - a natural number is an integer greater than OR EQUAL TO zero.
Some people prefer a definition which I have never found to be of any
use; I'm not sure which branch of mathematics it hails from.
 - a natural number is an integer STRICTLY GREATER THAN zero.

Pool is using the less natural/less useful definition.

:- type bit
   ---> zero			% represents 0
      ; one.			% represents 1
:- type unnatural
   ---> one			% represents 1
      ; b(unnatural,bit)	% b(U,B) represents 2U'+B'

	a)number(N) is true if N is the form of a number.
	
The Jackson/Sterling rule:  "code usually has the same shape
as either the input it matches or the output it produces".

So you are looking for something like

    is_bit(zero).
    is_bit(one).
    
    is_unnatural(one).
    is_unnatural(b(U,B)) :- is_unnatural(U), is_bit(B).

Linearity obvious by inspection.

	b)succ(N,M) is true if M is the number after number N.
	
The obvious way to start is

    succ(one, ???).
    succ(b(U,B), ???) :- ???.

The first one is easy enough to fill in: succ(1) = 2 which is
represented by b(one,zero), so

    succ(one, b(one,zero)).
    succ(b(U,B), ???) :- ???.

The second case requires a bit more thought.  In fact, my first thought
is that this really isn't a good data structure for unnaturals.  I'd
prefer

    :- type less_unnatural
       ---> '1'
          ; '2n+0'(less_unnatural)
          ; '2n+1'(less_unnatural).

Either way, this suggests a case analysis on B.

    succ(b(U,zero), ???) :- ???.
    succ(b(U,one), ???) :- ???.

Adding 1 to zero gives you one with no carry, which takes care of the
B=zero case.  Adding 1 to one gives you one with a carry of 1, which
can be handled by a recursive call, and that takes care of the B=one case.
So

    succ(one, b(one,zero)).
    succ(b(U,zero), b(U,one)).
    succ(b(U,one),  b(V,zero)) :- succ(U, V).

Given this example of how to think about it, the remaining exercises
are trivial.

	h) Suppose someone suggested extending this representation to all 
	non negative integers simply by adding zero as a number. Why might 
	this cause problem? Hint: Consider b(zero,one).

The hint relates to the SECOND FUNDAMENTAL QUESTION ABOUT ABSTRACT DATA TYPES:
    what is the relationship between	
	representation(X) = representation(Y)		% concrete level
    and	
	X = Y						% abstract level

(The first fundamental question is, of course,
    what is the relationship between X and representation(X)?)