From: Oliver Scholz
Subject: [newbie] state machines
Date: 
Message-ID: <m3r8jeqbdf.fsf@ID-87814.user.dfncis.de>
Hello!

Are there any information on state machines and the programming of
state machines in Lisp -- available on the web (well, preferably ...)
and comprehensible for a non-computer-scientist, non-programmer and
Lisp-novice?

I found state machines sometimes mentioned in usenet articles or on
the web and I understand that there are different kinds (?) of them:
finite and infinite, deterministic and non-deterministic.  I don't
really understand this issue, but I want to learn more about this.

My notion is that state machines are useful whenever I have to parse
input from a stream. I don't know if this statement is correct. My
Lisp experience is currently limited to Emacs Lisp. Some kind soul in
an Emacs newsgroup gave me the very first basic ideas about state
machines some time ago. Since then I sometimes use something which I
_believe_ to be a state machine. Now I want to make sure. :-) That is:
I want to learn a) the (fundamentals of) the concept, b) when to use
them, c) how to construct them in a proper way and d) how to implement
them in Lisp.

Could someone help me?

    -- Oliver

-- 
23 Prairial an 210 de la R�volution
Libert�, Egalit�, Fraternit�!
From: Raymond Wiker
Subject: Re: [newbie] state machines
Date: 
Message-ID: <86ofei137o.fsf@raw.grenland.fast.no>
Oliver Scholz <··········@gmx.de> writes:

> Hello!
> 
> Are there any information on state machines and the programming of
> state machines in Lisp -- available on the web (well, preferably ...)
> and comprehensible for a non-computer-scientist, non-programmer and
> Lisp-novice?

        Here's a small example of a state machine that strips away
markup elements from HTML (and XML, and SGML). Note that it does *not*
complete (lacks handling of character entities, CDATA sections, etc),
but it may serve as an illustration.

(defparameter *strip-xml-parse-table*
  #(((#\< . 1) 0)			; 0 - normal state
    ((#\! . 2) 5)			; 1 - after <
    ((#\- . 3) 5)			; 2 - after <!
    ((#\- . 4) 5)			; 3 - after <!-
    ((#\- . 8) 4)			; 4 - comment <!--
    ((#\' . 6)				; 5 - markup
      (#\" . 7)
      (#\> . 0)
      5)
    ((#\' . 5) 6)			; 6 - markup, single-quote
    ((#\" . 5) 7)			; 7 - markup, double-quote
    ((#\- . 9) 4)			; 8 - comment, after -
    ((#\> . 0) (#\- . 9) 4)		; 9 - comment, after --(*)
    ))

(defun lookup-transition (state input)
  (let ((transitions (svref *strip-xml-parse-table* state)))
    (dolist (elt transitions)
      (cond ((atom elt)
	     (return-from lookup-transition elt))
	    ((char-equal input (car elt))
	     (return-from lookup-transition (cdr elt)))))
    (error "State table error")))
	      
(defun strip-xml-markup (string)
  (let ((state 0))
    (with-output-to-string (out)
      (with-input-from-string (in string)
	(do ((char (read-char in nil) (read-char in nil)))
	    ((null char))
	  (let ((new-state (lookup-transition state char)))
	    (when (zerop new-state)
	      (write-char
	       (if (zerop state)
		   char
		   #\Space)
	       out))
	    (setf state new-state)))))))

-- 
Raymond Wiker                        Mail:  ·············@fast.no
Senior Software Engineer             Web:   http://www.fast.no/
Fast Search & Transfer ASA           Phone: +47 23 01 11 60
P.O. Box 1677 Vika                   Fax:   +47 35 54 87 99
NO-0120 Oslo, NORWAY                 Mob:   +47 48 01 11 60

Try FAST Search: http://alltheweb.com/
From: Joel Ray Holveck
Subject: Re: [newbie] state machines
Date: 
Message-ID: <y7cofeg6yls.fsf@sindri.juniper.net>
> Are there any information on state machines and the programming of
> state machines in Lisp -- available on the web (well, preferably ...)
> and comprehensible for a non-computer-scientist, non-programmer and
> Lisp-novice?

I wrote an introductory paper on the topic, but can't find it right
now... when I find it, I'll send it your way.

joelh
From: Paolo Amoroso
Subject: Re: [newbie] state machines
Date: 
Message-ID: <rU8HPWxu+Tn8OkL0GnDah7LsN+2G@4ax.com>
On Tue, 11 Jun 2002 14:16:23 +0200, Oliver Scholz <··········@gmx.de>
wrote:

> Are there any information on state machines and the programming of
> state machines in Lisp -- available on the web (well, preferably ...)
> and comprehensible for a non-computer-scientist, non-programmer and
> Lisp-novice?

This book:

  Common Lisp: A Gentle Introduction to Symbolic Computation
  http://www.cs.cmu.edu:80/afs/cs.cmu.edu/user/dst/www/LispBook/index.html

includes a simple state machine example.


Paolo
-- 
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://www.paoloamoroso.it/ency/README
comp.lang.lisp / 2002 / jun