Table of Links
2 Course Structure and Conditions
4 Practical Part
4.2 Technical Setup and Automated Assessment
4.3 Selected Exercises and Tools
8 Conclusion, Acknowledgements, and References
4.3 Selected Exercises and Tools
Many students at TUM have questioned the applicability and usefulness of functional languages after completing the mandatory functional programming course. We believe this is mainly due to two reasons: 1) introductory courses often stick to simple algorithmic or mathematically inspired challenges and 2) side-effects (in particular I/O) are often introduced rather late in functional programming courses.
While we were able to introduce I/O midway through the course, introducing it even earlier appeared difficult to us: we think that students would be confused if a “special” IO type and do notation were to be introduced before they are comfortable with the basic features of functional languages. We thus focused on the other issue and created exercises that go beyond simple terminal applications. Designing and implementing such exercises, however, is labour-intensive. As mentioned in Section 4.1, we thus decided to reallocate resources and let our student assistants help us with this work rather than providing feedback for homework submissions.
This turned out to be a very fruitful idea: the quality of our student assistants’ work was often way above what we expected. The one difficulty we faced was the mediocre quality of tests written by most assistants since they only had the rudimentary knowledge of QuickCheck taught as part of the course. We thus hosted a workshop for them that explained our testing infrastructure and best-practice patterns when writing tests. The quality of tests significantly increased following this workshop, though we still had to polish them before publication.
We next introduce a few exercises and tools that were created as part of the course. They are available in this article’s repository[19], next to our other exercises, including a music synthesiser framework, a turtle graphics framework, an UNO framework, and guided exercises for DPLL and resolution provers.
Game Tournament Framework It has become a course tradition to run a game tournament over the Christmas break. In this tournament, students are tasked with writing an AI for a board game that competes against the AIs of their fellow students. To pass the homework sheet, it suffices to implement a basic strategy, but to score well in the competition, students came up with quite sophisticated strategies in past years. The framework allows students to use statefulness and randomisation, so that there are few limits to the students’ creativity.
The tournament runs continuously for 2–3 weeks and the results are displayed on a website (see Figure 1a for an example from WS20). Students thus get reasonably quick feedback on how their strategy performs, which keeps them engaged and allows them to improve their strategy iteratively. The tournament became a popular feature of the course with 182 participating students in WS19 and 220 in WS20.
In our repository, we provide the framework along with code specific to the game from WS, which is based on Chain Reaction[20]. It runs a round-robin tournament, collecting statistics for each game and player. Instructions for adapting the framework to a different game can also be found in the repository.
Programming Contest Framework To foster social interaction and diversify the bonus system, we hosted an ACM-ICPC-like programming contest. In such contests, students participate in teams of 2–3, solving as many programming challenges as possible in a given time frame, and can check their ranking on a live scoreboard.
We found existing solutions to run such contests too complex for our purpose and hence created a lightweight alternative. Our framework continuously receives test results, computes each team’s score, and displays the live scoreboard and task instructions on a website. It is agnostic to the programming language and test runner used. It expects tests results adhering to the Apache Ant JUnit XML schema, but modifying it to support other formats is straightforward. Deployment instructions can be found in this article’s repository.
We ran an online iteration of the contest in WS20, again using ArTEMiS as a test runner. Teams were cooperating on their platform of choice and were able to ask for clarifications on a dedicated online channel. Our experiences are positive: 27 teams participated in the contest and most stayed for the social hangout following it. Using our framework, the technical setup of the contest requires little time. Some significant time, however, must be spent on setting up the challenges, tests, and solutions, though plenty of them may be found online by searching for other contests, which one then may modify and reuse. We recommend offering such contests to programming course instructors in general.
I/O-Mocking Library As discussed in Section 4.2, we primarily use QuickCheck to automatically assess homework submissions. This raises the question how monadic I/O in Haskell can be tested. Since we do not want to actually execute the side effects that the submitted code produces, the obvious solution is to use a mocked version of Haskell’s IO type.
A standard approach to mock IO, which is put forward by packages such as monad-mock[21] and HMock[22], is to first extract the side effects that are required for a certain computation into a new typeclass. Since a typeclass allows multiple instantiations, we can then provide one instantiation that actually executes the side effects on the machine and another one that just modifies a mocked version of the environment. For example, to implement a function that copies a file, we need two operations: one for reading a file and one for writing a file.
The implementation is straightforward.
While this approach is sufficient for many use cases, it lacks one important property: transparency. More specifically, the code submitted by students must contain or import MonadFileSystem and the signatures of terms that use IO must be adapted. This is especially problematic because the lecture introduces IO without mentioning monads. Other approaches to test I/O face similar issues [36, 39].
Instead of modifying existing code, we delay the mocking to the compilation stage. We achieve this with a mixin that replaces the IO module of a submission with a mocked version. The mocked IO type can be realised similarly to above mock file system. However, to achieve full transparency, we not only need a file system but also handles, such as standard input and output, as well as a working directory.
All these aspects of the machine state are summarised in the type RealWorld as seen below. Crucially, the type also contains a mock user, represented by a computation of type IO (), which interacts with a student’s submission; that is, the user generates the input for and reads the output of the student’s submission. For brevity, we do not show the full type here.
In a normal (non-mocked) execution of the program, the program blocks and waits for input when getLine is called. If our mocked IO type would only consist of a state monad, all the input to the program would have to be passed in one monolithic unit. However, programs may consume input multiple times. We thus need a way to suspend the program every time a blocking operation is called and transfer control over to our mock user. The mock user then reacts to the output of the program and generates the input that the program is waiting for. When the user is done, it yields and the program of the student is resumed.
These considerations lead us to the monad below, consisting of two operations: The first one pauses execution and the second one runs a computation of the monad until either pause is called or the computation finishes. In the former case, stepPauseT returns a Left c where c represents the rest of the computation, i.e. the part of the computation that is executed when resuming. Otherwise, the final result r of the computation is returned as Right r. It should be noted that the pause monad is an instance of the
more general coroutine monad as provided by the monad-coroutine[23] package. For the implementation details of the corresponding monad transformer PauseT, we refer to the repository.
We exemplify the mechanics of the mocking framework with a simple test of above main function. To this end, we first implement a mock user that takes a name and supplies it to the standard input of main. The user then reads the output of the program and checks whether it printed the expected greeting. In the QuickCheck property prop_hello, we evaluate the interaction between the mock user and the program with Mock.evalIO on Mock.emptyWorld, a minimal RealWorld that contains no files and only the absolutely necessary handles: standard input, standard output, and standard error. The interaction itself sets the user to user s, then executes the main function, and finally runs the user to completion.
Figure 2 illustrates the evaluation steps of Mock.evalIO. Note that there are two blocking operations (i.e. operations that call pause internally), namely getLine and Mock.hGetLine Mock.stdout. When Mock.evalIO encounters any such operation, it transfers control between the user and the program as indicated by the black arrows. Control is also transferred if the computation runs until completion without meeting a pause. The horizontal axis with white arrows illustrates the return values of stepPauseT. Focusing on main, we see that stepPauseT returns the remaining computation putStrLn $ "Hello " ++ x wrapped in a Left when encountering getLine. After the user provides the input for getLine and yields, the main function prints the greeting and finishes with the result Right (). Similarly, the user is blocked on Mock.hGetLine, which means that the remaining computation only consists of the when check, which is executed as soon as main is done. This explains why we need to run Mock.runUser after Sub.main since the crucial when check would never be executed otherwise.
All in all, the mocking framework lets us uniformly test student submissions with common frameworks like QuickCheck and SmallCheck regardless of whether they contain I/O effects.
Authors:
(1) Kevin Kappelmann, Department of Informatics, Technical University of Munich, Germany ([email protected]);
(2) Jonas Radle, Department of Informatics, Technical University of Munich, Germany ([email protected]);
(3) Lukas Stevens, Department of Informatics, Technical University of Munich, Germany ([email protected]).
This paper is
[19] https://github.com/kappelmann/engaging-large-scale-functional-programming
[20] https://brilliant.org/wiki/chain-reaction-game/
[21] https://hackage.haskell.org/package/monad-mock
[22] https://hackage.haskell.org/package/HMock
[23] https://hackage.haskell.org/package/monad-coroutine
