15-150

15-150: Principles of Functional Programming (Fall 2019)

Overview
The purpose of this course is to introduce functional programming. Saying that this is another "programming paradigm" is an understatement. Instead, think of functional programming as a different way to understand computation, one coming from a mathematical perspective. This has interesting implications. First of all, programs become more structured objects, which facilitates reasoning about their correctness. We will see how to apply the well-know principle of induction to do that. Learning how to implement programs with this particular mathematical structure will change the way we solve problems. We will learn how to decompose problems in smaller parts and use these parts to compose a solution. This approach results in natural and elegant solutions for many computer science problems.

Learning goals
Upon completion of this course, students will have acquired a mastery of basic functional programming techniques, including the design of programs using types, the development of programs using mathematical techniques for verification and analysis, the use of abstract types and modules to structure code, and the exploitation of parallelism in applications.
In particular, a student taking this course will learn to:

Write well-typed functional programs using the language ML
Develop specifications and prove program correctness using rigorous techniques
Apply equational, evaluational, and compositional reasoning techniques, and use mathematical and structural induction in proofs
Analyze sequential and parallel running time of programs using the concepts of work and span
Develop cost graphs and recurrences from programs, and use them to derive asymptotic bounds on work and span
Use abstract types and modules to structure code with clear and well-designed interfaces
Identify opportunities for parallelism in code and exploit parallelism by choosing appropriate data structures and function designs

Moreover, you should be able to understand this (do not forget the tooltip).

Pre-requisites
You must have completed 21-127 (Concepts of Mathematics) and 15-112 (Fundamentals of Programming) to attend this course.

Credits
This is a 10 unit core course.

Place and time

Sundays and Tuesdays	15:00 to 16:20	CMB 1190	lectures
Thursdays	15:00 to 16:20	CMB 1032	labs

Schedule

In the table below, labs are in purple, exams are in red and the next lecture/lab is yellow. Grey days are in the past or have no lectures.

Staff

Giselle Reis (Instructor)

Office: 1008
Office hours: by appointment
E-mail: giselle@cmu.edu

Laila El-Beheiry (CA)

Office: ARC
Office hours:

Thursday: 12:00 - 15:00

E-mail: loe@andrew.cmu.edu

Mohammed Nurul Hoque (CA)

Office: ARC
Office hours:

Thursday: 16:30 - 18:00
Saturday: 14:00 - 15:30

E-mail: mnur@cmu.edu

Jize Ning (CA)

Office: ARC
Office hours:

Sunday: 10:30 - 12:00
Tuesday: 16:30 - 18:00
Wednesday: 13:30 - 15:00

E-mail: jizen@andrew.cmu.edu

Kaustubh Iyer (CA)

Office: ARC
Office hours:

Wednesday: 12:00 - 13:30 and 17:30 - 19:00
Saturday: 15:00 - 16:30

E-mail: kkiyer@andrew.cmu.edu

Assessment

Grading

Homework: 30%

Due on Sundays at noon
To be solved individually
Evaluated based on:

Correct type-checking
Correct functionality
Presence of structured comments (type, description, requires/ensures)
Presence of test-cases
Style

Midterm: 20%
Labs: 25%

To get grades for the lab you need to be at the lab
To be solved individually during the time of the lab
Evaluated based on:

Correct type-checking
Correct functionality

Final exam: 25%

Getting the Assignments

The writeup and starter files for each assignment can be found on Autolab. Log in with your andrewID, select the course and then the assignment. You can see the pdf with the instructions by clicking on "View writeup". The starter code and template for typing your answers are in a tgz file which can be downloaded by clicking on "Download handout". Uncompressing this file will create the directory <asgn>-handout with the starter code and a LaTeX template in the latex subdirectory. If you need to download these files again, be careful not to overwrite your work!

Submitting the Assignments

The handout contains a Makefile to help you organize your files for submission. Typing make in the handout directory will create the file <asgn>-handin.tgz and latex/<asgn>.pdf. If you need help using this Makefile, ask the course staff. The tgz file must contain the solutions for the coding part. The pdf must contain the solutions for the written part. It is your responsibility to ensure that the generated files contain the correct material.

The tgz file needs to be submitted to Autolab. It will immediately run a series of tests on your code and give you a score with some feedback. Make sure to check it! If your code does not pass all tests, you can submit it again until the deadline. You are limited to a total of 10 submissions for each assignment.

The pdf with your written solutions must be submitted to Gradescope. No other file formats will be accepted.

Tools

Setting up your programming environment:
The functional programming language we will use for this course is in the ML (for Meta-Language) family and it is called SML (Standard ML). There are different compilers (i.e. implementations) for SML, but your code will be tested with Standard ML of New Jersey (or SML/NJ) version 110.81.

You can use SML/NJ in one of two ways:

