Course:CPSC312-2021/NPlanetary

From UBC Wiki

NPlanetary

Authors: Bronwyn, Johann, Justin

What is the problem?

We are creating a protocol for networked electronic board games, demonstrated using attack and movement mechanics from the board game Triplanetary. We want to be able to send board states to the client and receive moves from the client, which are resolved by the server.

What is the something extra?

Using an existing TCP/IP stack and Haskell's built-in concurrency primitives, we designed an original application-level protocol to allow servers to serialize and send Haskell data to clients and to allow clients to submit serialized Haskell data in response. Our demonstration involves implementing this protocol using a multi-threaded server taking advantage of Haskell's built-in concurrency primitives to provide thread safety and allow for multiple threads to simultaneously send and receive data to and from clients.

We also investigated the use of QuickCheck2's property-based testing to verify that the client and server were properly serializing data to be sent and that the server was correctly implementing the game mechanics.

The project is in a state where it could, with expenditure of time, be extended into a full implementation of any board game with minimal edits to game-specific code.

What did we learn from doing this?

(This should be written after you have done the work.) What is the bottom-line? Is functional programming suitable for (part-of) the task? Make sure you include the evidence for your claims.

Networking in Haskell

We learned that handling network disconnects was difficult due to the way the TCP protocol itself handles network disconnects. The protocol and our demonstration implementation assume a reliable network - we did not find a way to get around this assumption.

The actual process of reading and writing data on the network was not more difficult than reading and writing data to and from files or the console - Haskell's networking library is well-documented and well-designed.

We found it difficult to implement a protocol that could send arbitrary Haskell data with minimal boilerplate - as it stands, we reserve the use of some ASCII control characters for the protocol itself, and require that no user-supplied data contain those characters. Additionally, we found it difficult to send binary data, especially floating point numbers, since we did not have easy access to the raw binary data. We got around this by converting integers to strings and floating point to fixed-precision strings, and sending those. While this did limit the precision and magnitude of sent floating point data, we believe that most games will not need to send floating point numbers that ordinarily would require exponential notation. Finally, our protocol does not handle arbitrary nested lists - we do not have enough reserved control characters to handle more than four levels of nesting. We also believe that most games will not need to send such data.

These limitations came about since we wanted to handle parsing of incoming data by splitting the data into tokens based on our reserved control characters. The use of control characters for in-band signalling and the limitations on nested lists could be more easily solved by changing the protocol to require a full-up parser to be able to parse incoming data. Additionally, a better format for sending arbitrary magnitude and precision floating point numbers could be implemented, but it would also require additional protocol complexities that we did not think were useful.

Concurrency and Mutability in Haskell

Haskell, despite its claim to be a purely functional language, offers some ways to program in an imperative style, using the IO monad and IORefs. IORefs are useful, since they allow sharing of state between multiple threads similar to how shared memory is used in other languages. However, IORefs are not thread-safe, and our protocol itself, if implemented on a multi-threaded server, also requires synchronization between threads. We found the built-in concurrency primitives (especially semaphores) to be similar to those in other languages. Additionally, random number generators are implemented oddly in Haskell, compared to other languages - random number generators depend on the IO monad.

The requirement that the IO monad be used for IO, inter-thread communication, and random number generation leads to an interesting case of "coloured functions" - any function that uses the IO monad can call any other function, but a function that does not use the IO monad may not call one that does. This issue, however, is not as severe as the situation with JavaScript's coloured functions and "callback hell" - it is just as easy to call a function that uses the IO monad as one that does not. The nature of the IO monad meant that some of our leaf functions could be implemented purely functionally, many non-leaf functions needed to use the IO monad, even if they themselves did not directly use it.

Implementation of Demo Game Mechanics

Our implementation had a somewhat inappropriate type structure - we ended up creating an Entity type with several different constructors to represent the different kinds of entities that could be on the board (ships, planets, etc.) and overall this was slightly clunky. In retrospect, we believe it is possible to make it less clunky by making Entity a type class and creating a separate sum type to cover all the different entity types. We used GLUT to implement our client's UI - it was very similar to big-bang from the CPSC 110 student languages, but it too relied on mutable state and the IO monad. As before, the nature of the IO monad was not a significant hurdle to implementation.

Finally, we tested the serialization of data and resolution of game mechanics using property-based testing offered by QuickCheck2, in addition to unit tests. Property based testing was useful, in that it allowed us to express tests in terms of behaviour and invariants independent of concrete examples, but involved plenty of boilerplate, especially when generating arbitrary instances of user-defined data types.

Testing

Despite not testing connections originating from remote networks, we believe our current implementation supports them. The clients and server initialized from our program all run on separate processes. This requires all communication between these processes to be done through the established network connection. As mentioned in the network section of this post, we assume a stable connection between the clients and the server. This leaves the only source of error to be in the processing of the data sent by the end stations of the connection. This processing is agnostic to the location of these end stations and the routing done between them - whether that be routing on a private network for local connections or routing on the wider web for remote connections.

Links to code etc

https://github.com/JustinHuPrime/NPlanetary