ракетка: (оценка т LST)

Question

Я реализовал функцию, которая принимает арифметическое выражение и возвращает значение:

; an arithmetic expression (t) is one of the following: 
; - a number 
; - a list of the form '(a operator b) where a and b are arithmetic expressions 
; arithmetic expression -> number 

; computes the value of the arithmetic expression 

(define (eval t) 
    (cond 
    [(number? t) t] 
    [else ((cond 
      [(equal? (second t) '+) +] 
      [(equal? (second t) '-) -] 
      [(equal? (second t) '*) *] 
      [(equal? (second t) '/) /]) 
      (eval (first t)) (eval (third t)))])) 

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

(eval '(1 + (3 * x)) (make-const 'x 3)      -> 10 
(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2)) -> 4 
(eval '(1 + (y * x)) (make-const 'x 3)      -> "error" 

Моя идея состояла в том, чтобы определения структуры:

(define struct const (symbol number)) 


(define (eval. t x) 
    (cond 
    [(number? t) t] 
    [(symbol? t) ???] 
    [else ((cond 
      [(equal? (second t) '+) +] 
      [(equal? (second t) '-) -] 
      [(equal? (second t) '*) *] 
      [(equal? (second t) '/) /]) 
      (eval. (first t) lst) (eval. (third t) lst))])) 

Может кто-нибудь сказать мне, если я направился в правильном направлении и, может быть, дал мне подсказку? Это будет высоко ценится!

Answer 1

Во-первых, обратите внимание, что ваши примеры немного неправильно:

(eval '(1 + (3 * x)) (make-const 'x 3) 
; you need a closing parenthesis 

(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2)) 
; same as above. also, ((make-const 'x 1) (make-const 'y 2)) doesn't make 
; sense. Do you mean (list (make-const 'x 1) (make-const 'y 2)) 

Во всяком случае, есть два способа сделать это.

Первый способ состоит в том, чтобы сделать eval имеет две фазы: первая фаза - заменить все переменные. Если все будет хорошо, вы получите выражение без идентификатора. Второй шаг - вызвать вашу первую версию eval (где я буду называть eval-helper).

; eval :: expr, listof const -> number 
(define (eval t vars) 
    (eval-helper (subst-all t vars))) 

Действительно, сложная часть состоит в том, чтобы правильно получить subst-all. Чтобы упростить задачу, вы можете написать функцию с именем subst, которая заменяет только один идентификатор за раз. Это можно сделать путем рекурсии над выражением и заменить символ числом, если символ совпадает. Тогда subst-all может использовать subst в качестве вспомогательной функции.

(С таким образом, как бы вы знаете, если есть несвязанный идентификатор?)

Второй способ следовать шаблон кода:

(define struct const (symbol number)) 

(define (eval t env) 
    (cond 
    [(number? t) t] 
    [(symbol? t) ???] 
    [else ((cond 
      [(equal? (second t) '+) +] 
      [(equal? (second t) '-) -] 
      [(equal? (second t) '*) *] 
      [(equal? (second t) '/) /]) 
      (eval (first t) env) (eval (third t) env))])) 

канонически, второй аргумент этой функции (например, (list (make-const 'x 1) (make-const 'y 2))) известен как Окружающая среда. Когда вы видите символ, вы просто просматриваете среду и возвращаете значение, которое ассоциируется с символом, который вы просматриваете.

; lookup :: symbol, listof const -> number 
(define (lookup sym env) 
    (cond 
    [(empty? env) ???] 
    [else (if (equal? sym (const-symbol (first env))) 
      ??? ; you want to return the value! 
      ??? ; recursively call lookup on the rest of the environment 
      )])) 

(С таким образом, как вы знаете, если есть несвязанный идентификатор?)

Смотрите также:

• http://cs.brown.edu/courses/cs173/2012/book/adding-functions.html
• http://cs.brown.edu/courses/cs173/2012/book/From_Substitution_to_Environments.html