chibi-r.scm

;
; Chibiのsyntax-rules実装を動かしてみる
;
; original: ~/research/chibi-scheme/lib/init-7.scm
(import (scheme base) (scheme write) (chibi)) ; (chibi syntax-case))

(define (syntax-rules-transformer expr rename compare)
  (let ((ellipsis-specified? (identifier? (cadr expr)))
        (count 0)
        (_er-macro-transformer (rename 'er-macro-transformer))
        (_lambda (rename 'lambda))      (_let (rename 'let))
        (_begin (rename 'begin))        (_if (rename 'if))
        (_and (rename 'and))            (_or (rename 'or))
        (_eq? (rename 'eq?))            (_equal? (rename 'equal?))
        (_car (rename 'car))            (_cdr (rename 'cdr))
        (_cons (rename 'cons))          (_pair? (rename 'pair?))
        (_null? (rename 'null?))        (_expr (rename 'expr))
        (_rename (rename 'rename))      (_compare (rename 'compare))
        (_quote (rename 'syntax-quote)) (_apply (rename 'apply))
        (_append (rename 'append))      (_map (rename 'map))
        (_vector? (rename 'vector?))    (_list? (rename 'list?))
        (_len (rename 'len))            (_length (rename 'length*))
        (_- (rename '-))   (_>= (rename '>=))   (_error (rename 'error))
        (_ls (rename 'ls)) (_res (rename 'res)) (_i (rename 'i))
        (_reverse (rename 'reverse))
        (_vector->list (rename 'vector->list))
        (_list->vector (rename 'list->vector))
        (_cons3 (rename 'cons-source))
        (_underscore (rename '_)))
    ; Decompose input (Note that the arity differs if custom ellipsis is specified)
    (define ellipsis (if ellipsis-specified? (cadr expr) (rename '...)))
    (define lits (if ellipsis-specified? (car (cddr expr)) (cadr expr)))
    (define forms (if ellipsis-specified? (cdr (cddr expr)) (cddr expr)))
    ; gensym
    (define (next-symbol s)
      (set! count (+ count 1))
      (rename (string->symbol (string-append s (%number->string count)))))

    (define (expand-pattern pat tmpl)
      (let lp ((p (cdr pat))
               (x (list _cdr _expr))
               (dim 0)
               (vars '())
               (k (lambda (vars)
                    (list _cons (expand-template tmpl vars) #f))))
        (display `(dim: ,dim vars: ,vars p: ,p)) (newline)
        (let ((v (next-symbol "v.")))
          (list
           _let (list (list v x))
           (cond
            ((identifier? p)
             (cond
              ((ellipsis-mark? p)
               (error "bad ellipsis" p))
              ((memq p lits)
               (list _and
                     (list _compare v (list _rename (list _quote p)))
                     (k vars)))
              ((compare p _underscore)
               (k vars))
              (else
               (list _let (list (list p v)) (k (cons (cons p dim) vars))))))
            ((ellipsis? p)
             (cond
              ((not (null? (cdr (cdr p))))
               (cond
                ((any (lambda (x) (and (identifier? x) (ellipsis-mark? x)))
                      (cddr p))
                 (error "multiple ellipses" p))
                (else
                 (let ((len (length* (cdr (cdr p))))
                       (_lp (next-symbol "lp.")))
                   ; Something like:
                   ; (let ((len (length <v>)))
                   ;   (and (>= len <len>)
                   ;        (let lp ((ls <v>)
                   ;                 (i (- len <len>))
                   ;                 (res (quote '())))
                   ;          (if (>= 0 i)
                   ;            <next loop>
                   ;            (lp (cdr ls) (- i 1) (cons3 (car ls) res ls))))))
                   `(,_let ((,_len (,_length ,v)))
                      (,_and (,_>= ,_len ,len)
                             (,_let ,_lp ((,_ls ,v)
                                          (,_i (,_- ,_len ,len))
                                          (,_res (,_quote ())))
                                    (,_if (,_>= 0 ,_i)
                                        ,(lp `(,(cddr p)
                                               (,(car p) ,(car (cdr p))))
                                             `(,_cons ,_ls
                                                      (,_cons (,_reverse ,_res)
                                                              (,_quote ())))
                                             dim
                                             vars
                                             k)
                                        (,_lp (,_cdr ,_ls)
                                              (,_- ,_i 1)
                                              (,_cons3 (,_car ,_ls)
                                                       ,_res
                                                       ,_ls))))))))))
              ((identifier? (car p))
               (list _and (list _list? v)
                     (list _let (list (list (car p) v))
                           (k (cons (cons (car p) (+ 1 dim)) vars)))))
              (else
               (let* ((w (next-symbol "w."))
                      (_lp (next-symbol "lp."))
                      (new-vars (all-vars (car p) (+ dim 1)))
                      (ls-vars (map (lambda (x)
                                      (next-symbol
                                       (string-append
                                        (symbol->string
                                         (identifier->symbol (car x)))
                                        "-ls")))
                                    new-vars))
                      (once
                       (lp (car p) (list _car w) (+ dim 1) '()
                           (lambda (_)
                             (cons
                              _lp
                              (cons
                               (list _cdr w)
                               (map (lambda (x l)
                                      (list _cons (car x) l))
                                    new-vars
                                    ls-vars)))))))
                 (list
                  _let
                  _lp (cons (list w v)
                            (map (lambda (x) (list x (list _quote '()))) ls-vars))
                  (list _if (list _null? w)
                        (list _let (map (lambda (x l)
                                          (list (car x) (list _reverse l)))
                                        new-vars
                                        ls-vars)
                              (k (append new-vars vars)))
                        (list _and (list _pair? w) once)))))))
            ((pair? p)
             (list _and (list _pair? v)
                   (lp (car p)
                       (list _car v)
                       dim
                       vars
                       (lambda (vars)
                         (lp (cdr p) (list _cdr v) dim vars k)))))
            ((vector? p)
             (list _and
                   (list _vector? v)
                   (lp (vector->list p) (list _vector->list v) dim vars k)))
            ((null? p) (list _and (list _null? v) (k vars)))
            (else (list _and (list _equal? v p) (k vars))))))))

    ; Return #t if it is an ellipsis
    (define ellipsis-mark?
      (if (if ellipsis-specified?   ; You cannot use ellipsis when the symbol is listed in `literals`
              (memq ellipsis lits)
              (any (lambda (x) (compare ellipsis x)) lits))
          (lambda (x) #f)
          (if ellipsis-specified?
              (lambda (x) (eq? ellipsis x))
              (lambda (x) (compare ellipsis x)))))

    ; Ellipsis means "escape this" when appeared on the head of a list
    (define (ellipsis-escape? x)
      (and (pair? x) (ellipsis-mark? (car x))))

    ; Return #t if it looks like `(foo ...)`
    (define (ellipsis? x)
      (and (pair? x) (pair? (cdr x)) (ellipsis-mark? (cadr x))))

    ; Return 1 for `(foo ...)`, `((foo ...) ...)`, etc.
    ; Return 2 for `(foo ... ...)`
    (define (ellipsis-depth x)
      (if (ellipsis? x)
          (+ 1 (ellipsis-depth (cdr x)))
          0))

    ; Return `()` for `(foo ...)`
    ; Return `1` for `(foo ... . 1)`
    ; Return `1` for `(foo ... ... . 1)`
    (define (ellipsis-tail x)
      (if (ellipsis? x)
          (ellipsis-tail (cdr x))
          (cdr x)))

;    (define (all-vars x dim)
;      (let ((result (all-vars_ x dim)))
;        (display `(all-vars x: ,x dim: ,dim result: ,result)) (newline)
;        result))
    ; List all the variables and its dimention like `((x . 1) (y . 1) (z . 2))`
    (define (all-vars x dim)
      (let lp ((x x) (dim dim) (vars '()))
        (cond ((identifier? x)
               (if (or (memq x lits)
                       (compare x _underscore))
                   vars
                   (cons (cons x dim) vars)))
              ((ellipsis? x) (lp (car x) (+ dim 1) (lp (cddr x) dim vars)))
              ((pair? x) (lp (car x) dim (lp (cdr x) dim vars)))
              ((vector? x) (lp (vector->list x) dim vars))
              (else vars))))

;    (define (free-vars x vars dim)
;      (let ((result (free-vars_ x vars dim)))
;        (display `(free-vars x: ,x vars: ,vars dim: ,dim result: ,result)) (newline)
;        result))
    ; eg. x: x vars: ((y . 1) (x . 2) (z . 0)) dim: 2 result: (x)
    (define (free-vars x vars dim)
      (let lp ((x x) (free '()))
        (cond
         ((identifier? x)
          (if (and (not (memq x free))
                   (cond ((assq x vars) => (lambda (cell) (>= (cdr cell) dim)))
                         (else #f)))
              (cons x free)
              free))
         ((pair? x) (lp (car x) (lp (cdr x) free)))
         ((vector? x) (lp (vector->list x) free))
         (else free))))

    (define (expand-template tmpl vars)
      (let lp ((t tmpl) (dim 0) (ell-esc #f))
        (cond
         ((identifier? t)
          (cond
           ((find (lambda (v) (eq? t (car v))) vars)
            => (lambda (cell)
                 (if (<= (cdr cell) dim)
                     t
                     (error "too few ...'s"))))
           (else
            (list _rename (list _quote t)))))
         ((pair? t)
          (cond
           ((and (ellipsis-escape? t) (not ell-esc))
            (lp (if (and (pair? (cdr t)) (null? (cddr t))) (cadr t) (cdr t)) dim #t))
           ((and (ellipsis? t) (not ell-esc))
            (let* ((depth (ellipsis-depth t))
                   (ell-dim (+ dim depth))
                   (ell-vars (free-vars (car t) vars ell-dim)))
              (cond
               ((null? ell-vars)
                (error "too many ...'s"))
               ((and (null? (cdr (cdr t))) (identifier? (car t)))
                ;; shortcut for (var ...)
                (lp (car t) ell-dim ell-esc))
               (else
                (let* ((once (lp (car t) ell-dim ell-esc))
                       (nest (if (and (null? (cdr ell-vars))
                                      (identifier? once)
                                      (eq? once (car vars)))
                                 once ;; shortcut
                                 (cons _map
                                       (cons (list _lambda ell-vars once)
                                             ell-vars))))
                       (many (do ((d depth (- d 1))
                                  (many nest
                                        (list _apply _append many)))
                                 ((= d 1) many))))
                  (if (null? (ellipsis-tail t))
                      many ;; shortcut
                      (list _append many (lp (ellipsis-tail t) dim ell-esc))))))))
           (else (list _cons3 (lp (car t) dim ell-esc) (lp (cdr t) dim ell-esc) (list _quote t)))))
         ((vector? t) (list _list->vector (lp (vector->list t) dim ell-esc)))
         ((null? t) (list _quote '()))
         (else t))))

    ; Main
    ; 
    ;   (er-macro-transformer (lambda (expr rename compare)
    ;     (car
    ;       (or
    ;         <expand-pattern>
    ;         (cons (error "no expansion for" (strip-syntactic-closures expr))
    ;               #f)))))
    (list
     _er-macro-transformer
     (list _lambda (list _expr _rename _compare)
           (list
            _car
            (cons
             _or
             (append
              (map
               (lambda (clause) (expand-pattern (car clause) (cadr clause)))
               forms)
              (list
               (list _cons
                     (list _error "no expansion for"
                           (list (rename 'strip-syntactic-closures) _expr))
                     #f)))))))))
; ----

;(define identifier? symbol?)
(display
  (syntax-rules-transformer
    ; expr
;    '(syntax-rules () 
;       ((_ a b)
;        (let ((temp a)) (set! a b) (set! b a))))
    '(syntax-rules ()
       ((a b)
        (b a)))

    (lambda (name) name) ; rename
    equal? ; compare
    ))

使い方

$ chibi-scheme chibi-r.scm

例

% chibi-scheme ,/syntax-rules/chibi-r.scm
(dim: 0 vars: () p: (b))
(dim: 0 vars: () p: b)
(dim: 0 vars: ((b . 0)) p: ())
(er-macro-transformer (lambda (expr rename compare) (car (or (let ((v.1 (cdr expr))) (and (pair? v.1) (let ((v.2 (car v.1))) (let ((b v.2)) (let ((v.3 (cdr v.1))) (and (null? v.3) (cons (cons-source b (cons-source (rename (syntax-quote a)) (syntax-quote ()) (syntax-quote (a))) (syntax-quote (b a))) #f))))))) (cons (error "no expansion for" (strip-syntactic-closures expr)) #f)))))

これを整形すると以下のような形になっていることがわかる。

(er-macro-transformer 
(lambda (expr rename compare) 
(car (or 
  ;; clause 1
  ; 入力を分解しつつパーツをa, bに束縛する
  (let ((v.1 (cdr expr)))
  (and (pair? v.1)
  (let ((v.2 (car v.1)))
  (let ((b v.2))
  (let ((v.3 (cdr v.1)))
  (and (null? v.3)
  ; 最後までマッチしたら以下のようにして「a,bから変換後プログラムを組み立てるSchemeコード」を作る
  (cons (cons-source b (cons-source (rename (syntax-quote a)) (syntax-quote ()) (syntax-quote (a))) (syntax-quote (b a))) #f)))))))

ちなみに (car (or のようにcarを取ってるのは、「clauseにマッチしなかった場合の#f」と「clauseの実行結果が#fだった場合」を区別するためかなと思う。

cons-sourceの第三引数は無視するとシンプルになる

  (cons (cons-source b 
              (cons-source (rename (syntax-quote a)) (syntax-quote ())))
            #f)))))))