Реализация моделирования конечного автомата в ISL + (Racket)

Question

Я новичок, работающий через HTDP2 (Felleisen et al.) Самостоятельно, но застрял в вопросе № 380 главы IV - Переплетенные данные. Проблема в контексте создания DSL, но я сначала повторно ознакомился с общим симулятором FSM и получил следующий код:

; An FSM is a [List-of 1Transition]
; A 1Transition is a list of two items:
;   (cons FSM-State (cons FSM-State '()))
; An FSM-State is a String that specifies a color

; data examples 
(define fsm-traffic
  '(("red" "green") ("green" "yellow") ("yellow" "red")))

; FSM FSM-State -> FSM-State 
; matches the keys pressed by a player with the given FSM 
(define (simulate state0 transitions)
  (big-bang state0 ; FSM-State
    [to-draw
     (lambda (current)
      (overlay (text current 12 "black")
               (square 100 "solid" current)))]
[on-key
  (lambda (current key-event)
    (find transitions current))]))

; [X Y] [List-of [List X Y]] X -> Y
; finds the matching Y for the given X in alist
(define (find alist x)
  (local ((define fm (assoc x alist)))
    (if (cons? fm) (second fm) (error "not found"))))

Проблема тогда сформулирована следующим образом:

Переформулируйте определение данных для 1Transition, чтобы можно было ограничить переходы определенными нажатиями клавиш. Попробуйте сформулировать изменение так, чтобы find продолжал работать без изменений. Что еще нужно изменить, чтобы заставить работать всю программу? Какая часть рецепта дизайна дает ответ (ы)? См. Упражнение 229. Исходное утверждение упражнения.

В упражнении 229 вводится определение типа структуры для отслеживания состояний и переходов, но, поскольку в заявлении о проблеме содержится просьба остаться в рамках предоставленной функции find, мне трудно найти аналогичное определение типа структуры. Вместо этого я придумал следующее определение данных:

; An FSM is a [List-of Transition]
; A Transition is a two-item list of the following form:
; (cons FSM-State (cons (cons KeyEvent (cons FSM-State '()))'()))

; data example
(define fsm-traffic (list (list "red" (list "r" "green"))
                          (list "green" (list "g" "yellow"))
                          (list "yellow" (list "y" "red"))))

Следовательно, вызывая (find fsm-traffic "green") Я получаю (list "g" "yellow") Я изменил предложение on-key следующим образом:

(lambda (current key-event)
  (if (string=? key-event (first (first (rest (first transitions)))))
      (second (find transitions current))
      (error "invalid input")))

Теперь, если я запускаю программу с * 1019, * отображается State0, и если я нажимаю «r», он переходит в «зеленое» состояние FSM, но затем не принимает «g» для перехода в следующее состояние и т. Д. на.

Если я начинаю мировую программу с (simulate "yellow" fsm-traffic), то FSM-состояние «желтый» отображается, но оно не переходит в какое-либо другое состояние (включено условие error); аналогично с «зеленым» в качестве исходного состояния.

Моя догадка заключается в том, что, поскольку я сначала определил fsm-traffic с "красным" состоянием, он принимает свой вход для перехода к "зеленому", но поскольку этого не происходит с другими состояниями big-bang не "жонглирует" transitions параметр справа. Но я просто не знаю, как это исправить. Я также не знаю, ошибся ли я с самого начала определения данных.

Заранее спасибо за помощь.

P.D. пожалуйста, дайте мне знать, если я следовал правилам публикации на stackoverflow (это мой первый пост :).

Answer 1

Вы правильно указали источник проблемы. Вы определили fsm-traffic с состоянием "red" и переходом "r", а обработчик on-key смотрит только на first. Это делается в вопросе if:

(string=? key-event (first (first (rest (first transitions)))))
;                    ^                   ^
;                    |                   this makes it only look at `"red"`
;                    this makes it only look at `"r"` within that

Этот if вопрос кажется сложным. Точно так же, как если бы это была функция с сигнатурой и назначением, мы можем спроектировать входные, выходные данные и назначение этого выражения.

Входные данные: от чего это должно зависеть?

Какие ключи действительны, зависит от таблицы переходов, но также зависит от текущего состояния. По этой причине только "r" допустимо в состоянии "red", но "g" допустимо в состоянии "green". Таким образом, его входные данные:

current : FSM-State
key-event : KeyEvent
transitions : FSM

Ваше существующее выражение игнорирует current.

Выход и назначение

Это вопрос if, поэтому он должен вывести Boolean. Цель этого логического выражения - определить, является ли ключ действительным в текущем состоянии.

Это должно быть верно, если в таблице есть любой переход как для состояния current, так и для key-event.

Эта формулировка цели с " any " и " обоими " звучит достаточно сложно, поэтому она заслуживает своей собственной функции. Используя входы, выход и цель, которую мы только что сделали:

;; FSM-State KeyEvent FSM -> Boolean
;; Determines whether there is any transition in the FSM table for both the current
;; state and the key event.
(define (transition-for-state-and-key? state key table)
  ....)

Ваше текущее выражение для тела, это не включает state,

(string=? key (first (first (rest (first table)))))

Но фактическое тело должно зависеть от state и key.

Так же, как это зависит от обоих, функция find также должна зависеть как от state, так и от key.

;; FSM-State KeyEvent FSM -> FSM-State
;; Finds the matching transition-state from the given state with the given key in the table.
(define (find-transition-state state key table)
  ....)

И обратите внимание на связь между transition-for-state-and-key? и find-transition-state. Функция transition-for-state-and-key? должна возвращать истину именно тогда, когда find-transition-state не выдаст ошибку.

Этого должно быть достаточно для продолжения.