ISL+ (Racket) 中的有限状态机仿真实现
Finite State Machine Simulation Implementation in ISL+ (Racket)
我是一个独自研究 HTDP2(Felleisen 等人)的新手,但在第 IV 章 - 交织数据的问题 #380 上遇到了困难。问题出在创建 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")))
现在,如果我使用 (simulate "red" fsm-traffic)
启动程序,则会呈现 State0,如果我按 "r",它会转到 "green" FSM-State,但它不会接受 "g" 进入下面的状态等等。
如果我用 (simulate "yellow" fsm-traffic)
开始世界程序,那么 FSM-State "yellow" 会被渲染,但它不会转换到任何其他状态(error
子句被激活);与 "green" 类似地作为起始状态。
我的直觉是,由于我首先用 "red" 状态定义了 fsm-traffic
,它接受其输入以过渡到 "green",但由于其他状态没有发生同样的情况 big-bang
不是 "juggling" transitions
参数吧。但我只是不知道如何解决这个问题。我也不知道从我的数据定义开始我是否出错了。
预先感谢您帮助我。
P.D。如果我在 Whosebug 上遵守了 posting 的规则,请告诉我(这是我的第一个 post :)。
您正确地确定了问题的根源。您首先使用 "red"
状态和 "r"
转换定义了 fsm-traffic
,而 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
问题似乎很复杂。就像如果它是一个具有签名和目的的函数我们会做的那样,我们可以设计这个表达式的输入、输出和目的。
输入:它应该依赖于什么?
哪些键有效取决于转换 table,但也取决于当前状态。这就是为什么只有"r"
在"red"
状态下有效,而"g"
在"green"
状态下有效的原因。所以它的输入是:
current : FSM-State
key-event : KeyEvent
transitions : FSM
您现有的表达式忽略 current
。
输出和目的
是if
题,所以应该输出Boolean
。此布尔值的目的是确定密钥在当前状态下是否有效。
对于 current
状态和 key-event
状态,当 table 中存在 any 转换时应该为真。
这个带有“any”和“both”的目的声明听起来很复杂,它应该是它自己的功能。使用我们刚刚做出的输入、输出和目的:
;; 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
之间的关系。当 find-transition-state
不会出错时,transition-for-state-and-key?
函数应该 return 为真。
这应该足以让您继续。
我是一个独自研究 HTDP2(Felleisen 等人)的新手,但在第 IV 章 - 交织数据的问题 #380 上遇到了困难。问题出在创建 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")))
现在,如果我使用 (simulate "red" fsm-traffic)
启动程序,则会呈现 State0,如果我按 "r",它会转到 "green" FSM-State,但它不会接受 "g" 进入下面的状态等等。
如果我用 (simulate "yellow" fsm-traffic)
开始世界程序,那么 FSM-State "yellow" 会被渲染,但它不会转换到任何其他状态(error
子句被激活);与 "green" 类似地作为起始状态。
我的直觉是,由于我首先用 "red" 状态定义了 fsm-traffic
,它接受其输入以过渡到 "green",但由于其他状态没有发生同样的情况 big-bang
不是 "juggling" transitions
参数吧。但我只是不知道如何解决这个问题。我也不知道从我的数据定义开始我是否出错了。
预先感谢您帮助我。
P.D。如果我在 Whosebug 上遵守了 posting 的规则,请告诉我(这是我的第一个 post :)。
您正确地确定了问题的根源。您首先使用 "red"
状态和 "r"
转换定义了 fsm-traffic
,而 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
问题似乎很复杂。就像如果它是一个具有签名和目的的函数我们会做的那样,我们可以设计这个表达式的输入、输出和目的。
输入:它应该依赖于什么?
哪些键有效取决于转换 table,但也取决于当前状态。这就是为什么只有"r"
在"red"
状态下有效,而"g"
在"green"
状态下有效的原因。所以它的输入是:
current : FSM-State
key-event : KeyEvent
transitions : FSM
您现有的表达式忽略 current
。
输出和目的
是if
题,所以应该输出Boolean
。此布尔值的目的是确定密钥在当前状态下是否有效。
对于 current
状态和 key-event
状态,当 table 中存在 any 转换时应该为真。
这个带有“any”和“both”的目的声明听起来很复杂,它应该是它自己的功能。使用我们刚刚做出的输入、输出和目的:
;; 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
之间的关系。当 find-transition-state
不会出错时,transition-for-state-and-key?
函数应该 return 为真。
这应该足以让您继续。