Scheme - Full adder output format

Question

So I have pretty much completed my entire assignment now but there is 1 question that is confusing me(even though I feel like the answer is really easy).

Question 3.5:

Write a procedure to convert your result into the required output format.

The expect outputs and format are as follows:

((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)

Where, the first element is the carry-out of the addition. If the carry-out is (1), it represents an overflow in the adder. The remaining elements of the list are the sum.

Now the output I am getting is this:

(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)

Does anyone know how I can properly get this formatted? I have been thinking and not sure what to do.

Edit-

This is the code that produces the output:

(define binaryadd (lambda(L1 L2)
    (let ((len1 (length L1)) (len2 (length L2)))
        (if (> len1 len2)
            (binaryadd L2 L1)
            (if  (< len1 len2)
                (binaryadd (append '(0) L1) L2)
                (recursiveAdd (append '(0) L1) (append '(0) L2) 0)
))  )   ))

(define recursiveAdd (lambda(L1 L2 carry)
    (if (null?  L1)  
        '()
        (let    ((t  (+ (tail L1) (tail L2) carry)))
            (append (recursiveAdd (rmtail L1)
                                         (rmtail L2) 
                                         (quotient t 2))
                        (list (remainder t 2))
))  )   )   )

(define n-bit-adder (lambda(A B n)
                      (binaryAdd A B)
                      ))
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1   0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0   1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1   0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1   1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )
(n-bit-adder X1 X2 32)
(n-bit-adder  X3 X4 32)
(n-bit-adder  X5 X6 32)
(n-bit-adder  X2 X3 32)
(n-bit-adder  X4 X5 32)
(n-bit-adder  X1 X6 32)

Answer 1

In case you still need a full adder along with the rest of it, which will produce your required output. You needed a method to reverse the list. Check the last procedure reverseList in the code below.

Be careful if using the code for HW.

(define and-gate
  (lambda (a b)
    (if (= a b 1)
        1
        0)))

(and-gate 0 0)
(and-gate 0 1)
(and-gate 1 0)
(and-gate 1 1)

(newline)

(define (or-gate a b)
  (if (not (= 0 (+ a b)))
      1
      0))

(or-gate 0 0)
(or-gate 0 1)
(or-gate 1 0)
(or-gate 1 1)

(newline)

(define xor-gate
  (lambda (a b)
    (if (= a b)
        0
        1)))

(xor-gate 0 0)
(xor-gate 0 1)
(xor-gate 1 0)
(xor-gate 1 1)

(newline)

(define (bitAdder x a b)
  (cons (sum-bit x a b)    
    (carry-out x a b)))

(define (sum-bit x a b)
  (xor-gate x (xor-gate a b)))

(define (carry-out x a b)
  (or-gate (and-gate a b)
           (or-gate (and-gate x a)
                    (and-gate x b))))

(bitAdder 0 0 0)
(bitAdder 0 0 1)
(bitAdder 0 1 0)
(bitAdder 0 1 1)
(bitAdder 1 0 0)
(bitAdder 1 0 1)
(bitAdder 1 1 0)
(bitAdder 1 1 1)

(newline)

(define (tail lst)
  (if (null? (cdr lst))
      (car lst)
      (tail (cdr lst))))

(define (rmtail lst)
  (if (null? (cdr lst))      
      '()
      (cons (car lst)
            (rmtail (cdr lst)))))

(define (recursiveAdd a b c)
  (if (null? a)      
      (list (list c))     
      (cons (car (bitAdder (tail a) (tail b) c))            
            (recursiveAdd (rmtail a) (rmtail b) (cdr (bitAdder (tail a) (tail b) c))))))

(define (n-bit-adder a b n)
  (reverseList (recursiveAdd a b 0)))

(define (reverseList lst)
  (if (null? lst)
      '()
      (append (reverseList (cdr lst)) (list (car lst)))))

;; Test cases
(define X1 '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) )
(define X2 '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) )
(define X3 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) )
(define X4 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0) )
(define X5 '(0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1) )
(define X6 '(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1) )

(n-bit-adder X1 X2 32)
(n-bit-adder X3 X4 32)
(n-bit-adder X5 X6 32)
(n-bit-adder X2 X3 32)
(n-bit-adder X4 X5 32)
(n-bit-adder X1 X6 32)

Output: (which should match your expected output)

((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((0) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
((1) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0)
((1) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
((0) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1)

Answer 2

Let's make a full adder:

#lang racket

(define (adder-output S Cout)
    (hash 'S S
          'Cout Cout))   

;; bit bit bit -> bit bit
;; A B Cin -> S Cout
(define (full-adder inputs)
  (match (hash-values inputs)
    ['(0 0 0) (adder-output 0 0)]
    ['(1 0 0) (adder-output 1 0)]
    ['(0 1 0) (adder-output 1 0)]
    ['(0 0 1) (adder-output 1 0)]
    ['(1 1 0) (adder-output 0 1)]
    ['(1 0 1) (adder-output 0 1)]
    ['(0 1 1) (adder-output 0 1)]
    ['(1 1 1) (adder-output 1 1)]
    [ _ (error "binary-adder: bad input")]))

And maybe write some tests for it:

(module+ test
  (require rackunit
       rackunit/text-ui)

  (define bit-values '(0 1))

  (define inputs
    (map
     (lambda (x)
       (hash 'A (first x)
             'B (second x)
             'Cin (third x)))
     (for*/list ([A bit-values]
                 [B bit-values]
                 [Cin bit-values])
       (list A B Cin))))

  (define outputs
    (map (lambda (x)
           (hash 'S (first x)
                 'Cout (second x)))
     '((0 0)
       (1 0)
       (1 0)
       (0 1)
       (1 0)
       (0 1)
       (0 1)
       (1 1))))

  (define (unit-test in out)
    (check-equal? (full-adder in)
                   out))

  (define (test-harness ins outs)
    (if (or (null? ins)
            (null? outs))
    'test-complete
    (begin
      (unit-test (first ins)
                 (first outs))
      (test-harness (rest ins)
                    (rest outs)))))

  (define-test-suite
    full-adder-tests
    (test-harness inputs outputs))

  (run-tests full-adder-tests))

Now that all works we'll just string the full-adder into a ripple-carry-adder with a recursive interior definition utilizing a trampoline and turning the big-bit-endinian value into little-bit-endian values so it's easier to cons up the output.

(define (ripple-adder value1 value2)

  (define v1 (reverse value1))
  (define v2 (reverse value2))

  (define (add v1 v2 previous-result output)

    (define carry-bit (hash-ref previous-result 'Cout))
    (define out-bit (hash-ref previous-result 'S))

    (if (or (null? v1)
            (null? v2))
      (cons (list carry-bit) (cons out-bit output))
      (let
        ([next-add-input
          (hash 'A (first v1)
                'B (first v2)
                'Cin carry-bit)])

      (add (rest v1)
           (rest v2)
           (full-adder next-add-input)
           (cons out-bit output)))))

  (add (rest v1)
       (rest v2)
       (full-adder (hash 'A (first v1)
                         'B (first v2)
                         'Cin 0 ))
       null))

Then if these tests work:

(module+ test
  (define-test-suite
    ripple-adder-tests

   (test-equal?
     "two bit 0 + 0"
     (ripple-adder '(0 0) '(0 0))
     '((0) 0 0))

   (test-equal?
     "three bit 0 + 0"
     (ripple-adder '(0 0 0) '(0 0 0))
     '((0) 0 0 0))

   (test-equal?
     "three bit 1 + 0"
     (ripple-adder '(0 0 1) '(0 0 0))
     '((0) 0 0 1))

   (test-equal?
     "two bit 1 + 1"
     (ripple-adder '(0 1) '(0 1))
     '((0) 1 0))

   (test-equal?
     "two bit 2 + 2"
     (ripple-adder '(1 0) '(1 0))
     '((1) 0 0)))

    (test-equal?
     "three bit 2 + 2"
     (ripple-adder '(0 1 0) '(0 1 0))
     '((0) 1 0 0))

(run-tests ripple-adder-tests))

We can probably risk turning this in as homework. Subject of course to academic honesty requirements.