### CS250 Symbolic Computation (Fall 2002)

#### Course Prerequisites: CS142 Introduction to Computer Science II

#### Course Contact Information

**Instructor**: Christino Tamon

**Lectures**: Monday Wednesday Friday 2pm Science Center 160

**Office hours**: Monday Wednesday 9-11am and Friday 10-11am Science Center 373

**Contact**: Science Center 373, tino@clarkson.edu

The main text is **Concrete Abstractions**
by Max Hailperin, Barbara Kaiser and Karl Knight, Brooks/Cole, 1999.

#### Topical Outline

This course is a study of functional programming. In previous introductory courses,
a particular type of programming paradigm called the imperative or procedural programming was studied.
These two paradigms differ in the way computation is viewed. The imperative paradigm treats computation
as operations performed on state variables; the functional paradigm treats computation as functions operating
on *values*. Some benefits of the functional approach, among others, are the clean and direct approach to
program design without introducing unnecessary side-effects. Typical well-written functional programs are easier
to understand, simpler to debug, and have a simple proof of correctness.
Most functional programming languages are interpreted (instead of compiled) and strongly supports symbolic
computation (as opposed to numerical). Recursion and higher-order functions will play an important role in
exploring symbolic computation through functional programming.
Other topics include streams (infinite list structure) and generic procedures.
This course uses the programming language Scheme, a dialect of Lisp, as the main example of a functional
programming language.

#### Objectives and Outcomes

The objective of this course is to introduce students to the functional paradigm of progrmaming with some
emphasis on symbolic computation, its implications and applications, and the beautiful types of abstractions
that they provide.
The specific outcomes of this course include:

- Proficiency in programming with the interpreted programming language Scheme in a UNIX-based environment.
- Developed good habits and skills in defensive programming.
- Familiarity with advanced uses of recursive reasoning for designing program and data abstractions
and its impact on the efficiency and correctness of programs.
- Exposure to higher-order procedures and the many abstractions that they provide.

#### Requirements and Policies

Although attendance is not mandatory, students are responsible for all course materials
covered in lectures and any quizzes given during class periods. Students that need to
make up missing course work must provide the required Clarkson official exempt form.
All students must submit their own work; the exchange of ideas are encouraged but
ultimately the submitted work must be the student's own. Please refer to the Clarkson
University Regulations for more guidelines on academic integrity and related matters.

#### Grading scheme

- Final exam: 40%
- Midterm exam: 20% (tentative date: November 1st)
- Assignments and Quizzes: 40%

#### Schedule of Topics

- Functional paradigm of programming versus procedural, object-oriented and logical.
- Basics of Scheme: S-expressions, variables and numbers, DEFINE, LAMBDA.
- Types of recursions: simple/pure, tail, fast (logarithmic), double (tree).

Some examples: addition, multiplication, factorial, exponentiation,
Fibonacci sequence.
- Correctness: inductive proofs vs invariant-based proofs for recursive vs iterative procedures.

*Coming up soon*.
- Functions as
*first-class objects*. Passing functions as inputs and as outputs.

An example using the composition operation on functions.
- Examples of recursions on numbers and their digits: prelude to lists.
See the second lab for more information.
- Lists and their recursive manipulations: digits, CAR/CDR, CONS, map, filter and accumulation.

Some random notes on lists.
- Generic procedures: sorting.
- Data abstractions: using functions and others.
- Streams and continuations

#### Lab Exercises

The MIT Scheme
interpreter is installed on our UNIX system (crux.clarkson.edu). Follow the above link,
for more information and documentation about the MIT Scheme interpreter.