October 12, 2004 Project class

Opening Remarks / Overview

1. 5 minutes on XML from MattC
2. Theoretically everyone's been working on FSM/regexp stuff

3. Lynn hopes to add to the list of stuff people are looking at -- parsers -- play with one. See SICP(wizard book) ch 4, Lex/YACC, and the internet(s). Parsers are awesome.

Things people are working on

[NB: Lynn wants a paragraph every week updating her on what you're up to -- she doesn't need to see every line of code you ever write, but if you want her to run something send everything necessary for the running of the thing.]

• Lex/YACC in low-level C (vs something more abstracted like Python -- tradeoff between ease of coding vs level of control?)
• FSA simulators
  • Mel -- uses nodes as a thing you would pass an input to, and would give you the next node
  • MattC -- uses nodes as procedures
  • JonT -- generalization to the max
  • Katie -- uses a transition table with scheme-symbols rather than individual nodes

  • It would be cool to put up code snippets here and continue discussion, since it's a hard thing to talk about in abstract and in class.

  === FSA discussion ===

Matt C's code:

;Example of how to use the FSM simulator
(define q0 (create-state '(('a q1))))
(define q1 (create-final-state '(('a q0) ('b q1))))

;Alias to the general function
(define create-final-state
  (lambda (links)
    (create-state-general links 'final)
  )
)
;Alias to the general function
(define create-state
  (lambda (links)
    (create-state-general links 'not-final)
  )
)
;General function to create states
(define create-state-general
  (lambda (links state)
    (lambda (expr)
      (eval
        (append-
          '(cond)
          `(((null? ',expr) ',state))
          (map (lambda (pair)
               `((eq? ',expr ,(car pair)) ',(cadr pair))
               )
          links)
          '((else #f))
        )
      )
    )
  )
)
;Function that tail-recurses through a given FSM
(define simulate-fsm-
  (lambda (initial parameters)
    (let ((result (if (pair? parameters)
                    ((eval initial) (car parameters))
                    ((eval initial) '())
                  )
          ))
      (cond ((eq? result #f) #f)
            ((null? parameters)
              (cond ((eq? 'final result) #t)
                    (else #f)
              )
            )
            (else (simulate-fsm result (cdr parameters)))
      )
    )
  )
)

Katie's code mostly at NotesOctober12Proj/KatieCode; an example run is here:

;; this tests an fsm which accepts the regular expression (a* U b*)
(run-fsm (make-fsm (list 'q0 'q1 'q2) ; states
                   (list 'a 'b) ;alphabet
                   (delta-add 'q0 'a 'q1 
                              (delta-add 'q0 'b 'q2 
                                         (delta-add 'q1 'a 'q1 
                                                    (delta-add 'q2 'b 'q2 
                                                               (make-empty-delta))))) ;delta
                   (list 'q0) ; start-state
                   (list 'q0 'q1 'q2)) ; accept-states
         (list 'a 'a 'a)) ;; input string

Output:

q0
q1
q1
q1
#t
> 

5 min on XML

• XML is strict, easily parsable
  • Direct relationship with the grammars stuff we were talking about in class
• Separates data from presentation -- makes data processing really easily
• A simplification(?) of SGML
• Two ways to look at a document:
  • DOM model (document-object model) of processing
    • Gives you a lovely object hierarchy, easy to translate between text files and objects
    • "Here's the tree: Now we manipulate it"
    • Tradeoff: a bit behemothy
  • SAX model
    • a bit more complicated
    • well-suited for streams
    • event-driven: "If I see this tag, what should I do?"

For Next Time

1. Interpreters: See ProjectAssignment3

2. If you can't tear yourself away from the other things you've been working on, then continue being productive in that fashion.