;;==============================================================================
;; CMPS 112, Winter 07
;; Asg 5: Encoding Integers
;; Date: February 5, 2007
;;==============================================================================

#| Notes to the Grader:  We did not have enough time to correctly implement the
         Fibonacci function.  We tested the other functions and they are working
         perfectly.
|#

;; Booleans
;;------------------------------------------------------------------------------
; True
( define %true ( lambda ( x y ) x ))

; False
( define %false ( lambda ( x y ) y ))

; Not
( define %not ( lambda ( b ) ( b %false %true ))) 
( print "Not" )
( newline )
( test ( %not %true ) %false )
( test ( %not %false ) %true )
( newline )
;;------------------------------------------------------------------------------

; If
( define %if ( lambda ( b e1 e2 ) ( b e1 e2 )))

;; Pairs
;;------------------------------------------------------------------------------
( define %pair ( lambda ( x y ) ( lambda ( b ) ( b x y ))))
( define %left ( lambda ( p ) ( p %true )))
( define %right ( lambda ( p ) ( p %false )))
( print "Pairs" )
( newline )
( test ( %left ( %pair %true %false )) %true )
( test ( %left ( %pair %false %true )) %false )
( newline )
;;------------------------------------------------------------------------------

;; Natural Numbers
;; represent n as a function that takes f and z,
;; and applies f to z n times
;;------------------------------------------------------------------------------
( define %zero ( lambda ( f z ) z ))
( define %one ( lambda ( f z ) ( f z )))

;; %add1: N -> N + 1
;; Adds one to N.
( define %add1 ( lambda ( n ) ( lambda ( f z ) ( n f ( f z )))))
( define %two ( %add1 %one ))
( define %three ( %add1 %two ))

;; to-scheme-num: Natural Numbers -> Scheme Number
;; Changes Natural Numbers to Scheme Numbers
( define scheme-add1 ( lambda ( sn ) ( + sn 1 )))
( define ( to-scheme-num n ) ( n scheme-add1 0 ))
( print "to-scheme-num" )
( newline )
( test ( to-scheme-num %two ) 2 )
( newline )

; %sub1: N -> N - 1
; Subtracts 1 from N
(define %sub1 ( lambda ( n ) 
                ( %left ( n
                  ( lambda ( p )
                    ( %pair ( %right p )
                           ( %add1 ( %right p ))))
                  ( %pair %zero %zero )))))
( print "%Sub1" )
( newline )
(test (to-scheme-num (%sub1 %three)) 2)
(test (to-scheme-num (%sub1 %two)) 1)
(test (to-scheme-num (%sub1 %one)) 0)
( newline )

;; add: N N -> N
;; Takes two Natural numbers and add them together
( define add ( lambda ( n m ) ( lambda ( f  z ) ( n f ( m f z )))))
( print "Add" )
( newline )
( test ( to-scheme-num ( add %two %three )) 5 )
( newline )

;; sub: N N -> N
;; Subtract one N from the other and returns the difference
( define sub ( lambda ( n m ) ( m ( lambda ( k ) ( %sub1 k )) n )))
( print "Sub" )
( newline )
( test ( to-scheme-num ( sub %three %one )) 2 )
( test ( to-scheme-num ( sub %three %two )) 1 )
( newline )

;;------------------------------------------------------------------------------

;; Z = pair of ( sign, N)
;; where sign = boolean
;; An integer is a pair of sign and Natural Number.  Positive numbers have a
;; pair of %true boolean and N.  Negative would have a pair of %false boolean
;; and N.
;;------------------------------------------------------------------------------
( define Zzero ( %pair %true %zero ))
( define Zone ( %pair %true %one ))
( define Ztwo ( %pair %true %two ))
( define Zthree ( %pair %true %three ))

; Negative Num
( define Znegone ( %pair %false %one ))
( define Znegtwo ( %pair %false %two ))
( define Znegthree ( %pair %false %three ))

;; Zto-scheme-num: Z  -> Scheme Number
;; Changes Integer to Scheme Numbers
( define ( Zto-scheme-num n )
   ( %if (%left n)   
      (( %right n ) scheme-add1 0 )
   (* -1 (( %right n ) scheme-add1 0 ))))
( print "Zto-scheme-num" )
( newline )
( test ( Zto-scheme-num Znegthree ) -3)
( test ( Zto-scheme-num Zthree ) 3)
( newline )

;; Zabs: ( -Z or Z ) -> Z
;; Returns the absolute value of Z
( define ( Zabs n )
   ( %pair %true ( %right n )))
( print "abs" )
( newline )
( test ( Zto-scheme-num ( Zabs Zthree )) 3 )
( test ( Zto-scheme-num ( Zabs Znegthree )) 3 )
(newline)

;; zero?: Z -> Boolean
;; Checks if the Z is zero
(define Zzero? (lambda (n) ( ( %right n ) (lambda (ignore) %false) %true)))
( print "Zero?" )
( newline )
( test ( Zzero? Zone ) %false )
( test ( Zzero? Zzero ) %true )
( test ( Zzero? Znegone ) %false )
( newline ) 

