5
;; Reads a C source file on stdin. Comments of the form
12
;; are treated specially, and C code for the class is written to
13
;; stdout. Typically, the code is saved to a file and included by the
14
;; C source file in question.
16
;; FIXME: Perhaps the files should somehow be fed through the
17
;; preprocessor first?
19
;; FIXME: Turn this into a scheme48 module
21
(define-syntax let-and
23
((let-and (expr) clause clauses ...)
24
(and expr (let-and clause clauses ...)))
25
((let-and (name expr) clause clauses ...)
27
(and name (let-and clause clauses ...))))
28
((let-and expr) expr)))
30
(define (atom? o) (not (list? o)))
31
(define (lambda? o) (and (pair? o) (eq? 'lambda (car o))))
33
(define (make-lambda formal body) `(lambda ,formal ,body))
34
(define lambda-formal cadr)
35
(define lambda-body caddr)
37
(define make-appliction list)
38
(define application-op car)
39
(define application-arg cadr)
40
(define application-args cdr)
42
(define (normalize-application op args)
44
(normalize-application (make-appliction op (car args)) (cdr args))))
46
;; Transform (a b c)-> ((a b) c) and
47
;; (lambda (a b) ...) -> (lambda a (lambda b ...)
48
(define (make-preprocess specials)
50
(define (preprocess expr)
52
(let ((op (car expr)))
53
(cond ((and (atom? op)
55
=> (lambda (pair) ((cdr pair) (cdr expr) preprocess)))
57
(normalize-application (preprocess op)
58
(map preprocess (cdr expr))))))))
61
(define preprocess-applications (make-preprocess '()))
63
(define (do-lambda args preprocess)
64
(let loop ((formals (reverse (car args)))
65
(body (preprocess (cadr args))))
66
(if (null? formals) body
68
(make-lambda (car formals) body)))))
70
(define (do-let* args preprocess)
71
(let loop ((definitions (reverse (car args)))
72
(body (preprocess (cadr args))))
73
(if (null? definitions) body
74
(loop (cdr definitions)
76
(make-lambda (caar definitions)
78
(preprocess (cadar definitions)))))))
80
(define (do-let args preprocess)
81
(let ((definitions (car args))
83
(normalize-application
84
(do-lambda (list (map car definitions) body) preprocess)
85
(map cadr definitions))))
87
(define preprocess (make-preprocess
88
`((lambda . ,do-lambda)
92
(define (free-variable? v expr)
93
(cond ((atom? expr) (eq? v expr))
95
(and (not (eq? v (lambda-formal expr)))
96
(free-variable? v (lambda-body expr))))
98
(or (free-variable? v (application-op expr))
99
(free-variable? v (application-arg expr))))))
101
(define (match pattern expr)
103
(if (eq? '* pattern) (list expr)
104
(and (eq? pattern expr) '()))
105
(let-and ((pair? expr))
106
(op-matches (match (application-op pattern)
107
(application-op expr)))
108
(arg-matches (match (application-arg pattern)
109
(application-arg expr)))
110
(append op-matches arg-matches))))
112
(define (rule pattern f)
113
(cons (preprocess-applications pattern) f))
115
(define (make-K e) (make-combine 'K e))
116
(define (make-S p q) (make-combine 'S p q))
117
;; (define (make-B p) (make-combine 'B p))
118
;; (define (make-C p q) (make-combine 'C p q))
119
;; (define (make-S* p q) (make-combine 'S* p q))
120
;; (define (make-B* p q) (make-combine 'B* p q))
121
;; (define (make-C* p q) (make-combine 'C* p q))
123
;; Some mor patterns that can ba useful for optimization. From "A
124
;; combinator-based compiler for a functional language" by Hudak &
129
;; S (K (K x)) => K (K x)
131
;; S (K x) (K y) => K (x y)
132
;; S f g x = f x (g x)
137
(define optimizations
138
(list (rule '(S (K *) (K *)) (lambda (p q) (make-K (make-appliction p q))))
139
(rule '(S (K *) I) (lambda (p) p))
140
;; (rule '(B K I) (lambda () 'K))
141
(rule '(S (K *) (B * *)) (lambda (p q r) (make-combine 'B* p q r)))
142
(rule '(S (K *) *) (lambda (p q) (make-combine 'B p q)))
143
(rule '(S (B * *) (K *)) (lambda (p q r) (make-combine 'C* p q r)))
144
;; (rule '(C (B * *) *) (lambda (p q r) (make-combine 'C* p q r)))
145
(rule '(S * (K *)) (lambda (p q) (make-combine 'C p q)))
146
(rule '(S (B * * ) r) (lambda (p q r) (make-combine 'S* p q r)))))
148
(define (optimize expr)
149
;; (werror "optimize ~S\n" expr)
150
(let loop ((rules optimizations))
151
;; (if (not (null? rules)) (werror "trying pattern ~S\n" (caar rules)) )
152
(cond ((null? rules) expr)
153
((match (caar rules) expr)
154
=> (lambda (parts) (apply (cdar rules) parts)))
155
(else (loop (cdr rules))))))
157
(define (optimize-application op args)
159
(optimize-application (optimize (make-appliction op (car args)))
162
(define (make-combine op . args)
163
(optimize-application op args))
165
(define (translate-expression expr)
166
(cond ((atom? expr) expr)
168
(translate-lambda (lambda-formal expr)
169
(translate-expression (lambda-body expr))))
171
(make-appliction (translate-expression (application-op expr))
172
(translate-expression (application-arg expr))))))
174
(define (translate-lambda v expr)
176
(if (eq? v expr) 'I (make-K expr)))
178
(error "translate-lambda: Unexpected lambda" expr))
180
(make-S (translate-lambda v (application-op expr))
181
(translate-lambda v (application-arg expr))))))
183
(define (make-flat-application op arg)
184
(if (atom? op) `(,op ,arg)
187
(define (flatten-application expr)
188
(if (or (atom? expr) (lambda? expr)) expr
189
(make-flat-application (flatten-application (application-op expr))
190
(flatten-application (application-arg expr)))))
192
(define (translate expr)
193
(flatten-application (translate-expression (preprocess expr))))
196
;; (translate '(lambda (port connection)
197
;; (start-io (listen port connection)
198
;; (open-direct-tcpip connection))))
199
;; ===> (C (B* S (B start-io) listen) open-direct-tcpip)
201
;; (translate '(lambda (f) ((lambda (x) (f (lambda (z) ((x x) z))))
202
;; (lambda (x) (f (lambda (z) ((x x) z)))) )))
203
;; ===> (S (C B (S I I)) (C B (S I I)))
205
;; (translate '(lambda (r) (lambda (x) (if (= x 0) 1 (* x (r (- x 1)))))))
206
;; ===> (B* (S (C* if (C = 0) 1)) (S *) (C B (C - 1)))
209
(define (werror f . args)
210
(display (apply format #f f args) 2))
212
(define (string-prefix? prefix s)
213
(let ((l (string-length prefix)))
214
(and (<= l (string-length s))
215
(string=? prefix (substring s 0 l)))))
217
(define (read-expression p)
218
(let ((line (read-line)))
219
; (werror "read line: '~s'\n" (if (eof-object? line) "<EOF>" line))
220
(cond ((eof-object? line) line)
222
(else (read-expression p)))))
224
(define (get key alist select)
225
(cond ((assq key alist) => select)
228
(define (append-deep o)
229
; (werror "append-deep: ~S\n" o)
230
(cond ((string? o) o)
231
((symbol? o) (symbol->string o))
232
((number? o) (number->string o))
234
(apply string-append (map append-deep o)))))
236
(define (identity x) x)
238
(define (filter p list)
239
(cond ((null? list) list)
240
((p (car list)) (cons (car list)
241
(filter p (cdr list))))
242
(else (filter p (cdr list)))))
244
(define (implode list separator)
245
(cond ((null? list) '())
246
((null? (cdr list)) list)
247
(else `(,(car list) ,separator ,@(implode (cdr list) separator)))))
249
(define (atom? x) (or (symbol? x) (string? x)))
251
;; Variables are describes as lists (name . type)
252
;; Known types (and corresponding C declarations) are
254
;; (string) struct ol_string *name
255
;; (object class) struct class *name
256
;; (bignum) mpz_t name
257
;; (simple c-type) c-type
258
;; (special c-type mark-fn free-fn)
259
;; (special-struct c-type mark-fn free-fn)
263
;; (array type size) type name[size]
264
;; Variable size array (must be last) */
265
;; (var-array type size-field) type name[1]
267
;; (pointer type) type *name
268
;; (space type) Like pointer, but should be freed
270
;; (function type . arg-types) type name(arg-types)
272
;; NOTE: For function types, the arguments are represented simply as
273
;; strings or lists containing C declarations; they do not use the
276
;; (method type args)
277
;; is transformed into (pointer (function type self-arg args)) before
280
(define (type->category type)
282
(type->category `(simple ,type))
283
(let ((tag (car type)))
285
((string object static-object simple special special-struct
286
indirect-special space bignum struct) tag)
287
((array var-array pointer) (type->category (cadr type)))
289
(else (error "make_class: type->category: Invalid type" type))))))
291
(define (type->declaration type expr)
293
(type->declaration `(simple ,type) expr)
295
((string) (list "struct ol_string *" expr))
296
((object) (list "struct " (cadr type) " *" expr))
297
((static-object) (list "struct " (cadr type) " " expr))
298
((struct) (list "struct " (cadr type) " " expr))
299
((bignum) (list "mpz_t " expr))
300
((simple special special-struct indirect-special) (list (cadr type) " " expr))
301
((pointer space) (type->declaration (cadr type)
302
(list "(*(" expr "))")))
303
((array) (type->declaration (cadr type)
304
(list "((" expr ")[" (caddr type) "])")))
305
((var-array) (type->declaration (cadr type)
306
(list "((" expr ")[1])")))
307
((function) (type->declaration (cadr type)
309
"(" (implode (cddr type) ", ")
311
(else (error "make_class: type->declaration: Invalid type" type)))))
313
(define (type->mark type expr)
315
(type->mark `(simple ,type) expr)
317
((string simple function space bignum) #f)
318
((object) (list "mark((struct ol_object *) " expr ");\n"))
319
((static-object) (list "mark((struct ol_object *) &" expr ");\n"))
320
((struct) (list (cadr type) "_mark(&" expr ", mark);\n"))
321
((pointer) (if (null? (cddr type))
322
(type->mark (cadr type) (list "*(" expr ")"))
324
;; The optional argument should be the name of
325
;; an instance variable holding the length of
326
;; the area pointed to
327
(let ((mark-k (type->mark (cadr type)
328
(list "(" expr ")[k]"))))
330
(list "{\n unsigned k;\n"
331
" for (k=0; k<i->" (caddr type)
336
((special) (let ((mark-fn (caddr type)))
337
(and mark-fn (list mark-fn "(" expr ", mark);\n"))))
338
((indirect-special) (let ((mark-fn (caddr type)))
339
(and mark-fn (list mark-fn "(&(" expr
341
((special-struct) (let ((mark-fn (caddr type)))
342
(and mark-fn (list mark-fn "(&(" expr "), mark);\n"))))
344
;; FIXME: Doesn't handle nested arrays
346
(let ((mark-k (type->mark (cadr type) (list "(" expr ")[k]"))))
348
(list "{\n unsigned k;\n"
349
" for (k=0; k<" (caddr type) "; k++)\n"
353
(let ((mark-k (type->mark (cadr type) (list "(" expr ")[k]"))))
355
(list "{\n unsigned k;\n"
356
" for (k=0; k<i->" (caddr type) "; k++)\n"
360
(else (error "make_class: type->mark: Invalid type" type)))))
362
(define (type->free type expr)
364
(and f (list f "(" expr ");\n")))
367
(type->free `(simple ,type) expr)
369
((object simple function pointer) #f)
370
((static-object) (list "CLASS(" (cadr type) ").free_instance((struct ol_object *) &" expr ");\n"))
371
((struct) (list (cadr type) "_free(&" expr ");\n"))
372
((string) (free/f "ol_string_free"))
373
((bignum) (free/f "mpz_clear"))
374
((space) (free/f "ol_space_free"))
375
((special) (free/f (cadddr type)))
376
((special-struct) (let ((free-fn (cadddr type)))
378
(list free-fn "(&(" expr "));\n"))))
379
((indirect-special) (let ((free-fn (cadddr type)))
381
(list free-fn "(&(" expr "));\n"))))
385
(let ((free-k (type->free (cadr type) (list "(" expr ")[k]"))))
387
(list "{\n unsigned k;\n"
388
" for (k=0; k<" (caddr type) "; k++)\n"
392
(let ((free-k (type->free (cadr type) (list "(" expr ")[k]"))))
394
(list "{\n unsigned k;\n"
395
" for (k=0; k<i->" (caddr type) "; k++)\n"
399
(else (error "make_class: type->free: Invalid type" type)))))
402
(define (type->init type expr)
404
(type->init `(simple ,type) expr)
406
((object string space pointer) (list expr "= NULL;\n"))
407
((bignum) (list "mpz_init(" expr ");\n"))
409
(let ((init-k (type->init (cadr type) (list "(" expr ")[k]"))))
411
(list "{\n unsigned k;\n"
412
" for (k=0; k<" (caddr type) "; k++)\n"
416
(else (error "make_class: type->init: Invalid type" type)))))
419
(define var-name car)
420
(define var-type cdr)
422
(define (fix-method name var)
423
(let ((type (var-type var))
424
(variable (var-name var)))
429
`(,variable pointer (function ,(cadr type)
430
("struct " ,name " *self")
433
`(,variable pointer (function ,(cadr type)
434
("struct " ,name " **self")
438
(define (do-instance-struct name super vars)
439
; (werror "do-instance-struct\n")
442
" struct " (or super "ol_object") " super;\n"
444
(list " " (type->declaration (var-type var)
445
(var-name var)) ";\n"))
449
(define (do-struct name super vars)
450
; (werror "do-struct\n")
454
(list " " (type->declaration (var-type var)
455
(var-name var)) ";\n"))
459
(define (do-mark-function name vars)
460
; (werror "do-mark-function\n")
461
(let ((markers (filter identity
463
(type->mark (var-type var)
464
(list "i->" (var-name var))))
466
; (werror "gazonk\n")
467
(and (not (null? markers))
468
(list "static void do_"
469
name "_mark(struct ol_object *o, \n"
470
"void (*mark)(struct ol_object *o))\n"
472
" struct " name " *i = (struct " name " *) o;\n"
473
(map (lambda (x) (list " " x))
477
(define (do-free-function name vars)
478
; (werror "do-free-function\n")
479
(let ((freers (filter identity
481
(type->free (var-type var)
482
(list "i->" (var-name var))))
485
; (werror "gazonk\n")
487
(and (not (null? freers))
488
(list "static void do_"
489
name "_free(struct ol_object *o)\n"
491
" struct " name " *i = (struct " name " *) o;\n"
492
(map (lambda (x) (list " " x))
496
(define (declare-struct-mark-function name)
497
(list "void " name "_mark(struct " name " *i, \n"
498
" void (*mark)(struct ol_object *o))"))
500
(define (do-struct-mark-function name vars)
501
; (werror "do-struct-mark-function\n")
502
(let ((markers (filter identity
504
(type->mark (var-type var)
505
(list "i->" (var-name var))))
507
; (werror "gazonk\n")
508
(list (declare-struct-mark-function name)
510
; To avoid warnings for unused parameters
511
" (void) mark; (void) i;\n"
512
(map (lambda (x) (list " " x))
516
(define (declare-struct-free-function name)
517
(list "void " name "_free(struct " name " *i)"))
519
(define (do-struct-free-function name vars)
520
; (werror "do-struct-free-function\n")
521
(let ((freers (filter identity
523
(type->free (var-type var)
524
(list "i->" (var-name var))))
527
; (werror "gazonk\n")
529
(list (declare-struct-free-function name)
531
; To avoid warnings for unused parameters
533
(map (lambda (x) (list " " x))
537
(define (do-class name super mark-function free-function meta methods)
539
(list "{ STATIC_HEADER,\n "
541
; FIXME: A cast (struct ol_class *) or something
542
; equivalent is needed if the super class is not a
543
; struct ol_class *. For now, fixed with macros
544
; expanding to the right component of extended class
546
(list "&" super "_class")
548
", \"" name "\", sizeof(struct " name "),\n "
549
(if mark-function (list "do_" name "_mark") "NULL") ",\n "
550
(if free-function (list "do_" name "_free") "NULL") "\n"
552
; (werror "do-class\n")
554
(list "struct " meta "_meta " name "_class_extended =\n"
557
(map (lambda (m) (list ",\n " m)) methods)
560
"#define " name "_class (" name "_class_extended.super)\n")
561
(list "struct ol_class " name "_class =\n"
564
(define (process-class attributes)
565
(let ((name (get 'name attributes cadr))
566
(super (get 'super attributes cadr))
567
(raw-vars (get 'vars attributes cdr))
568
(meta (get 'meta attributes cadr))
569
(methods (get 'methods attributes cdr)))
570
(werror "Processing class ~S\n" name)
572
(let ((vars (map (lambda (var) (fix-method name var))
574
(let ((mark-function (do-mark-function name vars))
575
(free-function (do-free-function name vars)))
577
(list "#ifndef CLASS_DEFINE\n"
578
(do-instance-struct name super vars)
580
(list "extern struct " meta "_meta "
581
name "_class_extended;\n")
582
(list "extern struct ol_class " name "_class;\n"))
583
"#endif /* !CLASS_DEFINE */\n\n"
584
"#ifndef CLASS_DECLARE\n"
585
(or mark-function "")
586
(or free-function "")
587
(do-class name super mark-function free-function
589
"#endif /* !CLASS_DECLARE */\n\n")))))
591
(define (process-meta attributes)
592
(let ((name (get 'name attributes cadr))
593
(methods (get 'methods attributes cdr)))
594
(werror "Processing meta ~S\n" name)
595
(list "#ifndef CLASS_DEFINE\n"
596
"struct " name "_meta\n"
598
" struct ol_class super;\n"
599
(map (lambda (m) (list " " m ";\n"))
602
"#endif /* !CLASS_DEFINE */\n\n")))
604
(define (process-struct attributes)
605
(let ((name (get 'name attributes cadr))
606
(super (get 'super attributes cadr))
607
(raw-vars (get 'vars attributes cdr))
608
(meta (get 'meta attributes cadr))
609
(methods (get 'methods attributes cdr)))
610
(werror "Processing struct ~S\n" name)
612
;; FIXME: Is this really needed?
613
(let ((vars (map (lambda (var) (fix-method name var))
616
(list "#ifndef CLASS_DEFINE\n"
617
(do-struct name super vars)
618
"extern " (declare-struct-mark-function name) ";\n"
619
"extern " (declare-struct-free-function name) ";\n"
620
"#endif /* !CLASS_DEFINE */\n\n"
621
"#ifndef CLASS_DECLARE\n"
622
(do-struct-mark-function name vars)
623
(do-struct-free-function name vars)
624
"#endif /* !CLASS_DECLARE */\n\n"))))
626
;;;; Expression compiler
628
;; Can't use load; it writes messages to stdout.
631
;; Constants is an alist of (name value call_1 call_2 ... call_n)
632
;; where value is a C expression representing the value. call_i is
633
;; present, it is a function that can be called to apply the value to
634
;; i arguments directly.
635
(define (make-output constants)
636
;; OP and ARGS are C expressons
637
(define (apply-generic op args)
638
;; (werror "(apply-generic ~S)\n" (cons op args))
640
(apply-generic (list "A(" op ", " (car args) ")")
642
;; INFO is the (value [n]) associated with a constant,
643
;; and ARGS is a list of C expressions
644
(define (apply-constant info args)
645
;; (werror "apply-constant : ~S\n" info)
646
;; (werror " args : ~S\n" args)
647
(let ((calls (cdr info)))
649
(apply-generic (car info) args)
650
(let ((n (min (length calls) (length args))))
651
;; (werror "n: ~S\n" n)
652
(apply-generic (list (nth info n)
653
"(" (implode (list-prefix args n) ", ") ")")
654
(list-tail args n))))))
655
(define (lookup-global v)
656
(cond ((assq v constants) => cdr)
657
(else (error "make_class: undefined global" v))))
659
(define (output-expression expr)
660
;; (werror "output-expression ~S\n" expr)
662
(car (lookup-global expr))
663
(let ((op (application-op expr))
664
(args (map output-expression (application-args expr))))
666
(apply-constant (lookup-global op) args)
667
(apply-generic op args)))))
670
(define (process-expr attributes)
671
(define (declare-params params)
672
(implode (map (lambda (var)
673
(type->declaration (var-type var)
677
(define (params->alist params)
679
(let ((name (var-name var)))
680
(list name (list "((struct ol_object *) " name ")" ))))
684
(let ((name (get 'name attributes cadr))
685
(globals (or (get 'globals attributes cdr) '()))
686
(params (get 'params attributes cdr))
687
(expr (get 'expr attributes cadr)))
688
(werror "Processing expression ~S\n" name)
689
(let ((translated (translate expr)))
690
(werror "Compiled to ~S\n" translated)
691
(list "static struct ol_object *\n" name "("
692
(if params (declare-params params) "void")
694
(format #f " /* ~S */\n" translated)
695
"#define A CLASS_APPLY\n"
696
"#define I CLASS_VALUE_I\n"
697
"#define K CLASS_VALUE_K\n"
698
"#define K1 CLASS_APPLY_K_1\n"
699
"#define S CLASS_VALUE_S\n"
700
"#define S1 CLASS_APPLY_S_1\n"
701
"#define S2 CLASS_APPLY_S_2\n"
702
"#define B CLASS_VALUE_B\n"
703
"#define B1 CLASS_APPLY_B_1\n"
704
"#define B2 CLASS_APPLY_B_2\n"
705
"#define C CLASS_VALUE_C\n"
706
"#define C1 CLASS_APPLY_C_1\n"
707
"#define C2 CLASS_APPLY_C_2\n"
708
"#define Sp CLASS_VALUE_Sp\n"
709
"#define Sp1 CLASS_APPLY_Sp_1\n"
710
"#define Sp2 CLASS_APPLY_Sp_2\n"
711
"#define Sp3 CLASS_APPLY_Sp_3\n"
712
"#define Bp CLASS_VALUE_Bp\n"
713
"#define Bp1 CLASS_APPLY_Bp_1\n"
714
"#define Bp2 CLASS_APPLY_Bp_2\n"
715
"#define Bp3 CLASS_APPLY_Bp_3\n"
716
"#define Cp CLASS_VALUE_Cp\n"
717
"#define Cp1 CLASS_APPLY_Cp_1\n"
718
"#define Cp2 CLASS_APPLY_Cp_2\n"
719
"#define Cp3 CLASS_APPLY_Cp_3\n"
721
((make-output (append '( (I I)
731
(params->alist params)
762
(define (process-input exp)
763
(let ((type (car exp))
765
;; (werror "process-class: type = ~S\n" type)
767
((class) (process-class body))
768
((meta) (process-meta body))
769
((struct) (process-struct body))
770
((expr) (process-expr body))
771
(else (list "#error Unknown expression type " type "\n")))))
774
(let ((test (lambda (s) (string-prefix? "/* CLASS:" s))))
776
(let ((exp (read-expression test)))
777
(if (not (eof-object? exp))
779
(display (append-deep (process-input exp)))