%% Your name here
%% Programming assignment 2
%% Computer Science 3675
%% Fall 2004

%% Write your program by adding to this file.  Delete this comment.

Package arithmetic

=======================================================
                         Export
=======================================================

%%======================================================
%%                 Representing numbers
%%======================================================
%%
%% Integers are represented in the form (c,L) where c is either
%% '+' or '-' and L is a list of bits giving the binary representation
%% of the number, from low order to high order.  An empty list 
%% represents 0.  Here are some examples.
%%
%%   Number (decimal)       Representation here
%%   ----------------       -------------------
%%         0                     ('+', [])
%%         1                     ('+', [1])
%%        -1                     ('-', [1])
%%        12                     ('+', [0,0,1,1])
%%       -12                     ('-', [0,0,1,1])
%%
%% A number can be written with extra zeroes.  For example,
%% in decimal, you can write 012 for 12.  In our list
%% notation,  you might use ('+', [0,0,1,1,0]) to represent
%% 12, with an extra 0 at the end of the list.
%%
%% Say that a number is normalized if its list of bits
%% does not end on 0.  So ('+', [0,0,1,1]) is normalized, but
%% ('+', [0,0,1,1,0]) is not.
%%
%% The functions provided by this package do not require
%% their parameters to be normalized, but they always
%% product normalized results.
%%======================================================

Abbrev Number = (Char, [Natural]).
          
========================================================
%%       Functions exported by this package
========================================================

Expect
  sum	  : (Number, Number) -> Number
  
          %" sum(x,y) is x + y, in terms of numbers.
	  %"
	  %" See number representation.
	  ;
	  
  diff	  : (Number, Number) -> Number
  
          %" diff(x,y) is x - y, in terms of numbers
	  %"
	  %" See number representation.
	  ;
	  
  product : (Number, Number) -> Number
  
          %" product(x,y) is x * y, in terms of numbers.
	  %"
	  %" See number representation.
	  ;

  compare : (Number, Number) -> Integer
  
  	  %" compare(x,y) is
	  %"    1   if x > y
	  %"    0   if x == y
	  %"   -1   if x < y
	  %"
	  %" See number representation.
%Expect

=======================================================
                        Implementation
=======================================================

Import "collect/listfun".
Advise nowarn notExhaustive.

=======================================================
%%		Functions on lists
=======================================================

=======================================================
%%			inc
=======================================================
%% inc(x) yields the representation of x + 1
=======================================================

Define 
  Example inc[1,0,1] = [0,1,1].    %% 5 + 1 = 6
  Example inc[1,1,1] = [0,0,0,1].  %% 7 + 1 = 8
  
  case inc []      = [1]
  case inc (0::?t) = 1::t
  case inc (1::?t) = 0::inc t
%Define

=======================================================
%% dec(x) yields the representation of x - 1.  It is
%% required that x > 0, so that the result will be
%% nonnegative.
=======================================================

Define 
  Example dec [0,1,1]   = [1,0,1].     %% 6 - 1 = 5
  Example dec [0,0,0,1] = [1,1,1,0].   %% 8 - 1 = 7

  -- Define this
%Define

=======================================================
%%			sumU
=======================================================
%% sumU(x,y) yields the representation of x + y
=======================================================

Define 
  Example sumU([1,0,1], [0,0,1,1]) = [1,0,0,0,1].  %% 5 + 12 = 17
  Example sumU([1,1,1], [1,1])     = [0,1,0,1].    %% 7 + 3 = 10

  -- Define this
%Define

=======================================================
%%			diffU
=======================================================
%% diffU(x,y) yields the representation of x - y.  It is
%% required that x >= y.  This function will work when
%% its parameters are not normalized, but it is not
%% guaranteed to produce a normalized result.
=======================================================

Define 
  Example diffU([1,1,1], [0,0,1]) = [1,1,0].    %% 7 - 4 = 3
  Example diffU([0,0,0,1], [1,1]) = [1,0,1,0].  %% 8 - 3 = 5

  -- Define this
%Define

=======================================================
%%			productU
=======================================================
%% productU(x,y) yields the represenation of x * y.
=======================================================

Define
  Example productU([1,0,1], [0,0,1,1]) = [0,0,1,1,1,1].   %% 5 * 12 = 60
  
  -- Define this
%Define

=======================================================
%%			compareU
=======================================================
%% compareU(x,y) yields 
%%     1 if x >= y
%%     0 if x == y
%%    -1 if x < y
%%
%% This function requires that both x and y are
%% normalized.
=======================================================

Define 
  Example compareU([0,1,1], [1,0,1])   = 1.   %% 6 > 5
  Example compareU([0,1,1], [0,1,1])   = 0.   %% 6 = 6
  Example compareU([0,1,1], [0,0,0,1]) = -1.  %% 6 < 8

  case compareU([], [])   = 0
  case compareU([], ?::?) = -1
  case compareU(?::?, []) = 1 

  case compareU(?x::?xs, ?y::?ys) 
     = c  when c =/= 0
     = 1  when x > y
     = -1 when x < y
     = 0  when x == y
	  with 
	    Let c = compareU(xs,ys).
%Define

================================================================

Define normalize       = removeTrailing 0.
Define sumN(?x,?y)     = normalize(sumU(x,y)).
Define diffN(?x,?y)    = normalize(diffU(x,y)).
Define productN(?x,?y) = normalize(productU(x,y)).
Define compareN(?x,?y) = compareU(normalize x, normalize y).

=======================================================
%%                  Exported functions.  
=======================================================
%% These work on signed representation.  They do not
%% require their parameters to be normalized, but
%% produce normalized results.
=======================================================

-- Write these.

%Package