;; Znegative?: Z -> Boolean
;; Checks if Z is negative
( define ( Znegative? n )
   ( %if ( %left n)
          %false 
          %true ))
( print "Znegative" )
( newline )
( test ( Znegative? ( %pair %true %one )) %false )
( test ( Znegative? Zone ) %false )
( test ( Znegative? ( %pair %false %one )) %true )
(newline)

;; signcheck: Z -> Boolean
;; Checks the sign of the integer.
( define ( signcheck n )
   ( %if ( %left n )
         %true
         %false))

;; Zadd1: Z -> Z + 1
;; Adds 1 to Z
( define ( Zadd1 n )
   ( %if ( %left n )         
         ( %pair %true ( %add1 ( %right n )))
         ( %if ( Zzero? ( %pair %true ( %sub1 ( %right n ))))
               (%pair %true ( %sub1 ( %right n )))
               (%pair %false ( %sub1 ( %right n ))))))
( print "Zadd1" )
( newline )
( test ( Zto-scheme-num ( Zadd1 Ztwo )) 3 )
( test ( Zto-scheme-num ( Zadd1 Znegthree )) -2 )
( test ( Zto-scheme-num ( Zadd1 Znegone )) 0 )
( test ( signcheck ( Zadd1 Znegone )) %true )
( test ( Zto-scheme-num ( Zadd1 Zzero )) 1 )
( newline )

;; Zsub1: Z -> Z - 1
;; Subtracts 1 from Z
( define ( Zsub1 n )
   ( %if ( Znegative? n )
         ( %pair ( %left n ) ( %add1 ( %right n )))
         ( %if ( Zzero? n )
               ( %pair %false ( %add1 ( %right n )))
               ( %pair %true ( %sub1 ( %right n ))))))
( print "Zsub1" )
( newline )
( test ( Zto-scheme-num ( Zsub1 Ztwo )) 1 )
( test ( Zto-scheme-num ( Zsub1 Znegthree )) -4 )
( test ( Zto-scheme-num ( Zsub1 Zzero )) -1 )
( newline )

;; Zinverter: Z -> Z(-1)
;; Inverts the sign of Z
( define Zinverter ( lambda ( n ) ( %pair ( %not ( %left n )) ( %right n ))))
( print "Zinverter" )
( newline )
( test ( Zto-scheme-num ( Zinverter Znegthree )) 3 )
( test ( Zto-scheme-num ( Zinverter Zthree )) -3 )
( test ( Zto-scheme-num ( Zinverter Zzero )) 0 )
( newline )


(define Ziadd (lambda (n m) ((%right n) Zadd1 m)))
(define Zisub (lambda (n m) ((%right m) Zsub1 n)))


;; Zadd: Z Z -> Z
;; Adds two integer and returns the sum
( define ( Zadd n m )
   ( %if ( %left n )
         ( %if ( %left m )
               ( %pair %true ( add ( %right n ) ( %right m ))) 
               ( Ziadd n m ))
         ( %if ( %left m )
               ( Zisub m n )
               ( %pair %false ( add ( %right n ) ( %right m ))))))

( print "Zadd" )
( newline )
( test ( Zto-scheme-num ( Zadd Zone Zthree )) 4)
( test ( Zto-scheme-num ( Zadd Zthree Znegthree )) 0)
( test ( Zto-scheme-num ( Zadd Znegone Zthree )) 2)
( test ( Zto-scheme-num ( Zadd Znegone Znegthree )) -4)
( newline ) 



;; Zsub: Z Z -> Z
;; Subtracts one integer from the other and returns the difference
#|
( define ( Zsub n m )
   ( %if ( %left n )
         ( %if ( %left m )
               ( %pair %true ( sub ( %right n ) ( %right m ))) 
               ( %pair %true ( add ( %right n ) ( %right m ))))
         ( %if ( %left m )
               ( %pair %false ( add ( %right m ) ( %right n )))  
               ( %pair %false ( add ( %right n ) ( %right m ))))))
|#
( define Zsub ( lambda ( n m ) (( %right m ) Zsub1 n)))
( print "Zsub" )
( newline )
( test ( Zto-scheme-num ( Zsub Zthree Zone )) 2)
( test ( Zto-scheme-num ( Zsub Zone Znegthree )) -2)
( test ( Zto-scheme-num ( Zsub Znegone Zone )) -2)
( test ( Zto-scheme-num ( Zsub Znegone Znegthree )) -4)
( newline )     

;; fib: Z -> Z
;; Gives returns 0 on negative numbers.  It otherwise
;; gives the representation of the number in the 
;; Fibonacci sequence
#|
(define mk-fib2
  (lambda (f)
    (lambda (n)
      (if (< n %two)
          %one
          (Zadd(f (Zsub1 n))
            (f (Zsub %two n)))))))




(define Y
  (lambda (x)
    ((lambda (p)
       (x (lambda (a) ((p p) a))))
     (lambda (p)
       (x (lambda (a) ((p p) a)))))))


(define mk-fib
  (lambda (f)
    (lambda (n)
      (if (< n 2)
          1
          (+ (f (- n 1))
            (f (- n 2)))))))

(define fib (Y mk-fib))

|#         
;;------------------------------------------------------------------------------