path: root/compiler.scm

(use-modules (ice-9 format)
             (ice-9 popen)
             (ice-9 rdelim)
             (srfi srfi-1))

;; Assuming a 64 bit intel machine here.
(define wordsize 8)
(define fixnum-mask 3)
(define fixnum-shift 2)
(define fixnum-tag 0)
(define char-mask 255)
(define char-shift 8)
(define char-tag 15)
(define boolean-mask 127)
(define boolean-shift 7)
(define boolean-tag 31)
(define empty-list 47) ;; #b00101111
;; 3 bit tags for heap allocated values.
(define pair-tag 1)
(define vector-tag 2)
(define string-tag 3)

(define (immediate-rep x)
  (cond
   ((integer? x)
    (ash x fixnum-shift))
   ((char? x)
    (logior (ash (char->integer x) char-shift) char-tag))
   ((boolean? x)
    (logior (ash (if x 1 0) boolean-shift) boolean-tag))
   ((null? x)
    empty-list)))

(define (immediate? x)
  (or (integer? x)
      (char? x)
      (boolean? x)
      (null? x)))

(define (variable? x)
  (symbol? x))

(define (if? x)
  (and (pair? x)
       (eq? (first x) 'if)))

(define (let? x)
  (and (pair? x)
       (eq? (first x) 'let)))

(define (primcall? x)
  (and (pair? x)
       (memq (first x)
             '(add1 sub1
               integer->char char->integer
               zero? null? integer? char? boolean?
               + - *
               = < <= > >=
               eq? char=?
               cons car cdr
               make-vector vector vector-length vector-ref vector-set!
               make-string string string-length string-ref string-set!))))

(define (labels? x)
  (and (pair? x)
       (eq? (first x) 'labels)))

(define (code? x)
  (and (pair? x)
       (eq? (first x) 'code)))

(define (labelcall? x)
  (and (pair? x)
       (eq? (first x) 'labelcall)))

(define (primcall-op x)
  (first x))

(define (primcall-operand1 x)
  (second x))

(define (primcall-operand2 x)
  (third x))

(define (primcall-operand3 x)
  (fourth x))

(define (lookup name env)
  (or (assq-ref env name)
      (error "unbound variable:" name)))

(define (extend-env name si-or-label env)
  (cons (cons name si-or-label) env))

(define (bindings x)
  (second x))

(define (body x)
  (third x))

(define (lhs b)
  (first b))

(define (rhs b)
  (second b))

(define (test x)
  (second x))

(define (consequent x)
  (third x))

(define (alternate x)
  (fourth x))

(define (lvar x)
  (second x))

(define (arguments x)
  (drop x 2))

(define unique-counter (make-parameter 0))

(define (unique-label)
  (let ((n (unique-counter)))
    (unique-counter (+ n 1))
    (format #f "L~a" n)))

(define (register name)
  (format #f "%~a" name))

(define (immediate value)
  (format #f "$~a" value))

(define rax (register "rax"))
(define rbx (register "rbx"))
(define rsp (register "rsp"))
(define rsi (register "rsi"))
(define al (register "al"))

(define (offset n register)
  (format #f "~a(~a)" n register))

(define (register-offset base-register index-register)
  (format #f "(~a, ~a)" base-register index-register))

(define (emit template-string . args)
  (display "        ")
  (apply format #t template-string args)
  (newline))

(define (emit-mov src dest)
  (emit "mov ~a, ~a" src dest))

(define (emit-movb src dest)
  (emit "movb ~a, ~a" src dest))

(define (emit-and mask dest)
  (emit "and ~a, ~a" mask dest))

(define (emit-andq mask dest)
  (emit "andq ~a, ~a" mask dest))

(define (emit-or addend dest)
  (emit "or ~a, ~a" addend dest))

(define (emit-add addend dest)
  (emit "add ~a, ~a" addend dest))

(define (emit-sub subtrahend dest)
  (emit "sub ~a, ~a" subtrahend dest))

(define (emit-imul multiplicand dest)
  (emit "imul ~a, ~a" multiplicand dest))

(define (emit-sal n dest)
  (emit "sal ~a, ~a" n dest))

(define (emit-shr n dest)
  (emit "shr ~a, ~a" n dest))

(define (emit-cmp a b)
  (emit "cmp ~a, ~a" a b))

(define (emit-setl dest)
  (emit "setl ~a" dest))

(define (emit-setle dest)
  (emit "setle ~a" dest))

(define (emit-setg dest)
  (emit "setg ~a" dest))

(define (emit-setge dest)
  (emit "setge ~a" dest))

(define (emit-sete dest)
  (emit "sete ~a" dest))

(define (emit-je label)
  (emit "je ~a" label))

(define (emit-jmp label)
  (emit "jmp ~a" label))

(define (emit-call label)
  (emit "call ~a" label))

(define (emit-ret)
  (emit "ret"))

(define (emit-label label)
  (format #t "~a:\n" label))

(define (emit-tag-check x mask tag si env)
  (emit-expr x si env)
  (emit-and (immediate mask) rax)
  (emit-cmp (immediate tag) rax)
  (emit-mov (immediate 0) rax)
  (emit-sete al)
  (emit-sal (immediate boolean-shift) rax)
  (emit-or (immediate boolean-tag) rax))

(define (emit-comparison x y instruction si env)
  (emit-expr y si env)
  (emit-mov rax (offset si rsp))
  (emit-expr x (- si wordsize) env)
  (emit-cmp (offset si rsp) rax)
  (emit-mov (immediate 0) rax)
  (instruction al)
  (emit-sal (immediate boolean-shift) rax)
  (emit-or (immediate boolean-tag) rax))

(define (emit-primitive-call x si env)
  (case (primcall-op x)
    ((add1)
     (emit-expr (primcall-operand1 x) si env)
     (emit-add (immediate (immediate-rep 1)) rax))
    ((sub1)
     (emit-expr (primcall-operand1 x) si env)
     (emit-sub (immediate (immediate-rep 1)) rax))
    ((integer->char)
     (emit-expr (primcall-operand1 x) si env)
     (emit-sal (immediate (- char-shift fixnum-shift)) rax)
     (emit-or (immediate char-tag) rax))
    ((char->integer)
     (emit-expr (primcall-operand1 x) si env)
     (emit-shr (immediate (- char-shift fixnum-shift)) rax))
    ((zero?)
     (emit-expr (primcall-operand1 x) si env)
     ;; Since the tag of fixnums is 0, we can skip an 'andl'
     ;; instruction that would apply the mask to the immediate
     ;; value.
     (emit-cmp (immediate 0) rax)
     (emit-mov (immediate 0) rax)
     (emit-sete al)
     (emit-sal (immediate boolean-shift) rax)
     (emit-or (immediate boolean-tag) rax))
    ((null?)
     (emit-expr (primcall-operand1 x) si env)
     (emit-cmp (immediate empty-list) rax)
     (emit-mov (immediate 0) rax)
     (emit-sete al)
     (emit-sal (immediate boolean-shift) rax)
     (emit-or (immediate boolean-tag) rax))
    ((integer?)
     (emit-tag-check (primcall-operand1 x) fixnum-mask fixnum-tag si env))
    ((char?)
     (emit-tag-check (primcall-operand1 x) char-mask char-tag si env))
    ((boolean?)
     (emit-tag-check (primcall-operand1 x) boolean-mask boolean-tag si env))
    ((+)
     (emit-expr (primcall-operand2 x) si env)
     (emit-mov rax (offset si rsp))
     (emit-expr (primcall-operand1 x) (- si wordsize) env)
     (emit-add (offset si rsp) rax))
    ((-)
     (emit-expr (primcall-operand2 x) si env)
     (emit-mov rax (offset si rsp))
     (emit-expr (primcall-operand1 x) (- si wordsize) env)
     (emit-sub (offset si rsp) rax))
    ((*)
     (emit-expr (primcall-operand2 x) si env)
     (emit-mov rax (offset si rsp))
     (emit-expr (primcall-operand1 x) (- si wordsize) env)
     (emit-imul (offset si rsp) rax)
     ;; When two fixnums (which have 2 tag bits) are multiplied, the
     ;; relevant bits for the result are now 4 bytes to the left, so
     ;; we have to shift back 2 bytes.
     (emit-shr (immediate fixnum-shift) rax))
    ((=)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-sete si env))
    ((<)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-setl si env))
    ((<=)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-setle si env))
    ((>)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-setg si env))
    ((>=)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-setge si env))
    ((eq?)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-sete si env))
    ((char=?)
     (emit-comparison (primcall-operand1 x) (primcall-operand2 x) emit-sete si env))
    ((cons)
     (emit-expr (primcall-operand2 x) si env) ; eval cdr
     (emit-mov rax (offset si rsp)) ; save car to stack
     (emit-expr (primcall-operand1 x) (- si wordsize) env) ; eval car
     (emit-mov rax (offset 0 rsi)) ; move car onto heap
     (emit-mov (offset si rsp) rax) ; copy cdr from the stack
     (emit-mov rax (offset wordsize rsi)) ; move cdr onto heap
     (emit-mov rsi rax) ; heap pointer is the value returned
     (emit-or (immediate pair-tag) rax) ; set tag
     (emit-add (immediate (* wordsize 2)) rsi)) ; bump heap pointer
    ((car)
     (emit-expr (primcall-operand1 x) si env)
     ;; We have to untag the pair to get the pointer to the 'car'.
     ;; The pair tag is 1 so simply subtracting 1 gets us the pointer.
     (emit-mov (offset -1 rax) rax))
    ((cdr)
     (emit-expr (primcall-operand1 x) si env)
     ;; Again, the value is the pointer incremented by 1, so to get to
     ;; the cdr we need to jump ahead one word minus 1 byte.
     (emit-mov (offset (- wordsize 1) rax) rax))
    ((make-vector)
     (emit-expr (primcall-operand1 x) si env)
     ;; Wouldn't it be better to save the length untagged so that
     ;; vector-ref and vector-set! don't have untag it and
     ;; vector-length just needs to retag it?
     (emit-mov rax (offset 0 rsi)) ; save length onto heap
     (emit-mov rax rbx) ; save length in another register
     (emit-mov rsi rax) ; copy heap pointer
     (emit-or (immediate vector-tag) rax) ; set tag
     ;; Align to next two-word object boundary.  I had to add an
     ;; additional shift instruction compared to what the paper did to
     ;; accommodate the difference in word size (the paper uses 4 byte
     ;; words, I'm using 8 byte words) which makes me wonder: For a 64
     ;; bit compiler, should the fixnum tag be 3 bits instead of 2?
     (emit-sal (immediate 1) rbx)
     (emit-add (immediate (* 2 wordsize)) rbx)
     (emit-and (immediate (- (* 2 wordsize))) rbx)
     (emit-add rbx rsi)) ; bump heap pointer by length of vector
    ((vector)
     (let ((items (cdr x)))
       ;; Eval all vector items and save them to stack locations.
       ;; It's important that we eval all items first, and not copy to
       ;; the heap as we go, because any sub-expression that also does
       ;; heap allocation will corrupt the heap space we think we have
       ;; all to ourselves here.
       (let loop ((items items)
                  (si si))
         (unless (null? items)
           (emit-expr (car items) si env) ; eval item
           (emit-mov rax (offset si rsp)) ; save to stack
           (loop (cdr items) (- si wordsize))))
       ;; Save length onto heap (tagged as immediate int)
       (emit-mov (immediate (ash (length items) 2)) rax)
       (emit-mov rax (offset 0 rsi))
       ;; Copy items from the stack to the vector.
       (let loop ((items items)
                  (si si)
                  (heap-offset wordsize))
         (unless (null? items)
           (emit-mov (offset si rsp) rax) ; copy from stack
           (emit-mov rax (offset heap-offset rsi)) ; save to heap
           (loop (cdr items) (- si wordsize) (+ heap-offset wordsize))))
       (emit-mov rsi rax) ; copy heap pointer
       (emit-or (immediate vector-tag) rax) ; set tag
       ;; Align heap pointer to next available 2 word boundary.
       (emit-add (immediate (logand (* (+ (length items) 2) wordsize)
                                    (- (* 2 wordsize))))
                 rsi)))
    ((vector-length)
     (emit-expr (primcall-operand1 x) si env) ; get vector pointer
     (emit-sub (immediate vector-tag) rax) ; untag vector
     (emit-mov (offset 0 rax) rax)) ; the first word contains the length
    ((vector-ref)
     (emit-expr (primcall-operand2 x) si env) ; get index arg
     (emit-shr (immediate fixnum-shift) rax) ; untag it
     (emit-add (immediate 1) rax) ; first word is the length so skip over it
     (emit-imul (immediate wordsize) rax) ; scale by word size
     (emit-mov rax rbx) ; save index to another register
     (emit-expr (primcall-operand1 x) si env) ; get vector pointer
     (emit-sub (immediate vector-tag) rax) ; untag vector
     (emit-mov (register-offset rbx rax) rax)) ; get element
    ((vector-set!)
     (emit-expr (primcall-operand1 x) si env) ; get vector pointer
     (emit-sub (immediate vector-tag) rax) ; untag vector
     (emit-mov rax rbx) ; save vector
     (emit-expr (primcall-operand2 x) si env) ; get index
     (emit-shr (immediate fixnum-shift) rax) ; untag it
     (emit-add (immediate 1) rax) ; first word is the length so skip over it
     (emit-imul (immediate wordsize) rax) ; scale by word size
     (emit-add rax rbx) ; advance pointer to element being set
     (emit-expr (primcall-operand3 x) si env) ; get value
     (emit-mov rax (offset 0 rbx)))
    ((make-string)
     (emit-expr (primcall-operand1 x) si env)
     (emit-mov rax (offset 0 rsi)) ; save length onto heap
     (emit-mov rax rbx) ; save length in another register
     (emit-mov rsi rax) ; write to heap
     (emit-or (immediate string-tag) rax) ; set tag
     (emit-shr (immediate fixnum-shift) rbx) ; untag length
     ;; Align to next two-word object boundary, keeping in mind that
     ;; we need one additional word to store the length.  Since we're
     ;; only storing ASCII characters in this simple compiler, we only
     ;; need 1 byte per character.
     (emit-add (immediate (- (* 3 wordsize) 1)) rbx)
     (emit-and (immediate (- (* 2 wordsize))) rbx)
     (emit-add rbx rsi)) ; bump heap pointer by length of string
    ((string)
     (let ((chars (cdr x)))
       ;; Save length onto heap (tagged as immediate int)
       (emit-mov (immediate (ash (length chars) 2)) rax)
       (emit-mov rax (offset 0 rsi))
       ;; Add chars to string, one byte per item since we're only
       ;; covering the ASCII character set.
       (let loop ((chars chars)
                  (heap-offset 1))
         (unless (null? chars)
           (emit-expr (first chars) si env) ; eval arg (should be char)
           (emit-shr (immediate char-shift) rax) ; untag char
           (emit-andq (immediate -255) (offset heap-offset rsi)) ; clear LSB
           (emit-or rax (offset heap-offset rsi)) ; set char
           (loop (cdr chars) (+ heap-offset 1))))
       (emit-mov rsi rax) ; copy heap pointer
       (emit-or (immediate string-tag) rax) ; set tag
       ;; Align heap pointer to next available 2 word boundary.
       (emit-add (immediate (logand (+ (length chars) (- (* 3 wordsize) 1))
                                    (- (* 2 wordsize))))
                 rsi)))
    ((string-length)
     (emit-expr (primcall-operand1 x) si env) ; get string pointer
     (emit-sub (immediate string-tag) rax) ; untag string
     (emit-mov (offset 0 rax) rax)) ; the first word contains the length
    ((string-ref)
     (emit-expr (primcall-operand2 x) si env) ; get index arg
     (emit-shr (immediate fixnum-shift) rax) ; untag it
     ;; The first word of a string contains the length, however we
     ;; don't want to advance the pointer by a word because each
     ;; character is only a single byte.  Instead, we advance the
     ;; pointer by a single byte so that the character we want to
     ;; access is in the least significant bit (LSB) section of the
     ;; word.  From there, its a simple matter of masking out
     ;; everything but the LSB to isolate the character.
     (emit-add (immediate 1) rax)
     (emit-mov rax rbx) ; save index to another register
     (emit-expr (primcall-operand1 x) si env) ; get string pointer
     (emit-sub (immediate string-tag) rax) ; untag string
     (emit-mov (register-offset rbx rax) rax) ; get char into LSB position
     (emit-and (immediate 255) rax) ; clear out everything but the LSB
     (emit-sal (immediate char-shift) rax) ; tag char
     (emit-or (immediate char-tag) rax))
    ((string-set!)
     (emit-expr (primcall-operand1 x) si env) ; get string pointer
     (emit-sub (immediate string-tag) rax) ; untag string
     (emit-mov rax rbx) ; save string pointer
     (emit-expr (primcall-operand2 x) si env) ; get index arg
     (emit-shr (immediate fixnum-shift) rax) ; untag it
     (emit-add (immediate 1) rax)
     (emit-add rax rbx) ; get char into LSB position
     (emit-expr (primcall-operand3 x) si env) ; get value
     (emit-shr (immediate char-shift) rax) ; untag char
     (emit-andq (immediate -255) (offset 0 rbx)) ; clear LSB
     (emit-or rax (offset 0 rbx))) ; copy char
    (else
     (error "unknown primcall op" (primcall-op x)))))

(define (emit-let bindings body si env)
  (let loop ((b* bindings) (new-env env) (si si))
    (if (null? b*)
        (emit-expr body si new-env)
        (let ((b (first b*)))
          (emit-expr (rhs b) si env)
          (emit-mov rax (offset si rsp))
          (loop (cdr b*)
                (extend-env (lhs b) si new-env)
                (- si wordsize))))))

(define (emit-if test conseq altern si env)
  (let ((L0 (unique-label))
        (L1 (unique-label)))
    (emit-expr test si env)
    (emit-cmp (immediate (immediate-rep #f)) rax)
    (emit-je L0)
    (emit-expr conseq si env)
    (emit-jmp L1)
    (emit-label L0)
    (emit-expr altern si env)
    (emit-label L1)))

(define (emit-code label vars body env)
  (emit-label label)
  (let loop ((vars vars)
             (env env)
             (si (- wordsize)))
    (if (null? vars)
        (begin
          (emit-expr body si env)
          (emit-ret))
        (loop (cdr vars)
              (extend-env (first vars) si env)
              (- si wordsize)))))

(define (emit-labels lvars body-exp si env)
  (let* ((lvars* (map (lambda (lvar)
                        (cons (unique-label) lvar))
                      lvars))
         (env* (fold (lambda (lvar env)
                       (let ((label (first lvar))
                             (name (second lvar)))
                         (extend-env name label env)))
                     env lvars*)))
    (for-each (lambda (lvar)
                (let ((label (first lvar))
                      (code (third lvar)))
                  (if (code? code)
                      (emit-code label (bindings code) (body code) env*)
                      (error "expected a code expression" code))))
              lvars*)
    (emit-label "scheme_entry")
    (emit-expr body-exp si env*)
    (emit-ret)))

(define (emit-labelcall lvar args si env)
  (let ((label (lookup lvar env)))
    (let loop ((args args)
               (si* (- si wordsize)))
      (if (null? args)
          ;; The stack pointer needs to be advanced to one word below
          ;; the return point of the upcoming call.  Our stack index
          ;; value starts at (- wordsize).  The 'call' instruction
          ;; automatically increments the stack pointer by a word.
          ;; So, if we incremented by the stack index, we'd be moving
          ;; too far.  We need to advance by one less word.  In the
          ;; case where nothing has been allocated to the stack before
          ;; the call, it means not incrementing the stack pointer at
          ;; all!  Took me awhile to wrap my head around this!
          (let ((stack-start (+ si wordsize)))
            (unless (zero? stack-start)
              (emit-add (immediate stack-start) rsp))
            (emit-call label)
            (unless (zero? stack-start)
              (emit-sub (immediate stack-start) rsp)))
          (begin
            (emit-expr (first args) si* env)
            (emit-mov rax (offset si* rsp))
            (loop (cdr args)
                  (- si* wordsize)))))))

(define (emit-expr x si env)
  (cond
   ((immediate? x)
    (emit-mov (immediate (immediate-rep x)) rax))
   ((variable? x)
    (emit-mov (offset (lookup x env) rsp) rax))
   ((if? x)
    (emit-if (test x) (consequent x) (alternate x) si env))
   ((let? x)
    (emit-let (bindings x) (body x) si env))
   ((primcall? x)
    (emit-primitive-call x si env))
   ((labels? x)
    (emit-labels (bindings x) (body x) si env))
   ((labelcall? x)
    (emit-labelcall (lvar x) (arguments x) si env))
   (else
    (error "unknown expression" x))))

(define (compile-program x)
  (parameterize ((unique-counter 0))
    (let ((x* (if (labels? x)
                  x
                  `(labels () ,x))))
      (emit-expr x* (- wordsize) '()))))

(define (compile-and-run x)
  (with-output-to-file "scheme_entry.s"
    (lambda ()
      (display ".text
.p2align 4
.globl	scheme_entry
.type	scheme_entry, @function
")
      (compile-program x)))
  (unless (zero? (system* "gcc" "-c" "scheme_entry.s"))
    (error "failed to compile scheme_entry.s"))
  (unless (zero? (system* "gcc" "-c" "test.c"))
    (error "failed to compile test.c"))
  (unless (zero? (system* "gcc" "-o" "test" "scheme_entry.o" "test.o"))
    (error "failed to link program"))
  (let* ((pipe (open-pipe* OPEN_READ "./test"))
         (output (read-line pipe)))
    (close pipe)
    output))

(define (test-case x expected-output)
  (let ((result (compile-and-run x)))
    (if (and (not (eof-object? result))
             (string=? result expected-output))
        #t
        (begin
          (display "expected: ")
          (display expected-output)
          (display ", got: ")
          (display result)
          (newline)
          #f))))

(begin
  (test-case 1 "1")
  (test-case #\b "b")
  (test-case #t "#t")
  (test-case #f "#f")
  (test-case '(add1 3) "4")
  (test-case '(sub1 3) "2")
  (test-case '(integer->char 98) "b")
  (test-case '(char->integer #\b) "98")
  (test-case '(zero? 1) "#f")
  (test-case '(zero? 0) "#t")
  (test-case '(null? 1) "#f")
  (test-case '(null? #\b) "#f")
  (test-case '(null? #t) "#f")
  (test-case '(null? #f) "#f")
  (test-case '(null? ()) "#t")
  (test-case '(integer? #\b) "#f")
  (test-case '(integer? #f) "#f")
  (test-case '(integer? 1) "#t")
  (test-case '(char? 1) "#f")
  (test-case '(char? #f) "#f")
  (test-case '(char? #\b) "#t")
  (test-case '(boolean? 1) "#f")
  (test-case '(boolean? #\b) "#f")
  (test-case '(boolean? #f) "#t")
  (test-case '(boolean? #t) "#t")
  (test-case '(+ 1 2) "3")
  (test-case '(- 3 1) "2")
  (test-case '(* 2 3) "6")
  (test-case '(= 1 2) "#f")
  (test-case '(= 1 1) "#t")
  (test-case '(< 2 1) "#f")
  (test-case '(< 1 2) "#t")
  (test-case '(<= 2 1) "#f")
  (test-case '(<= 1 2) "#t")
  (test-case '(<= 2 2) "#t")
  (test-case '(> 1 2) "#f")
  (test-case '(> 2 1) "#t")
  (test-case '(>= 1 2) "#f")
  (test-case '(>= 2 1) "#t")
  (test-case '(>= 2 2) "#t")
  (test-case '(char=? #\a #\b) "#f")
  (test-case '(char=? #\b #\b) "#t")
  (test-case '(let ((x 1)) x) "1")
  (test-case '(let ((x 1) (y 2)) (+ x y)) "3")
  (test-case '(if #t 1 2) "1")
  (test-case '(if #f 1 2) "2")
  (test-case '(car (cons 10 20)) "10")
  (test-case '(cdr (cons 10 20)) "20")
  (test-case '(car (cdr (cons 1 (cons 2 '())))) "2")
  (test-case '(vector-length (make-vector 3)) "3")
  (test-case '(vector-ref (vector 1 2 3) 1) "2")
  (test-case '(string-length (make-string 5)) "5")
  (test-case '(string-ref (string #\a #\b #\c) 1) "b")
  (test-case '(labels ((perimeter (code (length width)
                                        (+ (* length 2)
                                           (* width 2)))))
                      (labelcall perimeter 4 3))
             "14"))