Assignments + Final Project

Assignments

• Assignment 1 - Due Feb 8
• Assignment 2 - Due Feb 18
• Assignment 3 - Due Mar 2
• Assignment 4 - Due Mar 17

Final Project

Project proposal (due Tuesday April 12th, before class)

This is the first step of your final project. Your job is to come up with a project proposal, a sketch of what you plan to do for the final project. The project itself will be due at the end of the semester, but this proposal will allow you to get feedback about your plans before you get started.

Proposal steps:

• (optional) Choose a partner
• Choose a topic

The topic of your project should be something that you are interested in! And fun! Perhaps you would like to go deeper into one of the topics that we have covered in this course. Perhaps there is different topic that you have studied in a different course and that you would like to try out in Haskell.

Note that your project must have some sort of design element to it: whether it is designing a library, or an embedded language, or a new type class, or an application. Projects that are merely porting an assignment from another course to Haskell are rarely successful.

When choosing your application domain, browse this state of the Haskell ecosystem. You should choose a topic where Haskell excels (i.e. marked “Best in Class” or “Mature”). Topics in other domains could lead to frustration and do not give you an opportunity to demonstrate what you have learned this semester. Read the description of “Immature” application domains carefully; some may work for your project, but others may be completely unsuitable. Your project must also connect to the topics that we are covering in class. You can write C-like code in Haskell, using the IO monad and imperative arrays, but we don’t want to see that.

You should do some research on Stackage to see what libraries are already available and easy for you to use. However, you can use any library that works with GHC 8.10.4, even if it is not distributed with Stackage. If there is already code to do what you want to do, don’t despair. It is fine to extend, redesign, rethink, or even redo from scratch an existing library. The only caveat is that you acknowledge all outside code and respect their license agreements.

If you are stumped, I and the TAs can give suggestions. Stick around after class, or if that is not convenient, send email to schedule a time.

• Write a 1 page PDF document following this template. You may edit this LaTeX file to generate your proposal.

• Submit your document to gradescope. Make sure that you include your name, your githubid, your partner’s name and your partner’s githubid (if applicable) at the top of the file.

This proposal is worth 5 points of your final project grade.

Project Rubric

Correctness

• Does it work? And is the project “complete”? We will be looking to see whether the project achives its goals and works as intended. During the course of your work, your mentor will help you refine your project goals.

• How “difficult” was the project? We will be looking for projects that include a significant amount of well-thought out code and design. We would like to see evidence that you have stretched yourself in some way and have produced something more in-depth than, say, a standard data structure or algorithm.

Design

• Not all projects will demonstrate the same opportunities for design. The following are qualities that projects can use to demonstrate their knowledge of CIS 552 design principles. Simple projects may lose points here because there may not have enough opportunity to encounter meaningful design decisions.

• Decomposes the project into modules. Gives thought to constructing a reusable interface for at least one module (i.e. explicit export list, own type class, or clear indication that this should be a library.) We are especially interested in the compositionality of the library operations—witnessed perhaps by Monoid or Applicative/Monad instances.

• Defines appropriate data structures and uses them appropriately. In particular, the project employs newtypes and/or datatypes instead of builtin types when appropriate. The data structures used lead to good running time (i.e. the code doesn’t use !! for lists, or include redundant traversals). Furthermore, the type structure should captures invariants.

• Uses a nontrivial purely functional algorithm. In particular, the code does not put pure code in the IO Monad. The project may extend or adapt a homework problem or (better) develop or implement a new algorithm.

• Uses abstractions covered in class (e.g. Monoid, Functor, Applicative, any Monad other than IO). This may be merely a use of some of the libraries we developed in class (e.g. State or Parser) or it may be as sophisticated as the use of monad transformers.

• Demonstrates abstraction via higher-order functions or type classes. This also includes well-designed helper functions that identify common patterns. We would like to see uses of higher-order library functions, such as map or fold. Even better is a design that uses new higher-order functions to structure their program, or lenses.

Testing

• Testing should be appropriate for the project and should be a convincing demonstration of the project correctness (without relying on the demo). E.g. what are the QuickCheck properties that should hold about your code?

Other considerations may affect the final score of the project. These include:

• Does the project follows style guidelines ?
• Did the project require applying advanced features of Haskell (profiling, type system features, etc.) ?
• Did all team members work together on the project?

Project Presentation

Format

• Prepare a 5 minute per person (hard limit - there’s many of you!) presentation of what you’ve done.
• Can be in the form of slides, a demo, or a combination of the two. Don’t just show your code!
• If you want to show code, select one or two interesting bits: the main data structure you used for representing your data, the cool QuickCheck property you wrote, some particularly crazy bit of Haskell. But don’t do a code tour!
• Give a high level description of what your goal was when you started.
• Give a high level description of where you are currently in the project.
• Add anything that might be interesting/worth sharing: Something you learned/something you’d do different/something that Haskell did weirdly/etc.

Schedule

Thursday, May 5th (extra credit!)

• Elvin Liu/Claude Zou
• Grayson Wolf
• Vyoma Jani/Samuel Howard
• Mitchel Fanger/Matvey Stepanov
• Garrett Hill
• Kameron Hnath
• Guido Ambasz
• Susan Wen
• Chris Jose

Tuesday, May 10th

• Philip Wang
• Segev Elazar Mittelman, Azhdaha Fayyaz
• Yusuf Bham
• Siddarth Taneja
• Aaron Ortwein
• Yishan Zhao
• Jacob Ginsburg
• Hammaad Khan
• Reid Huntley
• Bahaa Haraz
• Talha Muhib
• Yuvraj Nayak

Project Ideas

Here is an example project idea to get you started:

List Comprehensions

You can implement a language of list comprehensions, a subset of those in Haskell. List expressions should contain at least variables, tuples, lists, integer and boolean constants, and some arithmetic and boolean operations. List iterables should at least include some kind of range, variables, and guard in the form of equality/inequality checks.

Your goal would be to write:

• A parser for such expressions from Haskell to your datatype.
• An evaluator that evaluates your list comprehensions within Haskell.
• A pretty printer that leads to valid Haskell programs.
• A random generator that generates arbitrary well-typed list comprehensions in your fragment.
• Run a property that compares the results between your evaluator, and the Haskell implementation to ensure correctness.
• A pretty printer that leads to valid Python programs.
• Run a property that compares the results between the Haskell and Python implementations of list comprehensions.
• Report any interesting findings!

Funge!

You can implement the esoteric programming language Befunge (that the instructor is for some reason a fan of). This project would involve:

• Defining a Befunge interpreter (with whatever alterations you want to make it easier to program)
• Defining a graphical debugger using Brick
• Definining a higher-level (but still low level!) programming language to compile down to Befunge
• Generate programs in your higher-level language and test that interpreting them or compiling them down to Befunge and evaluating them there yields the same result.

The main design component of this project is in creating a high level language that is easy enough to program in (e.g. try solving a couple of Google Code Jam qualifying round problems in it), while still making it easy to compile down to the Funge!