Goals

• Introduction to C++ Classes & C++ Memory Management
• More familiarity with Finite State Machines

Collaboration

For assignments in CIS 3990, you will complete each of them on your own. However, you may discuss high-level ideas with other students, but any viewing, sharing, copying, or dictating of code is forbidden. If you are worried about whether something violates academic integrity, please post on Ed or contact the instructor(s).

Setup

You can downlowd the starter files into your environment by running the following command. You should run it from inside your git repository since that is how you will submit your code.

curl -o fsm_starter.zip https://www.seas.upenn.edu/~tqmcgaha/cis3990/current/projects/code/fsm_starter.zip

You can also download the files manually here if you would like: fsm_starter.zip

From here, you need to extract the files by running

unzip fsm_starter.zip

You should now have a folder called fsm that has the starter files. We expect this to be a folder inside the base of your github repository, similar to cowsay and check-setup. If you accidentally put the folder somewhere else, you can move it with the mv command in the terminal.

Starter Files

In the zip you will find several files:

The first two are important directly for the work you will do:

• FSM.hpp: Contains the declarations and extensive comments detailing the object and the memeber functions you will have to implement for this assignment.
• Makefile: Makefile for compilng the tests and source code. This is here because you will likely want to targets and source files to the project.

The rest are related to the tests suite:

• ParseFSM.hpp: Contains the declarations for a function to parse a FSM from a string.
• ParseFSM.cpp: Contains the implementation for the ParseFSM function.
• test_fsm.cpp: The tests that we will be using to evaluate your FSM implementation.
• test_suite.cpp: Entry point for running our tests.
• catch.cpp: Catch2 testing framework source
• catch.hpp: Catch2 testing framework source

We recommend reading all of FSM.hpp before you get started on the assignment.

Overview

In this assignment you will gain more familiarity with C++ classes by implementing a class that represents a Finite State Machine.

What is an FSM

A Finite State Machine (FSM) is one of the most important abstractions in computer science.

An FSM represents a machine that can be in one of many possible defined finite states. The machine then moves between these states in response to some “transition” or “input”.

You may not be familiar with a Finite State Machine, but you should be familiar with graphs at this point.

We can represent a FSM with a directed graph where each node represents some “state” and each edge represents some “change” to go from one state to another. The machine starts at the designated starting state, and then moves to other states as it processes input.

Consider the following simple finite state machine:

This finite state machine is constructed to determine if a binary string (a string consisting of only 0s and 1s) contains the substring “001”

We can demonstrate FSMs by showing how this one may be used to solve the problem it was designed for. Lets say that we have the input string “010010” and we want to use the above FSM to see if it has the “001” substring.

We start at the node marked with the “start” arrow and begin parsing the string one character at a time to transition us between states.

First is the character 0 to transfer us to the marked state in the diagram

Then the machine handles the next character 1, which sends us back to the start:

We then get 0 which again changes the state again.

Next is 0 which moves us to the next state:

We get 1 which moves us to the state all the way on the right:

Finally we have 0 and that keeps the machine in the current state since there is a transition pointing to itself to handle the 0 transition.

Finally, you may notice this last state is special as it is made of two cocentric circles. This is to mark this state as an “accept” state, meaning that whatever the machine is trying to “solve” is true (in this case, it is true that the input 010010 contains the substring 001).

Other things to note about FSMs:

• Note that it is possible for a FSM to have more than one accept state
• The FSMs we deal with in this assignment will always have exactly one start state
• If we are on some state and get an input that doesn’t have a corresponding transition, then we stop transitioning in the FSM and evaluate the machine as “not having reached an accept state”
• The FSMs we deal with are deterministic and can only be in one state at a time. e.g. this is not a legal FSM since there are multiple transitions that occur on the same input, and the FSM cannot be in both states at once.

Take a look at the starter code in FSM.hpp to see more details on how exactly we want you to implement the FSM in this assignment.

Match

The most important function in the FSM is the Match Function, which is used to see if a certain sequence of inputs will make the machine reach an accept state from the start state.

There is a detail that makes this function a little bit more complex though. Consider the following FSM

If we have an FSM object representing this, and then call Match("cat"), it will return the StateID of the accepting state. Hopefully this is clear why, if not then please ask for clarification and we would be more than happy to explain.

What is a little tricky is that we are having our FSM match if any substring of the input will take the machine from the start state to an accept state. Consider the following example inputs:

• catchy - succeeds on the input substring “cat”
• haaaaaaaaaaaaaaat - does not succeed
• halibut - does not succeed
• thank you for that - succeeds on substring “hat” (inside the word “that”)
• carmat - does not succed
• what are you doing? - succeeds on substring “hat” (inside the word “what”)