On CMU’s machines: All machines should have SML/NJ installed, so you can use it by simply ssh-ing them (type ssh your_andrew_id@unix.qatar.cmu.edu in a terminal and press enter).
On your machine: Go to http://www.smlnj.org/ to download the files and follow the installation instruction for your operating system. Having a local installation is convenient since you will not need to rely on a good internet connection and you can compile local files edited in your favorite text editor. I recommend vim or emacs (both can be used in a terminal, and remember to keep an eye on the status bar at the bottom of the screen). Many students also work with Sublime Text.

emacs

If you are using emacs, there is an sml-mode where you can edit your file and run it interactively. To install, see http://elpa.gnu.org/packages/sml-mode.html. Here are a few useful commands (C-x means hit Ctrl+x):

C-x C-f : open a file (if this is a .sml file and sml-mode is installed, you should see (SML) on the status bar)
C-space : select a text region
C-x C-c : exit emacs

Additionally, the following commands can be used to interact with the repl

C-c C-l : load the file in an sml repl (first time asks the name of the sml command used)

C-x `

C-c C-b : send selected region to sml repl

vim

As far as I know, there is no sml integration with vim, but this is a good text editor which I use on a daily basis. Vim has three main modes: command, insert or visual. By default, it starts on command mode. You can enter insert mode (for editing) by typing i and visual mode (for selecting) by typing v. Hitting ESC will return to command mode. Here are a few useful commands:

i : enter insert mode
ESC : return to command mode
:w : write file (aka save)
:q : quit vim

Sublime Text

Download and install Sublime Text from http://www.sublimetext.com (preferably version 2).
Similar to emacs, Sublime has also integration with SML, which provides syntax highlighting, a repl and code templates. The SML package is installed using Package Control.
To install Package Control, see the instructions at https://packagecontrol.io/installation. To install SML Package:

Press Control/Command+Shift+p in Sublime
Type "Install Package"
Then search for "SML (Standard ML)"

You can either use Sublime as a text editor to work on your machine locally, or you can setup your Andrew File SFTP server and modify your files on the server on Sublime. To set up SFTP server on your Sublime:

Step1: Install the SFTP plugin (which allows you to edit files on AFS):

Press Control/Command+Shift+p in Sublime
Type "Install Package"
Then search for "SFTP"

Step2: Setting up server:

Go to File → SFTP/FTP → Setup Server

Delete the template and paste (substituting your andrew ID where appropriate):


            {
              "type": "sftp",
              "sync_down_on_open": true,
              "sync_same_age": true,
              "host": "linux.andrew.cmu.edu",
              "user": "YOUR_ANDREW_ID",
              "remote_path": "/afs/andrew.cmu.edu/usr/YOUR_ANDREW_ID/private/15150",
              "connect_timeout": 30,
            }

Save this file under the name AFS. This is the name you will use to refer to this connection.

Once eveything is set up, you can open a file on AFS via File → SFTP/FTP → Browse Server. Saving the file will cause it to be uploaded to AFS, where you can compile and run it.

As for the rest, you can find a million resources online, so just google it 😉

References:

LaTeX
Your written assignments will look much better if you develop them in LaTeX. Typically you will edit a .tex file which is compiled into a pdf. This file uses specific tags and commands for typesetting. If you only know Word (or similar) for creating documents, LaTeX takes a little getting used to, but it is worth it. After you become familiar with the syntax, some advantages are:

Typing math is much (much, much) faster
You do not have to worry about margins or consistent style of headers or alignment
Changing the order of sections involves no renumbering on your part
References are formatted and numbered for you (APA? What is that?)

There are various tools for editing and compiling LaTeX. If you do not want to install anything locally, you can use one of the web-based ones, such as ShareLatex. If you use one of those tools, upload all files in the latex directory of the handout.

Policy

You are expected to comply with the university policy on academic integrity (see also The Word and Understanding Academic Integrity).

Collaboration is regulated by the whiteboard policy: you can bounce ideas about a homework with other students, but when it comes to typing it down for submission, you are on your own. You are not allowed to use notes, files, pictures, etc, from any previous discussion nor previous versions of this course.

And remember not to ignore your inner voice when it says “That’s probably not the best decision...”.

An Invitation to Students with Learning Disabilities:

Carnegie Mellon University is committed to providing reasonable accommodations for all persons with disabilities. To access accommodation services you are expected to initiate the request and submit a Voluntary Disclosure of Disability Form to the office of Health & Wellness or CaPS-Q. In order to receive services/accommodations, verification of a disability is required as recommended in writing by a doctor, licensed psychologist or psycho-educational specialist. The office of Health & Wellness, CaPS-Q and Office of Disability Resources in Pittsburgh will review the information you provide. All information will be considered confidential and only released to appropriate persons on a need to know basis.

Once the accommodations have been approved, you will be issued a Summary of Accommodations Memorandum documenting the disability and describing the accommodation. You are responsible for providing the Memorandum to your professors at the beginning of each semester.

Take Care of Yourself:

Do your best to maintain a healthy lifestyle this semester by eating well, exercising, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS-Q) is here to help: call 4454 8525 or make an appointment to see the counselor by emailing student-counselling@qatar.cmu.edu. Consider reaching out to a friend, faculty or family member you trust for help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night at 5554 7913. If the situation is life threatening, call 999.