n+

Conformance: SketchyLISP Core

Purpose: Add two natural numbers.

Arguments:
A - natural number
B - natural number

Model:

(define (n+ a b)
  (letrec
    ; Compute the sum of two digits and a carry flag.
    ; X Y - digits
    ; CI CO - carry in, out
    ; RESULT - (sum . carry out)
    ((d+
       (lambda (x y ci co)
         (cond ((eq? x 0d)
             (cond ((eq? ci 1d)
                 ; add carry flag
                 (d+ 1d y 0d co))
               (else (cons y co))))
           ; handle overflow
           ((null? (succ y))
             (d+ (pred x) 0d ci 1d))
           (else (d+ (pred x) (succ y) ci co)))))
     ; Add lists of digit
     ; A,B - lists
     ; C - carry
     ; R - result
     (add
       (lambda (a b c r)
         (cond ((null? a)
             (cond
               ; A=() ; B=()
               ((null? b)
                 (cond
                   ; carry not set? return R
                   ((eq? c 0d) r)  
                   ; else prepend overflow
                   (else (cons 1d r))))
               ; B\=(): keep adding leading zeroes
               (else (add '() (cdr b)
                          (cdr (d+ 0d (car b) c 0d))
                          (cons (car (d+ 0d (car b) c 0d))
                                r)))))
           ((null? b)
             ; B=() ; A\=()
             (add (cdr a) '()
                  (cdr (d+ (car a) 0d c 0d))
                  (cons (car (d+ (car a) 0d c 0d))
                      r)))
           ; default: advance to next two digits
           (else (add (cdr a) (cdr b)
                      (cdr (d+ (car a) (car b) c 0d))
                      (cons (car (d+ (car a) (car b) c 0d))
                            r)))))))
    (list->integer
      (add (reverse (integer->list a))
           (reverse (integer->list b))
           0d '())
      #t)))

Implementation:

; This function is a primitive function.

Example:

(n+ 5 7) 
=> 12

See also:
digits, n-, nquotient, nremainder, n*, +.