;; BF AST Transformer in Scheme
;; Jon Simons (simonsj at ccs dot neu dot edu)
;; August, 2007
;; -------------------------------------------------------------------------
(module bf-ast-to-ir mzscheme
  
  ;; Provide AST transformations
  (provide (all-defined))
  
  ;; For AST structs (SEQ, EXPR)
  (require (prefix ast1_ "bf-parser.scm"))
  
  ;; ------------------------------------------------
  ;; BF Program IR
  ;; ------------------------------------------------
  ;;
  ;; This BF IR is an extension of the BF AST
  ;; from bf-parser which has multiplication nodes and
  ;; zero nodes.
  ;;
  ;; n, m stand for a numbers
  ;;
  ;; ptr-relation and factor are numbers that describe the relative
  ;;                         location of the BF pointer
  ;;                         (relative to the given operation)
  ;;
  ;; <PRGM> ::= <EXPR> ...
  ;; 
  ;; <EXPR> ::= INC(n, ptr-relation)
  ;;          | DEC(n, ptr-relation)
  ;;          | LT(n)
  ;;          | RT(n)
  ;;          | OUT(ptr-relation)
  ;;          | IN(ptr-relation)
  ;;          | LOOP(<EXPR> ..., ptr-relation)
  ;;          | MUL(<MUL-EXPR> ..., factor)
  ;;          | ZERO(ptr-relation)
  ;;
  ;; <MUL-EXPR> ::= INC(n, ptr-relation)
  ;;              | DEC(n, ptr-relation)
  ;;
  ;; For LOOPs, the ptr-relation is the relative BF pointer location at the
  ;; beginning of the loop body.
  ;;
  ;; TODO: Blah.. push MUL-EXPR to EXPR so that INC, DEC are only in one place
  
  
  ;; make-EXPR : symbol number number (list of EXPRs) -> EXPR
  (define-struct EXPR (type N ptr exprs))
  
  ;; Shorthand constructors
  ;;
  ;; The convention followed is that _only_ these constructors
  ;; are allowed to be used.  There shouldn't be any instances of
  ;; make-struct being used.
  ;;
  ;; TODO: To reduce memory footprint, it would be nice to memoize struct
  ;;       instances so that there is never more than one struct with the
  ;;       exact same information.  This could well be a *drastic*
  ;;       improvement for extreme BF programs (extreme being ~16 million
  ;;       characters).
  (define (INC n ptr)      (make-EXPR 'inc n  ptr #f))
  (define (DEC n ptr)      (make-EXPR 'dec n  ptr #f))
  (define (RT  n)          (make-EXPR 'rt  n  #f  #f))
  (define (LT  n)          (make-EXPR 'lt  n  #f  #f))
  (define (OUT ptr)        (make-EXPR 'out #f ptr #f))
  (define (IN  ptr)        (make-EXPR 'in  #f ptr #f))
  (define (LOOP exprs ptr) (make-EXPR 'loop #f ptr exprs))
  (define (MUL exprs ptr)  (make-EXPR 'mul #f ptr exprs))
  (define (ZERO ptr)       (make-EXPR 'zero #f ptr #f))
  
  ;; Maps the given AST to the BF IR (described above).
  ;;
  ;; ast->ir : (list of ast1_EXPRs) -> (list of EXPRs)
  (define (ast->ir AST)
    (map (lambda (expr)
           (let ((type  (ast1_EXPR-type  expr))
                 (n     (ast1_EXPR-N     expr))
                 (ptr   (ast1_EXPR-ptr   expr))
                 (exprs (ast1_EXPR-exprs expr)))
             (make-EXPR type n ptr (if exprs
                                       (ast->ir exprs)
                                       exprs))))
         AST))
  )