;;; codegen.scm -- compile flic code to Lisp
;;;
;;; Author : Sandra Loosemore
;;; Date : 29 Apr 1992
;;;
;;; to do: check completeness of special cases for constructors
;;; constants still need work
;;; optimized entry points
;;;
;;; The code generated here uses the following helper functions:
;;; (make-curried-fn opt-fn strictness)
;;; make a curried function that calls opt-fn after collecting the
;;; arguments and processing them according to strictness. Both
;;; the arguments are evaluated.
;;; (make-tuple-constructor arity)
;;; return a function that makes an untagged data structure with "arity"
;;; slots. "arity" is a constant.
;;; (make-tuple . args)
;;; uncurried version of the above
;;; (make-tagged-data-constructor n arity)
;;; return a function that makes a data structure with tag "n" and
;;; "arity" slots.
;;; (make-tagged-data n . args)
;;; uncurried version of the above
;;; (tuple-select arity i object)
;;; extract component "i" from untagged "object"
;;; (tagged-data-select arity i object)
;;; extract component "i" from tagged "object"
;;; (constructor-number object)
;;; return the tag from "object"
;;; (delay form)
;;; returns a delay object with unevaluated "form".
;;; (box form)
;;; returns a delay object with evaluated "form".
;;; (force delay)
;;; return the value of the delay object.
;;; (make-haskell-string string)
;;; Converts a Lisp string lazily to a haskell string (using a magic
;;; delay function). Returns an unboxed result.
;;;======================================================================
;;; Code walker
;;;======================================================================
;;; Here is the main entry point.
(define (codegen-top big-let)
(do ((bindings (flic-let-bindings big-let) (cdr bindings))
(result '())
(decls '()))
((null? bindings) `(begin ,@(nreverse decls) ,@(nreverse result)))
(let ((var (car bindings)))
(push `(predefine ,(fullname var)) decls)
(push (codegen-definition var (var-value var)) result))))
;;; See box.scm for more information about this...
(define (do-codegen object)
(let ((x (codegen object))
(unboxed? (flic-exp-unboxed? object))
(strict-result? (flic-exp-strict-result? object))
(cheap? (flic-exp-cheap? object)))
(if unboxed?
(if strict-result?
x
(if cheap?
`(unbox ,x)
`(force ,x)))
(if strict-result?
(if cheap?
`(box ,x)
`(delay ,x))
(if cheap?
x
`(delay (force ,x)))))))
(define (do-codegen-list list)
(map (function do-codegen) list))
(define-flic-walker codegen (object))
;;; For top-level definitions bound to lambda expressions, make both
;;; a standard entry point (with possibly unboxed arguments) and
;;; a standard entry point.
(define (codegen-definition var exp)
(let ((fullname (fullname var)))
(when (or (memq 'codegen (dynamic *printers*))
(memq 'codegen-flic (dynamic *printers*)))
; (format '#t "~%Codegen of ~A [~A] " (def-name var) (struct-hash var))
(format '#t "~%Codegen of ~A " (def-name var))
(when (not (var-strict? var))
(format '#t "Nonstrict "))
(when (not (eq? (var-strictness var) '()))
(format '#t "Strictness: ")
(dolist (s (var-strictness var))
(format '#t (if s "S " "N "))))
(when (var-simple? var)
(format '#t " Inline "))
(format '#t "~%")
(when (memq 'codegen-flic (dynamic *printers*))
(pprint* exp)))
(let ((lisp-code
(if (not (flic-lambda? exp))
`(define ,fullname ,(do-codegen exp))
(let* ((optname (optname var))
(lambda (codegen-lambda-aux exp))
(def `(define (,optname ,@(cadr lambda))
,@(cddr lambda))))
(if (var-selector-fn? var)
;; Standard entry point for selectors is never used.
def
`(begin
,def
(define ,fullname
,(maybe-make-box-value
(codegen-curried-fn
`(function ,optname) (var-strictness var))
(var-strict? var)))))))))
(when (or (memq 'codegen (dynamic *printers*))
(memq 'codegen-flic (dynamic *printers*)))
(pprint* lisp-code))
lisp-code)))
(define (codegen-lambda-list vars)
(map (function fullname) vars))
(define (codegen-curried-fn opt-fn strictness)
(if (null? (cdr strictness))
;; one-argument special cases
(if (car strictness)
`(make-curried-fn-1-strict ,opt-fn)
`(make-curried-fn-1-nonstrict ,opt-fn))
;; general case
`(make-curried-fn ,opt-fn ',strictness)))
;;; Curry lambdas. Functions always return an unboxed value.
(define-codegen flic-lambda (object)
(codegen-curried-fn
(codegen-lambda-aux object)
(map (lambda (x) (var-strict? x)) (flic-lambda-vars object))))
(define (codegen-lambda-aux object)
(let* ((vars (flic-lambda-vars object))
(ignore '())
(args (codegen-lambda-list vars)))
(dolist (v vars)
(if (eqv? (var-referenced v) 0)
(push (fullname v) ignore)))
`(lambda ,args
,@(if (not (null? ignore))
`((declare (ignore ,@ignore)))
'())
,(do-codegen (flic-lambda-body object)))))
;;; This is only for non-top-level lets.
;;; The boxing of the value of each of the bindings is controlled by its
;;; strict? property.
(define-codegen flic-let (object)
(let ((bindings (flic-let-bindings object))
(body (flic-let-body object))
(recursive? (flic-let-recursive? object)))
(if recursive?
(codegen-letrec bindings body)
(codegen-let* bindings body))))
;;; For efficiency reasons, we want to make all the function bindings
;;; in the function namespace (some implementations do not do tail-recursion
;;; or other optimizations correctly otherwise). This means we have
;;; to sort out the variable bindings from the function bindings here.
(define (codegen-letrec bindings body)
(let ((let-bindings '())
(labels-bindings '()))
(dolist (var bindings)
(let ((value (var-value var))
(fullname (fullname var))
(strict? (var-strict? var)))
(if (flic-lambda? value)
;; Some functions may need only the optimized or standard
;; entry points, but not both.
(let ((optname (optname var))
(lambda (codegen-lambda-aux value))
(optimized? (var-optimized-refs? var))
(standard? (var-standard-refs? var)))
(when standard?
(push (list fullname
(maybe-make-box-value
(codegen-curried-fn
(if optimized? `(function ,optname) lambda)
(var-strictness var))
strict?))
let-bindings))
(when optimized?
(push (cons optname (cdr lambda)) labels-bindings)))
(push (list fullname (do-codegen value)) let-bindings))))
(setf let-bindings (nreverse let-bindings))
(setf labels-bindings (nreverse labels-bindings))
(cond ((null? let-bindings)
`(labels ,labels-bindings ,(do-codegen body)))
((null? labels-bindings)
`(letrec ,let-bindings ,(do-codegen body)))
(t
`(let ,(map (lambda (b) `(,(car b) '#f)) let-bindings)
(labels ,labels-bindings
,@(map (lambda (b) `(setf ,@b)) let-bindings)
,(do-codegen body))))
)))
(define (codegen-let* bindings body)
(if (null? bindings)
(do-codegen body)
(let* ((var (car bindings))
(value (var-value var))
(fullname (fullname var))
(strict? (var-strict? var))
(body (codegen-let* (cdr bindings) body)))
(if (flic-lambda? value)
;; Some functions may need only the optimized or standard
;; entry points, but not both.
(let ((optname (optname var))
(lambda (codegen-lambda-aux value))
(optimized? (var-optimized-refs? var))
(standard? (var-standard-refs? var)))
(when standard?
(setf body
(add-let-binding
(list fullname
(maybe-make-box-value
(codegen-curried-fn
(if optimized? `(function ,optname) lambda)
(var-strictness var))
strict?))
body)))
(when optimized?
(setf body `(flet ((,optname ,@(cdr lambda))) ,body)))
body)
(add-let-binding (list fullname (do-codegen value)) body)))))
(define (add-let-binding binding body)
(if (and (pair? body) (eq? (car body) 'let*))
`(let* (,binding ,@(cadr body)) ,@(cddr body))
`(let* (,binding) ,body)))
(define-codegen flic-app (object)
(let ((fn (flic-app-fn object))
(args (flic-app-args object))
(saturated? (flic-app-saturated? object)))
(cond ((and saturated? (flic-pack? fn))
;; Saturated call to constructor
(codegen-constructor-app-aux
(flic-pack-con fn)
(do-codegen-list args)))
((and saturated? (flic-ref? fn))
;; Saturated call to named function
(let* ((var (flic-ref-var fn))
(optname (optname var))
(argcode (do-codegen-list args)))
`(,optname ,@argcode)))
(else
;; Have to make a curried call to standard entry point.
(let ((fncode (do-codegen fn))
(argcode (do-codegen-list args)))
(if (and (pair? fncode)
(eq? (car fncode) 'force))
`(funcall-force ,(cadr fncode) ,@argcode)
`(funcall ,fncode ,@argcode))))
)))
(define (codegen-constructor-app-aux con argcode)
(let ((alg (con-alg con)))
(cond ((eq? con (core-symbol ":"))
`(cons ,@argcode))
((algdata-implemented-by-lisp? alg)
(apply-maybe-lambda (cadr (con-lisp-fns con)) argcode))
((algdata-tuple? alg)
`(make-tuple ,@argcode))
(else
`(make-tagged-data ,(con-tag con) ,@argcode)))))
(define-codegen flic-ref (object)
(fullname (flic-ref-var object)))
(define-codegen flic-const (object)
(let ((value (flic-const-value object)))
(cond ((string? value)
`(make-haskell-string ,value))
((char? value)
;; *** I think the parser ought to convert characters to their
;; *** ASCII codes instead of doing it here. There are problems
;; *** with valid Haskell characters that can't be represented
;; *** portably as Lisp characters.
(char->integer value))
((number? value)
value)
(else
;; It must be a ratio. This is a bit of a hack - this depends on
;; the fact that 2 tuples are represented in the same manner as
;; rationals. Hacked for strict rationals - jcp
`(make-tuple ,(car value) ,(cadr value)))
)))
;;; Returns a function or constant, so doesn't need to delay result.
;;; See flic-app for handling of saturated constructor calls.
(define-codegen flic-pack (object)
(let* ((con (flic-pack-con object))
(arity (con-arity con))
(alg (con-alg con))
(tuple? (algdata-tuple? alg))
(strictness (con-slot-strict? con))
(index (con-tag con)))
(cond ((eq? con (core-symbol "Nil"))
''())
((eq? con (core-symbol "True"))
''#t)
((eq? con (core-symbol "False"))
''#f)
((eq? con (core-symbol ":"))
'(function make-cons-constructor))
((algdata-implemented-by-lisp? alg)
(let ((fn (cadr (con-lisp-fns con))))
(if (eqv? (con-arity con) 0)
fn
(codegen-curried-fn
(if (and (pair? fn) (eq? (car fn) 'lambda))
fn
`(function ,fn))
strictness))))
((algdata-enum? alg)
;; All constructors have 0 arity; represent them just
;; by numbers.
index)
(tuple?
;; Only a single constructor for this type.
(codegen-curried-fn
`(make-tuple-constructor ,arity)
strictness))
((eqv? arity 0)
;; No arguments to this constructor.
`(make-tagged-data ,index))
(else
;; General case.
(codegen-curried-fn
`(make-tagged-data-constructor ,index ,arity)
strictness))
)))
;;; These expressions translate directly into their Lisp equivalents.
(define-codegen flic-case-block (object)
`(block ,(flic-case-block-block-name object)
,@(do-codegen-list (flic-case-block-exps object))))
(define-codegen flic-return-from (object)
`(return-from ,(flic-return-from-block-name object)
,(do-codegen (flic-return-from-exp object))))
(define-codegen flic-and (object)
`(and ,@(do-codegen-list (flic-and-exps object))))
(define-codegen flic-if (object)
`(if ,(do-codegen (flic-if-test-exp object))
,(do-codegen (flic-if-then-exp object))
,(do-codegen (flic-if-else-exp object))))
(define-codegen flic-sel (object)
(codegen-flic-sel-aux
(flic-sel-con object)
(flic-sel-i object)
(do-codegen (flic-sel-exp object))))
(define (codegen-flic-sel-aux con index exp)
(let* ((alg (con-alg con))
(tuple? (algdata-tuple? alg))
(arity (con-arity con)))
(cond ((eq? con (core-symbol ":"))
(if (eqv? index 0)
`(car ,exp)
`(cdr ,exp)))
((algdata-implemented-by-lisp? alg)
(apply-maybe-lambda (list-ref (cddr (con-lisp-fns con)) index)
(list exp)))
(tuple?
`(tuple-select ,arity ,index ,exp))
(else
`(tagged-data-select ,arity ,index ,exp))
)))
(define-codegen flic-is-constructor (object)
(codegen-flic-is-constructor-aux
(flic-is-constructor-con object)
(do-codegen (flic-is-constructor-exp object))))
(define (codegen-flic-is-constructor-aux con exp)
(let ((type (con-alg con)))
(cond ((eq? type (core-symbol "Bool"))
(if (eq? con (core-symbol "True"))
exp
`(not ,exp)))
((eq? type (core-symbol "List"))
(if (eq? con (core-symbol ":"))
`(pair? ,exp)
`(null? ,exp)))
((algdata-implemented-by-lisp? type)
(let ((fn (car (con-lisp-fns con))))
(apply-maybe-lambda fn (list exp))))
((algdata-tuple? type)
;; This should never happen.
''#t)
((algdata-enum? type)
`(eqv? (the fixnum ,exp) (the fixnum ,(con-tag con))))
(else
`(eqv? (the fixnum (constructor-number ,exp))
(the fixnum ,(con-tag con))))
)))
(define-codegen flic-con-number (object)
(let ((type (flic-con-number-type object))
(exp (do-codegen (flic-con-number-exp object))))
`(the fixnum
,(cond ((eq? type (core-symbol "Bool"))
`(if ,exp 1 0))
((eq? type (core-symbol "List"))
`(if (pair? ,exp) 0 1))
((algdata-tuple? type)
;; This should never happen.
0)
((algdata-implemented-by-lisp? type)
(let ((var (gensym)))
`(let ((,var ,exp))
(cond ,@(map (lambda (con)
`(,(apply-maybe-lambda
(car (con-lisp-fns con))
(list var))
',(con-tag con)))
(algdata-constrs type))
(else (error "No constructor satisfies ~A.~%"
',(def-name type)))))))
((algdata-enum? type)
exp)
(else
`(constructor-number ,exp))
))
))
;;;======================================================================
;;; Utility functions
;;;======================================================================
;;; Here are some helper functions for handing boxing and unboxing
;;; of values.
;;; maybe-make-box-delay is used to box forms that are "expensive" to
;;; compute; maybe-make-box-value is used to box forms like constants
;;; or functions that are "cheap" to compute eagerly.
;;; Maybe-unbox is used to unbox a form that returns a boxed result.
(define (maybe-make-box-delay form unboxed?)
(if unboxed?
form
`(delay ,form)))
(define (maybe-make-box-value form unboxed?)
(if unboxed?
form
`(box ,form)))
(define (maybe-unbox form unboxed?)
(if unboxed?
`(force ,form)
form))
;;; These two var slots are filled in lazily by the code generator,
;;; since most vars generated don't need them. You should always
;;; use these functions instead of accessing the structure slot
;;; directly.
(define (fullname var)
(or (var-fullname var)
(setf (var-fullname var)
(if (var-toplevel? var)
;; For toplevel names, use module name glued onto base names.
;; These are always interned symbols.
(if (def-core? var)
(symbol-append '|*Core:| (def-name var))
(symbol-append (def-module var) '\: (def-name var)))
;; Otherwise, make sure we have a gensym.
;; The uniquification of interned symbols is required
;; because there may be multiple nested bindings of the
;; same name, and we want to be able to distinguish between
;; the different bindings.
(let ((name (def-name var)))
(if (gensym? name)
name
(gensym (symbol->string name))))))
))
(define (optname var)
(or (var-optimized-entry var)
(let ((name (string-append (symbol->string (fullname var)) "/OPT")))
(setf (var-optimized-entry var)
(if (var-toplevel? var)
(string->symbol name)
(gensym name))))))
;;;======================================================================
;;; Exported functions
;;;======================================================================
;;; This handles types exported to lisp from Haskell
;;; *** Is this really supposed to create variable bindings as
;;; *** opposed to function bindings???
;;; *** I assume all of these functions want strict arguments and return
;;; *** strict results, even if the data structures contain boxed values.
(define (codegen-exported-types mods)
(let ((defs '()))
(dolist (m mods)
(dolist (a (module-alg-defs m))
(when (algdata-export-to-lisp? a)
(dolist (c (algdata-constrs a))
(setf defs (nconc (codegen-constr c) defs))))))
`(begin ,@defs)))
(define (codegen-constr c)
(let ((lisp-fns (con-lisp-fns c)))
(if c
(let ((res
`(,(codegen-lisp-predicate (car lisp-fns) c)
,(codegen-lisp-constructor (cadr lisp-fns) c)
,@(codegen-lisp-accessors
(cddr lisp-fns) (con-slot-strict? c) c 0))))
(when (memq 'codegen (dynamic *printers*))
(dolist (d res)
(pprint* d)))
res)
'())))
(define (codegen-lisp-predicate name c)
`(define (,name x)
,(codegen-flic-is-constructor-aux c 'x)))
(define (codegen-lisp-constructor name c)
(let ((strictness (con-slot-strict? c))
(args '())
(exps '()))
(dolist (s strictness)
(let ((arg (gensym)))
(push arg args)
(push (if s arg `(box ,arg)) exps)))
`(define (,name ,@(nreverse args))
,(codegen-constructor-app-aux c (nreverse exps)))))
(define (codegen-lisp-accessors names strictness c i)
(declare (type fixnum i))
(if (null? names)
'()
(let ((body (codegen-flic-sel-aux c i 'x)))
(when (not (car strictness))
(setf body `(force ,body)))
(cons `(define (,(car names) x) ,body)
(codegen-lisp-accessors (cdr names) (cdr strictness) c (+ i 1))))
))
;;; This is a special hack needed due to brain-dead common lisp problems.
;;; This allows the user to place lambda defined functions in ImportLispType
;;; *** I'm not convinced this is necessary; ((lambda ...) args)
;;; *** is perfectly valid Common Lisp syntax!
(define (apply-maybe-lambda fn args)
(if (and (pair? fn)
(eq? (car fn) 'lambda))
`(funcall ,fn ,@args)
`(,fn ,@args)))