Как создать определение схемы для разбора составного S-выражения и приведения его к нормальной форме

Давайте быстро отвлечемся от исходной проблемы к чему-то связанному с ней. Скажем, вам дали следующее: вы хотите написать вычислитель, который берет выражения "строки", такие как (* 3 "hello"), и "оценивает" их как "hellohellohello". Другие примеры, которые мы хотели бы заставить работать, включают такие вещи, как

(+ "rock" (+ (* 5 "p") "aper"))     ==> "rockpppppaper"
(* 3 (+ "scis" "sors"))             ==> "scissorsscissorsscissors"

Чтобы решить подобную проблему, нам нужно точно указать форму входных данных. По сути, мы хотим описать тип данных. Мы скажем, что наши входные данные будут «строковыми выражениями». Назовем их str-exprs для краткости. Тогда давайте определим, что значит быть str-expr.

str-expr это либо:

1. <string>
2. (+ <str-expr> <str-expr>)
3. (* <number> <str-expr>)

С помощью этой записи мы пытаемся сказать, что все str-expr соответствуют одной из этих трех форм.

Когда у нас будет хорошее представление о форме данных, у нас будет лучшее руководство по написанию функций, которые обрабатывают str-exprs: они должны анализировать эти три варианта!

;; A str-expr is either:
;;      a plain string, or
;;     (+ str-expr str-expr), or
;;     (* number str-expr)

;; We want to write a definition to "evaluate" such string-expressions.

;; evaluate: str-expr -> string
(define (evaluate expr)
  (cond
    [(string? expr)
     ...]
    [(eq? (first expr) '+)
     ...]
    [(eq? (first expr) '*)
     ...]))

где "..." - это то, что мы будем заполнять.

На самом деле, мы знаем, как добавить немного больше о '...': мы знаем, что во втором и третьем случаях внутренние части сами являются строковыми выражениями. Это основные места, где, вероятно, произойдет повторение: поскольку наши данные описываются в терминах самих себя, программы, которые их обрабатывают, также, вероятно, должны будут ссылаться на самих себя. Короче говоря, программы, обрабатывающие str-exprs, почти наверняка будут следовать этой форме:

(define (evaluate expr)
  (cond
    [(string? expr)
     ... expr 
     ...]
    [(eq? (first expr) '+)
     ... (evaluate (second expr))
     ... (evaluate (third expr))
     ...]
    [(eq? (first expr) '*)
     ... (second expr) 
     ... (evaluate (third expr))
     ...]))

Это все, даже не выполняя никакой реальной работы: мы можем понять эту часть просто потому, что об этом говорит нам форма данных. Заполнение оставшейся части «...», чтобы все это сработало, на самом деле не так уж плохо, особенно если мы также рассматриваем тестовые примеры, которые мы приготовили. (Код)

Именно такой стандартный анализ данных/кейс-анализ лежит в основе вашего вопроса, и он широко освещается в таких учебных программах, как HTDP. Это не специфично для Scheme или Racket: вы бы сделали такой же анализ данных в Java, и вы видите такой же подход во многих других местах. В Java низкоуровневый механизм, используемый для анализа прецедентов, может быть выполнен по-другому, возможно, с динамической диспетчеризацией, но основные идеи все те же. Вам нужно описать данные. Получив определение данных, используйте его, чтобы набросать, как должен выглядеть код для обработки этих данных. Используйте тестовые случаи, чтобы триангулировать, как заполнить эскиз.

Вам нужно разобрать свою проблему. Я бы начал с подхода HtDP (www.htdp.org). Каковы ваши входы? Можете ли вы указать их точно? В этом случае эти входные данные будут самореферентными.

Затем укажите форму вывода. На самом деле, ваш текст выше немного нечеткий по этому поводу: я думаю, что знаю, как выглядит ваша форма вывода, но я не совсем уверен.

Далее напишите набор тестов. Они должны быть основаны на структуре ваших входных терминов; начните с самых простых и двигайтесь вверх оттуда.

Если у вас есть хороший набор тестов, реализация функции должна быть довольно простой. Я буду рад помочь, если вы застряли!