Scheme Lisp — Использование eval для произвольных арифметических выражений

Если, как вы говорите, выражения, которые вы пытаетесь проанализировать, могут иметь несбалансированные скобки, то эти выражения явно живут в некоторых неструктурированных данных, которые почти наверняка представляют собой последовательность символов какого-то типа. Поскольку синтаксис выражений, которые вы хотите прочитать, является подмножеством синтаксиса Scheme, вы можете просто использовать инструмент, который предоставляет вам язык: read: вы определенно не хотите писать свои собственный синтаксический анализатор для этого, если вы не любите тратить много времени на получение правильных угловых случаев.

Обратите внимание, что любой синтаксический анализатор, который превращает последовательность символов в какой-либо объект, должен в какой-то момент запросить следующий символ из последовательности. В ответ на это могут произойти две вещи:

• он может получить символ, возможно, после ожидания чего-то на другом конце этой последовательности — возможно, человека — для создания персонажа;
• он может получить указание на то, что символов больше нет — своего рода индикатор конца файла.

Никакая магия, которую вы можете сделать, не может избежать этого. Таким образом, описанная вами проблема с читателем, ожидающим закрывающей скобки, не реальна: любой парсер, который вы пишете, будет иметь ту же проблему при чтении из интерактивного потока: ему просто нужно дождаться человеческого на другом конце этого потока, чтобы либо ввести что-то, либо указать, что поток завершен, и в этот момент он может решить, было ли то, что он видел, правильным или нет.

Таким образом, ответ на часть вашей проблемы, связанную с превращением последовательностей символов в объект, заключается в использовании read, предоставляемого языком. Вот один из способов сделать это — поскольку вы указали, что используете Racket, для любого n используется Racket, а не схема RnRS. Почти весь этот код не понадобился бы, если бы вы не позаботились о некотором ограничении средства чтения (и я не уверен, что ограничил его достаточно). Остальная часть связана с обработкой исключений из модуля чтения и преобразованием их в несколько значений.

(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 исключение или нет.

Теперь вы можете использовать этот считыватель вещей, чтобы накормить оценщика. Например, вы можете использовать такую ​​функцию:

(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, чего я делать не собираюсь.

Вот пример использования этой функции с тривиальным оценщиком, который просто возвращает заданную форму.

> (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]

Конечно, вся эта штука с обработкой исключения в считывателе здесь не нужна, так как все, что я в конечном итоге делаю, это повторно поднимаю его, но это действительно показывает вам, как вы можете обрабатывать такую ​​​​ошибку.

Примечание о написании оценщика. Заманчиво сказать, что (+ 1 2) является допустимым выражением Scheme, а в Scheme есть eval, поэтому просто используйте его. Это похоже на использование термоядерного устройства для сноса дома: оно хорошо сносит дом, но имеет нежелательные последствия, такие как гибель сотен тысяч людей. Учтите, например, что (system "rm -rf $HOME") является также допустимым выражением Racket, но вы можете не захотеть запускать его.

Чтобы избежать такой атаки с внедрением кода, вы хотите максимально ограничить оценщик, чтобы он оценивал только интересующий вас язык. То же самое относится к считывателю: над полный читатель Racket может, я почти уверен, оценить произвольный код Racket во время чтения: я пытался (но, вероятно, потерпел неудачу) обезвредить его выше.

Racket имеет значительный набор инструментов, которые позволяют вам определить более ограниченный язык, для которого eval будет безопасным. Однако для действительно простого языка, такого как вычисление арифметических выражений, почти наверняка проще просто написать собственный вычислитель. Это, безусловно, более познавательно.

Ваша стратегия не сработает. В Scheme есть 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"

С помощью @tfb и @sorawee-porncharoenwase я получил рабочее решение. что, на мой взгляд, безопасно в отношении выполнения произвольных выражений Scheme/Racket, некоторые из которых могут быть бесполезными.

Давайте сначала поиграем с определениями процедур @tfb.

(+ 1 b) является допустимым выражением схемы/рэкета, поэтому 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, мы можем оценить их с помощью нашей собственной процедуры оценки. Мы могли бы использовать eval от Scheme/Racket, но это было бы вообще опасно. Для написания пользовательской процедуры оценки меня сильно вдохновила книга «Структура и интерпретация компьютерных программ», глава «Металингвистическая абстракция».

В книге гораздо больше говорится о настройке и манипулировании средой, потому что процедура оценки предназначена для интерпретации кода схемы. просто.

(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"