Scheme：如何快速识别宏展开前后s-exp的对应关系？

Programming
,
1

我正在写scheme-langserver的一个核心功能，它要求快速识别宏展开前后s-expression的对应关系，场景如下。

;;a try-except s-expression to handle possible exceptions
(try 
  ;;some works
  todo 
  ;;to catch exception c
  (except c 
  ;; a branch to handle
    [else c])

对于以上代码，在LSP（language server protocol）支持的IDE场景下，我们经常希望识别branch里面的c，把它和except后面的c做一个关联。因为显然后者是try-except结构捕捉到的一个异常，而前者是对这个异常的调用。这个关联可以用于goto-definition等操作，即当用户想要寻找branch里面的c的时候，IDE把except后面那个c突显（高亮等）出来。

很多情况下，待处理的宏往往是用户自定义如下：

(define-syntax try
  (lambda (x)
    (syntax-case x (except)
      [(try body0 body1 ... (except condition clause0 clause1 ...))
       #`((call/1cc
       (lambda (escape)
         (with-exception-handler
           (lambda (c)
         (let ([condition c])     ;; clauses may set! this
           #,(let loop ([first #'clause0] [rest #'(clause1 ...)])
               (if (null? rest)
               (syntax-case first (else =>)
                 [(else h0 h1 ...) #'(escape (lambda () h0 h1 ...))]
                 [(tst) #'(let ([t tst]) (if t (escape (lambda () t)) (raise c)))]
                 [(tst => l) #'(let ([t tst]) (if t (escape (lambda () (l t))) (raise c)))]
                 [(tst h0 h1 ...) #'(if tst (escape (lambda () h0 h1 ...)) (raise c))])
               (syntax-case first (=>)
                 [(tst) #`(let ([t tst]) (if t (escape (lambda () t)) #,(loop (car rest) (cdr rest))))]
                 [(tst => l) #`(let ([t tst]) (if t (escape (lambda () (l t))) #,(loop (car rest) (cdr rest))))]
                 [(tst h0 h1 ...) #`(if tst (escape (lambda () h0 h1 ...)) #,(loop (car rest) (cdr rest)))])))))
           (lambda ()
         ;; cater for multiple return values
         (call-with-values
             (lambda () body0 body1 ...)
           (lambda args
             (escape (lambda ()
                   (apply values args))))))))))])))

我可以获得宏展开以后的结果如下：

((call/1cc
   (lambda (escape)
     (with-exception-handler
       (lambda (c) (let ([c c]) (escape (lambda () c))))
       (lambda ()
         (call-with-values
           (lambda () todo)
           (lambda args (escape (lambda () (apply values args))))))))))

难题：我现在已经实现了一个分析的程序，但是效率比较低，程序比较复杂。能否使用scheme本身的一些函数和机制优化？

2

标准 Scheme 没有什么有用的东西能给你用，建议魔改 Chez 的 src/syntax.ss，看 gen-syntax-case 的定义，想办法在 syntax-case 展开时把原来的 source 信息挂上去

2 个赞
3

我现在的情况是写了一个“伪”step-by-step expander，获得了这样一条关系链： callee->template->template in expansion rules->expansion。 显然，我想要的是callee->expansion。 这里面template in expansion rules->expansion效率很低。因为等于是两个树从根节点开始一一对比，并且按规则确定是否要跳转树上的下一个节点。 说起来这算是……树的对比算法？

4

有个取巧的方法，宏展开前对原代码做变換，对变量名编码进位置信息(可能还要 hook 一些相关 built in function 在展开时无视编码的信息)

;;a try-except s-expression to handle possible exceptions
(try 
  ;;some works
  todo
  ;;to catch exception c
  (except c:#1
  ;; a branch to handle
    [else c:#2])

在展开的代码里正常做 variable scope 分析，找到变量的声明位置，再按额外编码的信息到展开前的代码里找对应的变量名。

至于怎么判定是变量名还是关键字，简单的方法是先展开一次看哪些 id 是共通的。

这样，只要展开两次就行了，之后就是简单的 treewalk

5

这个方法我想过，难点在于不清楚这是否会改变宏的逻辑。

6

所以需要去翻Chez对syntax object的实现看哪里适合揷入额外的信息而不影响 syntax rule 工作

参考 R6RS library manual chapter 12 的内容就是了

7

借这个话题问一下大佬，define-syntax的实现难度高么？可以纯粹用Scheme实现么？

我现在在Goldfish Scheme里面没有define-syntax用，挺难受的

8

参考 MIT Scheme，写个 R4RS 版本的 syntax-rules 实现不那么难

要实现 syntax-case 成本就上去了

编译器本身不支持基本的宏的话是不能实现的，s7 的过程宏可以当个基础。