lisp - 通过在 racket 中设计一个解释器来重写这个脚本

Question

原脚本是这样的:

#lang racket
(for ([i (in-range 3)])
    (for ([j (in-range 9)])
      (display "X"))
     (display "\n"))

(for ([i (in-range 6)])
  (for ([j (in-range 3)])
    (display " "))
  (for ([j (in-range 3)])
    (display "X"))
  (for ([j (in-range 3)])
    (display " "))
  (display "\n"))

(for ([i (in-range 3)])
    (for ([j (in-range 9)])
      (display "X"))
     (display "\n"))

输出是:

XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
   XXX   
   XXX   
   XXX   
   XXX   
   XXX   
   XXX   
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

我想知道我是否可以使用像这样的 DSL 重写它:

(define a
  "3 9 X
6 3 b 3 X 3 b
3 9 X")

然后:

(interpret a)

绘制此图。

有谁知道最好的方法是什么？

Answer 1

要解决此类问题，首先要描述一种数据类型，它可以捕获您在 DSL 中所需的操作，而不是专注于表面语法。一旦掌握了数据类型，您应该更容易解决问题。

乍一看，我们似乎可以用您的语言设计 3 种基本形式:

1. 字符串
2. 重复
3. 测序

我们可以用原始字符串和结构来表示这个不相交的类。让我们将这个类作为一个整体称为“pexpr”，表示“可打印的 expr”。在代码中:

;; An pexpr is one of the following:
;;   * a primitive string,
;;   * a seq, or
;;   * a repeat
(struct seq (bodies) #:transparent)    ;; bodies is a list of pexpr
(struct repeat (n body) #:transparent) ;; n is a number, body is a pexpr

由于“seq”和“repeat”本身有点冗长，因此将一些辅助函数作为缩写可能会有所帮助。

;; For convenience, we define some abbreviations s and r for seq and repeat,
;; respectively.
(define (s . bodies)
  (seq bodies))
(define (r n . bodies)
  (repeat n (seq bodies)))

您的示例“I”字符串可以这样写:

(define an-example
  (s
   (r 3 (r 9 "X") "\n")
   (r 6 (r 3 " ") (r 3 "X") "\n")
   (r 3 (r 9 "X") "\n")))

请注意，此编码对换行符有显式表示，仅从表面语法来看，它是隐式的。然后解析器的工作就是在你的表面语法中提取行并将它们转换成 pexprs，但这应该不会太难。希望。 :)

无论如何，interpret 函数变成了为模板填写详细信息的问题，如下所示:

(define (interpret pexpr)
  (match pexpr
    [(? string?)
     ...]
    [(struct seq (bodies))
     ...]
    [(struct repeat (n body))
     ...]))

“...”应该很容易填写。

这种解决此类问题的方法由 How to Design Programs 描述。和 Programming Languages: Application and Interpretation .我建议您看看它们:它们是好东西。