Note that this is the behaviour by default. We also have two helper functions MarkStartAnchor and MarkEndAnchor which affect how we process the string input in Match.

If a user calls MarkStartAnchor(true) then we only look at only substrings that start at the beginning of the input string. (So in the examples above, what are you doing? would no longer match since there is no substring that starts at the beginning of the string that will get the machine to an accept state).

If a user calls MarkEndAnchor(true) then we only look at substrings that end at the end of the input string. In the examples above, both catchy and what are you doing? would no longer match on the FSM.

If a user calls both MarkStartAnchor(true) and MarkEndAnchor(true) then only the whole input string is considered, and each substring does not need to be analyzed. In our example, only cat and hat as inputs would match onto this FSM.

Note: You do not have to do anything fancy for checking all possible substrings. “Brute force” is fine.

Last Few Details

Lastly there are a few other small details specific to our implementation that are worth noting:

• the . character acts as a wildcard character, and corresponds to any specific character input. e.g. if you parse a character (lets say “H”) to move from a state and there is no transition for the “H” character but there is one for the . character, you should take the . transition.
• Your finite state machines should construct with a single state: 0. This state is the starting state of your FSM.

C++ Classes

A big part of this assignment is that you will have to handle making a C++ class. Part of this means that you will have to define at least one constructor for the FSM class itself. However, implementing this FSM will necessitate some usage of dynamic memory so that your FSM can grow to add more edges and states.

As a result, you will likely have to define 1 or more destructors, copy constructors, assignment operators, move constructor and move assignment.

Note that for some of these you can define it as either default or disable them when it is useful. For example, to specify that the default behaviour for copy constructing and assignment operator on an FSM is fine, you can put this in the FSM declaration (in the .hpp file).

  FSM(const FSM& other) = default;
  FSM& operator=(const FSM& other) = default;

To disable these, you would just set them equal to delete instead of default.

Per the C++ “rule of 5”, if you define, set equal to default, or delete one of these, you should do one of those 3 options for the others:

• destructor
• copy constructor
• assignment operator
• move constructor
• move assignment operator

Clang-tidy will ask that since FSM sets a non-default constructor that you also delete, default, or define everything in the rule of 5.

Tips

• We HIGHLY HIGHLY HIGHLY encourage you to make your own data structure(s) to aid you in this assignment. It will probably make your life simpler if you can set your FSM destructor, copy constructor, etc to default because it is made of data structures that handle memory for you.
  • You can take inspiration from the objects we made in class together :)
  • See the templates section below for how to make a data structure “generic”.
