; Complete source for Twobit and Sparc assembler in one file. ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; See 'twobit-benchmark', at end. ; Copyright 1998 Lars T Hansen. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Completely fundamental pathname manipulation. ; This takes zero or more directory components and a file name and ; constructs a filename relative to the current directory. (define (make-relative-filename . components) (define (construct l) (if (null? (cdr l)) l (cons (car l) (cons "/" (construct (cdr l)))))) (if (null? (cdr components)) (car components) (apply string-append (construct components)))) ; This takes one or more directory components and constructs a ; directory name with proper termination (a crock -- we can finess ; this later). (define (pathname-append . components) (define (construct l) (cond ((null? (cdr l)) l) ((string=? (car l) "") (construct (cdr l))) ((char=? #\/ (string-ref (car l) (- (string-length (car l)) 1))) (cons (car l) (construct (cdr l)))) (else (cons (car l) (cons "/" (construct (cdr l))))))) (let ((n (if (null? (cdr components)) (car components) (apply string-append (construct components))))) (if (not (char=? #\/ (string-ref n (- (string-length n) 1)))) (string-append n "/") n))) ; eof ; Copyright 1998 Lars T Hansen. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Nbuild parameters for SPARC Larceny. (define (make-nbuild-parameter dir source? verbose? hostdir hostname) (let ((parameters `((compiler . ,(pathname-append dir "Compiler")) (util . ,(pathname-append dir "Util")) (build . ,(pathname-append dir "Rts" "Build")) (source . ,(pathname-append dir "Lib")) (common-source . ,(pathname-append dir "Lib" "Common")) (repl-source . ,(pathname-append dir "Repl")) (interp-source . ,(pathname-append dir "Eval")) (machine-source . ,(pathname-append dir "Lib" "Sparc")) (common-asm . ,(pathname-append dir "Asm" "Common")) (sparc-asm . ,(pathname-append dir "Asm" "Sparc")) (target-machine . SPARC) (endianness . big) (word-size . 32) (always-source? . ,source?) (verbose-load? . ,verbose?) (compatibility . ,(pathname-append dir "Compat" hostdir)) (host-system . ,hostname) ))) (lambda (key) (let ((probe (assq key parameters))) (if probe (cdr probe) #f))))) (define nbuild-parameter (make-nbuild-parameter "" #f #f "Larceny" "Larceny")) ; eof ; Copyright 1998 Lars T Hansen. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Useful list functions. ; ; Notes: ; * Reduce, reduce-right, fold-right, fold-left are compatible with MIT Scheme. ; * Make-list is compatible with MIT Scheme and Chez Scheme. ; * These are not (yet) compatible with Shivers's proposed list functions. ; * remq, remv, remove, remq!, remv!, remov!, every?, and some? are in the ; basic library. ; Destructively remove all associations whose key matches `key' from `alist'. (define (aremq! key alist) (cond ((null? alist) alist) ((eq? key (caar alist)) (aremq! key (cdr alist))) (else (set-cdr! alist (aremq! key (cdr alist))) alist))) (define (aremv! key alist) (cond ((null? alist) alist) ((eqv? key (caar alist)) (aremv! key (cdr alist))) (else (set-cdr! alist (aremv! key (cdr alist))) alist))) (define (aremove! key alist) (cond ((null? alist) alist) ((equal? key (caar alist)) (aremove! key (cdr alist))) (else (set-cdr! alist (aremove! key (cdr alist))) alist))) ; Return a list of elements of `list' selected by the predicate. (define (filter select? list) (cond ((null? list) list) ((select? (car list)) (cons (car list) (filter select? (cdr list)))) (else (filter select? (cdr list))))) ; Return the first element of `list' selected by the predicate. (define (find selected? list) (cond ((null? list) #f) ((selected? (car list)) (car list)) (else (find selected? (cdr list))))) ; Return a list with all duplicates (according to predicate) removed. (define (remove-duplicates list same?) (define (member? x list) (cond ((null? list) #f) ((same? x (car list)) #t) (else (member? x (cdr list))))) (cond ((null? list) list) ((member? (car list) (cdr list)) (remove-duplicates (cdr list) same?)) (else (cons (car list) (remove-duplicates (cdr list) same?))))) ; Return the least element of `list' according to some total order. (define (least less? list) (reduce (lambda (a b) (if (less? a b) a b)) #f list)) ; Return the greatest element of `list' according to some total order. (define (greatest greater? list) (reduce (lambda (a b) (if (greater? a b) a b)) #f list)) ; (mappend p l) = (apply append (map p l)) (define (mappend proc l) (apply append (map proc l))) ; (make-list n) => (a1 ... an) for some ai ; (make-list n x) => (a1 ... an) where ai = x (define (make-list nelem . rest) (let ((val (if (null? rest) #f (car rest)))) (define (loop n l) (if (zero? n) l (loop (- n 1) (cons val l)))) (loop nelem '()))) ; (reduce p x ()) => x ; (reduce p x (a)) => a ; (reduce p x (a b ...)) => (p (p a b) ...)) (define (reduce proc initial l) (define (loop val l) (if (null? l) val (loop (proc val (car l)) (cdr l)))) (cond ((null? l) initial) ((null? (cdr l)) (car l)) (else (loop (car l) (cdr l))))) ; (reduce-right p x ()) => x ; (reduce-right p x (a)) => a ; (reduce-right p x (a b ...)) => (p a (p b ...)) (define (reduce-right proc initial l) (define (loop l) (if (null? (cdr l)) (car l) (proc (car l) (loop (cdr l))))) (cond ((null? l) initial) ((null? (cdr l)) (car l)) (else (loop l)))) ; (fold-left p x (a b ...)) => (p (p (p x a) b) ...) (define (fold-left proc initial l) (if (null? l) initial (fold-left proc (proc initial (car l)) (cdr l)))) ; (fold-right p x (a b ...)) => (p a (p b (p ... x))) (define (fold-right proc initial l) (if (null? l) initial (proc (car l) (fold-right proc initial (cdr l))))) ; (iota n) => (0 1 2 ... n-1) (define (iota n) (let loop ((n (- n 1)) (r '())) (let ((r (cons n r))) (if (= n 0) r (loop (- n 1) r))))) ; (list-head (a1 ... an) m) => (a1 ... am) for m <= n (define (list-head l n) (if (zero? n) '() (cons (car l) (list-head (cdr l) (- n 1))))) ; eof ; Copyright 1998 Lars T Hansen. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Larceny -- compatibility library for Twobit running under Larceny. (define ($$trace x) #t) (define host-system 'larceny) ; Temporary? (define (.check! flag exn . args) (if (not flag) (apply error "Runtime check exception: " exn args))) ; The compatibility library loads Auxlib if compat:initialize is called ; without arguments. Compat:load will load fasl files when appropriate. (define (compat:initialize . rest) (if (null? rest) (let ((dir (nbuild-parameter 'compatibility))) (compat:load (string-append dir "compat2.sch")) (compat:load (string-append dir "../../Auxlib/list.sch")) (compat:load (string-append dir "../../Auxlib/pp.sch"))))) (define (with-optimization level thunk) (thunk)) ; Calls thunk1, and if thunk1 causes an error to be signalled, calls thunk2. (define (call-with-error-control thunk1 thunk2) (let ((eh (error-handler))) (error-handler (lambda args (error-handler eh) (thunk2) (apply eh args))) (thunk1) (error-handler eh))) (define (larc-new-extension fn ext) (let* ((l (string-length fn)) (x (let loop ((i (- l 1))) (cond ((< i 0) #f) ((char=? (string-ref fn i) #\.) (+ i 1)) (else (loop (- i 1))))))) (if (not x) (string-append fn "." ext) (string-append (substring fn 0 x) ext)))) (define (compat:load filename) (define (loadit fn) (if (nbuild-parameter 'verbose-load?) (format #t "~a~%" fn)) (load fn)) (if (nbuild-parameter 'always-source?) (loadit filename) (let ((fn (larc-new-extension filename "fasl"))) (if (and (file-exists? fn) (compat:file-newer? fn filename)) (loadit fn) (loadit filename))))) (define (compat:file-newer? a b) (let* ((ta (file-modification-time a)) (tb (file-modification-time b)) (limit (vector-length ta))) (let loop ((i 0)) (cond ((= i limit) #f) ((= (vector-ref ta i) (vector-ref tb i)) (loop (+ i 1))) (else (> (vector-ref ta i) (vector-ref tb i))))))) ; eof ; Copyright 1998 Lars T Hansen. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Larceny -- second part of compatibility code ; This file ought to be compiled, but doesn't have to be. ; ; 12 April 1999 (define host-system 'larceny) ; Don't remove this! ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; A well-defined sorting procedure. (define compat:sort (lambda (list less?) (sort list less?))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; Well-defined character codes. ; Returns the UCS-2 code for a character. (define compat:char->integer char->integer) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; Input and output (define (write-lop item port) (lowlevel-write item port) (newline port) (newline port)) (define write-fasl-datum lowlevel-write) ; The power of self-hosting ;-) (define (misc->bytevector x) (let ((bv (bytevector-like-copy x))) (typetag-set! bv $tag.bytevector-typetag) bv)) (define string->bytevector misc->bytevector) (define bignum->bytevector misc->bytevector) (define (flonum->bytevector x) (clear-first-word (misc->bytevector x))) (define (compnum->bytevector x) (clear-first-word (misc->bytevector x))) ; Clears garbage word of compnum/flonum; makes regression testing much ; easier. (define (clear-first-word bv) (bytevector-like-set! bv 0 0) (bytevector-like-set! bv 1 0) (bytevector-like-set! bv 2 0) (bytevector-like-set! bv 3 0) bv) (define (list->bytevector l) (let ((b (make-bytevector (length l)))) (do ((i 0 (+ i 1)) (l l (cdr l))) ((null? l) b) (bytevector-set! b i (car l))))) (define bytevector-word-ref (let ((two^8 (expt 2 8)) (two^16 (expt 2 16)) (two^24 (expt 2 24))) (lambda (bv i) (+ (* (bytevector-ref bv i) two^24) (* (bytevector-ref bv (+ i 1)) two^16) (* (bytevector-ref bv (+ i 2)) two^8) (bytevector-ref bv (+ i 3)))))) (define (twobit-format fmt . rest) (let ((out (open-output-string))) (apply format out fmt rest) (get-output-string out))) ; This needs to be a random number in both a weaker and stronger sense ; than `random': it doesn't need to be a truly random number, so a sequence ; of calls can return a non-random sequence, but if two processes generate ; two sequences, then those sequences should not be the same. ; ; Gross, huh? (define (an-arbitrary-number) (system "echo \\\"`date`\\\" > a-random-number") (let ((x (string-hash (call-with-input-file "a-random-number" read)))) (delete-file "a-random-number") x)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; Miscellaneous (define cerror error) ; eof ; Copyright 1991 Wiliam Clinger. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; Sets represented as lists. ; ; 5 April 1999. (define (empty-set) '()) (define (empty-set? x) (null? x)) (define (make-set x) (define (loop x y) (cond ((null? x) y) ((member (car x) y) (loop (cdr x) y)) (else (loop (cdr x) (cons (car x) y))))) (loop x '())) (define (set-equal? x y) (and (subset? x y) (subset? y x))) (define (subset? x y) (every? (lambda (x) (member x y)) x)) ; To get around MacScheme's limit on the number of arguments. (define apply-union) (define union (letrec ((union2 (lambda (x y) (cond ((null? x) y) ((member (car x) y) (union2 (cdr x) y)) (else (union2 (cdr x) (cons (car x) y))))))) (set! apply-union (lambda (sets) (do ((sets sets (cdr sets)) (result '() (union2 (car sets) result))) ((null? sets) result)))) (lambda args (cond ((null? args) '()) ((null? (cdr args)) (car args)) ((null? (cddr args)) (union2 (car args) (cadr args))) (else (union2 (union2 (car args) (cadr args)) (apply union (cddr args)))))))) (define intersection (letrec ((intersection2 (lambda (x y) (cond ((null? x) '()) ((member (car x) y) (cons (car x) (intersection2 (cdr x) y))) (else (intersection2 (cdr x) y)))))) (lambda args (cond ((null? args) '()) ((null? (cdr args)) (car args)) ((null? (cddr args)) (intersection2 (car args) (cadr args))) (else (intersection2 (intersection2 (car args) (cadr args)) (apply intersection (cddr args)))))))) (define (difference x y) (cond ((null? x) '()) ((member (car x) y) (difference (cdr x) y)) (else (cons (car x) (difference (cdr x) y))))) ; Reasonably portable hashing on EQ?, EQV?, EQUAL?. ; Requires bignums, SYMBOL-HASH. ; ; Given any Scheme object, returns a non-negative exact integer ; less than 2^24. (define object-hash (lambda (x) 0)) ; hash on EQ?, EQV? (define equal-hash (lambda (x) 0)) ; hash on EQUAL? (let ((n 16777216) (n-1 16777215) (adj:fixnum 9000000) (adj:negative 8000000) (adj:large 7900000) (adj:ratnum 7800000) (adj:complex 7700000) (adj:flonum 7000000) (adj:compnum 6900000) (adj:char 6111000) (adj:string 5022200) (adj:vector 4003330) (adj:misc 3000444) (adj:pair 2555000) (adj:proc 2321001) (adj:iport 2321002) (adj:oport 2321003) (adj:weird 2321004) (budget0 32)) (define (combine hash adjustment) (modulo (+ hash hash hash adjustment) 16777216)) (define (hash-on-equal x budget) (if (> budget 0) (cond ((string? x) (string-hash x)) ((pair? x) (let ((budget (quotient budget 2))) (combine (hash-on-equal (car x) budget) (hash-on-equal (cdr x) budget)))) ((vector? x) (let ((n (vector-length x)) (budget (quotient budget 4))) (if (> n 0) (combine (combine (hash-on-equal (vector-ref x 0) budget) (hash-on-equal (vector-ref x (- n 1)) budget)) (hash-on-equal (vector-ref x (quotient n 2)) (+ budget budget))) adj:vector))) (else (object-hash x))) adj:weird)) (set! object-hash (lambda (x) (cond ((symbol? x) (symbol-hash x)) ((number? x) (if (exact? x) (cond ((integer? x) (cond ((negative? x) (combine (object-hash (- x)) adj:negative)) ((< x n) (combine x adj:fixnum)) (else (combine (modulo x n) adj:large)))) ((rational? x) (combine (combine (object-hash (numerator x)) adj:ratnum) (object-hash (denominator x)))) ((real? x) adj:weird) ((complex? x) (combine (combine (object-hash (real-part x)) adj:complex) (object-hash (imag-part x)))) (else adj:weird)) (cond (#t ; We can't really do anything with inexact numbers ; unless infinities and NaNs behave reasonably. adj:flonum) ((rational? x) (combine (combine (object-hash (inexact->exact (numerator x))) adj:flonum) (object-hash (inexact->exact (denominator x))))) ((real? x) adj:weird) ((complex? x) (combine (combine (object-hash (real-part x)) adj:compnum) (object-hash (imag-part x)))) (else adj:weird)))) ((char? x) (combine (char->integer x) adj:char)) ((string? x) (combine (string-length x) adj:string)) ((vector? x) (combine (vector-length x) adj:vector)) ((eq? x #t) (combine 1 adj:misc)) ((eq? x #f) (combine 2 adj:misc)) ((null? x) (combine 3 adj:misc)) ((pair? x) adj:pair) ((procedure? x) adj:proc) ((input-port? x) adj:iport) ((output-port? x) adj:oport) (else adj:weird)))) (set! equal-hash (lambda (x) (hash-on-equal x budget0)))); Hash tables. ; Requires CALL-WITHOUT-INTERRUPTS. ; This code should be thread-safe provided VECTOR-REF is atomic. ; ; (make-hashtable ) ; ; Returns a newly allocated mutable hash table ; using as the hash function ; and , e.g. ASSQ, ASSV, ASSOC, to search a bucket ; with buckets at first, expanding the number of buckets as needed. ; The must accept a key and return a non-negative exact ; integer. ; ; (make-hashtable ) ; ; Equivalent to (make-hashtable n) ; for some value of n chosen by the implementation. ; ; (make-hashtable ) ; ; Equivalent to (make-hashtable assv). ; ; (make-hashtable) ; ; Equivalent to (make-hashtable object-hash assv). ; ; (hashtable-contains? ) ; ; Returns true iff the contains an entry for . ; ; (hashtable-fetch ) ; ; Returns the value associated with in the if the ; contains ; otherwise returns . ; ; (hashtable-get ) ; ; Equivalent to (hashtable-fetch #f) ; ; (hashtable-put! ) ; ; Changes the to associate with , replacing ; any existing association for . ; ; (hashtable-remove! ) ; ; Removes any association for within the . ; ; (hashtable-clear! ) ; ; Removes all associations from the . ; ; (hashtable-size ) ; ; Returns the number of keys contained within the . ; ; (hashtable-for-each ) ; ; The must accept two arguments, a key and the value ; associated with that key. Calls the once for each ; key-value association. The order of these calls is indeterminate. ; ; (hashtable-map ) ; ; The must accept two arguments, a key and the value ; associated with that key. Calls the once for each ; key-value association, and returns a list of the results. The ; order of the calls is indeterminate. ; ; (hashtable-copy ) ; ; Returns a copy of the . ; These global variables are assigned new values later. (define make-hashtable (lambda args '*)) (define hashtable-contains? (lambda (ht key) #f)) (define hashtable-fetch (lambda (ht key flag) flag)) (define hashtable-get (lambda (ht key) (hashtable-fetch ht key #f))) (define hashtable-put! (lambda (ht key val) '*)) (define hashtable-remove! (lambda (ht key) '*)) (define hashtable-clear! (lambda (ht) '*)) (define hashtable-size (lambda (ht) 0)) (define hashtable-for-each (lambda (ht proc) '*)) (define hashtable-map (lambda (ht proc) '())) (define hashtable-copy (lambda (ht) ht)) ; Implementation. ; A hashtable is represented as a vector of the form ; ; #(("HASHTABLE") ) ; ; where is the number of associations within the hashtable, ; is the hash function, is the bucket searcher, ; and is a vector of buckets. ; ; The and fields are constant, but ; the and fields are mutable. ; ; For thread-safe operation, the mutators must modify both ; as an atomic operation. Other operations do not require ; critical sections provided VECTOR-REF is an atomic operation ; and the operation does not modify the hashtable, does not ; reference the field, and fetches the ; field exactly once. (let ((doc (list "HASHTABLE")) (count (lambda (ht) (vector-ref ht 1))) (count! (lambda (ht n) (vector-set! ht 1 n))) (hasher (lambda (ht) (vector-ref ht 2))) (searcher (lambda (ht) (vector-ref ht 3))) (buckets (lambda (ht) (vector-ref ht 4))) (buckets! (lambda (ht v) (vector-set! ht 4 v))) (defaultn 10)) (let ((hashtable? (lambda (ht) (and (vector? ht) (= 5 (vector-length ht)) (eq? doc (vector-ref ht 0))))) (hashtable-error (lambda (x) (display "ERROR: Bad hash table: ") (newline) (write x) (newline)))) ; Internal operations. (define (make-ht hashfun searcher size) (vector doc 0 hashfun searcher (make-vector size '()))) ; Substitute x for the first occurrence of y within the list z. ; y is known to occur within z. (define (substitute1 x y z) (cond ((eq? y (car z)) (cons x (cdr z))) (else (cons (car z) (substitute1 x y (cdr z)))))) ; Remove the first occurrence of x from y. ; x is known to occur within y. (define (remq1 x y) (cond ((eq? x (car y)) (cdr y)) (else (cons (car y) (remq1 x (cdr y)))))) (define (resize ht0) (call-without-interrupts (lambda () (let ((ht (make-ht (hasher ht0) (searcher ht0) (+ 1 (* 2 (count ht0)))))) (ht-for-each (lambda (key val) (put! ht key val)) ht0) (buckets! ht0 (buckets ht)))))) ; Returns the contents of the hashtable as a vector of pairs. (define (contents ht) (let* ((v (buckets ht)) (n (vector-length v)) (z (make-vector (count ht) '()))) (define (loop i bucket j) (if (null? bucket) (if (= i n) (if (= j (vector-length z)) z (begin (display "BUG in hashtable") (newline) '#())) (loop (+ i 1) (vector-ref v i) j)) (let ((entry (car bucket))) (vector-set! z j (cons (car entry) (cdr entry))) (loop i (cdr bucket) (+ j 1))))) (loop 0 '() 0))) (define (contains? ht key) (if (hashtable? ht) (let* ((v (buckets ht)) (n (vector-length v)) (h (modulo ((hasher ht) key) n)) (b (vector-ref v h))) (if ((searcher ht) key b) #t #f)) (hashtable-error ht))) (define (fetch ht key flag) (if (hashtable? ht) (let* ((v (buckets ht)) (n (vector-length v)) (h (modulo ((hasher ht) key) n)) (b (vector-ref v h)) (probe ((searcher ht) key b))) (if probe (cdr probe) flag)) (hashtable-error ht))) (define (put! ht key val) (if (hashtable? ht) (call-without-interrupts (lambda () (let* ((v (buckets ht)) (n (vector-length v)) (h (modulo ((hasher ht) key) n)) (b (vector-ref v h)) (probe ((searcher ht) key b))) (if probe ; Using SET-CDR! on the probe would make it necessary ; to synchronize the CONTENTS routine. (vector-set! v h (substitute1 (cons key val) probe b)) (begin (count! ht (+ (count ht) 1)) (vector-set! v h (cons (cons key val) b)) (if (> (count ht) n) (resize ht))))) #f)) (hashtable-error ht))) (define (remove! ht key) (if (hashtable? ht) (call-without-interrupts (lambda () (let* ((v (buckets ht)) (n (vector-length v)) (h (modulo ((hasher ht) key) n)) (b (vector-ref v h)) (probe ((searcher ht) key b))) (if probe (begin (count! ht (- (count ht) 1)) (vector-set! v h (remq1 probe b)) (if (< (* 2 (+ defaultn (count ht))) n) (resize ht)))) #f))) (hashtable-error ht))) (define (clear! ht) (if (hashtable? ht) (call-without-interrupts (lambda () (begin (count! ht 0) (buckets! ht (make-vector defaultn '())) #f))) (hashtable-error ht))) (define (size ht) (if (hashtable? ht) (count ht) (hashtable-error ht))) ; This code must be written so that the procedure can modify the ; hashtable without breaking any invariants. (define (ht-for-each f ht) (if (hashtable? ht) (let* ((v (contents ht)) (n (vector-length v))) (do ((j 0 (+ j 1))) ((= j n)) (let ((x (vector-ref v j))) (f (car x) (cdr x))))) (hashtable-error ht))) (define (ht-map f ht) (if (hashtable? ht) (let* ((v (contents ht)) (n (vector-length v))) (do ((j 0 (+ j 1)) (results '() (let ((x (vector-ref v j))) (cons (f (car x) (cdr x)) results)))) ((= j n) (reverse results)))) (hashtable-error ht))) (define (ht-copy ht) (if (hashtable? ht) (let* ((newtable (make-hashtable (hasher ht) (searcher ht) 0)) (v (buckets ht)) (n (vector-length v)) (newvector (make-vector n '()))) (count! newtable (count ht)) (buckets! newtable newvector) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! newvector i (append (vector-ref v i) '()))) newtable) (hashtable-error ht))) ; External entry points. (set! make-hashtable (lambda args (let* ((hashfun (if (null? args) object-hash (car args))) (searcher (if (or (null? args) (null? (cdr args))) assv (cadr args))) (size (if (or (null? args) (null? (cdr args)) (null? (cddr args))) defaultn (caddr args)))) (make-ht hashfun searcher size)))) (set! hashtable-contains? (lambda (ht key) (contains? ht key))) (set! hashtable-fetch (lambda (ht key flag) (fetch ht key flag))) (set! hashtable-get (lambda (ht key) (fetch ht key #f))) (set! hashtable-put! (lambda (ht key val) (put! ht key val))) (set! hashtable-remove! (lambda (ht key) (remove! ht key))) (set! hashtable-clear! (lambda (ht) (clear! ht))) (set! hashtable-size (lambda (ht) (size ht))) (set! hashtable-for-each (lambda (ht proc) (ht-for-each ht proc))) (set! hashtable-map (lambda (ht proc) (ht-map ht proc))) (set! hashtable-copy (lambda (ht) (ht-copy ht))) #f)) ; Hash trees: a functional data structure analogous to hash tables. ; ; (make-hashtree ) ; ; Returns a newly allocated mutable hash table ; using as the hash function ; and , e.g. ASSQ, ASSV, ASSOC, to search a bucket. ; The must accept a key and return a non-negative exact ; integer. ; ; (make-hashtree ) ; ; Equivalent to (make-hashtree assv). ; ; (make-hashtree) ; ; Equivalent to (make-hashtree object-hash assv). ; ; (hashtree-contains? ) ; ; Returns true iff the contains an entry for . ; ; (hashtree-fetch ) ; ; Returns the value associated with in the if the ; contains ; otherwise returns . ; ; (hashtree-get ) ; ; Equivalent to (hashtree-fetch #f) ; ; (hashtree-put ) ; ; Returns a new hashtree that is like except that ; is associated with . ; ; (hashtree-remove ) ; ; Returns a new hashtree that is like except that ; is not associated with any value. ; ; (hashtree-size ) ; ; Returns the number of keys contained within the . ; ; (hashtree-for-each ) ; ; The must accept two arguments, a key and the value ; associated with that key. Calls the once for each ; key-value association. The order of these calls is indeterminate. ; ; (hashtree-map ) ; ; The must accept two arguments, a key and the value ; associated with that key. Calls the once for each ; key-value association, and returns a list of the results. The ; order of the calls is indeterminate. ; These global variables are assigned new values later. (define make-hashtree (lambda args '*)) (define hashtree-contains? (lambda (ht key) #f)) (define hashtree-fetch (lambda (ht key flag) flag)) (define hashtree-get (lambda (ht key) (hashtree-fetch ht key #f))) (define hashtree-put (lambda (ht key val) '*)) (define hashtree-remove (lambda (ht key) '*)) (define hashtree-size (lambda (ht) 0)) (define hashtree-for-each (lambda (ht proc) '*)) (define hashtree-map (lambda (ht proc) '())) ; Implementation. ; A hashtree is represented as a vector of the form ; ; #(("hashtree") ) ; ; where is the number of associations within the hashtree, ; is the hash function, is the bucket searcher, ; and is generated by the following grammar: ; ; ::= () ; | ( ) ; ::= () ; ::= ; | ; ::= ( . ) ; ; If is of the form (n alist buckets1 buckets2), ; then n is the hash code of all keys in alist, all keys in buckets1 ; have a hash code less than n, and all keys in buckets2 have a hash ; code greater than n. (let ((doc (list "hashtree")) (count (lambda (ht) (vector-ref ht 1))) (hasher (lambda (ht) (vector-ref ht 2))) (searcher (lambda (ht) (vector-ref ht 3))) (buckets (lambda (ht) (vector-ref ht 4))) (make-empty-buckets (lambda () '())) (make-buckets (lambda (h alist buckets1 buckets2) (list h alist buckets1 buckets2))) (buckets-empty? (lambda (buckets) (null? buckets))) (buckets-n (lambda (buckets) (car buckets))) (buckets-alist (lambda (buckets) (cadr buckets))) (buckets-left (lambda (buckets) (caddr buckets))) (buckets-right (lambda (buckets) (cadddr buckets)))) (let ((hashtree? (lambda (ht) (and (vector? ht) (= 5 (vector-length ht)) (eq? doc (vector-ref ht 0))))) (hashtree-error (lambda (x) (display "ERROR: Bad hash tree: ") (newline) (write x) (newline)))) ; Internal operations. (define (make-ht count hashfun searcher buckets) (vector doc count hashfun searcher buckets)) ; Substitute x for the first occurrence of y within the list z. ; y is known to occur within z. (define (substitute1 x y z) (cond ((eq? y (car z)) (cons x (cdr z))) (else (cons (car z) (substitute1 x y (cdr z)))))) ; Remove the first occurrence of x from y. ; x is known to occur within y. (define (remq1 x y) (cond ((eq? x (car y)) (cdr y)) (else (cons (car y) (remq1 x (cdr y)))))) ; Returns the contents of the hashtree as a list of pairs. (define (contents ht) (let* ((t (buckets ht))) (define (contents t alist) (if (buckets-empty? t) alist (contents (buckets-left t) (contents (buckets-right t) (append-reverse (buckets-alist t) alist))))) (define (append-reverse x y) (if (null? x) y (append-reverse (cdr x) (cons (car x) y)))) ; Creating a new hashtree from a list that is almost sorted ; in hash code order would create an extremely unbalanced ; hashtree, so this routine randomizes the order a bit. (define (randomize1 alist alist1 alist2 alist3) (if (null? alist) (randomize-combine alist1 alist2 alist3) (randomize2 (cdr alist) (cons (car alist) alist1) alist2 alist3))) (define (randomize2 alist alist1 alist2 alist3) (if (null? alist) (randomize-combine alist1 alist2 alist3) (randomize3 (cdr alist) alist1 (cons (car alist) alist2) alist3))) (define (randomize3 alist alist1 alist2 alist3) (if (null? alist) (randomize-combine alist1 alist2 alist3) (randomize1 (cdr alist) alist1 alist2 (cons (car alist) alist3)))) (define (randomize-combine alist1 alist2 alist3) (cond ((null? alist2) alist1) ((null? alist3) (append-reverse alist2 alist1)) (else (append-reverse (randomize1 alist3 '() '() '()) (append-reverse (randomize1 alist1 '() '() '()) (randomize1 alist2 '() '() '())))))) (randomize1 (contents t '()) '() '() '()))) (define (contains? ht key) (if (hashtree? ht) (let* ((t (buckets ht)) (h ((hasher ht) key))) (if ((searcher ht) key (find-bucket t h)) #t #f)) (hashtree-error ht))) (define (fetch ht key flag) (if (hashtree? ht) (let* ((t (buckets ht)) (h ((hasher ht) key)) (probe ((searcher ht) key (find-bucket t h)))) (if probe (cdr probe) flag)) (hashtree-error ht))) ; Given a t and a hash code h, returns the alist for h. (define (find-bucket t h) (if (buckets-empty? t) '() (let ((n (buckets-n t))) (cond ((< h n) (find-bucket (buckets-left t) h)) ((< n h) (find-bucket (buckets-right t) h)) (else (buckets-alist t)))))) (define (put ht key val) (if (hashtree? ht) (let ((t (buckets ht)) (h ((hasher ht) key)) (association (cons key val)) (c (count ht))) (define (put t h) (if (buckets-empty? t) (begin (set! c (+ c 1)) (make-buckets h (list association) t t)) (let ((n (buckets-n t)) (alist (buckets-alist t)) (left (buckets-left t)) (right (buckets-right t))) (cond ((< h n) (make-buckets n alist (put (buckets-left t) h) right)) ((< n h) (make-buckets n alist left (put (buckets-right t) h))) (else (let ((probe ((searcher ht) key alist))) (if probe (make-buckets n (substitute1 association probe alist) left right) (begin (set! c (+ c 1)) (make-buckets n (cons association alist) left right))))))))) (let ((buckets (put t h))) (make-ht c (hasher ht) (searcher ht) buckets))) (hashtree-error ht))) (define (remove ht key) (if (hashtree? ht) (let ((t (buckets ht)) (h ((hasher ht) key)) (c (count ht))) (define (remove t h) (if (buckets-empty? t) t (let ((n (buckets-n t)) (alist (buckets-alist t)) (left (buckets-left t)) (right (buckets-right t))) (cond ((< h n) (make-buckets n alist (remove left h) right)) ((< n h) (make-buckets n alist left (remove right h))) (else (let ((probe ((searcher ht) key alist))) (if probe (begin (set! c (- c 1)) (make-buckets n (remq1 probe alist) left right)) t))))))) (let ((buckets (remove t h))) (make-ht c (hasher ht) (searcher ht) buckets))) (hashtree-error ht))) (define (size ht) (if (hashtree? ht) (count ht) (hashtree-error ht))) (define (ht-for-each f ht) (if (hashtree? ht) (for-each (lambda (association) (f (car association) (cdr association))) (contents ht)) (hashtree-error ht))) (define (ht-map f ht) (if (hashtree? ht) (map (lambda (association) (f (car association) (cdr association))) (contents ht)) (hashtree-error ht))) ; External entry points. (set! make-hashtree (lambda args (let* ((hashfun (if (null? args) object-hash (car args))) (searcher (if (or (null? args) (null? (cdr args))) assv (cadr args)))) (make-ht 0 hashfun searcher (make-empty-buckets))))) (set! hashtree-contains? (lambda (ht key) (contains? ht key))) (set! hashtree-fetch (lambda (ht key flag) (fetch ht key flag))) (set! hashtree-get (lambda (ht key) (fetch ht key #f))) (set! hashtree-put (lambda (ht key val) (put ht key val))) (set! hashtree-remove (lambda (ht key) (remove ht key))) (set! hashtree-size (lambda (ht) (size ht))) (set! hashtree-for-each (lambda (ht proc) (ht-for-each ht proc))) (set! hashtree-map (lambda (ht proc) (ht-map ht proc))) #f)) ; Copyright 1994 William Clinger ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; 24 April 1999 ; ; Compiler switches needed by Twobit. (define make-twobit-flag) (define display-twobit-flag) (define make-twobit-flag (lambda (name) (define (twobit-warning) (display "Error: incorrect arguments to ") (write name) (newline) (reset)) (define (display-flag state) (display (if state " + " " - ")) (display name) (display " is ") (display (if state "on" "off")) (newline)) (let ((state #t)) (lambda args (cond ((null? args) state) ((and (null? (cdr args)) (boolean? (car args))) (set! state (car args)) state) ((and (null? (cdr args)) (eq? (car args) 'display)) (display-flag state)) (else (twobit-warning))))))) (define (display-twobit-flag flag) (flag 'display)) ; Debugging and convenience. (define issue-warnings (make-twobit-flag 'issue-warnings)) (define include-source-code (make-twobit-flag 'include-source-code)) (define include-variable-names (make-twobit-flag 'include-variable-names)) (define include-procedure-names (make-twobit-flag 'include-procedure-names)) ; Space efficiency. ; This switch isn't fully implemented yet. If it is true, then ; Twobit will generate flat closures and will go to some trouble ; to zero stale registers and stack slots. ; Don't turn this switch off unless space is more important than speed. (define avoid-space-leaks (make-twobit-flag 'avoid-space-leaks)) ; Major optimizations. (define integrate-usual-procedures (make-twobit-flag 'integrate-usual-procedures)) (define control-optimization (make-twobit-flag 'control-optimization)) (define parallel-assignment-optimization (make-twobit-flag 'parallel-assignment-optimization)) (define lambda-optimization (make-twobit-flag 'lambda-optimization)) (define benchmark-mode (make-twobit-flag 'benchmark-mode)) (define benchmark-block-mode (make-twobit-flag 'benchmark-block-mode)) (define global-optimization (make-twobit-flag 'global-optimization)) (define interprocedural-inlining (make-twobit-flag 'interprocedural-inlining)) (define interprocedural-constant-propagation (make-twobit-flag 'interprocedural-constant-propagation)) (define common-subexpression-elimination (make-twobit-flag 'common-subexpression-elimination)) (define representation-inference (make-twobit-flag 'representation-inference)) (define local-optimization (make-twobit-flag 'local-optimization)) ; For backwards compatibility, until I can change the code. (define (ignore-space-leaks . args) (if (null? args) (not (avoid-space-leaks)) (avoid-space-leaks (not (car args))))) (define lambda-optimizations lambda-optimization) (define local-optimizations local-optimization) (define (set-compiler-flags! how) (case how ((no-optimization) (set-compiler-flags! 'standard) (avoid-space-leaks #t) (integrate-usual-procedures #f) (control-optimization #f) (parallel-assignment-optimization #f) (lambda-optimization #f) (benchmark-mode #f) (benchmark-block-mode #f) (global-optimization #f) (interprocedural-inlining #f) (interprocedural-constant-propagation #f) (common-subexpression-elimination #f) (representation-inference #f) (local-optimization #f)) ((standard) (issue-warnings #t) (include-source-code #f) (include-procedure-names #t) (include-variable-names #t) (avoid-space-leaks #f) (runtime-safety-checking #t) (integrate-usual-procedures #f) (control-optimization #t) (parallel-assignment-optimization #t) (lambda-optimization #t) (benchmark-mode #f) (benchmark-block-mode #f) (global-optimization #t) (interprocedural-inlining #t) (interprocedural-constant-propagation #t) (common-subexpression-elimination #t) (representation-inference #t) (local-optimization #t)) ((fast-safe) (let ((bbmode (benchmark-block-mode))) (set-compiler-flags! 'standard) (integrate-usual-procedures #t) (benchmark-mode #t) (benchmark-block-mode bbmode))) ((fast-unsafe) (set-compiler-flags! 'fast-safe) (runtime-safety-checking #f)) (else (error "set-compiler-flags!: unknown mode " how)))) (define (display-twobit-flags which) (case which ((debugging) (display-twobit-flag issue-warnings) (display-twobit-flag include-procedure-names) (display-twobit-flag include-variable-names) (display-twobit-flag include-source-code)) ((safety) (display-twobit-flag avoid-space-leaks)) ((optimization) (display-twobit-flag integrate-usual-procedures) (display-twobit-flag control-optimization) (display-twobit-flag parallel-assignment-optimization) (display-twobit-flag lambda-optimization) (display-twobit-flag benchmark-mode) (display-twobit-flag benchmark-block-mode) (display-twobit-flag global-optimization) (if (global-optimization) (begin (display " ") (display-twobit-flag interprocedural-inlining) (display " ") (display-twobit-flag interprocedural-constant-propagation) (display " ") (display-twobit-flag common-subexpression-elimination) (display " ") (display-twobit-flag representation-inference))) (display-twobit-flag local-optimization)) (else ; The switch might mean something to the assembler, but not to Twobit #t))) ; eof ; Copyright 1991 William Clinger ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; 14 April 1999 / wdc ($$trace "pass1.aux") ;*************************************************************** ; ; Each definition in this section should be overridden by an assignment ; in a target-specific file. ; ; If a lambda expression has more than @maxargs-with-rest-arg@ required ; arguments followed by a rest argument, then the macro expander will ; rewrite the lambda expression as a lambda expression with only one ; argument (a rest argument) whose body is a LET that binds the arguments ; of the original lambda expression. (define @maxargs-with-rest-arg@ 1000000) ; infinity (define (prim-entry name) #f) ; no integrable procedures (define (prim-arity name) 0) ; all of which take 0 arguments (define (prim-opcodename name) name) ; and go by their source names ; End of definitions to be overridden by target-specific assignments. ; ;*************************************************************** ; Miscellaneous routines. (define (m-warn msg . more) (if (issue-warnings) (begin (display "WARNING from macro expander:") (newline) (display msg) (newline) (for-each (lambda (x) (write x) (newline)) more)))) (define (m-error msg . more) (display "ERROR detected during macro expansion:") (newline) (display msg) (newline) (for-each (lambda (x) (write x) (newline)) more) (m-quit (make-constant #f))) (define (m-bug msg . more) (display "BUG in macro expander: ") (newline) (display msg) (newline) (for-each (lambda (x) (write x) (newline)) more) (m-quit (make-constant #f))) ; Given a , returns a list of bound variables. ' (define (make-null-terminated x) (cond ((null? x) '()) ((pair? x) (cons (car x) (make-null-terminated (cdr x)))) (else (list x)))) ; Returns the length of the given list, or -1 if the argument ; is not a list. Does not check for circular lists. (define (safe-length x) (define (loop x n) (cond ((null? x) n) ((pair? x) (loop (cdr x) (+ n 1))) (else -1))) (loop x 0)) ; Given a unary predicate and a list, returns a list of those ; elements for which the predicate is true. (define (filter1 p x) (cond ((null? x) '()) ((p (car x)) (cons (car x) (filter1 p (cdr x)))) (else (filter1 p (cdr x))))) ; Given a unary predicate and a list, returns #t if the ; predicate is true of every element of the list. (define (every1? p x) (cond ((null? x) #t) ((p (car x)) (every1? p (cdr x))) (else #f))) ; Binary union of two sets represented as lists, using equal?. (define (union2 x y) (cond ((null? x) y) ((member (car x) y) (union2 (cdr x) y)) (else (union2 (cdr x) (cons (car x) y))))) ; Given an association list, copies the association pairs. (define (copy-alist alist) (map (lambda (x) (cons (car x) (cdr x))) alist)) ; Removes a value from a list. May destroy the list. ' (define remq! (letrec ((loop (lambda (x y prev) (cond ((null? y) #t) ((eq? x (car y)) (set-cdr! prev (cdr y)) (loop x (cdr prev) prev)) (else (loop x (cdr y) y)))))) (lambda (x y) (cond ((null? y) '()) ((eq? x (car y)) (remq! x (cdr y))) (else (loop x (cdr y) y) y))))) ; Procedure-specific source code transformations. ; The transformer is passed a source code expression and a predicate ; and returns one of: ; ; the original source code expression ; a new source code expression to use in place of the original ; #f to indicate that the procedure is being called ; with an incorrect number of arguments or ; with an incorrect operand ; ; The original source code expression is guaranteed to be a list whose ; car is the name associated with the transformer. ; The predicate takes an identifier (a symbol) and returns true iff ; that identifier is bound to something other than its global binding. ; ; Since the procedures and their transformations are target-specific, ; they are defined in another file, in the Target subdirectory. ; FIXME: ; I think this is now used in only one place, in simplify-if. (define (integrable? name) (and (integrate-usual-procedures) (prim-entry name))) ; MAKE-READABLE strips the referencing information ; and replaces (begin I) by I. ; If the optional argument is true, then it also reconstructs LET. (define (make-readable exp . rest) (let ((fancy? (and (not (null? rest)) (car rest)))) (define (make-readable exp) (case (car exp) ((quote) (make-readable-quote exp)) ((lambda) `(lambda ,(lambda.args exp) ,@(map (lambda (def) `(define ,(def.lhs def) ,(make-readable (def.rhs def)))) (lambda.defs exp)) ,(make-readable (lambda.body exp)))) ((set!) `(set! ,(assignment.lhs exp) ,(make-readable (assignment.rhs exp)))) ((if) `(if ,(make-readable (if.test exp)) ,(make-readable (if.then exp)) ,(make-readable (if.else exp)))) ((begin) (if (variable? exp) (variable.name exp) `(begin ,@(map make-readable (begin.exprs exp))))) (else (make-readable-call exp)))) (define (make-readable-quote exp) (let ((x (constant.value exp))) (if (and fancy? (or (boolean? x) (number? x) (char? x) (string? x))) x exp))) (define (make-readable-call exp) (let ((proc (call.proc exp))) (if (and fancy? (lambda? proc) (list? (lambda.args proc))) ;(make-readable-let* exp '() '() '()) (make-readable-let exp) `(,(make-readable (call.proc exp)) ,@(map make-readable (call.args exp)))))) (define (make-readable-let exp) (let* ((L (call.proc exp)) (formals (lambda.args L)) (args (map make-readable (call.args exp))) (body (make-readable (lambda.body L)))) (if (and (null? (lambda.defs L)) (= (length args) 1) (pair? body) (or (and (eq? (car body) 'let) (= (length (cadr body)) 1)) (eq? (car body) 'let*))) `(let* ((,(car formals) ,(car args)) ,@(cadr body)) ,@(cddr body)) `(let ,(map list (lambda.args L) args) ,@(map (lambda (def) `(define ,(def.lhs def) ,(make-readable (def.rhs def)))) (lambda.defs L)) ,body)))) (define (make-readable-let* exp vars inits defs) (if (and (null? defs) (call? exp) (lambda? (call.proc exp)) (= 1 (length (lambda.args (call.proc exp))))) (let ((proc (call.proc exp)) (arg (car (call.args exp)))) (if (and (call? arg) (lambda? (call.proc arg)) (= 1 (length (lambda.args (call.proc arg)))) (null? (lambda.defs (call.proc arg)))) (make-readable-let* (make-call proc (list (lambda.body (call.proc arg)))) (cons (car (lambda.args (call.proc arg))) vars) (cons (make-readable (car (call.args arg))) inits) '()) (make-readable-let* (lambda.body proc) (cons (car (lambda.args proc)) vars) (cons (make-readable (car (call.args exp))) inits) (map (lambda (def) `(define ,(def.lhs def) ,(make-readable (def.rhs def)))) (reverse (lambda.defs proc)))))) (cond ((or (not (null? vars)) (not (null? defs))) `(let* ,(map list (reverse vars) (reverse inits)) ,@defs ,(make-readable exp))) ((and (call? exp) (lambda? (call.proc exp))) (let ((proc (call.proc exp))) `(let ,(map list (lambda.args proc) (map make-readable (call.args exp))) ,@(map (lambda (def) `(define ,(def.lhs def) ,(make-readable (def.rhs def)))) (lambda.defs proc)) ,(make-readable (lambda.body proc))))) (else (make-readable exp))))) (make-readable exp))) ; For testing. ; MAKE-UNREADABLE does the reverse. ; It assumes there are no internal definitions. (define (make-unreadable exp) (cond ((symbol? exp) (list 'begin exp)) ((pair? exp) (case (car exp) ((quote) exp) ((lambda) (list 'lambda (cadr exp) '(begin) (list '() '() '() '()) (make-unreadable (cons 'begin (cddr exp))))) ((set!) (list 'set! (cadr exp) (make-unreadable (caddr exp)))) ((if) (list 'if (make-unreadable (cadr exp)) (make-unreadable (caddr exp)) (if (= (length exp) 3) '(unspecified) (make-unreadable (cadddr exp))))) ((begin) (if (= (length exp) 2) (make-unreadable (cadr exp)) (cons 'begin (map make-unreadable (cdr exp))))) (else (map make-unreadable exp)))) (else (list 'quote exp)))) ; Copyright 1991 William D Clinger. ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; 12 April 1999. ; ; Procedures for fetching and clobbering parts of expressions. ($$trace "pass2.aux") (define (constant? exp) (eq? (car exp) 'quote)) (define (variable? exp) (and (eq? (car exp) 'begin) (null? (cddr exp)))) (define (lambda? exp) (eq? (car exp) 'lambda)) (define (call? exp) (pair? (car exp))) (define (assignment? exp) (eq? (car exp) 'set!)) (define (conditional? exp) (eq? (car exp) 'if)) (define (begin? exp) (and (eq? (car exp) 'begin) (not (null? (cddr exp))))) (define (make-constant value) (list 'quote value)) (define (make-variable name) (list 'begin name)) (define (make-lambda formals defs R F G decls doc body) (list 'lambda formals (cons 'begin defs) (list 'quote (list R F G decls doc)) body)) (define (make-call proc args) (cons proc (append args '()))) (define (make-assignment lhs rhs) (list 'set! lhs rhs)) (define (make-conditional e0 e1 e2) (list 'if e0 e1 e2)) (define (make-begin exprs) (if (null? (cdr exprs)) (car exprs) (cons 'begin (append exprs '())))) (define (make-definition lhs rhs) (list 'define lhs rhs)) (define (constant.value exp) (cadr exp)) (define (variable.name exp) (cadr exp)) (define (lambda.args exp) (cadr exp)) (define (lambda.defs exp) (cdr (caddr exp))) (define (lambda.R exp) (car (cadr (cadddr exp)))) (define (lambda.F exp) (cadr (cadr (cadddr exp)))) (define (lambda.G exp) (caddr (cadr (cadddr exp)))) (define (lambda.decls exp) (cadddr (cadr (cadddr exp)))) (define (lambda.doc exp) (car (cddddr (cadr (cadddr exp))))) (define (lambda.body exp) (car (cddddr exp))) (define (call.proc exp) (car exp)) (define (call.args exp) (cdr exp)) (define (assignment.lhs exp) (cadr exp)) (define (assignment.rhs exp) (caddr exp)) (define (if.test exp) (cadr exp)) (define (if.then exp) (caddr exp)) (define (if.else exp) (cadddr exp)) (define (begin.exprs exp) (cdr exp)) (define (def.lhs exp) (cadr exp)) (define (def.rhs exp) (caddr exp)) (define (variable-set! exp newexp) (set-car! exp (car newexp)) (set-cdr! exp (append (cdr newexp) '()))) (define (lambda.args-set! exp args) (set-car! (cdr exp) args)) (define (lambda.defs-set! exp defs) (set-cdr! (caddr exp) defs)) (define (lambda.R-set! exp R) (set-car! (cadr (cadddr exp)) R)) (define (lambda.F-set! exp F) (set-car! (cdr (cadr (cadddr exp))) F)) (define (lambda.G-set! exp G) (set-car! (cddr (cadr (cadddr exp))) G)) (define (lambda.decls-set! exp decls) (set-car! (cdddr (cadr (cadddr exp))) decls)) (define (lambda.doc-set! exp doc) (set-car! (cddddr (cadr (cadddr exp))) doc)) (define (lambda.body-set! exp exp0) (set-car! (cddddr exp) exp0)) (define (call.proc-set! exp exp0) (set-car! exp exp0)) (define (call.args-set! exp exprs) (set-cdr! exp exprs)) (define (assignment.rhs-set! exp exp0) (set-car! (cddr exp) exp0)) (define (if.test-set! exp exp0) (set-car! (cdr exp) exp0)) (define (if.then-set! exp exp0) (set-car! (cddr exp) exp0)) (define (if.else-set! exp exp0) (set-car! (cdddr exp) exp0)) (define (begin.exprs-set! exp exprs) (set-cdr! exp exprs)) (define expression-set! variable-set!) ; used only by pass 3 ; FIXME: This duplicates information in Lib/procinfo.sch. (define (make-doc name arity formals source-code filename filepos) (vector name source-code arity filename filepos formals)) (define (doc.name d) (vector-ref d 0)) (define (doc.code d) (vector-ref d 1)) (define (doc.arity d) (vector-ref d 2)) (define (doc.file d) (vector-ref d 3)) (define (doc.filepos d) (vector-ref d 4)) (define (doc.formals d) (vector-ref d 5)) (define (doc.name-set! d x) (if d (vector-set! d 0 x))) (define (doc.code-set! d x) (if d (vector-set! d 1 x))) (define (doc.arity-set! d x) (if d (vector-set! d 2 x))) (define (doc.file-set! d x) (if d (vector-set! d 3 x))) (define (doc.filepos-set! d x) (if d (vector-set! d 4 x))) (define (doc.formals-set! d x) (if d (vector-set! d 5 x))) (define (doc-copy d) (list->vector (vector->list d))) (define (ignored? name) (eq? name name:IGNORED)) ; Fairly harmless bug: rest arguments aren't getting flagged. (define (flag-as-ignored name L) (define (loop name formals) (cond ((null? formals) ;(pass2-error p2error:violation-of-invariant name formals) #t) ((symbol? formals) #t) ((eq? name (car formals)) (set-car! formals name:IGNORED) (if (not (local? (lambda.R L) name:IGNORED)) (lambda.R-set! L (cons (make-R-entry name:IGNORED '() '() '()) (lambda.R L))))) (else (loop name (cdr formals))))) (loop name (lambda.args L))) (define (make-null-terminated formals) (cond ((null? formals) '()) ((symbol? formals) (list formals)) (else (cons (car formals) (make-null-terminated (cdr formals)))))) (define (list-head x n) (cond ((zero? n) '()) (else (cons (car x) (list-head (cdr x) (- n 1)))))) (define (remq x y) (cond ((null? y) '()) ((eq? x (car y)) (remq x (cdr y))) (else (cons (car y) (remq x (cdr y)))))) (define (make-call-to-LIST args) (cond ((null? args) (make-constant '())) ((null? (cdr args)) (make-call (make-variable name:CONS) (list (car args) (make-constant '())))) (else (make-call (make-variable name:LIST) args)))) (define (pass2-error i . etc) (apply cerror (cons (vector-ref pass2-error-messages i) etc))) (define pass2-error-messages '#("System error: violation of an invariant in pass 2" "Wrong number of arguments to known procedure")) (define p2error:violation-of-invariant 0) (define p2error:wna 1) ; Procedures for fetching referencing information from R-tables. (define (make-R-entry name refs assigns calls) (list name refs assigns calls)) (define (R-entry.name x) (car x)) (define (R-entry.references x) (cadr x)) (define (R-entry.assignments x) (caddr x)) (define (R-entry.calls x) (cadddr x)) (define (R-entry.references-set! x refs) (set-car! (cdr x) refs)) (define (R-entry.assignments-set! x assignments) (set-car! (cddr x) assignments)) (define (R-entry.calls-set! x calls) (set-car! (cdddr x) calls)) (define (local? R I) (assq I R)) (define (R-entry R I) (assq I R)) (define (R-lookup R I) (or (assq I R) (pass2-error p2error:violation-of-invariant R I))) (define (references R I) (cadr (R-lookup R I))) (define (assignments R I) (caddr (R-lookup R I))) (define (calls R I) (cadddr (R-lookup R I))) (define (references-set! R I X) (set-car! (cdr (R-lookup R I)) X)) (define (assignments-set! R I X) (set-car! (cddr (R-lookup R I)) X)) (define (calls-set! R I X) (set-car! (cdddr (R-lookup R I)) X)) ; A notepad is a vector of the form #(L0 (L1 ...) (L2 ...) (I ...)), ; where the components are: ; element 0: a parent lambda expression (or #f if there is no enclosing ; parent, or we want to pretend that there isn't). ; element 1: a list of lambda expressions that the parent lambda ; expression encloses immediately. ; element 2: a subset of that list that does not escape. ; element 3: a list of free variables. (define (make-notepad L) (vector L '() '() '())) (define (notepad.parent np) (vector-ref np 0)) (define (notepad.lambdas np) (vector-ref np 1)) (define (notepad.nonescaping np) (vector-ref np 2)) (define (notepad.vars np) (vector-ref np 3)) (define (notepad.lambdas-set! np x) (vector-set! np 1 x)) (define (notepad.nonescaping-set! np x) (vector-set! np 2 x)) (define (notepad.vars-set! np x) (vector-set! np 3 x)) (define (notepad-lambda-add! np L) (notepad.lambdas-set! np (cons L (notepad.lambdas np)))) (define (notepad-nonescaping-add! np L) (notepad.nonescaping-set! np (cons L (notepad.nonescaping np)))) (define (notepad-var-add! np I) (let ((vars (notepad.vars np))) (if (not (memq I vars)) (notepad.vars-set! np (cons I vars))))) ; Given a notepad, returns the list of variables that are closed ; over by some nested lambda expression that escapes. (define (notepad-captured-variables np) (let ((nonescaping (notepad.nonescaping np))) (apply-union (map (lambda (L) (if (memq L nonescaping) (lambda.G L) (lambda.F L))) (notepad.lambdas np))))) ; Given a notepad, returns a list of free variables computed ; as the union of the immediate free variables with the free ; variables of nested lambda expressions. (define (notepad-free-variables np) (do ((lambdas (notepad.lambdas np) (cdr lambdas)) (fv (notepad.vars np) (let ((L (car lambdas))) (union (difference (lambda.F L) (make-null-terminated (lambda.args L))) fv)))) ((null? lambdas) fv))) ; Copyright 1992 William Clinger ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; 13 December 1998 ; Implementation-dependent parameters and preferences that determine ; how identifiers are represented in the output of the macro expander. ; ; The basic problem is that there are no reserved words, so the ; syntactic keywords of core Scheme that are used to express the ; output need to be represented by data that cannot appear in the ; input. This file defines those data. ($$trace "prefs") ; FIXME: The following definitions are currently ignored. ; The following definitions assume that identifiers of mixed case ; cannot appear in the input. (define begin1 (string->symbol "Begin")) (define define1 (string->symbol "Define")) (define quote1 (string->symbol "Quote")) (define lambda1 (string->symbol "Lambda")) (define if1 (string->symbol "If")) (define set!1 (string->symbol "Set!")) ; The following defines an implementation-dependent expression ; that evaluates to an undefined (not unspecified!) value, for ; use in expanding the (define x) syntax. (define undefined1 (list (string->symbol "Undefined"))) ; End of FIXME. ; A variable is renamed by suffixing a vertical bar followed by a unique ; integer. In IEEE and R4RS Scheme, a vertical bar cannot appear as part ; of an identifier, but presumably this is enforced by the reader and not ; by the compiler. Any other character that cannot appear as part of an ; identifier may be used instead of the vertical bar. (define renaming-prefix-character #\.) (define renaming-suffix-character #\|) (define renaming-prefix (string renaming-prefix-character)) (define renaming-suffix (string renaming-suffix-character)) ; Patches for Twobit. Here temporarily. (define (make-toplevel-definition id exp) (if (lambda? exp) (doc.name-set! (lambda.doc exp) id)) (make-begin (list (make-assignment id exp) (make-constant id)))) (define (make-undefined) (make-call (make-variable 'undefined) '())) (define (make-unspecified) (make-call (make-variable 'unspecified) '())) ; Copyright 1992 William Clinger ; ; $Id: twobit-smaller.sch,v 1.1 1999/09/09 22:13:42 lth Exp $ ; ; 9 December 1998 ; Syntactic environments. ; ; A syntactic environment maps identifiers to denotations, ; where a denotation is one of ; ; (special ) ; (macro ) ; (inline ) ; (identifier ) ; ; and where is one of ; ; quote ; lambda ; if ; set! ; begin ; define ; define-syntax ; let-syntax ; letrec-syntax ; syntax-rules ; ; and where is a compiled (see R4RS), ; is a syntactic environment, and is an identifier. ; ; An inline denotation is like a macro denotation, except that it ; is not an error when none of the rules match the use. Inline ; denotations are created by DEFINE-INLINE. ; The standard syntactic environment should not include any ; identifier denotations; space leaks will result if it does. ($$trace "syntaxenv") (define standard-syntactic-environment `((quote . (special quote)) (lambda . (special lambda)) (if . (special if)) (set! . (special set!)) (begin . (special begin)) (define . (special define)) (define-inline . (special define-inline)) (define-syntax . (special define-syntax)) (let-syntax . (special let-syntax)) (letrec-syntax . (special letrec-syntax)) (syntax-rules . (special syntax-rules)) )) ; Unforgeable synonyms for lambda and set!, used to expand definitions. (define lambda0 (string->symbol " lambda ")) (define set!0 (string->symbol " set! ")) (define (syntactic-copy env) (copy-alist env)) (define (make-basic-syntactic-environment) (cons (cons lambda0 (cdr (assq 'lambda standard-syntactic-environment))) (cons (cons set!0 (cdr (assq 'set! standard-syntactic-environment))) (syntactic-copy standard-syntactic-environment)))) ; The global-syntactic-environment will always be a nonempty ; association list since there is no way to remove the entry ; for lambda0. That entry is used as a header by destructive ; operations. (define global-syntactic-environment (make-basic-syntactic-environment)) (define (global-syntactic-environment-set! env) (set-cdr! global-syntactic-environment env) #t) (define (syntactic-bind-globally! id denotation) (if (and (identifier-denotation? denotation) (eq? id (identifier-name denotation))) (letrec ((remove-bindings-for-id (lambda (bindings) (cond ((null? bindings) '()) ((eq? (caar bindings) id) (remove-bindings-for-id (cdr bindings))) (else (cons (car bindings) (remove-bindings-for-id (cdr bindings)))))))) (global-syntactic-environment-set! (remove-bindings-for-id (cdr global-syntactic-environment)))) (let ((x (assq id global-syntactic-environment))) (if x (begin (set-cdr! x denotation) #t) (global-syntactic-environment-set! (cons (cons id denotation) (cdr global-syntactic-environment))))))) (define (syntactic-divert env1 env2) (append env2 env1)) (define (syntactic-extend env ids denotations) (syntactic-divert env (map cons ids denotations))) (define (syntactic-lookup env id) (let ((entry (assq id env))) (if entry (cdr entry) (make-identifier-denotation id)))) (define (syntactic-assign! env id denotation) (let ((entry (assq id env))) (if entry (set-cdr! entry denotation) (m-bug "Bug detected in syntactic-assign!" env id denotation)))) ; Denotations. (define denotation-class car) (define (special-denotation? denotation) (eq? (denotation-class denotation) 'special)) (define (macro-denotation? denotation) (eq? (denotation-class denotation) 'macro)) (define (inline-denotation? denotation) (eq? (denotation-class denotation) 'inline)) (define (identifier-denotation? denotation) (eq? (denotation-class denotation) 'identifier)) (define (make-macro-denotation rules env) (list 'macro rules env)) (define (make-inline-denotation id rules env) (list 'inline rules env id)) (define (make-identifier-denotation id) (list 'identifier id '() '() '())) (define macro-rules cadr) (define macro-env caddr) (define inline-rules macro-rules) (define inline-env macro-env) (define inline-name cadddr) (define identifier-name cadr) (define identifier-R-entry cdr) (define (same-denotation? d1 d2) (or (eq? d1 d2) (and (identifier-denotation? d1) (identifier-denotation? d2) (eq? (identifier-name d1) (identifier-name d2))))) (define denotation-of-quote (syntactic-lookup standard-syntactic-environment 'quote)) (define denotation-of-lambda (syntactic-lookup standard-syntactic-environment 'lambda)) (define denotation-of-if (syntactic-lookup standard-syntactic-environment 'if)) (define denotation-of-set! (syntactic-lookup standard-syntactic-environment 'set!)) (define denotation-of-begin (syntactic-lookup standard-syntactic-environment 'begin)) (define denotation-of-define (syntactic-lookup standard-syntactic-environment 'define)) (define denotation-of-define-inline (syntactic-lookup standard-syntactic-environment 'define-inline)) (define denotation-of-define-syntax (syntactic-lookup standard-syntactic-environment 'define-syntax)) (define denotation-of-let-syntax (syntactic-lookup standard-syntactic-environment 'let-syntax)) (define denotation-of-letrec-syntax (syntactic-lookup standard-syntactic-environment 'letrec-syntax)) (define denotation-of-syntax-rules (syntactic-lookup standard-syntactic-environment 'syntax-rules)) (define denotation-of-... (syntactic-lookup standard-syntactic-environment '...)) (define denotation-of-transformer (syntactic-lookup standard-syntactic-environment 'transformer)) ; Given a syntactic environment env to be extended, an alist returned ; by rename-vars, and a syntactic environment env2, extends env by ; binding the fresh identifiers to the denotations of the original ; identifiers in env2. (define (syntactic-alias env alist env2) (syntactic-divert env (map (lambda (name-pair) (let ((old-name (car name-pair)) (new-name (cdr name-pair))) (cons new-name (syntactic-lookup env2 old-name)))) alist))) ; Given a syntactic environment and an alist returned by rename-vars, ; extends the environment by binding the old identifiers to the fresh ; identifiers. ; For Twobit, it also binds the fresh identifiers to their denotations. ; This is ok so long as the fresh identifiers are not legal Scheme ; identifiers. (define (syntactic-rename env alist) (if (null? alist) env (let* ((old (caar alist)) (new (cdar alist)) (denotation (make-identifier-denotation new))) (syntactic-rename (cons (cons old denotation) (cons (cons new denotation) env)) (cdr alist))))) ; Renaming of variables. (define renaming-counter 0) (define (make-rename-procedure) (set! renaming-counter (+ renaming-counter 1)) (let ((suffix (string-append renaming-suffix (number->string renaming-counter)))) (lambda (sym) (if (symbol? sym) (let ((s (symbol->string sym))) (if (and (positive? (string-length s)) (char=? (string-ref s 0) renaming-prefix-character)) (string->symbol (string-append s suffix)) (string->symbol (string-append renaming-prefix s suffix)))) (m-warn "Illegal use of rename procedure" 'ok:FIXME sym))))) ; Given a datum, strips the suffixes from any symbols that appear within ; the datum, trying not to copy any more of the datum than necessary. (define (m-strip x) (define (original-symbol x) (define (loop sym s i n) (cond ((= i n) sym) ((char=? (string-ref s i) renaming-suffix-character) (string->symbol (substring s 1 i))) (else (loop sym s (+ i 1) n)))) (let ((s (symbol->string x))) (if (and (positive? (string-length s)) (char=? (string-ref s 0) renaming-prefix-character)) (loop x s 0 (string-length s)) x))) (cond ((symbol? x) (original-symbol x)) ((pair? x) (let ((a (m-strip (car x))) (b (m-strip (cdr x)))) (if (and (eq? a (car x)) (eq? b (cdr x))) x (cons a b)))) ((vector? x) (let* ((v (vector->list x)) (v2 (map m-strip v))) (if (equal? v v2) x (list->vector v2)))) (else x))) ; Given a list of identifiers, or a formal parameter "list", ; returns an alist that associates each identifier with a fresh identifier. (define (rename-vars original-vars) (let ((rename (make-rename-procedure))) (define (loop vars newvars) (cond ((null? vars) (reverse newvars)) ((pair? vars) (let ((var (car vars))) (if (symbol? var) (loop (cdr vars) (cons (cons var (rename var)) newvars)) (m-error "Illegal variable" var)))) ((symbol? vars) (loop (list vars) newvars)) (else (m-error "Malformed parameter list" original-vars)))) (loop original-vars '()))) ; Given a and an alist returned by rename-vars that contains ; a new name for each formal identifier in , renames the ; formal identifiers. (define (rename-formals formals alist) (cond ((null? formals) '()) ((pair? formals) (cons (cdr (assq (car formals) alist)) (rename-formals (cdr formals) alist))) (else (cdr (assq formals alist))))) ; Copyright 1992 William Clinger ; ; Permission to copy this software, in whole or in part, to use this ; software for any lawful purpose, and to redistribute this software ; is granted subject to the restriction that all copies made of this ; software must include this copyright notice in full. ; ; I also request that you send me a copy of any improvements that you ; make to this software so that they may be incorporated within it to ; the benefit of the Scheme community. ; ; 23 November 1998 ; Compiler for a . ; ; References: ; ; The Revised^4 Report on the Algorithmic Language Scheme. ; Clinger and Rees [editors]. To appear in Lisp Pointers. ; Also available as a technical report from U of Oregon, ; MIT AI Lab, and Cornell. ; ; Macros That Work. Clinger and Rees. POPL '91. ; ; The input is a and a syntactic environment. ; Syntactic environments are described in another file. ; ; The supported syntax differs from the R4RS in that vectors are ; allowed as patterns and as templates and are not allowed as ; pattern or template data. ; ; --> (syntax-rules ) ; --> () | ( . ) ; --> (