Chris Pollett>Old Classes>**CS440, Fall
1997**

*Last modified 09/22/97*

**Chris Pollett**

MCS 283

353-8926

Click here to send mail to cpollett@yahoo.com.

MMF 10-11 am

*and by appointment*

Classes meet MWF 9:00am - 10:00am in MCS B33, the basement of 111 Cummington St.

ML for the Working Programmer,
L.C. Paulson, Cambridge University Press.

*Programming in Prolog,*
W.F. Clocksin and C.S.Mellish, (4th ed.) Springer.

To enroll in this course, you must have satisfied the following course requirements. If you haven't done so but still want to remain in the course, please see me.

- MA 293 (Discrete Mathematics 1).
- CS 112 or CS 113 (Programming & Data Structures in C).

The purpose of this course is to introduce the student to functional and logic programming. Programming languages based on these two methodologies are quite different from traditional imperative languages such as FORTRAN and C. In the first half of this course we will be studying the functional programming language ML. The basic building blocks of ML programs are functions. To make a program one begins with simple functions and then one composes functions, performs recursion on subfunctions, curries functions, or makes higher order functions. We will see how data structures can be implemented in ML which is a fair bit different then the way they are implemented in C and discuss advanced features of this language such as structures, signatures, and funtors. ML is based on the typed lambda calculus. Since terms in the lambda calculus are closely related to proofs in intuitionistic logics and also because the semantics of the lambda calculus has been well-studied, it should somehow be easier to prove ML programs have certain properties than programs written in imperative languages. Although we will not go into gory detail about the connections between ML and logic we will casually introduce these topics as the quarter progresses so the student has a flavour for them. In the second half of this course we will cover the logic programming language Prolog. We will discuss applications of Prolog to knowledge representation and artificial intelligence. Prolog is a language based on the idea of proof search. Given a set of known facts about the world and a query Prolog tries to find a solution to the query given these facts. Besides learning how to program in Prolog we will discuss a bit how Prolog finds solutions. This is based on technique know as resolution. We will also discuss the use of cut to limit the search space a Prolog program must search through.

Homeworks 40% Midterm 30% Final 30%

The midterm will be Monday Oct 20 in class. The final will be Thursday, Dec 18. 3-5.

Homework will generally be given every week or two and will usually involve some kind of programming assignment. Turned in assignments whether they be programs or written assignments are expected to be the students own work. Although consultation between students is permitted and encouraged outright copying of another person's work in whole or in part is not permitted. Students found to have misrepresented anothers work as their own will be dealt in the strongest way allowed under BU policies governing academic misconduct.

In general, you will have at least one week to work on a homework assignment and three opportunities to attend my office hours before a given assignment is due.

Late homeworks will not be accepted; however, your low homework score will be dropped.

As shown above in the grade breakdown there will be both a midterm and final in this course. The final will cover only material from the second half or the semester. These exams will test whether or not the student has mastered the material both presented in class or assigned as homework during the quarter. I will try to avoid both tricky and ambiguous questions. The week before each exam I will try to give out a list of problems representative of the level of difficulty of problems the student will be expected to answer on the exam. As with the warning above against homework copying, students are similarly against cheating on exams.

Other announcements will be made only by email. To add yourself to the course mailing list, log on to a CS cluster computer (such as csa) and type

csmail -a cs440

- First homework set.
- Second homework set.
- Third homework set.
- Fourth homework set.
- Fifth homework set.
- Sixth homework set.

- 2nd homework set file.
- Abstract type and functor example.
- Connect4 program.
- Revised Connect4 program.
- Code to check for a win.

- L. C. Paulson.
*ML for the Working Programmer*, 2nd Edition. Cambridge University Press, 1996. **SML Frequently Asked Questions**- Bell Lab's site for
**Standard ML of NewJersey** - A site for
**The HOL Theorem Proving System** - A site for
**XSB Prolog**

Prepared by Chris Pollett.