• We don’t care about optimizing run-time efficieny in this homework assignment. You just need to get it to work. and for it to not be too slow (e.g. we don’t care about O(n) vs O(n^2). It would have to be REALLY REALLY slow like O(2^n) for us to care.
• You probably want to make one or more “private helper structs” to help you in this assignment. The staff solution only uses one struct, but more can be used. For example:
• You probably should start the Match() function by assuming that the start and end are anchored. Many of the test cases work with that so you can test your implemnetation while also not having to tackle everything at once.

class SomeClass {
 public:
 private:
  struct PrivateHelperStruct {
    // this struct is private to SomeClass
    int x;
    int y;
  };

  // Can be used as a field now:
  PrivateHelperStuct m_some_field;
}

Templates

If you want to make an object to work with any type, you can use templates to make the object “generic”. We will talk about templates and their implications in lecture later in the course, but this is a short example to communicate the point.

Lets say we had the following class:

// Thing.hpp
#ifndef THING_HPP_
#define THING_HPP_

class Thing {
 public:
  void Set(int value);
  int Get();
 private:
  int m_value;
};

#endif  // THING_HPP_

///////////////////////////////////
// Thing.cpp

void Thing::Set(int value) {
  m_value = value;
}

int Thing::Get() {
  return m_val;
}

We can genrealize it to use templates, so that it can store any type instead of an int:

///////////////////////////////////
// Thing.hpp
#ifndef THING_HPP_
#define THING_HPP_

template<typename T>
class Thing {
 public:
  void Set(T value);
  T Get();
 private:
  T m_value;
};

void Thing<T>::Set(T value) {
  m_value = value;
}

T Thing<T>::Get() {
  return m_val;
}

#endif  // THING_HPP_

VERY IMPORTANT TO NOTE: we put ALL of our code in the .hpp file! (something that is almost never done!!). If you try to split your template code up into a .hpp and .cpp file then the template code will not work.

Another intresting note is that how we use the typename T dictates the requirements we have for T: For example:

• The synthesized 0-arg constructor for Thing will have to default initialize T, so it must be default constructable (have a 0-arg constror) if it is a struct or class.
• The Set and Get functions take in a copy of a T and return a copy of a T respectively, so the copy constructor must be defined for T

Allowed Headers

You are allowed a few things from the standard library in this assignemnt. Most things are forbidden to avoid trivializing this assignment.

We are allowing you to use two objects from the C++ standard library to complete the assignment. We may have not covered these in class yet, but they are similar enough to constructs you have seen in other languages, that we will just give a short primer here:

std::string

This is a string object!!!!! We don’t have to use char* all the time anymore! It works as a string object, and for this assignment there are a few items that are useful to demonstrate:

string example {"Hello!"};  // constructs a string
string empty;   // default construts the string to be the empty string: ""

// print the string
cout << example << endl;

// gets the length of the string
size_t len = example.size();

// iterate over each character in the string
for (char c : example) {
  cout << c << endl;
}

// access the character at a specific index
// throws an exception on out of bounds:
char c = example.at(1);  // gets `1`

// iterate over each character with a normal for loop
for (size_t i = 0; i < example.size(); ++i) {
  cout << example.at(i) << endl;
}

std::optional

optional is a way for us to express that something is either some thing T or “nothing”. It essentially allows us to mimic the behaviour we see in Java where each object can refer to an object or null.

This is also the same as Option in OCaml or Optional in Java.

optional<int> StringToInt(const string& other) {
  if (/*string doesn't represent an int*/) {
    // return a "null value"
    return nullopt;
  } else {
    int val = /*convert the string to an int */

    // return a valid value
    return val;
  }
}

int main() {
  optional<int> opt = StringToInt("Hello!");

  if (opt.has_value()) { // see if the opt has a value
    int val = opt.value(); // get the value. Throws exception if the value is not present
    cout << "Conversion: " << val << endl; 
  } else {
    // Not a value :(
  }
}

Grading & Testing

Compilation

We have supplied you with a Makefile that can be used for compiling your code into an executable. To do this, open the terminal and then type in make.

You may need to resolve any compiler warnings and compiler errors that show up. Once all compiler errors have been resolved, if you ls in the terminal, you should be able to see an executable called test_suite. You can then run this by typing in ./test_suite to see the evaluation of your code.

Note that your submission will be partially evaluated on the number of compiler warnings. You should eliminate ALL compiler warnings in your code.

Valgrind

We will also test your submission on whether there are any memory errors or memory leaks. We will be using valgrind to do this. To do this, you should try running: valgrind --leak-check=full ./test_suite

If everything is correct, you should see the following towards the bottom of the output:

 ==1620== All heap blocks were freed -- no leaks are possible
 ==1620==
 ==1620== For counts of detected and suppressed errors, rerun with: -v
 ==1620== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

If you do not see something similar to the above in your output, valgrind will have printed out details about where the errors and memory leaks occurred.

catch2

As with mentioned above, you can compile the your implementation by using the make command. This will result in several output files, including an executable called test_suite.

After compiling your solution with make, You can run all of the tests for the homwork by invoking:

$ ./test_suite

You can also run only specific tests by passing command line arguments into test_suite

For example, to only run the “Binary Even Length” test, you can type in:

$ ./test_suite "Binary Even Length"

You can specify which tests are run for any of the tests in the assingment. You just need to know the names of the tests, and you can do this by running:

$ ./test_suite --list-tests

These settings can be helpful for debugging specific parts of the assignment, especially since test_suite can be run with these settings through valgrind and gdb!

Clang Format and Clang Tidy

The makefile we provided with this assignment is configured to help make sure your code is properly formatted and follows good (modern) C++ coding conventions.

To do this, we make use of two tools: clang-format and clang-tidy

To make sure your code identation is nice, we have clang-format. All you need to do to use this utility, is to run make format, which will run the tool and indent your code propely. Code that is turned in is expected to follow the specified style, code that is ill-formated must be fixed and re-submitted.

clang-tidy is a more complicated tool. Part of it is checking for style and readability issues but that is not all it does. It also checks for and can detect possible bugs in your program.

Because of all this, we are enforcing that your code does not produce any clang-tidy errors. You can run clang-tidy on your code by running: make tidy-check. Note that you will have to fix any compiler errors before clang-tidy will run (and be useful).

If you have any questions about understanding an error, please ask on Ed discussion and we will happily assist you.

Manual Checks

For this assignment the only checks we will be doing are:

• checking your Makefile to make sure you set it up correctly to include any custom objects or files you create.
• that you aren’t breaking the spirit of the assignment by hard-coding some test cases or something else

Submission

Please submit your completed FSM.cpp, FSM.hpp and other files to Gradescope via your github repo. We will be checking for compilation warnings, valgrind errors, making sure the test_suite runs correctly, and that you did not violate any rules established in the specification.