Introduction to Functional Programming

Sarah Lawrence College
Spring 2021

Course Description

This course will explore the functional programming paradigm, a style of programming in which all computation is performed by applying functions to arguments. Our study of functional programming will make ample use of recursion — one of the most powerful concepts in computer science — and recursively-defined data structures such as lists, using the strangely beautiful programming language Scheme. Scheme and other functional languages provide powerful abstraction techniques for controlling the complexity of programs, and a simple mathematical basis for reasoning about their correctness. Many of the most important concepts and features of modern programming languages were first introduced and studied within the framework of functional programming. Today, functional languages remain at the cutting edge of new programming language design, and key ideas from functional programming continue to play a central role in the development of highly parallel, scalable, and distributed computing systems. Topics to be covered include recursion and its close cousin mathematical induction; induction proofs and program correctness; mapping, filtering, and reducing lists; lambda expressions and higher-order functions; data abstraction and representation independence; infinite lists; continuations and continuation-passing style; and other topics as time permits. No prior knowledge of computer programming is necessary, though students should be comfortable with algebra and the fundamentals of mathematical thinking.

Open to any interested student.


Prof. Jim Marshall
Office: Ilchman Science Center 100
Phone: 2673 (from off campus: 914-395-2673)
Email: j + my last name +

Class Meeting Times (Online)

Online Classroom Environment

Our course this semester will be conducted synchronously online via Zoom, so you should read through the Zoom information for students provided by the SLC Help Desk. Most of the time, I will encourage everyone to keep their web camera turned on during class. This will help me to get to know everyone more quickly. If you would prefer that others not see your local surroundings, you might consider using a Zoom virtual background or customizing your Zoom profile to show a picture of yourself. Other things to keep in mind:


There are no required textbooks for this course. However, the following two books are excellent sources of additional information about functional programming and Scheme. Both are available online for free. From time to time I will assign readings and exercises from Concrete Abstractions.

Concrete Abstractions
Max Hailperin, Barbara Kaiser, and Karl Knight
The Scheme Programming Language, 4th edition
R. Kent Dybvig


I will often send out announcements to the class through email, so you are required to check your Sarah Lawrence email account at least once per day. I will use your address because it is reliable and easy to remember. You should also check the course web page frequently for code examples discussed in class, and for the homework assignments. I will be happy to answer your questions by email or Zoom and will try to respond as quickly as possible to messages that pertain to the course.

Homework Evaluation

Homework assignments are evaluated on both the functionality and style of your code, according to the following rubric. To receive a ☆, your code must not only work perfectly, it must also be logically well-organized and easy to read.

Work of excellent quality that clearly meets or exceeds all of the assignment expectations. All programs work correctly on all of the input data, and are written in a clear, easy-to-read style.
✓+ Work of very good quality that meets most of the assignment expectations. Programs work correctly or mostly correctly for most of the input data, though some programs may have a few minor deficiencies or stylistic problems.
Work of satisfactory quality that meets some of the assignment expectations and reflects a good effort overall, despite some deficiencies. Some programs work correctly or mostly correctly for most of the input data, but may have significant stylistic problems or other shortcomings.
✓− Work of subpar quality that falls short of assignment expectations and needs improvement. Some programs have serious deficiencies, and work incorrectly for a significant portion of the input data. Nevertheless, the work shows some degree of effort and understanding.
Work of poor quality that exhibits severe problems, reflecting minimal effort or understanding. Many programs crash or work incorrectly for most or all of the input data.

Getting Help

At times you may find some of the course material to be quite daunting. But don't be discouraged! If you find it difficult, most likely so does the rest of the class. This is just a normal part of the process of learning to program. You are strongly encouraged to contact me as soon as possible whenever you are having difficulty with the material. If you are confused about something, don't stay that way! Staying confused will only make things worse later. Contact me as soon as possible so that we can clear up the problem. There is no point in staring at the computer screen for hours trying to figure out why your code won't work, when just a few minutes is often all it takes to track down the problem together. I'll also be happy to answer questions over email, during conference, or in a separate Zoom meeting with you.

Reasonable Accommodations

If you have a disability that may interfere with your ability to participate in the activities, coursework, or assessment of the objectives of this course, or any of your other courses, you may be entitled to reasonable accommodations. Please contact Polly Waldman, Associate Dean of Studies and Disabilities Services located in Westlands 116. You may also call Disability Services at 914-395-2235 or email pwaldman at Under the Americans with Disabilities Act and Section 504 of the Vocational Rehabilitation Act of 1973, all students, with or without disabilities, are entitled to equal access to the programs and activities of Sarah Lawrence College and the College will make reasonable accommodations when appropriate and necessary.

Collaboration Policy

The highest level of academic integrity is expected of every student. You are strongly encouraged to discuss ideas and approaches to solving problems on a general level with your fellow classmates, but you are not allowed to share your program files, code, or solutions with others. I can almost always tell when two different programs derive from the same original source code, even if cosmetic changes have been made to it. The code you hand in must have been written by you from scratch, with the following permitted exceptions: code provided in class by me, code from the textbook, or code developed together with a partner if you are collaborating on a lab or project. In this case, you and your partner may freely exchange code developed as a team, and are jointly responsible for the work submitted. Under no circumstances may you hand in work done by someone other than yourself or your partner under your own name. Effective learning is compromised when this is not the case.

In all cases, if you make use of any code that was written by someone else in your assignment, including your partner, you must clearly acknowledge this in your code. This also goes for any help obtained via the Internet. When in doubt, credit the people or sources from whom you got help. If you are ever unsure about what constitutes acceptable collaboration, just ask. You are also responsible for carefully reading the College's official Policy on Academic Integrity in your SLC Student Handbook. Failure to abide by these rules is considered plagiarism, and will result in severe penalties, including possible failure in the course. Please do not put me, yourself, or anyone else in this unpleasant situation!