Program 4

Program 4:
Working with a DFA using File I/O and Iteration

Reading input from a file

Note: see links, below for links that will save you some typing.

In your last assignment, you wrote a function 

  (accepts input dfa)
that simulates a deterministic finite-state automaton running on the given input, returning T if the DFA accepts the input and NIL otherwise. Here we'll build on that to illustrate some basics of using LISP for input/output (I/O), and also to write a loop using the do macro.

First, let's look at some code that reads inputs from a file and uses accepts to find the first input accepted by the DFA. 

(defun accept-first-from-file (dfa infile)
  "Call accept-first-from-stream, reading data from infile."
  (with-open-file (instream infile)
    (accept-first-from-stream dfa instream)))

(defun accept-first-from-stream (dfa stream)
  "Reads inputs from stream and returns the first one that 
   the dfa accepts.  Returns NIL if end-of-file is reached without
   accepting any inputs.
  "
  (let ((input (read stream nil :EOF)))
    (format t "~&Input: ~S~%" input)
    (cond ((eq input :EOF) nil)
          ((accepts input dfa) input)
          (t (accept-first-from-stream dfa stream)))))
Notice that the first function is a helper for the second one: it gets things set up, in this case by opening up the stream for reading, so that the second function can make its recursive calls. (What would happen if you put the call to with-open-file inside the recursive function itself?)

Accept-first-from-stream reads an input from the stream, giving it the special value :EOF if the end of the file has been reached when the read operation is attempted. If that has happened, we know we've reached the end of the file without accepting any inputs, so NIL is returned. If not, we try the input in the DFA, and if it is accepted, we can return that input as the first accepted string. If it's rejected, well, we'll just have to keep reading more inputs from the file.

This is an interesting case of recursion. We know we can stop either if we've reached the end of the file, or if we've got an input that's accepted. Otherwise, we have a smaller problem to solve: even though the input file hasn't changed, the input stream is one input shorter. Or, to put this another way, the "remainder of the journey" is the trip from this point on to the end of the file.

Reading and writing

In this next function, you don't read the inputs from a file. Instead, you read the DFA from a file. And in addition, you'll see how to write results to an output file. 

(defun filter-list-using-dfa (inputs dfafile outfile)
  "Runs list of inputs through the DFA in dfafile, 
   writing out the ones the DFA accepts to outfile.
  "
  (with-open-file (instream dfafile)
     (let ((dfa (read instream)))
       (with-open-file (outstream outfile :direction :output)
	   (mapcar #'(lambda (x) 
		       (if (accepts x dfa) 
			   (format outstream "~S~%" x)))
		   inputs)))))
File infile contains the DFA, represented as a list; e.g., file "dfa2.dat" might contain the following: 
((ALPHABET       (a b))
 (STATES          (1 2 3 4))
 (INITIAL-STATE   1)
 (FINAL-STATES    (4))
 (TRANSITIONS     ((1 a 2) (1 b 5)   
                   (2 a 4) (2 b 3)   
                   (3 a 5) (3 b 2)   
                   (4 a 5) (4 b 5)   
                   (5 a 5) (5 b 5))))
As you can see, when you call 
  (filter-list-using-dfa '((a b) (a b b a) (a a)) "dfa2.dat" "test.out")
the first thing the function does is open the file and read in one item, the DFA, assigning it to variable dfa. Next, it opens up the output file, with the :direction specified as :output. (Those funny symbols with colons in the front are called "keywords". They're often used to specify parameters that modify the default behavior of a function, like opening a stream for writing rather than reading, which is what is done by default.)

Once the output stream is opened, the function does the mapcar over the list of inputs. Notice that it's not doing this in order to obtain a result list, as is usual for mapcar. Instead, the mapcar is done for the side-effect of calling format in those cases where the DFA accepts the input. As a result, when accepts returns true, those inputs are written to the output stream, that is they wind up in file test.out.

Using iteration

Here's a version of the same function but using iteration (hence it-) rather than the applicative mapcar function. 
(defun it-filter-list-using-dfa (inputs dfafile outfile)
  "Same as filter-list-using-dfa but iterative, using dolist."
  (with-open-file (instream dfafile)
     (let ((dfa (read instream)))
       (with-open-file (outstream outfile :direction :output)
	   (dolist (x inputs)
	      (if (accepts x dfa) 
		  (format outstream "~S~%" x)))))))
The dolist macro goes through the list inputs, assigning x first to the first item on the list, then to the second, etc. Each time, it executes the body, namely the if statement. This is stylistically a bit nicer than using mapcar just for a side-effect, and it also avoids unnecessarily consing up a list of results.

The assignment

For your assignment, you'll need to have read and understood the section on the do macro in Touretzky, Chapter 10. Below is the skeleton of a function that reads a DFA from one file (dfafile), and then reads inputs for the DFA from another file (infile), writing out to a third file (outfile) just those inputs that are accepted by the DFA. 
(defun filter-file-using-dfa (dfafile infile outfile)
  "Filters the inputs in infile, writing to outfile only
   those accepted by the DFA in dfafile.
  "
  (let ((dfa nil))

      (with-open-file (instream dfafile)
      ;; Insert one line of code here
      )

      (with-open-file (instream infile)
	(with-open-file (outstream outfile :direction :output)
	   (do ;; insert initialization/stepping condition(s) here
               ;; insert termination condition(s) here 
               ;; insert body of code here
	   ))))
  )
For dfafile you should use "dfa2.dat", as above. For infile you should create a file called "inputs.dat" that contains the following: 
(b a b)
(a b b)
(b)
(a a)
(a b a)
(a b b b b a)
(a b b a)

Turning in the Assignment

You should turn in a hardcopy of your filter-file-using-dfa function, and a hardcopy of "prog4.out" after running 
  (filter-file-using-dfa "dfa2.dat" "inputs.dat" "prog4.out")

If you have not completed a working version of the accepts function from Program 3, you can do the following to get a working version: 
 ftp umiacs.umd.edu
 Login as 'anonymous' with your e-mail address as the password
 cd pub/resnik/ling443/program3
 binary
 get dfa.axpf
 quit
This is a binary file containing a correct solution to Program 3. From within LISP execute (load "dfa") (not dfa.lisp!). This will give you a working accepts function if you have not yet successfully implemented it yourself.

Here are a few links that will save some typing: Don't forget that you'll need to load up your solution to Program 3, so that you have a definition for the accepts function.

Good luck, and have fun!