CS 135 Designing Functional Programs
Objectives
This course covers the principles of program design and the fundamentals of computation through functional evaluation.
Intended Audience
CS 135 is for students who would prefer a more conceptual treatment of introductory computer science in a simple language that is educationally effective but not commercially relevant. While the course is designed to be taken by those with no prior programming experience, students with prior experience will also find it relevant, due to its unusual focus. It is suitable for both CS majors and non-majors.
Related Courses
Antirequisites: CS 115, 121, 122, 123, 125, 131, 132, 133, 134, 137, 138, 145, CHE 121, CIVE 121, ECE 150, GENE 121, PHYS 139, SYDE 121
Successor: CS 136.
Hardware and Software
Used in course: Programs are written in subsets of the language Scheme. Student labs are equipped with the DrRacket integrated development environment running on networked personal computers. Versions for Windows, Mac OS, Unix/X and Linux are freely downloadable for use on computers owned by students.
References
How To Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi, MIT Press, 2003. This book is available in its entirety on the Web, though students are encouraged to purchase a physical copy.
I-Clicker RF Response Remote (Required) .
Schedule
Three hours of lecture per week, plus a tutorial. Available in Fall and Winter.
Outline
Simple Forms of Data (3 hours)
Numbers, arithmetic, function definition and composition, design recipes, conditional expressions, symbols.
Structured Data (3 hours)
Structure definitions, constructors, selectors, data definitions, type predicates, functions for mixed data.
Syntax and Semantics (1.5 hr)
Vocabulary and grammar of the beginning student language.
Arbitrarily Large Data: Lists (6 hours)
Definition of lists, designing functions to process and produce lists, recursive definition of natural numbers, recursive data definitions.
Non-Linear Structures (6 hours)
Multi-clausal recursive data definitions, trees, mutually referential data definitions, design methods for complex data, iterative refinement, multiplexing.
Abstraction Through Local Definitions (9 hours)
Encapsulation, block structure, binding, functional abstraction, filters, polymorphism, generic functions, parametric data definitions, functions as data, functions that produce functions, anonymous functions, abstract list and tree functions (definition and use).
Generative Recursion (6 hours)
Generative versus structural recursion, backtracking algorithms, accumulators and accumulative recursion.
History of Computer Science (1.5 hours)
Babbage, Hilbert, Godel, Church, Turing. Early development of electronic computers and programming languages. History of concepts covered in this course.