Scheme Lisp - 对任意算术表达式使用 eval
Scheme Lisp - Using eval for arbitrary arithmetic expressions
我正在尝试使用 eval 评估方案中的任意和嵌套算术表达式。
表达式由数字、运算符、常量绑定和括号组成。
例如，(eval (+ 1 1)) 或 (eval (+ (* 1 2) 3))
问题是，表达式也可能有不平衡的括号，比如
(eval ((+ 1 1))，而scheme中的reader只会在输入表达式时等待
直到所有括号都关闭并以某种方式匹配。
我查看了 scheme 中的引用，并通过在 scheme 中使用 try-catch-mechanism
(How to implement a try-catch block in scheme?) -
但这没有用。我也在考虑在方案中实现我自己的算术表达式求值器版本，
也许用括号作为分隔符。
我寻找一种方法来评估任意表达式，如果表达式是
无效，从 eval 中获取类似 'not valid expression' 的错误消息，并且没有 reader 等待右括号。
编辑：
请参阅下面的解决方案实施。
你的策略行不通。 Scheme 有“try-catch”，但就像大多数编程语言中的“try-catch”一样，它只适用于运行时错误（程序运行时发生的错误）。相比之下，不平衡的括号问题是语法错误（读取程序时发生的错误）。
例如在Python中可以这样写：
try:
1 / 0
except:
pass
这会捕获错误，但不会捕获像这样的语法错误：
try:
if
except:
pass
如果你想让输入有不平衡的括号，那么你需要将输入作为字符串而不是作为语言本身的表达式。例如：
(define my-input "(+ 1 1")
完全没问题，但是：
(define my-input (+ 1 1)
不是。
但是，对输入字符串进行计算很烦人。因此，您应该做的下一步是将输入字符串标记化并解析为一棵树。这里也是检测括号不平衡报错的地方：
(define (parse input-string)
;; TODO
)
(parse "(+ 1 2)")
;; expect '(+ 1 2)
(parse "(+ 1 2")
;; expect an error: "not valid expression"
假设 parse 没有错误，那么您将有一个像 '(+ 1 2) 这样的树作为输出。下一步是编写一个函数来消耗一棵树并产生一个答案
(define (interp input-tree)
;; TODO
)
(interp '(+ 1 2))
;; expect 3
(interp '(+ (+ 5 6) 7))
;; expect 18
你的 eval 只是 parse 和 interp:
的组合
(define (eval input-string)
(interp (parse input-string)))
(eval "(+ 1 2)")
;; expect 3
(eval "(+ 1 2")
;; expect an error: "not valid expression"
如果正如您所说，您尝试解析的表达式可能有不平衡的括号，那么这些表达式显然存在于一些非结构化数据中，几乎可以肯定是某种字符序列。由于你要阅读的表达式的语法是Scheme语法的一个子集，那么你可以简单地使用该语言为你提供的工具：read：你绝对不想为此编写自己的解析器，除非你喜欢花很多时间来正确处理极端情况。
请注意，任何 将字符序列转换为某个对象的解析器必须在某个时候请求序列中的下一个字符。对此可能会发生两件事：
- 它可以获得一个字符，可能是在等待该序列另一端的某个东西（也许是一个人）生成该字符之后；
- 它可以得到没有更多字符的指示——某种 end-of-file 指示。
没有任何魔法可以避免这种情况。所以你描述的 reader 等待 close-paren 的问题是不真实的： 你写的任何解析器 都会有同样的问题，当从交互式流中读取时：它只需等待该流另一端的人输入内容，或指示流已完成，此时它可以决定它看到的是否是 well-formed。
所以你问题的turning-sequences-of-characters-into-object部分的答案是使用语言提供的read。这是一种方法 - 因为您已经指定您正在使用 Racket，所以它使用 Racket，而不是任何 n 的 RnRS Scheme。如果您不关心对 reader 进行某种程度的限制（我不确定我是否对它进行了足够的限制），则几乎不需要所有这些代码。其余部分处理来自 reader 的异常，并将它们转换为多个值。
(define (read-thing source)
;; Read some object from a source port.
;; Return two values: either the object read and #t,
;; or some exception object and #f if something went wrong.
;;
;; This tries to defang the reader but I am not sure it does enough
(with-handlers ([exn? (λ (e) (values e #f))])
(call-with-default-reading-parameterization
(thunk
(parameterize ([read-accept-lang #f]
[read-accept-reader #f])
(values (read source) #t))))))
(define (read-thing-from-file f)
;; read a thing from a file
(call-with-input-file f read-thing))
(define (read-thing-from-string s)
;; read a thing from a string
(call-with-input-string s read-thing))
现在我们可以试试这个了：
> (read-thing-from-string "foo")
'foo
#t
> (read-thing-from-string "(foo")
(exn:fail:read:eof
"read: expected a `)` to close `(`"
#<continuation-mark-set>
(list (srcloc 'string #f #f 1 1)))
#f
如您所见，第二个值告诉您 read 是否引发异常。
现在您可以使用此 thing-reader 来为评估者提供信息。例如，您可以使用这样的函数：
(define (read-and-evaluate reader source
evaluator environment)
;; Read something with a read-thing compatible reader from source
;; and hand it to evaluator with environment as a second argument
;; If read-thing indicates an error then simply raise it again.
(call-with-values
(thunk (reader source))
(λ (thing good)
(when (not good)
(raise thing))
(evaluator thing environment))))
所以现在，问题减少到写 evaluator，我不打算这样做。
这里是这个函数与一个简单的求值器一起使用的例子，它只是 returns 它给出的形式。
> (read-and-evaluate
read-thing-from-string "(foo)"
(λ (form env) form) #f)
'(foo)
> (read-and-evaluate
read-thing-from-string "(foo"
(λ (form env) form) #f)
; string::1: read: expected a `)` to close `(` [,bt for context]
当然，这里不需要整个 handling-the-exception-in-the-reader 东西，因为我最终做了它重新提出它，但它确实向您展示了如何处理这样的错误。
关于编写求值器的说明。很容易说，好吧，(+ 1 2) 是一个有效的 Scheme 表达式，而 Scheme 有 eval 所以就用它吧。这就好比用热核装置拆房子，拆房子的效果很好，却造成了几十万人死亡等不良后果。例如，考虑 (system "rm -rf $HOME") 也是 也是 一个有效的 Racket 表达式，但您可能不想 运行.
为了避免这种 code-injection 攻击，您希望尽可能多地限制评估器，因此它将评估 仅 您感兴趣的语言. 这同样适用于 reader：在完整的 Racket reader 之上，我几乎可以肯定，可以在 read-time 评估任意 Racket 代码：我已经尝试（但可能失败）来 defang它在上面。
Racket 有一套重要的工具，可以让你定义一种更受限制的语言，eval 对这种语言来说是安全的。然而，对于 really 简单的语言，例如计算算术表达式，几乎可以肯定的是，简单地编写自己的计算器会更简单。这样做当然更有教育意义。
在@tfb 和@sorawee-porncharoenwase 的帮助下，我现在得到了一个可行的解决方案。
在我看来，这与执行任意 Scheme/Racket 表达式有关，
其中一些可能没有帮助。
让我们先来玩一下@tfb 的过程定义。
(+ 1 b) 是一个有效的 Scheme/Racket 表达式，因此 read-thing-from-string 应该声明它是有效的。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(+ 1 b)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
;; -> "Valid Scheme/Racket expression"
(( 1 b) 不是有效的 Scheme/Racket 表达式，正如 read-thing-from-string 识别的那样。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(( 1 b)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
; -> "Not valid Scheme/Racket expression"
我只想能够计算任意算术表达式，
像 (+ 1 1)，但是像 (a b 1) 这样的表达式是一个有效的 Scheme/Racket 表达式，应该被这样识别。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(a b 1)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
;; -> "Valid Scheme/Racket expression"
现在我们可以识别有效的 Scheme/Racket 表达式，我们可以用我们自己的表达式来评估它们
评估程序。我们本可以使用 Scheme's/Racket 的 eval，但一般来说
危险的。
对于自定义评估程序的编写，我从这本书中得到了很大的启发
“计算机程序的结构和解释”，“元语言抽象”一章。
书中还有很多关于环境设置和操作的内容，
因为那里的评估程序是为了解释 Scheme 代码——我只是想能够
解释算术表达式，从而可以保持对环境的处理更多
简单。
(define envr (hash 'a 1 'b 2 '+ + '- - '* * '/ /))
(define (eval-expr expr envr)
(cond ((self-evaluating? expr) expr)
((variable? expr) (lookup-variable-value expr envr))
((application? expr)
(apply-proc (eval-expr (operator expr) envr)
(list-of-values (operands expr) envr)))
(else (error "Not valid arithmetic expression: EVAL-EXPR" expr))))
(define (self-evaluating? expr)
(if (number? expr) true false))
(define (variable? expr)
(symbol? expr))
(define (lookup-variable-value var envr)
(with-handlers ([exn:fail? (lambda (exn)
(error "Unbound identifier: LOOKUP-VARIABLE-VALUE" var))])
(hash-ref envr var)))
;; Page 505: "A procedure application is any compound expression that is not
;; one of the above expression types. The car of the expression is
;; the operator, and the cdr is the list of operands:"
(define (application? expr) (pair? expr))
(define (operator expr) (car expr))
(define (operands expr) (cdr expr))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
(define (apply-proc procedure arguments)
(if (primitive-procedure? procedure)
(apply procedure arguments)
(error "Unknown procedure type: APPLY-PROC" procedure)))
(define (list-of-values exps envr)
(if (no-operands? exps)
'()
(cons (eval-expr (first-operand exps) envr)
(list-of-values (rest-operands exps) envr))))
(define primitive-procedures
(list (list '+ +)
(list '- -)
(list '* *)
(list '/ /)))
(define primitive-procedure-objects
(map (lambda (proc) (cadr proc))
primitive-procedures))
(define (primitive-procedure? proc)
(member proc primitive-procedure-objects))
我们现在得到了计算表达式的一切：
;; Example evaluations ;;
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr 1 envr))
; -> 1
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr 'b envr))
; -> 2
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr '(+ 1 b) envr))
; -> 3
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr '(> 1 b) envr))
; -> "Unbound identifier: LOOKUP-VARIABLE-VALUE >"
(let-values ([(expr is-valid-expr) (read-thing-from-string "(+ 1 b)")])
(if is-valid-expr (eval-expr expr envr) "Not valid Scheme/Racket expression"))
; -> 3
(let-values ([(expr is-valid-expr) (read-thing-from-string "(( 1 b)")])
(if is-valid-expr (eval-expr expr envr) "Not valid Scheme/Racket expression"))
; -> "Not valid Scheme/Racket expression"
我正在尝试使用 eval 评估方案中的任意和嵌套算术表达式。
表达式由数字、运算符、常量绑定和括号组成。
例如，(eval (+ 1 1)) 或 (eval (+ (* 1 2) 3))
问题是，表达式也可能有不平衡的括号，比如
(eval ((+ 1 1))，而scheme中的reader只会在输入表达式时等待
直到所有括号都关闭并以某种方式匹配。
我查看了 scheme 中的引用，并通过在 scheme 中使用 try-catch-mechanism (How to implement a try-catch block in scheme?) - 但这没有用。我也在考虑在方案中实现我自己的算术表达式求值器版本， 也许用括号作为分隔符。
我寻找一种方法来评估任意表达式，如果表达式是 无效，从 eval 中获取类似 'not valid expression' 的错误消息，并且没有 reader 等待右括号。
编辑： 请参阅下面的解决方案实施。
你的策略行不通。 Scheme 有“try-catch”，但就像大多数编程语言中的“try-catch”一样，它只适用于运行时错误（程序运行时发生的错误）。相比之下，不平衡的括号问题是语法错误（读取程序时发生的错误）。
例如在Python中可以这样写：
try:
1 / 0
except:
pass
这会捕获错误，但不会捕获像这样的语法错误：
try:
if
except:
pass
如果你想让输入有不平衡的括号，那么你需要将输入作为字符串而不是作为语言本身的表达式。例如：
(define my-input "(+ 1 1")
完全没问题，但是：
(define my-input (+ 1 1)
不是。
但是，对输入字符串进行计算很烦人。因此，您应该做的下一步是将输入字符串标记化并解析为一棵树。这里也是检测括号不平衡报错的地方：
(define (parse input-string)
;; TODO
)
(parse "(+ 1 2)")
;; expect '(+ 1 2)
(parse "(+ 1 2")
;; expect an error: "not valid expression"
假设 parse 没有错误，那么您将有一个像 '(+ 1 2) 这样的树作为输出。下一步是编写一个函数来消耗一棵树并产生一个答案
(define (interp input-tree)
;; TODO
)
(interp '(+ 1 2))
;; expect 3
(interp '(+ (+ 5 6) 7))
;; expect 18
你的 eval 只是 parse 和 interp:
(define (eval input-string)
(interp (parse input-string)))
(eval "(+ 1 2)")
;; expect 3
(eval "(+ 1 2")
;; expect an error: "not valid expression"
如果正如您所说，您尝试解析的表达式可能有不平衡的括号，那么这些表达式显然存在于一些非结构化数据中，几乎可以肯定是某种字符序列。由于你要阅读的表达式的语法是Scheme语法的一个子集，那么你可以简单地使用该语言为你提供的工具：read：你绝对不想为此编写自己的解析器，除非你喜欢花很多时间来正确处理极端情况。
请注意，任何 将字符序列转换为某个对象的解析器必须在某个时候请求序列中的下一个字符。对此可能会发生两件事：
- 它可以获得一个字符，可能是在等待该序列另一端的某个东西（也许是一个人）生成该字符之后；
- 它可以得到没有更多字符的指示——某种 end-of-file 指示。
没有任何魔法可以避免这种情况。所以你描述的 reader 等待 close-paren 的问题是不真实的： 你写的任何解析器 都会有同样的问题，当从交互式流中读取时：它只需等待该流另一端的人输入内容，或指示流已完成，此时它可以决定它看到的是否是 well-formed。
所以你问题的turning-sequences-of-characters-into-object部分的答案是使用语言提供的read。这是一种方法 - 因为您已经指定您正在使用 Racket，所以它使用 Racket，而不是任何 n 的 RnRS Scheme。如果您不关心对 reader 进行某种程度的限制（我不确定我是否对它进行了足够的限制），则几乎不需要所有这些代码。其余部分处理来自 reader 的异常，并将它们转换为多个值。
(define (read-thing source)
;; Read some object from a source port.
;; Return two values: either the object read and #t,
;; or some exception object and #f if something went wrong.
;;
;; This tries to defang the reader but I am not sure it does enough
(with-handlers ([exn? (λ (e) (values e #f))])
(call-with-default-reading-parameterization
(thunk
(parameterize ([read-accept-lang #f]
[read-accept-reader #f])
(values (read source) #t))))))
(define (read-thing-from-file f)
;; read a thing from a file
(call-with-input-file f read-thing))
(define (read-thing-from-string s)
;; read a thing from a string
(call-with-input-string s read-thing))
现在我们可以试试这个了：
> (read-thing-from-string "foo")
'foo
#t
> (read-thing-from-string "(foo")
(exn:fail:read:eof
"read: expected a `)` to close `(`"
#<continuation-mark-set>
(list (srcloc 'string #f #f 1 1)))
#f
如您所见，第二个值告诉您 read 是否引发异常。
现在您可以使用此 thing-reader 来为评估者提供信息。例如，您可以使用这样的函数：
(define (read-and-evaluate reader source
evaluator environment)
;; Read something with a read-thing compatible reader from source
;; and hand it to evaluator with environment as a second argument
;; If read-thing indicates an error then simply raise it again.
(call-with-values
(thunk (reader source))
(λ (thing good)
(when (not good)
(raise thing))
(evaluator thing environment))))
所以现在，问题减少到写 evaluator，我不打算这样做。
这里是这个函数与一个简单的求值器一起使用的例子，它只是 returns 它给出的形式。
> (read-and-evaluate
read-thing-from-string "(foo)"
(λ (form env) form) #f)
'(foo)
> (read-and-evaluate
read-thing-from-string "(foo"
(λ (form env) form) #f)
; string::1: read: expected a `)` to close `(` [,bt for context]
当然，这里不需要整个 handling-the-exception-in-the-reader 东西，因为我最终做了它重新提出它，但它确实向您展示了如何处理这样的错误。
关于编写求值器的说明。很容易说，好吧，(+ 1 2) 是一个有效的 Scheme 表达式，而 Scheme 有 eval 所以就用它吧。这就好比用热核装置拆房子，拆房子的效果很好，却造成了几十万人死亡等不良后果。例如，考虑 (system "rm -rf $HOME") 也是 也是 一个有效的 Racket 表达式，但您可能不想 运行.
为了避免这种 code-injection 攻击，您希望尽可能多地限制评估器，因此它将评估 仅 您感兴趣的语言. 这同样适用于 reader：在完整的 Racket reader 之上，我几乎可以肯定，可以在 read-time 评估任意 Racket 代码：我已经尝试（但可能失败）来 defang它在上面。
Racket 有一套重要的工具，可以让你定义一种更受限制的语言，eval 对这种语言来说是安全的。然而，对于 really 简单的语言，例如计算算术表达式，几乎可以肯定的是，简单地编写自己的计算器会更简单。这样做当然更有教育意义。
在@tfb 和@sorawee-porncharoenwase 的帮助下，我现在得到了一个可行的解决方案。 在我看来，这与执行任意 Scheme/Racket 表达式有关， 其中一些可能没有帮助。
让我们先来玩一下@tfb 的过程定义。
(+ 1 b) 是一个有效的 Scheme/Racket 表达式，因此 read-thing-from-string 应该声明它是有效的。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(+ 1 b)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
;; -> "Valid Scheme/Racket expression"
(( 1 b) 不是有效的 Scheme/Racket 表达式，正如 read-thing-from-string 识别的那样。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(( 1 b)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
; -> "Not valid Scheme/Racket expression"
我只想能够计算任意算术表达式，
像 (+ 1 1)，但是像 (a b 1) 这样的表达式是一个有效的 Scheme/Racket 表达式，应该被这样识别。
(let-values ([(expr is-valid-expr) (read-thing-from-string "(a b 1)")])
(if is-valid-expr "Valid Scheme/Racket expression" "Not valid Scheme/Racket expression"))
;; -> "Valid Scheme/Racket expression"
现在我们可以识别有效的 Scheme/Racket 表达式，我们可以用我们自己的表达式来评估它们
评估程序。我们本可以使用 Scheme's/Racket 的 eval，但一般来说
危险的。
对于自定义评估程序的编写，我从这本书中得到了很大的启发
“计算机程序的结构和解释”，“元语言抽象”一章。
书中还有很多关于环境设置和操作的内容， 因为那里的评估程序是为了解释 Scheme 代码——我只是想能够 解释算术表达式，从而可以保持对环境的处理更多 简单。
(define envr (hash 'a 1 'b 2 '+ + '- - '* * '/ /))
(define (eval-expr expr envr)
(cond ((self-evaluating? expr) expr)
((variable? expr) (lookup-variable-value expr envr))
((application? expr)
(apply-proc (eval-expr (operator expr) envr)
(list-of-values (operands expr) envr)))
(else (error "Not valid arithmetic expression: EVAL-EXPR" expr))))
(define (self-evaluating? expr)
(if (number? expr) true false))
(define (variable? expr)
(symbol? expr))
(define (lookup-variable-value var envr)
(with-handlers ([exn:fail? (lambda (exn)
(error "Unbound identifier: LOOKUP-VARIABLE-VALUE" var))])
(hash-ref envr var)))
;; Page 505: "A procedure application is any compound expression that is not
;; one of the above expression types. The car of the expression is
;; the operator, and the cdr is the list of operands:"
(define (application? expr) (pair? expr))
(define (operator expr) (car expr))
(define (operands expr) (cdr expr))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
(define (apply-proc procedure arguments)
(if (primitive-procedure? procedure)
(apply procedure arguments)
(error "Unknown procedure type: APPLY-PROC" procedure)))
(define (list-of-values exps envr)
(if (no-operands? exps)
'()
(cons (eval-expr (first-operand exps) envr)
(list-of-values (rest-operands exps) envr))))
(define primitive-procedures
(list (list '+ +)
(list '- -)
(list '* *)
(list '/ /)))
(define primitive-procedure-objects
(map (lambda (proc) (cadr proc))
primitive-procedures))
(define (primitive-procedure? proc)
(member proc primitive-procedure-objects))
我们现在得到了计算表达式的一切：
;; Example evaluations ;;
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr 1 envr))
; -> 1
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr 'b envr))
; -> 2
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr '(+ 1 b) envr))
; -> 3
(with-handlers ([exn:fail? (lambda (exn)
(exn-message exn))])
(eval-expr '(> 1 b) envr))
; -> "Unbound identifier: LOOKUP-VARIABLE-VALUE >"
(let-values ([(expr is-valid-expr) (read-thing-from-string "(+ 1 b)")])
(if is-valid-expr (eval-expr expr envr) "Not valid Scheme/Racket expression"))
; -> 3
(let-values ([(expr is-valid-expr) (read-thing-from-string "(( 1 b)")])
(if is-valid-expr (eval-expr expr envr) "Not valid Scheme/Racket expression"))
; -> "Not valid Scheme/Racket expression"