[racket] htdp/2e: exercise 197, a solution, feedback welcome

On Jan 21, 2015, at 8:03 AM, Daniel Bastos wrote:

> I had a lot of difficulties with exercise 195, 196, 197. I'm posting my solution to exercise 197 to get a chance to get feedback. How would have you represented the FSM from exercise 100?


See notes starting with MF (and lines above and below). Good start. Mostly: cut junk, organize top down (most important to less important to least important functions). -- Matthias



(require 2htdp/image)
(require 2htdp/universe)

;Exercise 197. Consider the following data representation for finite state machines:
(define-struct fsm (initial transitions final))
(define-struct transition (current key next))

; An FSM.v2 is a structure: 
;   (make-fsm FSM-State LOT FSM-State)
; A LOT is one of: 
; – empty 
; – (cons Transition.v3 LOT)
; A Transition.v3 is a structure: 
;   (make-transition FSM-State KeyEvent FSM-State)
; Represent the FSM from exercise 100 in this context.

; Design the function fsm-simulate, which accepts an FSM.v2 and runs it on a player’s key strokes. 
; If the sequence of key strokes force the FSM.v2 to reach a final state, fsm-simulate stops. 
; HINT The function uses the initial field of the given fsm structure to keep track of the current 
; state.

;(*) Solution

;; MF: don't define the same thing twice: 
; (define-struct fsm (initial transitions final))
; (define-struct transition (current key next))

; An FSM.v2 is a structure: 
;   (make-fsm FSM-State LOT FSM-State)
; A LOT is one of: 
; – empty 
; – (cons Transition.v3 LOT)
; A Transition.v3 is a structure: 
;   (make-transition FSM-State KeyEvent FSM-State)

; a(b|c)*d

(define AA "start, expect to see an 'a' next")
(define BC "expect to see: 'b', 'c', or 'd'")
(define DD "encountered a 'd', finished")
(define ER "error, user pressed illegal key")

(define fsm-exe100
  (make-fsm AA
            (list (make-transition AA "a" BC)
                  (make-transition BC "b" BC)
                  (make-transition BC "c" BC)
                  (make-transition BC "d" DD)
                  (make-transition AA "d" ER)) ;; <-- MF: fixed, see figure 27
            DD))

(define CANVAS (empty-scene 300 20))

;; MF: where signature, purpose, examples? 
(define (show-state a-fsm)
  ;; MF: why are you showing the actual (text of the) state? Okay but ugly. 
  ;; Exercise 100 suggests "initially your program shows a 100 by 100
  ;; white rectangle. Once your program has seen an "a", it displays
  ;; a yellow rectangle of the same size. ..." 
  (place-image (text (fsm-initial a-fsm) 14 "black")
               100 10 CANVAS))

;; MF: this is the main function and should be shown first: 
; FSM -> SimulationState.v2 
; match the keys pressed by a player with the given FSM
(define (fsm-simulate a-fsm)
   (big-bang a-fsm
             (to-draw show-state)
             (on-key find-next-state)
             (stop-when last-state?)))

; SimulationState.v2 -> Boolean
(define (last-state? world-fsm)
  (string=? (fsm-initial world-fsm) (fsm-final world-fsm)))
;; MF: I prefer to put the examples between the signature and the definition
(check-expect (not (last-state? fsm-exe100)) true)

;; MF: this function is unexpected. Why does it exist and why is it listed here? 
;; [It would NOT show up on your wish list if you followed the design recipe for programs.]
;; ALSO: use 'check syntax' and mouse over. No arrow goes anywhere from here, 
;; a sure sign of superfluous code. Programmers are not paid by the number of lines of code
;; but their quality. 
; Transition.v3 Transition.v3 -> Boolean
(define (transition=? t1 t2)
  (and 
   (string=? (transition-current t1) (transition-current t2))
   (string=? (transition-key t1) (transition-key t2))
   (string=? (transition-next t1) (transition-next t2))))

; FSM.v2 KeyEvent -> FSM.v2
; produces the machine with the next state associated with ke
(define (find-next-state a-fsm ke)
  (make-fsm (find (fsm-transitions a-fsm) (fsm-initial a-fsm) ke)
            (fsm-transitions a-fsm)
            (fsm-final a-fsm)))

;; MF: you are using abstraction notation even though you are only in Part II? LOT. 
; [List-of transition] FSM-State KeyEvent -> FSM-State
; finds the next FSM-State in the transition where 'current' is located
(define (find ls current ke)
  (cond 
    ;; MF: PERFECT SHAPE BUT: 
    ;; MF: exercise 100 list an error state, see figure 27
    [(empty? ls) (error (string-append "not found: " ke " " current))]
    [else (cond 
            [(and (string=? current (transition-current (first ls)))
                  (key=? ke (transition-key (first ls))))
             (transition-next (first ls))]
            [else 
             (find (rest ls) current ke)])]))

(check-error (find (fsm-transitions fsm-exe100) AA "b"))
(check-expect (find (fsm-transitions fsm-exe100) AA "a") BC)
(check-expect (find (fsm-transitions fsm-exe100) BC "b") BC)
(check-expect (find (fsm-transitions fsm-exe100) BC "c") BC)
(check-expect (find (fsm-transitions fsm-exe100) BC "d") DD)

(check-error (find-next-state fsm-exe100 "b"))
(check-expect (find-next-state fsm-exe100 "a") (make-fsm BC (fsm-transitions fsm-exe100) DD))

(check-expect (find-next-state 
               (find-next-state fsm-exe100 "a") "b") 
              (make-fsm BC (fsm-transitions fsm-exe100) DD))

(check-expect (find-next-state 
               (find-next-state 
                (find-next-state fsm-exe100 "a") "b") "c")
              (make-fsm BC (fsm-transitions fsm-exe100) DD))

(check-expect (find-next-state 
               (find-next-state 
                (find-next-state 
                 (find-next-state fsm-exe100 "a") "b") "c") "d")
              (make-fsm DD (fsm-transitions fsm-exe100) DD))

(check-expect (find-next-state 
                 (find-next-state fsm-exe100 "a") "d")
              (make-fsm DD (fsm-transitions fsm-exe100) DD))