home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
lisp
/
interpre
/
apteryx
/
compile.lsp
< prev
next >
Wrap
Lisp/Scheme
|
1994-06-25
|
41KB
|
1,095 lines
; Copyright 1994 Apteryx Lisp Ltd
(defmacro progv (symbols values &rest stmts)
(let ( (unbound-value (gensym))
(symbols2 (gensym))
(rest-values (gensym))
(old-value (gensym))
(old-values (gensym))
(result (gensym)) )
`(let* ( (,unbound-value (gensym))
(,symbols2 ,symbols)
(,rest-values ,values)
,old-value ,result
(,old-values (mapcar #'(lambda (sym)
(if (boundp sym)
(symbol-value sym)
,unbound-value) )
,symbols2) ) )
(unwind-protect
(progn
(dolist (sym ,symbols2)
(if ,rest-values
(progn
(set sym (car ,rest-values))
(setq ,rest-values (cdr ,rest-values)) )
(makunbound sym) ) )
(setq ,result (progn ,@stmts)) )
(dolist (sym ,symbols2)
(setq ,old-value (car ,old-values))
(setq ,old-values (cdr ,old-values))
(if (eq ,old-value ,unbound-value)
(makunbound sym)
(set sym ,old-value) ) )
,result) ) ) )
;;; position
(defun position (ob list &key (test #'eql))
(let ( (rest list) (found nil) (pos 0))
(while (and (not found) (consp rest) )
(if (funcall test (car rest) ob)
(setq found t)
(progn
(setq rest (cdr rest))
(setq pos (1+ pos)) ) ) )
(if found
pos
nil) ) )
(defun mapcan (fun list1 &rest lists)
(apply #'nconc (apply #'mapcar (cons fun (cons list1 lists)))) )
;;; setf macros
(defmacro appendf (place &rest lists)
`(setf ,place (append ,place ,@lists)) )
(defmacro incf (place)
`(setf ,place (1+ ,place)) )
(defmacro addf (place n)
`(setf ,place (+ ,place ,n)) )
(defmacro decf (place)
`(setf ,place (1- ,place)) )
(defmacro subf (place n)
`(setf ,place (- ,place ,n)) )
(defmacro pushf (place x)
`(setf ,place (cons ,x ,place)) )
(defun list-to-vector (list)
(let* ( (len (length list))
(pos 0)
(vec (make-array len)) )
(dolist (elt list vec)
(setf (aref vec pos) elt)
(incf pos) ) ) )
(defmacro with-open-file (name stream direc &rest exprs)
`(let ((,stream (open ,name :direction ,direc)))
(if ,stream
(unwind-protect
(progn ,@exprs)
(close ,stream) )
(error "Failure to open file" name) ) ) )
(defmacro compilef (code expr env height)
`(setf ,code (_compile ,code ,expr ,env ,height)) )
(defmacro instrf (code &rest instrs)
(cons 'progn
(mapcar #'(lambda (instr) `(setf ,code (cons ,instr ,code)))
instrs) ) )
(defun _compile-function (code fun args env height)
(let ( (argnum1 1))
(cond
((symbolp fun)
(instrf code `(push-fun ,fun)) )
((consp fun)
(if (and (eq 'setf (car fun)) (true-listp fun)
(= (length fun) 2) (symbolp (second fun)))
(instrf code `(push-setf-fun ,(second fun)))
(error "Invalid function name" fun) ) )
(t (instrf code `(setit ,fun) '(pushit))) )
(dolist (arg args)
(compilef code arg (cons argnum1 env) (+ argnum1 height))
(instrf code '(pushit))
(incf argnum1) )
(_env-height-checked (+ argnum1 height))
(instrf code `(call-with-num-args ,(length args))) ) )
(defun _compile-list (code expr env height)
(let* ( (head (car expr))
(args (cdr expr))
(compiler (if (symbolp head) (get head '_compiler) nil)) )
(if compiler
(apply compiler (cons code (cons env (cons height args))))
(_compile-function code head args env height)) ) )
(defun _compile (code expr env height)
'(format t "Compiling ~A ...~%" expr)
(cond
((keywordp expr) (_compile-constant code expr))
((symbolp expr)
(if (and (constantp expr)
(not (eq (type-of (symbol-value expr)) 'constant)) )
(_compile-constant code (symbol-value expr))
(_compile-symbol code expr env) ) )
((consp expr) (_compile-list code expr env height))
(t (_compile-constant code expr)) ) )
(setq _*code-marker* (make-symbol "code"))
(defun _is-code (ob)
(and (consp ob) (eq _*code-marker* (car ob)) ) )
(defun _make-code (ob)
(cons _*code-marker* ob) )
(defun _compile-constant (code expr)
(instrf code `(setit ,expr)) )
(defmacro def-compile (name args &rest stmts)
`(progn
(setf (get ',name '_compiler)
#'(lambda ,args ,@stmts) )
(list 'def-compile ',name) ) )
(defun _env-height-checked (height)
(if (> height *max-env-height*)
(setq *max-env-height* height) )
height)
(defun _search-env-elt (var-name env-elt depth)
(let ( (var nil) )
(case (car env-elt)
(field
(let ( (pos (position var-name (second env-elt))) )
(if pos
(setq var (cons 'field (cons depth pos))) ) ) )
((stack heap readonly)
(if (eq var-name (second env-elt))
(setq var (list (car env-elt) depth)) ) )
(copied
(setq var (_search-env-elt var-name (second env-elt) depth)) )
(uncopied)
(t (error "Invalid environment element" env-elt)) )
var) )
(defun _search-env (var-name env)
(let ( (rest env) (depth 0) (var nil) env-elt)
(while (and rest (not var))
(setq env-elt (car rest))
(if (integerp env-elt)
(addf depth env-elt)
(progn
(incf depth)
(if (not (consp env-elt))
(error "Invalid environment element" env-elt) )
(setq var (_search-env-elt var-name env-elt depth))
(if (eq (car env-elt) 'uncopied) (decf depth)) ) )
(setq rest (cdr rest)) )
(if (not var)
(list 'global var-name)
var) ) )
(defun _env-elt-matches (var-name env-elt)
(case (car env-elt)
(field
(member var-name (second env-elt)) )
((stack heap readonly)
(eq var-name (second env-elt)) )
((copied uncopied)
(_env-elt-matches var-name (second env-elt)) )
(t (error "Invalid environment element" env-elt)) ) )
(defun _search-env-for-usage (var-name env)
(let ( (rest env) env-elt (matching-elt nil))
(while (and rest (not matching-elt))
(setq env-elt (car rest))
(if (consp env-elt)
(if (_env-elt-matches var-name env-elt)
(setq matching-elt env-elt) ) )
(setq rest (cdr rest)) )
matching-elt) )
(defun _get-instruction (var)
(case (car var)
(stack (list 'stack-get (second var)))
(heap (list 'heap-get (second var)))
(readonly (list 'stack-get (second var)))
(global (list 'global-get (second var)))
(field (list 'field-get (cdr var))) ) )
(defun _change-to-used (instr)
(case (car instr)
(dont-save
(setf (car instr) 'save) )
(t (error "Don't know how to _change-to-used" instr)) ) )
(defun _notify-get-usage (env-elt)
(case (car env-elt)
(uncopied
(setf (car env-elt) 'copied)
(_notify-get-usage (second env-elt))
(_change-to-used (third env-elt)) ) ) )
(defun _compile-symbol (code sym env)
(let ((env-elt (_search-env-for-usage sym env)))
(if env-elt
(_notify-get-usage env-elt) ) )
(instrf code `(get ,sym ,env)) )
(defun _set-instruction (var)
(case (car var)
(stack (list 'stack-set (second var)))
(heap (list 'heap-set (second var)))
(readonly (error "Can't change value of " var))
(global (list 'global-set (second var)))
(field (list 'field-set (cdr var)))) )
(defun _change-stack-to-heap-instr (instr)
(case (car instr)
(push-stack-var
(setf (car instr) 'push-heap-var) )
(leave-on-stack
(setf (car instr) 'put-on-heap) )
(t (error "Don't know how to stack-to-heap" instr)) ) )
(defun _notify-set-copied-usage (env-elt)
(case (car env-elt)
(stack
(setf (car env-elt) 'heap)
(_change-stack-to-heap-instr (third env-elt)) )
(uncopied
(setf (car env-elt) 'copied)
(_notify-set-copied-usage (second env-elt))
(_change-to-used (third env-elt)) ) ) )
(defun _notify-set-usage (env-elt)
(case (car env-elt)
(uncopied
(setf (car env-elt) 'copied)
(_notify-set-copied-usage (second env-elt))
(_change-to-used (third env-elt)) )
(copied
(_notify-set-copied-usage (second env-elt)) ) ) )
(defun _compile-set-symbol (code sym env)
(let ((env-elt (_search-env-for-usage sym env)))
(if env-elt
(_notify-set-usage env-elt) ) )
(instrf code `(set ,sym ,env)) )
(defun _env-position (elt env)
(let ( (position 0) (found nil) (rest-env env) env-elt)
(while (and (consp rest-env) (not found))
(setq env-elt (car rest-env))
(if (eq elt env-elt)
(setq found t)
(progn
(if (integerp env-elt)
(addf position env-elt)
(incf position) )
(setq rest-env (cdr rest-env)) ) ) )
(if found position nil) ) )
(defun _resolved-save-env (saves env)
(let ( (positions nil) )
(dolist (save saves)
(if (eq (car save) 'save)
(let ( (pos (_env-position (second save) env)) )
(if pos
(pushf positions (1+ pos)) ) ) ) )
(list-to-vector positions) ) )
(defun _resolve-var-ref (instr)
(let ( (new-instr
(case (first instr)
(set (_set-instruction (_search-env (second instr)
(third instr))))
(get (_get-instruction (_search-env (second instr)
(third instr))))
(save-env
`(save-env ,(_resolved-save-env (second instr) (third instr))) ) ) ) )
(setf (car instr) (car new-instr))
(setf (cdr instr) (cdr new-instr)) ) )
;;; def-compiles
(defun _check-var-name (name)
(if (not (symbolp name))
(error "Invalid argument variable name" name) )
(if (constantp name)
(error "Invalid variable name - is a constant" name) ) )
(defmacro compile-stmts (prog stmts env height)
(let ( (stmt (gensym)) )
`(if (null ,stmts)
(instrf ,prog '(setit nil))
(dolist (,stmt ,stmts ,prog)
(compilef ,prog ,stmt ,env ,height) ) ) ) )
(def-compile progn (code env height &rest stmts)
(compile-stmts code stmts env height) )
(def-compile prog1 (code env height stmt1 &rest stmts)
(compilef code stmt1 env height)
(instrf code '(pushit))
(compile-stmts code stmts (cons 1 env)
(_env-height-checked (1+ height)) )
(instrf code '(popit)) )
(def-compile prog2 (code env height stmt1 stmt2 &rest stmts)
(compilef code stmt1 env height)
(compilef code stmt2 env height)
(instrf code '(pushit))
(compile-stmts code stmts (cons 1 env)
(_env-height-checked (1+ height)))
(instrf code '(popit)) )
(def-compile if (code env height cond then-stmt &optional else-stmt)
(let ( (not-true-label (gensym)) (end-label (gensym)) )
(compilef code cond env height)
(instrf code `(jump-not-true ,not-true-label))
(compilef code then-stmt env height)
(instrf code
`(jump ,end-label)
not-true-label)
(compilef code else-stmt env height)
(instrf code end-label) ) )
(def-compile when (code env height cond &rest stmts)
(_compile-list code `(if ,cond (progn ,@stmts)) env height) )
(def-compile unless (code env height cond &rest stmts)
(_compile-list code `(if (not ,cond) (progn ,@stmts)) env height) )
(def-compile quote (code env height value)
(instrf code `(setit ,value)) )
(def-compile dotimes (code env height counter-limit &rest stmts)
(let ( counter limit result
(loop (gensym)) (end (gensym)) )
(if (true-listp counter-limit)
(case (length counter-limit)
(2 (setq result nil))
(3 (setq result (third counter-limit)))
(t (error "Invalid counter-limit" counter-limit)) )
(error "Invalid counter-limit" counter-limit) )
(setq counter (first counter-limit))
(_check-var-name counter)
(setq limit (second counter-limit))
(compilef code limit env height)
(instrf code
'(pushit) '(setit 0) '(pushit) loop
'(check-counter-finished) `(jump-true ,end) )
(let ( (new-env `((readonly ,counter) 1 ,@env)) )
(compile-stmts code stmts new-env (_env-height-checked (+ 2 height))) )
(instrf code
'(inc-counter) `(jump ,loop) end '(pop-discard 2))
(compilef code result env height) ) )
(def-compile dolist (code env height elt-list &rest stmts)
(let ( elt list result
(loop (gensym)) (end (gensym)) )
(if (true-listp elt-list)
(case (length elt-list)
(2 (setq result nil))
(3 (setq result (third elt-list)))
(t (error "Invalid element-list" elt-list)) )
(error "Invalid element-list" elt-list) )
(setq elt (first elt-list))
(_check-var-name elt)
(setq list (second elt-list))
(compilef code list env height)
(instrf code
'(pushit) '(dupl) '(pushit) loop '(check-rest-is-cons)
`(jump-not-true ,end) )
(let ( (new-env `((readonly ,elt) 2 ,@env)) )
(instrf code '(get-next-list-elt))
(compile-stmts code stmts new-env (_env-height-checked (+ 3 height))) )
(instrf code
`(jump ,loop) end '(check-rest-is-nil)
'(pop-discard 3) )
(compilef code result env height) ) )
(def-compile while (code env height cond &rest stmts)
(let ( (loop (gensym)) (end (gensym)))
(instrf code loop)
(compilef code cond env height)
(instrf code `(jump-not-true ,end) )
(compile-stmts code stmts env height)
(instrf code `(jump ,loop) end) ) )
(def-compile cond (code env height &rest clauses)
(let ( (end (gensym)) )
(instrf code '(setit nil))
(dolist (clause clauses)
(let ( (cond (car clause))
(stmts (cdr clause)) (next (gensym)) )
(compilef code cond env height)
(instrf code `(jump-not-true ,next) )
(if (not (null stmts))
(compile-stmts code stmts env height) )
(instrf code `(jump ,end) next) ) )
(instrf code end) ) )
(def-compile case (code env height key-expr &rest clauses)
(let ( (end (gensym))
(new-env (cons 1 env))
(new-height (_env-height-checked (1+ height))) )
(instrf code '(setit nil))
(compilef code key-expr env height)
(instrf code '(pushit))
(dolist (clause clauses)
(let ( (keys (car clause))
(stmts (cdr clause))
(next (gensym)) (start (gensym)) )
(unless (eq keys t)
(if (not (consp keys))
(setq keys (list keys)) )
(dolist (key keys)
(instrf code
`(eql-key ,key) `(jump-true ,start) ) )
(instrf code `(jump ,next) start) )
(compile-stmts code stmts new-env new-height)
(instrf code `(jump ,end) next) ) )
(instrf code end '(pop-discard 1)) ) )
(def-compile and (code env height &rest exprs)
(let ( (end (gensym)))
(instrf code '(setit t))
(dolist (expr exprs)
(compilef code expr env height)
(instrf code `(jump-not-true ,end)) )
(instrf code end) ) )
(def-compile or (code env height &rest exprs)
(let ( (end (gensym)))
(instrf code '(setit nil))
(dolist (expr exprs)
(compilef code expr env height)
(instrf code `(jump-true ,end)) )
(instrf code end) ) )
(def-compile let (code env height decls &rest stmts)
(let ( (new-env env)
(new-height height)
(numvars 0) )
(dolist (decl decls)
(let (var init var-creator)
(if (symbolp decl)
(progn (setq var decl) (setq init nil))
(progn (setq var (first decl)) (setq init (second decl))) )
(_check-var-name var)
(setq var-creator (list 'push-stack-var)) ; note: must use list
(compilef code init (cons numvars env) new-height)
(instrf code var-creator)
(incf numvars)
(pushf new-env (list 'stack var var-creator))
(incf new-height) ) )
(compile-stmts code stmts new-env (_env-height-checked new-height))
(instrf code `(pop-discard ,numvars)) ) )
(def-compile let* (code env height decls &rest stmts)
(let ( (new-env env)
(new-height height)
(numvars 0) )
(dolist (decl decls)
(let (var init var-creator)
(if (symbolp decl)
(progn (setq var decl) (setq init nil))
(progn (setq var (first decl)) (setq init (second decl))) )
(_check-var-name var)
(setq var-creator (list 'push-stack-var)) ; note: must use list
(compilef code init new-env new-height)
(instrf code var-creator)
(pushf new-env (list 'stack var var-creator))
(incf new-height)
(incf numvars) ) )
(compile-stmts code stmts new-env (_env-height-checked new-height))
(instrf code `(pop-discard ,numvars)) ) )
(def-compile setq (code env height &rest args)
(let ( (is-var t) var value)
(if (null args)
(instrf code '(setit nil)) )
(dolist (arg args)
(if is-var
(setq var arg)
(progn
(setq value arg)
(compilef code value env height)
(setf code (_compile-set-symbol code var env)) ) )
(setq is-var (not is-var)) )
(if (not is-var)
(error "Odd number of args to setq") )
code) )
(def-compile psetq (code env height &rest args)
(let ( (is-var t) (numvalues 0)
value (vars nil) )
(if (null args)
(instrf code '(setit nil)) )
(dolist (arg args)
(if is-var
(pushf vars arg)
(progn
(setq value arg)
(compilef code value (cons numvalues env) (+ numvalues height))
(instrf code '(pushit))
(incf numvalues) ) )
(setq is-var (not is-var)) )
(_env-height-checked (+ numvalues height))
(if (not is-var)
(error "Odd number of args to psetq") )
(dolist (var vars)
(instrf code '(popit))
(decf numvalues)
(setf code (_compile-set-symbol code var (cons numvalues env))) )
code) )
(def-compile defun (code env height name args &rest stmts)
(_compile code
`(progn
((setf symbol-function) ',name #'(lambda ,args ,@stmts))
',name) env height) )
(def-compile defmacro (code env height name args &rest stmts)
(_compile code
`(progn
((setf symbol-function) ',name (macro-of-function #'(lambda ,args ,@stmts)))
',name) env height) )
(def-compile defsetf (code env height name fun)
(instrf code `(interpret (defsetf ,name ,fun))) )
(def-compile defconstant (code env height name value)
(_env-height-checked 2)
(compilef code value env height)
(instrf code '(pushit)
`(setit ,name) '(pushit) '(defconstant) ) )
(def-compile defstruct (code env height name &rest fields)
(instrf code `(interpret (defstruct ,name ,@fields)) ) )
(def-compile with-struct (code env height type-and-struct &rest stmts)
(let* ( (type (first type-and-struct)) (struct (second type-and-struct))
(new-env `((field ,(struct-fields type)) ,@env))
(new-height (_env-height-checked (1+ height))) )
(compilef code struct env height)
(instrf code `(check-struct ,type) '(pushit))
(compile-stmts code stmts new-env new-height)
(instrf code '(pop-discard 1)) ) )
(defun _bq-is-const (expr depth)
(if (and (true-listp expr) (= (length expr) 2))
(case (car expr)
(backquote (_bq-is-const (second expr) (1+ depth)))
((comma comma-at)
(if (= depth 0)
nil
(_bq-is-const (second expr) (1- depth)) ) )
(t (and (_bq-is-const (car expr) depth)
(_bq-is-const (cdr expr) depth) )) )
(if (consp expr)
(and (_bq-is-const (car expr) depth)
(_bq-is-const (cdr expr) depth) )
t) ) )
(defun _backquote-expand-cons (expr depth)
(let ( (expanded-head (_backquote-expand1 (car expr) depth))
(expanded-tail (_backquote-expand1 (cdr expr) depth)) )
(if (eq (car expanded-tail) 'splice)
(error "Invalid position for comma-at" expr) )
(if (eq (car expanded-head) 'splice)
`(eval (append ,(second expanded-head) ,(second expanded-tail)))
`(eval (cons ,(second expanded-head) ,(second expanded-tail))) ) ) )
(defun _backquote-expand1 (expr depth)
(if (_bq-is-const expr depth)
`(eval (quote ,expr))
(let ( (is-2-long (= (length expr) 2))
(head (car expr)) )
(cond
((and is-2-long (eq head 'backquote))
(_backquote-expand-cons expr (1+ depth)) )
((and is-2-long (eq head 'comma))
(if (= depth 0)
(list 'eval (second expr))
(_backquote-expand-cons expr (1- depth)) ) )
((and is-2-long (eq head 'comma-at))
(if (= depth 0)
(list 'splice (second expr))
(_backquote-expand-cons expr (1- depth)) ) )
(t (_backquote-expand-cons expr depth)) ) ) ) )
(defun _backquote-expand (expr)
(let ( (result (_backquote-expand1 expr 0)) )
(case (car result)
(eval (second result))
(splice (error "Invalid position for comma-at" expr)) ) ) )
(def-compile backquote (code env height expr)
(compilef code (_backquote-expand expr) env height) )
(def-compile catch (code env height tag-expr &rest forms)
(compilef code tag-expr env height)
(instrf code '(pushit)
`(catch ,(_make-code (_compile nil `(progn ,@forms) (cons 2 env)
(_env-height-checked (1+ height)) )) ) ) )
(def-compile unwind-protect (code env height expr &rest forms)
(let ( (inner-env (cons 2 env))
(inner-height (+ height 2))
(unwind-env (cons 3 env))
(unwind-height (_env-height-checked (+ height 3))) )
(instrf code
`(setit ,(_make-code (_compile nil expr inner-env inner-height )))
'(pushit)
`(unwind-protect ,(_make-code (_compile nil `(progn ,@forms)
unwind-env unwind-height)) ) ) ) )
(def-compile with-dc (code env height expr &rest forms)
(compilef code expr env height)
(instrf code '(pushit)
`(with-dc ,(_make-code (_compile nil `(progn ,@forms) (cons 2 env)
(_env-height-checked (+ height 2)))) ) ) )
(def-compile with-continuous-gc (code env height &rest forms)
(instrf code
`(with-continuous-gc ,(_make-code (_compile nil `(progn ,@forms)
(cons 1 env)
(_env-height-checked
(1+ height) ) )) ) ) )
(def-compile with-selected-objects (code env height expr &rest forms)
(compilef code expr env height)
(instrf code '(pushit)
`(with-selected-objects
,(_make-code (_compile nil `(progn ,@forms)
(cons 2 env)
(_env-height-checked
(+ height 2)))) ) ) )
(def-compile with-select (code env height objects &rest forms)
(compilef code `(with-selected-objects
(list ,@objects)
,@forms) env height) )
(def-compile cons (code env height arg1 arg2)
(compilef code arg1 env height)
(instrf code '(pushit))
(compilef code arg2 (cons 1 env)
(_env-height-checked (1+ height)))
(instrf code '(pushit) '(cons)) )
;;; post-compilation
(setq _*jump-ops* '(jump jump-true jump-not-true))
(defun _resolve-labels (instructions)
(let ( (pos 0)
(labels nil)
(new-instructions nil) )
(dolist (instr instructions)
(if (symbolp instr)
(pushf labels (cons instr pos))
(progn
(incf pos)
(if (not (true-listp instr))
(error "Invalid instruction" instr) )
(pushf new-instructions instr) ) ) )
(setq new-instructions (reverse new-instructions))
(setq pos 0)
(dolist (instr new-instructions)
(if (member (car instr) _*jump-ops*)
(let ( (jump-pos (assoc (second instr) labels)) )
(if (null jump-pos)
(error "Jump to non-existent label" (second instr)) )
(setf (second instr) (* 2 (- (cdr jump-pos) (1+ pos))) ) ) )
(incf pos) )
new-instructions) )
(defun _is-noop (instr)
(and (consp instr) (member (car instr) '(leave-on-stack))) )
(defun _push-version (instr)
(let ( (pair (assoc (car instr)
'( (setit . push-arg)
(stack-get . stack-get-pushit)
(call-with-num-args . call-and-pushit) ) ) ) )
(if (consp pair)
(cons (cdr pair) (rest instr))
nil) ) )
(defun _reverse-and-optimize (compiled)
(let ( (new-compiled nil) (pending-pushit nil) (push-version nil))
(dolist (instr compiled)
(when (not (_is-noop instr))
(if pending-pushit
(progn
(if (consp instr)
(setq push-version (_push-version instr))
(setq push-version nil) )
(if push-version
(setq new-compiled (cons push-version new-compiled))
(setq new-compiled (cons instr (cons '(pushit) new-compiled))) )
(setq pending-pushit nil) )
(progn
(setq pending-pushit (equal instr '(pushit)))
(if (not pending-pushit)
(setq new-compiled (cons instr new-compiled)) ) ) ) ) )
(if pending-pushit
(setq new-compiled (cons '(pushit) new-compiled)) )
new-compiled) )
(defun _make-exec-code (instrs)
(let ( (opcode-args nil) )
(dolist (instr instrs)
(case (length instr)
(1 (setq opcode-args (cons nil (cons (first instr) opcode-args))))
(2 (setq opcode-args (cons (second instr)
(cons (first instr) opcode-args))))
(t (error "Invalid instruction" instr)) ) )
(array-to-code (list-to-vector (reverse opcode-args))) ) )
(defun _post-compile (compiled)
(instrf compiled '(exit))
(dolist (instr compiled)
(if (consp instr)
(cond
((and (member (car instr) '(set get save-env)))
(_resolve-var-ref instr) )
((and (= (length instr) 2) (_is-code (second instr)))
(setf (second instr) (_post-compile (cdr (second instr)))) ) ) ) )
(let* ( (compiled-with-exit (_reverse-and-optimize compiled))
(resolved (_resolve-labels compiled-with-exit)) )
(_make-exec-code resolved) ) )
(defun _compile-toplevel (expr)
(progv '(*max-env-height*) '(0)
(let* ( (stack-checker (list 'check-stack 0))
(code (_compile (list stack-checker) (full-macroexpand expr) nil 0)) )
(setf (second stack-checker) *max-env-height*)
(_post-compile code) ) ) )
;;; lambda expr compilation
(defstruct _arglist args canonical-arglist varlist num-vars)
(defstruct _canonical-arglist
pos-args opt-args rest-arg kwd-args
allow-other-keys num-pos-args num-opt-args num-kwd-args
num-opt-vars num-kwd-vars opt-var-gaps kwd-list)
(defun _var-list (canonical-arglist)
(let ( (list nil) )
(with-struct (_canonical-arglist canonical-arglist)
(dolist (arg pos-args)
(pushf list arg) )
(dolist (arg opt-args)
(if (consp (first arg))
(progn
(pushf list (car (first arg)))
(pushf list (cdr (first arg))) )
(pushf list (first arg)) ) )
(dolist (arg rest-arg)
(rest (pushf list arg)) )
(dolist (arg kwd-args)
(if (consp (second arg))
(progn
(pushf list (car (second arg)))
(pushf list (cdr (second arg))) )
(pushf list (second arg)) ) ) )
(reverse list) ) )
(defun _analyze-args (arglist)
(let ( (state-pos -1)
(last-kwd '&positional)
(canonical-arglist (make-_canonical-arglist
:pos-args nil :opt-args nil
:rest-arg nil :kwd-args nil :kwd-list nil
:num-opt-vars 0 :num-kwd-vars 0
:opt-var-gaps nil) )
(lambda-kwd-list '(&optional &rest &key &allow-other-keys))
canonical-arg)
(if (not (true-listp arglist))
(error "Invalid argument list" arglist) )
(with-struct (_canonical-arglist canonical-arglist)
(setq allow-other-keys nil)
(dolist (arg arglist)
(let ( (kwd-pos (position arg lambda-kwd-list)) )
(if kwd-pos
(progn
(if (<= kwd-pos state-pos)
(error "Argument list keyword in wrong order" arg) )
(setq state-pos kwd-pos)
(setq last-kwd arg)
(if (eq arg '&allow-other-keys)
(if (and kwd-args rest-arg)
(setq allow-other-keys t)
(error "Can't have &allow-other-keys without &rest and &keys" arglist) ) ) )
(case last-kwd
(&positional
(_check-var-name arg)
(pushf pos-args arg) )
(&optional
(if (true-listp arg)
(let ( (arg-len (length arg))
arg-name arg-names suppliedp-arg (default nil))
(if (or (< arg-len 1) (> arg-len 3))
(error "Invalid optional arg" arg) )
(setq arg-name (first arg))
(incf num-opt-vars)
(_check-var-name arg-name)
(if (>= arg-len 2)
(setq default (second arg)) )
(if (= arg-len 3)
(progn
(pushf opt-var-gaps 2)
(setq suppliedp-arg (third arg))
(incf num-opt-vars)
(_check-var-name suppliedp-arg)
(setq arg-names (cons arg-name suppliedp-arg)) )
(progn
(setq arg-names arg-name)
(if opt-var-gaps (pushf opt-var-gaps 1)) ) )
(setq canonical-arg (list arg-names default)) )
(progn
(_check-var-name arg)
(incf num-opt-vars)
(if opt-var-gaps (pushf opt-var-gaps 1))
(setq canonical-arg (list arg nil)) ) )
(pushf opt-args canonical-arg) )
(&rest
(if rest-arg
(error "More than one &rest arg in arg list" arglist) )
(_check-var-name arg)
(setq rest-arg (list arg)) )
(&key
(setq allow-other-keys nil)
(let (kwd var
(has-suppliedp-var nil)
(suppliedp-var nil)
(default nil) )
(if (true-listp arg)
(let ( (arg-len (length arg)) )
(if (or (< arg-len 1) (> arg-len 3))
(error "Invalid keyword arg" arg) )
(let ( (arg-1 (first arg)) )
(if (and (true-listp arg-1) (= (length arg-1) 2))
(progn
(setq kwd (first arg-1))
(setq var (second arg-1)) )
(progn
(_check-var-name arg-1)
(setq kwd (keyword-of arg-1))
(setq var arg-1) ) ) )
(if (>= arg-len 2)
(setq default (second arg)) )
(when (>= arg-len 3)
(setq suppliedp-var (third arg))
(setq has-suppliedp-var t)
)
)
(progn
(_check-var-name arg)
(setq kwd (keyword-of arg))
(setq var arg)
) )
(_check-var-name var)
(pushf kwd-list (cons kwd num-kwd-vars))
(incf num-kwd-vars)
(when has-suppliedp-var
(_check-var-name suppliedp-var)
(incf num-kwd-vars) )
(if has-suppliedp-var
(setq canonical-arg
(list kwd (cons var suppliedp-var) default) )
(setq canonical-arg
(list kwd var default) ) ) )
(pushf kwd-args canonical-arg) )
(&allow-other-keys
(error "Can't have args following &allow-other-keys" arg) )
(t (error "Invalid last argument list keyword" last-kwd)) ) ) ) )
(setq pos-args (reverse pos-args))
(setq num-pos-args (length pos-args))
(setq opt-args (reverse opt-args))
(setq num-opt-args (length opt-args))
(setq kwd-args (reverse kwd-args))
(setq num-kwd-args (length kwd-args))
(setq kwd-list (reverse kwd-list)) )
(let ( (result
(make-_arglist
:args arglist :canonical-arglist canonical-arglist ) ) )
(with-struct (_arglist result)
(setf varlist (_var-list canonical-arglist))
(setf num-vars (length varlist)) )
result) ) )
(defun _arg-env (varlist)
(let ( (offset 1) (env nil) )
(dolist (var (reverse varlist))
(pushf env (list 'stack var (list 'leave-on-stack offset)))
(incf offset) )
(reverse env)) )
(defun _copy-env (env)
(let ( (new-env nil) )
(dolist (elt env)
(if (consp elt)
(pushf new-env (list 'uncopied elt (list 'dont-save elt))) ) )
(reverse new-env) ) )
(defun _compile-args-expander (code arglist)
(with-struct (_arglist arglist)
(with-struct (_canonical-arglist canonical-arglist)
(let ( (is-simple (not (or rest-arg kwd-args opt-args))) )
(if is-simple
(instrf code `(check-num-args ,num-pos-args))
(progn
(instrf code `(set-num-vars ,num-vars) `(check-min-num-args ,num-pos-args))
(if (not (or rest-arg kwd-args))
(instrf code `(check-max-num-args ,(+ num-pos-args num-opt-args))) )
(if (or rest-arg kwd-args)
(instrf code
`(shift-rest-args ,(+ num-pos-args num-opt-args)) ) )
(when opt-args
(instrf code
`(fill-out-opt-args ,(+ num-pos-args num-opt-args)) )
(when opt-var-gaps
(instrf code
`(set-opt-vars-top ,(+ num-pos-args num-opt-vars)) )
(dolist (opt-var-gap opt-var-gaps)
(instrf code
`(set-opt-var ,opt-var-gap) ) ) ) )
(if rest-arg
(instrf code
`(get-rest-arg ,(+ num-pos-args num-opt-vars)) ) )
(when kwd-args
(instrf code
`(init-kwd-args ,num-kwd-vars) )
(if allow-other-keys
(instrf code '(allow-other-keys)) )
(instrf code
`(get-kwd-args ,kwd-list) ) )
(instrf code `(reset-arg-stack)) ) ) ) ) )
code)
(defun _compile-opt-default-getter (code opt-arg arg-env saved-env height)
(let ( (arg-names (first opt-arg))
(default (second opt-arg))
var
(end (gensym)) )
(if (consp arg-names)
(setq var (car arg-names))
(setq var arg-names) )
(instrf code `(get ,var ,arg-env) '(test-suppliedp)
`(jump-true ,end) )
(compilef code default saved-env height)
(instrf code `(set ,var ,arg-env) end) ) )
(defun _compile-kwd-default-getter (code opt-arg arg-env saved-env height)
(let ( (arg-names (second opt-arg))
(default (third opt-arg))
var suppliedp-var
(middle (gensym)) (end (gensym)) )
(if (consp arg-names)
(progn
(setq var (car arg-names))
(setq suppliedp-var (cdr arg-names))
(instrf code
`(get ,var ,arg-env) '(test-suppliedp)
`(jump-true ,middle) )
(compilef code default saved-env height)
(instrf code `(set ,var ,arg-env)
'(setit nil) `(set ,suppliedp-var ,arg-env)
`(jump ,end)
middle
'(setit t) `(set ,suppliedp-var ,arg-env) end) )
(progn
(setq var arg-names)
(instrf code
`(get ,var ,arg-env) '(test-suppliedp)
`(jump-true ,end) )
(compilef code default saved-env height)
(instrf code
`(set ,var ,arg-env) end) ) ) ) )
(defun _compile-defaults-getters (code canonical-arglist arg-env saved-env height)
(with-struct (_canonical-arglist canonical-arglist)
(dolist (opt-arg opt-args)
(setf code (_compile-opt-default-getter code opt-arg
arg-env saved-env height)) )
(dolist (kwd-arg kwd-args)
(setf code (_compile-kwd-default-getter code kwd-arg
arg-env saved-env height)) kwd-args)
code) )
(defun _compile-lambda-function (code args body env height)
(if (not (true-listp args))
(error "Invalid function argument list" args) )
(if (not (true-listp body))
(error "Invalid function body" body) )
(let* ( (arglist (_analyze-args args))
(varlist (_arglist-varlist arglist))
(arg-env (_arg-env varlist))
(saved-env (_copy-env env))
(save-list (mapcar #'third saved-env))
(new-env (append arg-env saved-env))
(new-height (+ height (length varlist)))
(function-code nil)
(stack-checker (list 'check-stack 0)) )
(with-struct (_arglist arglist)
(progv '(*max-env-height*) (list new-height)
(setf function-code (_compile-args-expander function-code arglist))
(instrf function-code
`(dump-info ,(cons (length varlist) (cons nil varlist)))
stack-checker)
(setf function-code (_compile-defaults-getters function-code
canonical-arglist arg-env
(cons num-vars saved-env) new-height) )
(dolist (arg arg-env)
(instrf function-code (third arg)) )
(compilef function-code `(progn ,@body) new-env new-height)
(instrf function-code '(undump-info))
(setf (second stack-checker) *max-env-height*) )
(setq function-code (_make-code function-code))
(if saved-env
(instrf code `(save-env ,save-list ,env) `(make-closure ,function-code))
(instrf code `(setit ,function-code)) ) ) ) )
(def-compile function (code env height expr)
(if (symbolp expr)
(instrf code `(get-fun-with-name ,expr))
(progn
(if (not (true-listp expr))
(error "Invalid arg to function, not a list or symbol" expr) )
(if (not (eq (car expr) 'lambda))
(error "Invalid arg to function, list is not a lambda expression"
expr) )
(if (< (length expr) 2)
(error "Invalid lambda list, has no arguments") )
(setf code
(_compile-lambda-function code (second expr) (cddr expr) env height) ) ) ) )
;;; file compilation
(defun compile-and-load (infile-name outfile-name)
(let ( (the-compiler (the-compiler)) )
(if (null the-compiler)
(error "the-compiler is undefined") )
(with-open-file infile-name infile :input
(with-open-file outfile-name outfile :output
(while (not (eofp infile))
(let* ( (expr (read infile))
(compiled-expr (funcall the-compiler expr)) )
(format t "Compiled ~A~%" expr)
(print compiled-expr outfile)
(eval compiled-expr) ) ) ) ) )
outfile-name)
(setf (the-compiler) #'_compile-toplevel)