15-150: Principles of Functional Programming (Fall 2022)
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
21-127 (Concepts of Mathematics) and
15-112 (Fundamentals of Programming)
Credits
This is a 10 unit core course.
Place and time
Sundays and Tuesdays |
14:30 to 15:45 |
Room TBA |
lectures |
Thursdays |
14:30 to 15:45 |
Room TBA |
labs |
Homework
Grading
- Homework: 30%
- To be solved individually
- The programming part is evaluated on:
- Correct type-checking (autograded)
- Correct functionality (autograded)
- Correct requires and ensures (manually checked)
- Comprehensive test cases (manually checked)
- Style
(manually checked)
- The written part is evaluated on:
- Correct answer
- Clarity, objectiveness, and conciseness
- Self-containment
- Typesetting
- The lowest homework is dropped
- Labs: 10%
- To get grades for the lab you need to be at the lab and hand in the written
answers
- To be solved individually during the time of the lab
- Midterm I: 20%
- Midterm II: 20%
- Final exam: 20%
Getting the Assignments
The writeup and starter files for each assignment are in a
zip
file linked on the schedule above.
Uncompressing this file will create the directory
<asgn>-handout
with the starter code and a LaTeX
template.
If you need to download these files again, be
careful not to overwrite your work!
Submitting the Assignments
The handout contains Makefile
s to help you organize your
files for submission. Typing make
in the code
directory will create the file <asgn>-handin.zip
.
Typing make
in the latex
directory will
compile the LaTeX into a pdf.
If you need help using this Makefile
, ask the course staff.
The zip
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 zip
file needs to be submitted to the code part of the
assignment on
Gradescope.
It will immediately run a series of tests 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
file needs to be submitted to the written part of
the assignment on
Gradescope.
Submissions that are in another
format or badly typed will be penalized.
Staff
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.