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


;;;
;;; Syntax predicates and accessors
;;;

(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 (op-eq? lst op)
  (and (pair? lst)
       (eq? (first lst) op)))

(define (if? x)
  (op-eq? x 'if))

(define (let? x)
  (op-eq? 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!
               constant-init constant-ref))))

(define (labels? x)
  (op-eq? x 'labels))

(define (code? x)
  (op-eq? x 'code))

(define (datum? x)
  (op-eq? x 'datum))

(define (closure? x)
  (op-eq? x 'closure))

(define (funcall? x)
  (op-eq? x 'funcall))

(define (tail-call? x)
  (op-eq? x 'tail-call))

(define (lambda? x)
  (op-eq? x 'lambda))

(define (quote? x)
  (op-eq? x 'quote))

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

(define (primcall-operands x)
  (cdr 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 env)))

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

(define (let-bindings x)
  (second x))

(define (let-body x)
  (cddr x))

(define (label-bindings x)
  (second x))

(define (label-body x)
  (cddr 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 (closure-lvar x)
  (second x))

(define (closure-vars x)
  (cddr x))

(define (lambda-args x)
  (second x))

(define (lambda-body x)
  (third x))

(define (funcall-proc x)
  (second x))

(define (funcall-arguments x)
  (drop x 2))

(define (tail-call-proc x)
  (second x))

(define (tail-call-arguments x)
  (drop x 2))

(define (code-vars x)
  (second x))

(define (code-free-vars x)
  (third x))

(define (code-body x)
  (fourth x))

(define (quote-data x)
  (second x))

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

(define (unique-number)
  (let ((n (unique-counter)))
    (unique-counter (+ n 1))
    n))

(define (unique-lvar)
  (string->symbol
   (format #f "f~a" (unique-number))))

(define (unique-variable)
  (string->symbol
   (format #f "t~a" (unique-number))))


;;;
;;; Native code compilation
;;;

;; 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 closure-tag 6)

(define (unique-label)
  (format #f "L~a" (unique-number)))

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

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

(define rax (register "rax")) ; default register for storing values
(define rbx (register "rbx")) ; extra storage
(define rdi (register "rdi")) ; closure pointers
(define rsp (register "rsp")) ; heap
(define rsi (register "rsi")) ; stack
(define rip (register "rip")) ; instruction pointer
(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-lea src dest)
  (emit "lea ~a, ~a" src dest))

(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
    ((constant-init)
     (let ((label (lookup (primcall-operand1 x) env)))
       (emit-expr (primcall-operand2 x) si env)
       (emit-lea (offset label rip) rbx)
       (emit-mov rax (offset 0 rbx))))
    ((constant-ref)
     (let ((label (lookup (primcall-operand1 x) env)))
       (emit-lea (offset label rip) rax)
       (emit-mov (offset 0 rax) rax)))
    (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*)
        (for-each (lambda (x)
                    (emit-expr x si new-env))
                  body)
        (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-datum label)
  (display ".data\n")
  (emit-label label))

(define (emit-code label vars free-vars body env)
  (display ".text\n")
  (emit-label label)
  ;; Extend environment to include all procedure variables
  (let loop ((vars vars)
             (si (- wordsize))
             (env env))
    (if (null? vars)
        ;; Extend environment to include all free variables and
        ;; emit code to initialize their value from the current
        ;; closure pointer.
        (let free-loop ((free-vars free-vars)
                        (ci wordsize)
                        (si si)
                        (env env))
          (if (null? free-vars)
              ;; All variable setup is complete, we can finally
              ;; emit the body of the procedure.
              (begin
                (emit-expr body si env)
                (emit-ret))
              (begin
                (emit-mov (offset ci rdi) rax) ; get value from closure
                (emit-mov rax (offset si rsp)) ; push it to stack
                (free-loop (cdr free-vars)
                           (+ ci wordsize)
                           (- si wordsize)
                           (extend-env (first free-vars) si env)))))
        (loop (cdr vars)
              (- si wordsize)
              (extend-env (first vars) si env)))))

(define (emit-funcall proc args si env)
  (emit-mov rdi (offset si rsp)) ; save current closure pointer
  (let loop ((args args)
             ;; Skip a stack space to use as the return point.
             (si* (- si (* wordsize 2))))
    (if (null? args)
        (let ((stack-start si))
          (emit-expr proc si env) ; eval closure
          (emit-sub (immediate closure-tag) rax) ; untag it to get pointer
          (emit-mov rax rdi) ; store pointer in destination register
          (unless (zero? stack-start)
            (emit-add (immediate stack-start) rsp)) ; move stack pointer
          (emit-call (string-append "*" (offset 0 rdi)))
          (unless (zero? stack-start)
            (emit-sub (immediate stack-start) rsp)) ; restore stack pointer
          (emit-mov (offset (- si wordsize) rsp) rdi)) ; restore closure pointer
        (begin ; eval argument
          (emit-expr (first args) si* env)
          (emit-mov rax (offset si* rsp))
          (loop (cdr args)
                (- si* wordsize))))))

(define (emit-tail-call proc args si env)
  (let loop ((args* args)
             (si* si))
    (if (null? args*)
        (let ((stack-start si))
          (emit-expr proc si env) ; eval closure
          (emit-sub (immediate closure-tag) rax) ; untag it to get pointer
          (emit-mov rax rdi) ; store pointer in destination register
          ;; Copy all of the args from their current stack locations
          ;; at the top of the stack to the bottom of the stack.
          ;; Function calls are expecting to find the values of their
          ;; arguments starting from the bottom of the stack, so we
          ;; need to set things up as if we incremented the stack
          ;; pointer and made a 'call', but really we are doing a
          ;; 'jmp'.  I feel like we're playing a trick on the
          ;; function.  A very neat trick. :)
          (let copy-loop ((args* args)
                          (si* si))
            (unless (null? args*)
              (emit-mov (offset si* rsp) rax) ; copy from top of stack...
              (emit-mov rax (offset (- si* si wordsize) rsp)) ; ...to the bottom
              (copy-loop (cdr args*) (- si* wordsize))))
          (emit-jmp (string-append "*" (offset 0 rdi)))
          (emit-mov (offset (- si wordsize) rsp) rdi)) ; restore closure pointer
        (begin ; eval argument
          (emit-expr (first args*) si* env)
          (emit-mov rax (offset si* rsp))
          (loop (cdr args*)
                (- si* wordsize))))))

(define (emit-closure lvar vars si env)
  (let ((label (lookup lvar env)))
    (emit-lea (offset label rip) rax) ; first word of closure points to label
    (emit-mov rax (offset 0 rsi)) ; first element of closure is label pointer
    (let loop ((vars vars)
               (i wordsize))
      (if (null? vars)
          (begin
            (emit-mov rsi rax) ; capture heap pointer
            (emit-or (immediate closure-tag) rax) ; set tag
            ;; Align heap pointer to nearest 2 word boundary for next
            ;; heap allocation.
            (emit-add (immediate (logand (+ i wordsize)
                                         (- (* 2 wordsize))))
                      rsi))
          (let ((var-offset (lookup (first vars) env)))
            (emit-mov (offset var-offset rsp) rax) ; copy value of free variable
            (emit-mov rax (offset i rsi))  ; save it to closure
            (loop (cdr vars)
                  (+ i 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 (let-bindings x) (let-body x) si env))
   ((primcall? x)
    (emit-primitive-call x si env))
   ((labels? x)
    (emit-labels (label-bindings x) (label-body x) si env))
   ((closure? x)
    (emit-closure (closure-lvar x) (closure-vars x) si env))
   ((funcall? x)
    (emit-funcall (funcall-proc x) (funcall-arguments x) si env))
   ((tail-call? x)
    (emit-tail-call (tail-call-proc x) (tail-call-arguments x) si env))
   (else
    (error "unknown expression" x))))

(define (emit-labels lvars body-exps 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))
                      (x (third lvar)))
                  (cond
                   ((datum? x)
                    (emit-datum label))
                   ((code? x)
                    (emit-code label (code-vars x) (code-free-vars x)
                               (code-body x) env*))
                   (else
                    (error "unknown label expression" x)))))
              lvars*)
    (display ".text\n")
    (emit-label "scheme_entry")
    (for-each (lambda (body-exp)
                (emit-expr body-exp si env*))
              body-exps)
    (emit-ret)))


;;;
;;; Source to source program transformations
;;;

;; Find all free variables in an expression.
(define (free-variables x)
  (define (add-variables vars more-vars)
    (fold (lambda (new-var prev)
            (if (memq new-var vars)
                prev
                (cons new-var prev)))
          vars more-vars))
  (let loop ((vars (second x))
             (x (third x)))
    (cond
     ((immediate? x) '())
     ((quote? x) '())
     ((variable? x)
      (if (memq x vars)
          '()
          (list x)))
     ((if? x)
      (delete-duplicates
       (append (loop vars (test x))
               (loop vars (consequent x))
               (loop vars (alternate x)))))
     ((let? x)
      (append-map (lambda (y)
                    (loop (add-variables vars (map lhs (let-bindings x))) y))
                  (let-body x)))
     ((primcall? x)
      (append-map (lambda (operand)
                    (loop vars operand))
                  (cdr x)))
     ((lambda? x)
      (loop (add-variables vars (lambda-args x)) (lambda-body x)))
     ((pair? x)
      (append-map (lambda (arg)
                    (loop vars arg))
                  x)))))

;; Perform free variable analysis and transform 'lambda' forms into
;; closure/funcall forms and generate top-level labels for all
;; procedures.
(define (annotate-free-variables x)
  (cond
   ((immediate? x) x)
   ((quote? x) x)
   ((variable? x) x)
   ((if? x)
    `(if ,(annotate-free-variables (test x))
         ,(annotate-free-variables (consequent x))
         ,(annotate-free-variables (alternate x))))
   ((let? x)
    `(let ,(map (lambda (binding)
                  (list (lhs binding)
                        (annotate-free-variables (rhs binding))))
                (let-bindings x))
       ,@(map annotate-free-variables (let-body x))))
   ((primcall? x)
    (cons (primcall-op x)
          (map annotate-free-variables (cdr x))))
   ((lambda? x)
    `(lambda ,(lambda-args x)
       ,(free-variables x)
       ,(annotate-free-variables (lambda-body x))))
   ((pair? x)
    `(funcall ,@(map annotate-free-variables x)))))

;; Transforms a quote form into code.
(define (expand-quote x)
  (cond
   ((immediate? x) x)
   ((string? x)
    `(string ,@(string->list x)))
   ((vector? x)
    `(vector ,@(map expand-quote (vector->list x))))
   ((pair? x)
    `(cons ,(expand-quote (car x))
           ,(expand-quote (cdr x))))
   ((null? x)
    '())
   ;; The compiler doesn't support symbols yet...
   (else
    (error "unknown quoted thing" x))))

;; Extracts certain forms to global program labels.  Lambdas are
;; converted to closures and given a label.  Quoted expressions are
;; initialized at the start of program execution and given a label.
(define (convert-closures-and-constants x)
  (define (iter x)
    (cond
     ((immediate? x)
      (values x '() '()))
     ;; String literals and vectors are self-quoting.
     ((or (string? x) (vector? x))
      (iter `(quote x)))
     ;; Quoted forms are complex constant values that must be
     ;; evaluated exactly once and referred to by a global label.
     ((quote? x)
      (let ((quoted (expand-quote (quote-data x))))
        ;; Skip label generation if the quoted form expands to an
        ;; immediate value.
        (if (immediate? quoted)
            (values quoted '() '())
            (let ((const (unique-variable)))
                 (values `(constant-ref ,const)
                         (list (list const '(datum)))
                         (list `(constant-init ,const ,(expand-quote (quote-data x)))))))))
     ((variable? x)
      (values x '() '()))
     ((if? x)
      (let-values (((test* labels0 init0) (iter (test x)))
                   ((consequent* labels1 init1) (iter (consequent x)))
                   ((alternate* labels2 init2) (iter (alternate x))))
        (values `(if ,test* ,consequent* ,alternate*)
                (append labels0 labels1 labels2)
                (append init0 init1 init2))))
     ((let? x)
      (let ((bindings*
             (map (lambda (binding)
                    (let-values (((rhs* labels initializers)
                                  (iter (rhs binding))))
                      (list (list (lhs binding) rhs*)
                            labels
                            initializers)))
                  (let-bindings x)))
            (body*
             (map (lambda (y)
                    (let-values (((y* labels initializers) (iter y)))
                      (list y* labels initializers)))
                  (let-body x))))
        (values `(let ,(map first bindings*)
                   ,@(map first body*))
                (append (concatenate (map second bindings*))
                        (concatenate (map second body*)))
                (append (concatenate (map third bindings*))
                        (concatenate (map third body*))))))
     ((primcall? x)
      (let ((operands (map (lambda (operand)
                             (let-values (((operand* labels initializers)
                                           (iter operand)))
                               (list operand* labels initializers)))
                           (cdr x))))
        (values (cons (primcall-op x)
                      (map first operands))
                (concatenate (map second operands))
                (concatenate (map third operands)))))
     ;; Convert procedure calls to 'funcall' form that refers to a
     ;; closure.
     ((funcall? x)
      (let ((args (map (lambda (arg)
                         (let-values (((arg* labels initializers)
                                       (iter arg)))
                           (list arg* labels initializers)))
                       (cdr x))))
        (values `(funcall ,@(map first args))
                (concatenate (map second args))
                (concatenate (map third args)))))
     ;; Perform closure conversion.
     ((lambda? x)
      (let-values (((body* labels initializers)
                    (iter (fourth x))))
        (let ((name (unique-lvar)))
          (values `(closure ,name ,@(third x))
                  (cons (list name
                              `(code ,(second x) ,(third x) ,body*))
                        labels)
                  initializers))))))
  (let-values (((new-x labels initializers) (iter x)))
    `(labels ,labels ,@(append initializers (list new-x)))))

(define (mark-tail-calls x)
  (define (maybe-mark x)
    (if (funcall? x)
        `(tail-call ,@(cdr x))
        (mark-tail-calls x)))
  (cond
   ((immediate? x) x)
   ((variable? x) x)
   ((closure? x) x)
   ((if? x)
    `(if ,(mark-tail-calls (test x))
         ,(maybe-mark (consequent x))
         ,(maybe-mark (alternate x))))
   ((let? x)
    `(let ,(map (lambda (binding)
                  (list (lhs binding)
                        (mark-tail-calls (rhs binding))))
                (let-bindings x))
       ,@(map maybe-mark (let-body x))))
   ((primcall? x)
    (cons (primcall-op x)
          (map mark-tail-calls (cdr x))))
   ((funcall? x)
    `(funcall ,@(map mark-tail-calls (cdr x))))
   ((code? x)
    `(code ,(code-vars x) ,(code-free-vars x) ,(mark-tail-calls (fourth x))))
   ((datum? x)
    '(datum))
   ((labels? x)
    `(labels ,(map (lambda (binding)
                     (list (lhs binding)
                           (mark-tail-calls (rhs binding))))
                   (label-bindings x))
             ,@(map mark-tail-calls (drop x 2))))))

;; Apply all compiler passes to transform the input program into a
;; form that it is suitable for compilation to native assembly code.
(define (transform x)
  (parameterize ((unique-counter 0))
    (mark-tail-calls
     (convert-closures-and-constants
      (annotate-free-variables x)))))


;;;
;;; Compiler frontend
;;;

(define (compile-program x)
  (let ((x* (transform x)))
    (parameterize ((unique-counter 0))
      (emit-labels (second x*) (drop x* 2) (- wordsize) '()))))

(define (compile-and-run x)
  (with-output-to-file "scheme_entry.s"
    (lambda ()
      (display ".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))


;;;
;;; Tests
;;;

(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")
  ;; procedure with no free variables and multiple args
  (test-case '(let ((perimeter (lambda (length width)
                                 (+ (* length 2)
                                    (* width 2)))))
                (perimeter 4 3))
             "14")
  ;; closures!
  (test-case '(let ((x 5))
                (let ((f (lambda (y) (+ x y))))
                  (f 4)))
             "9")
  ;; recursive tail calls
  (test-case '(let ((f (lambda (x f)
                         (if (= x 5)
                             789
                             (f (add1 x) f)))))
                (f 0 f))
             "789")
  ;; complex constants
  (test-case '(let ((f (lambda () (quote (1 . "H")))))
              (eq? (f) (f)))
           "#t"))