% CSci 555: Functional Programming \ Mealy Machine Simulator Project % **H. Conrad Cunningham** % **IN WORK 6 March 2019** --- lang: en --- | Copyright (C) 2016, 2017, 2018, 2019, [H. Conrad Cunningham ]() | Professor of [Computer and Information Science ]() | [University of Mississippi ]() | 211 Weir Hall | P.O. Box 1848 | University, MS 38677 | (662) **Browser Advisory:** The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of March 2019 is a recent version of Firefox from Mozilla. TODO: - Complete description for use with Scala (was Haskell) - Are the operations and their specifications reasonable? - Is an `Either`{.scala} the appropriate return in the various cases? - Should `getTransitionsFrom`{.scala} return an `Either`{.scala} for an invalid state? \newpage ## Mealy Machine Simulator Project In this project, you are asked to design and implement a Scala program to represent Mealy Machines and to simulate their execution. This kind of machine is a useful abstraction for simple controllers that listen for input events and respond by generating output events. For example in an automobile application, the input might be an event such as "fuel level low" and the output might be command to "display low-fuel warning message". In the theory of computation, a *Mealy Machine* is a *finite-state automaton* whose output values are determined both by its current state and the current input. It is a *deterministic finite state transducer* such that, for each state and input, at most one transition is possible. Appendix A of the Linz textbook \[Linz 2017\] defines a Mealy Machine mathematically by a tuple > $M = (Q,\Sigma,\Gamma,\delta,\theta,q_{0})$ where > $Q$ is a finite set of internal states\ > $\Sigma$ is the input alphabet (a finite set of values)\ > $\Gamma$ is the output alphabet (a finite set of values)\ > $\delta: Q \times \Sigma \longrightarrow Q$ is the transition > function\ > $\theta: Q \times \Sigma \longrightarrow \Gamma$ is the output > function\ > $q_{0}$ is the initial state of $M$ (an element of $Q$) In an alternative formulation, the transition and output functions can be combined into a single function: > $\delta: Q \times \Sigma \longrightarrow Q \times \Gamma$ We often find it useful to picture a finite state machine as a *transition graph* where the states are mapped to vertices and the transition function represented by directed edges between vertices labelled with the input and output symbols. ## Exercises Design and implement a Mealy Machine simulator as an immutable Scala "module" using functional programming techniques. You may, but are not required to, use the doubly labelled Digraph abstract data type (presented in class) internally to represent the transition graph. Define an appropriate interface to the module. The Mealy Machine abstract data type should have, at least, public operations to - create a new machine (perhaps one with no states and no transitions) - add a new state to the machine - add a new transition to the machine - add all reset transitions (that is, make the transition function a total function by adding any missing transitions from a state back to the initial state) - set the "initial" state of the machine - get the current state of the machine - get a collection of all states of the machine - get a collection of all inputs enabled for a given state - move the machine forward one step given an input; the machine should generate the appropriate output and enable the next move from the destination state of this move (Note that, in a purely functional program, the "move" function probably needs to return two items--the next state and the output from the current move.) - do other needed tasks (if any) to complete the abstraction or to make your implementation work conveniently with Scala Define a function (either as a part of the abstract data type or that uses it) to execute the machine on a sequence of inputs, returning the corresponding sequence of outputs and enabling the machine to be continued with another sequence if needed. Alternatively, you might want to split the above into two parts--a builder abstract data type that enables a machine to be defined and a separate abstract data type that executes a machine. Remember, your design and implementation should avoid mutable state and imperative Scala code. Design appropriate tests for your functions and test them thoroughly. Document your program appropriately. Submit the source code and documentation for your program and test driver, any needed instructions on how to run the program, and appropriate test output to Blackboard. Be sure to identify yourself in the materials turned in. TODO: Decide whether these functions are appropriate for the intended Scala structure. In particular should these be methods on a class rather than just functions. Should the constructor be a class constructor? etc. 1. Specify, design, and implement a general representation for a Mealy Machine as a set of Scala definitions implementing an abstract data type. It should hide the representation of the machine behind an abstract interface and should have, at least, the following public operations. You may use the Labelled Digraph ADT internally to implement this new ADT. - Constructor `MealyMachine(s)`{.scala} creates a new machine with initial (and current) state `s`{.scala} and no transitions. - Mutator method `addState(s)`{.scala} adds a new state `s`{.scala} to this machine and returns an `Either`{.scala} wrapping the modified machine or an error message. - Mutator method `addTransition(s1,in,out,s2)`{.scala} adds a new transition to this machine and returns an `Either`{.scala} wrapping the modified machine or an error message. From state `s1`{.scala} with input `in`{.scala}, the modified machine outputs `out`{.scala} and transitions to state `s2`{.scala}. - Mutator method `addResets`{.scala} adds all reset transitions to this machine and returns the modified machine. This operation makes the transition function a total function by adding any missing transitions from a state back to the initial state. - Mutator method `setCurrent(s)`{.scala} sets the current state of this machine to `s`{.scala} and returns an `Either`{.scala} wrapping the modified machine or an error message. - Accessor method `getCurrent`{.scala} returns the current state of this machine. - Accessor method `getStates`{.scala} returns a list of the elements of the state set of this machine. - Accessor method `getInputs`{.scala} returns a list of the input set of this machine. - Accessor method `getOutputs`{.scala} returns a list of the output set of this machine. - Accessor method `getTransitions`{.scala} returns a list of the transition set of this machine. Tuple `(s1,in,out,s2)`{.scala} occurs in the returned list if and only if, from state `s1`{.scala} with input `in`{.scala}, the machine outputs `out`{.scala} and moves to state `s2`{.scala}. - Accessor method `getTransitionsFrom(m,s)`{.scala} returns an `Either`{.scala} wrapping a list of the set of transitions enabled from state `s`{.scala} of this machine or an error message. 2. Given the above implementation for a Mealy Machine, design and implement a separate Scala module that simulates the execution of a Mealy Machine. It should have, at least, the following new public operations. - Mutator `move(m,in)`{.scala} moves machine `m`{.scala} from the current state given input `in`{.scala} and returns an `Either`{.scala} wrapping a tuple `(mm,out)`{.scala} or an error message. The tuple gives the modified machine `mm`{.scala} and the output `out`{.scala}. - `simulate(m,ins(`{.scala} simulates execution of machine `m`{.scala} from its current state through a sequence of moves for the inputs in list `ins`{.scala} and returns an `Either`{.scala} wrapping a tuple `(mm,outs)`{.scala} or an error message. The tuple gives the modified machine `mm`{.scala} after the sequence of moves and the output list `outs`{.scala}. Note: It is possible to use a Labelled Digraph ADT module in the implementation of the Mealy Machine. 3. Implement a Scala abstract data type that uses a different representation for the Mealy Machine. Make sure the simulator module still works correctly. ## Acknowledgements I created the original version of this project in Spring 2016 as a programming exercise in the first Scala-based offering of CSci 555, Functional Programming. I adapted and revised this project for possible use in the Haskell-based CSci 556 course in Spring 2017 but did not assign it. In 2018, I revised the project description and merged it into new Chapter 23, Data Abstraction Revisited, in the textbook *Exploring Languages with Interpreters and Functional Programming*. In Spring 2019, I separated the Mealy Machine Simulator Project back into a separate document and modified it for use in a Scala-based course. I maintain this chapter as text in Pandoc's dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed. ## References \[Linz 2017\]: : Peter Linz. *Formal Languages and Automata*, 6th Edition, Jones & Bartlett, 2017. ## Terms and Concepts Mealy Machine, simulator, finite-state automaton (machine), deterministic finite state transducer, state, transition, transition graph.