自定义语言 - clojure 解释器中的 FOR 循环？

Question

我有一个 clojure 的基本解释器。现在我需要为

for (initialisation; finish-test; loop-update) {
    statements
}  

解释语言实现类似的 for 循环。模式将是：

(for variable-declarations end-test loop-update do statement)

变量声明将为变量设置初始值。结束测试返回一个布尔值，如果结束测试返回 false，则循环将结束。该语句被解释，然后是每个的循环更新 循环的通过。 使用示例有：

(run '(for ((i 0)) (< i 10) (set i (+ 1 i)) do (println i)))

(run '(for ((i 0) (j 0)) (< i 10) (seq (set i (+ 1 i)) (set j (+ j (* 2 i)))) do (println j)))

在我的解释器中。我将附上我到目前为止得到的解释器代码。任何帮助表示赞赏。

解释器

(declare interpret make-env) ;; needed as language terms call out to 'interpret'

(def do-trace false) ;; change to 'true' to show calls to 'interpret'

;; simple utilities

(def third ; return third item in a list
 (fn [a-list]
  (second (rest a-list))))

(def fourth ; return fourth item in a list
 (fn [a-list]
  (third (rest a-list))))

(def run ; make it easy to test the interpreter
 (fn [e]
  (println "Processing: " e)
  (println "=> " (interpret e (make-env)))))

;; for the environment

(def make-env
  (fn []
    '()))

(def add-var
  (fn [env var val]
    (cons (list var val) env)))

(def lookup-var
  (fn [env var]
    (cond (empty? env) 'error
          (= (first (first env)) var) (second (first env))
          :else (lookup-var (rest env) var))))

;; for terms in language

;; -- define numbers

(def is-number?
 (fn [expn]
  (number? expn)))

(def interpret-number
 (fn [expn env]
  expn))

;; -- define symbols

(def is-symbol?
  (fn [expn]
    (symbol? expn)))

(def interpret-symbol
  (fn [expn env]
    (lookup-var env expn)))

;; -- define boolean

(def is-boolean?
  (fn [expn]
    (or
      (= expn 'true)
      (= expn 'false))))

(def interpret-boolean
  (fn [expn env]
    expn))

;; -- define functions

(def is-function?
  (fn [expn]
    (and 
      (list? expn)
      (= 3 (count expn))
      (= 'lambda (first expn)))))

(def interpret-function ; keep function definitions as they are written
  (fn [expn env]
    expn))

;; -- define addition

(def is-plus?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '+ (first expn)))))

(def interpret-plus
 (fn [expn env]
  (+ 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define subtraction

(def is-minus?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '- (first expn)))))

(def interpret-minus
 (fn [expn env]
  (- 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define multiplication

(def is-times?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '* (first expn)))))

(def interpret-times
 (fn [expn env]
  (* 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define division

(def is-divides?
 (fn [expn]
  (and 
   (list? expn)
   (= 3 (count expn))
   (= '/ (first expn)))))

(def interpret-divides
 (fn [expn env]
  (/ 
   (interpret (second expn) env)
   (interpret (third expn) env))))

;; -- define equals test

(def is-equals?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= '= (first expn)))))

(def interpret-equals
  (fn [expn env]
    (=
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define greater-than test

(def is-greater-than?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= '> (first expn)))))

(def interpret-greater-than
  (fn [expn env]
    (>
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define not

(def is-not?
  (fn [expn]
    (and 
      (list? expn)
      (= 2 (count expn))
      (= 'not (first expn)))))

(def interpret-not
  (fn [expn env]
    (not
      (interpret (second expn) env))))

;; -- define or

(def is-or?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'or (first expn)))))

(def interpret-or
  (fn [expn env]
    (or
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define and

(def is-and?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'and (first expn)))))

(def interpret-and
  (fn [expn env]
    (and
      (interpret (second expn) env)
      (interpret (third expn) env))))

;; -- define print

(def is-print?
     (fn [expn]
  (and
    (list? expn)
    (= 2 (count expn))
    (= 'println (first expn)))))

(def interpret-print
     (fn [expn env]
  (println (interpret (second expn) env))))

;; -- define with

(def is-with?
  (fn [expn]
    (and
      (list? expn)
      (= 3 (count expn))
      (= 'with (first expn)))))

(def interpret-with
  (fn [expn env]
    (interpret (third expn)
               (add-var env 
                        (first (second expn))
                        (interpret (second (second expn)) env)))))

;; -- define if

(def is-if?
  (fn [expn]
    (and
      (list? expn)
      (= 4 (count expn))
      (= 'if (first expn)))))

(def interpret-if
  (fn [expn env]
    (cond (interpret (second expn) env) (interpret (third expn) env)
          :else                         (interpret (fourth expn) env))))

;; -- define function-application

(def is-function-application?
  (fn [expn env]
    (and
      (list? expn)
      (= 2 (count expn))
      (is-function? (interpret (first expn) env)))))

(def interpret-function-application
  (fn [expn env]
    (let [function (interpret (first expn) env)]
      (interpret (third function)
                 (add-var env
                          (first (second function))
                          (interpret (second expn) env))))))

;; the interpreter itself

(def interpret
  (fn [expn env]
    (cond do-trace (println "Interpret is processing: " expn))
    (cond 
      ; basic values
      (is-number? expn) (interpret-number expn env)
      (is-symbol? expn) (interpret-symbol expn env)
      (is-boolean? expn) (interpret-boolean expn env)
      (is-function? expn) (interpret-function expn env)
      ; built-in functions
      (is-plus? expn) (interpret-plus expn env)
      (is-minus? expn) (interpret-minus expn env)
      (is-times? expn) (interpret-times expn env)
      (is-divides? expn) (interpret-divides expn env)
      (is-equals? expn) (interpret-equals expn env)
      (is-greater-than? expn) (interpret-greater-than expn env)
      (is-not? expn) (interpret-not expn env)
      (is-or? expn) (interpret-or expn env)
      (is-and? expn) (interpret-and expn env)
      (is-print? expn) (interpret-print expn env)
      ; special syntax
      (is-with? expn) (interpret-with expn env)
      (is-if? expn) (interpret-if expn env)
      ; functions
      (is-function-application? expn env) (interpret-function-application expn env)
      :else 'error)))

;; tests of using environment

(println "Environment tests:")
(println (add-var (make-env) 'x 1))
(println (add-var (add-var (add-var (make-env) 'x 1) 'y 2) 'x 3))
(println (lookup-var '() 'x))
(println (lookup-var '((x 1)) 'x))
(println (lookup-var '((x 1) (y 2)) 'x))
(println (lookup-var '((x 1) (y 2)) 'y))
(println (lookup-var '((x 3) (y 2) (x 1)) 'x))

;; examples of using interpreter

(println "Interpreter examples:")
(run '1)
(run '2)
(run '(+ 1 2))
(run '(/ (* (+ 4 5) (- 2 4)) 2))
(run '(with (x 1) x))
(run '(with (x 1) (with (y 2) (+ x y))))
(run '(with (x (+ 2 4)) x))
(run 'false)
(run '(not false))
(run '(with (x true) (with (y false) (or x y))))
(run '(or (= 3 4) (> 4 3)))
(run '(with (x 1) (if (= x 1) 2 3)))
(run '(with (x 2) (if (= x 1) 2 3)))
(run '((lambda (n) (* 2 n)) 4))
(run '(with (double (lambda (n) (* 2 n)))
            (double 4)))
(run '(with (sum-to (lambda (n) (if (= n 0) 0 (+ n (sum-to (- n 1))))))
            (sum-to 100)))
(run '(with (x 1)
            (with (f (lambda (n) (+ n x)))
                  (with (x 2)
                        (println (f 3))))))

添加了 is-for？和解释，但仍然不确定不是最好的编写方式。

;; -- define for loop

(def is-for? 
  (fn [expn] 
    (and (list? expn) 
      (= 6 (count expn)) 
      (= 'for (first expn))
      (= 'do (fifth expn) ) 
      (list? (fourth expn)))))

(def interpret-for
  (fn [expn env]
    ()))

;;-插入到 def 解释中

      (is-for? expn) (interpret-for expn env)

Answer 1

Clojure 中的循环通常写成 loop/recur 形式，例如：

(loop [variable binding]
  ;; do something
  (if end-test
      return-value
      (recur (step variable))))

文档。

编辑：由于这似乎至少令一位读者不满意，因此我将添加一些您需要对此执行的操作，以符合解释器中规定的约定：

• 定义一个 is -for?，它检查您的表单
• 定义一个 interpret-for，它采用表达式的相应部分并构造上面所示类型的循环形式
• 向 cond 添加相应的子句解释中的表单

Answer 2

看看 clj-iter：https://github.com/nathell/clj-iter

Answer 3

请注意它现在有多有用，但我在 Clojure 中编写了一个 for 循环宏，它基本上可以满足您的需求。这是使用宏向语言添加新结构的一个很好的例子。

您可能需要修改它以适合您的解释器：

(defmacro for-loop [[sym init check change :as params] & steps]
  (cond
    (not (vector? params)) 
      (throw (Error. "Binding form must be a vector for for-loop"))
    (not= 4 (count params)) 
      (throw (Error. "Binding form must have exactly 4 arguments in for-loop"))
    :default
      `(loop [~sym ~init value# nil]
         (if ~check
           (let [new-value# (do ~@steps)]
             (recur ~change new-value#))
           value#))))

用法如下：

(for-loop [i 0 (< i 10) (inc i)] 
  (println i))

Answer 4

我很高兴看到您正在实现自己的语言！这是一次令人大开眼界的体验，因为您被迫理解语言含义中的微妙细节。

如何向当前形式的语言添加 for 循环结构并不明显。到目前为止，您的语言在其风格上看起来非常实用。表达式的含义是根据其子表达式的含义来描述的。很不错！一些副作用也是可能的，例如 println。

解释器当前形式的问题在于表达式没有任何方法可以更改其环境。换句话说，你没有任何方法来分配变量。对于像“for”这样的命令式循环结构，这是必需的。现在是决定循环是命令式的（如“for”）还是函数式的（使用递归或 Clojure 中的循环/递归之类的东西）的好时机。

为了回答实际问题，我将描述如何向语言添加命令式结构并添加“for”。我将首先描述一种纯函数式方法。

首先，您需要实现“set”结构。它有什么作用？给定 '(set x 2) 和环境 '((x 1)) 它应该产生一个像 '((x 2)) 这样的新环境代码>.这确实非常适合现有的解释函数，因为它们接收表达式和环境并返回值。我们还需要能够返回修改后的环境才能实现设置！

一种解决方案是更改“interpret-foo”函数的约定，让它们返回一对值和环境。以下是 inform-plus 在新方案中的外观：

(defn interpret-plus [plus-expn env0]
  (let [[_ l-expn r-expn] plus-expn
        [l-val env1] (interpret l-expn env0)
        [r-val env2] (interpret r-expn env1)]
    [(+ val1 val2) env2]))

请注意修改环境的效果是如何通过解释调用“线程化”的。我还冒昧地重新组织了一下代码： (def f (fn ...)) → (defn f ...), (f (第一个 x) (第二个 x)) → (let [[ab] x] (fab)), (list ab) → [ ab]。在新方案中，“set”很容易实现：

(defn set-var [env var val]
  (cond (empty? env) 'error
        (= (first (first env)) var) (cons (list var val) (rest env))
        :else (cons (first env) (set-var (rest env) var val))))

(defn interpret-set [set-expn env0]
  (let [[_ var val-expn] set-expn
        [val env1] (interpret val-expn env0)]
    [val (set-var env1 var val)]))

这里我选择让 (set ...) 表达式计算其绑定到变量的值，例如 = 在 C 中也是如此。其他值如 nil 或 'ok 也可以。现在可以实现“for”结构：

(defn apply-decl [decl env0]
  (let [[var expn] decl
        [val env1] (interpret expn env0)]
    (add-var env1 var val)))

(defn apply-decls [decls env0]
  (reduce (fn [env decl]
            (apply-decl devl env))
          env0
          decls))

(defn interpret-for [for-expn env0]
  (let [[_ decls end-test loop-update _ statement] for-expn
        env1 (apply-decls devls env0)]
    (loop [env env1]
      (let [[end-test-val env2] (interpret end-test env)]
        (if end-test-val
          (let [[_ env3] (interpret statement env2)
                [_ env4] (interpret loop-update env3)]
            (recur env4))
          [nil env2])))))

(defn interpret-seq [seq-expn env0]
  (reduce (fn [env expn]
            (let [[_ env1] (interpret expn env)]
              env1))
          env0
          (rest seq-expn)))

就是这样！这是一个纯粹的功能实现。您还可以“借用”Clojure 的副作用功能，并允许环境在内部发生变化。代码变得更短，但不那么明确。下面是原始解释器方案中的一个替代实现（其中解释函数只返回一个值）：

(defn make-env []
 '())

(defn add-var [env var val]
  (cons (list var (atom val))
        env))

(defn lookup-var [env var]
  (cond (empty? env) 'error
        (= (first (first env)) var) (deref (second (first env)))
        :else (recur (rest env) var)))

(defn set-var [env var val]
  (cond (empty? env) 'error
        (= (first (first env)) var) (reset! (second (first env)) val)
        :else (recur (rest env) var val)))

(defn interpret-set [expn env]
  (set-var env (second expn) (interpret (third expn) env)))

(defn apply-decl [decl env]
  (add-var env (first decl) (interpret (second decl) env)))

(defn apply-decls [decls env0]
  (reduce (fn [env decl]
            (apply-decl devl env))
          env0
          decls))

(defn interpret-for [expn env0]
  (let [env1 (apply-decls (second expn) env0)]
    (loop []
      (if (interpret (third expn) env1)
        (do (interpret (sixth expn) env1)
            (interpret (fourth expn) env1)
            (recur))
        nil))))

(defn interpret-seq [seq-expn env]
  (doseq [expn (rest seq-expn)]
    (interpret expn env)))

正如您所看到的，Clojure 更喜欢明确突变。这里使用的引用原语是atom，相关函数是atom、deref和reset!。另外，(loop [] (if x (do abc) nil)) 部分可以替换为 (while xabc)。我承认我有点马虎；我还没有测试上面的所有代码。如果某些内容不起作用或者您希望我澄清某些内容，请发表评论。