Department of Computer Science & Engineering
University of California, San Diego

CSE 130: Programming Languages: Principles & Paradigms

Overview

• CSE 130 (Section Id 392593) is a survey of the main features and fundamental concepts of imperative, object-oriented, functional, and logic programming paradigms. The principal languages considered are Haskell, Pascal, C, and Java, but the focus is on programming languages in general, not on the details of specific languages.
• CSE 130 is open to CSE majors only. The current offering has reached its maximum enrollment. The instructor will sign "add cards" only for students who absolutely need to take CSE 130 in order to graduate in the subsequent quarter. Any student in this situation must show proof, i.e. a "degree check" form and a transcript.

Schedule

• Lectures: Monday and Wednesday, 4:40pm-6pm, SOLIS Hall 104
• Discussion Sections: Wednesday, 2:30pm-3:20pm, CENTER Hall 105

Assignments and Examinations

• Midterm and Final together count for 50% of the overall grade.
• There will be several individual (homework) assignments and group projects (1 group = 3 students);
  the individual assignments and group projects each count 25% of the overall grade.
• The labs to use for CSE 130 are APM B402 and EBU-2 313.

• IA1: [Individual Assignment 1.pdf] [sample solutions]
• IA2: [Individual Assignment 2b.pdf] [sample solutions]
• IA3, GP1: [Individual Assignment 3 and Group Project 1] [sample solutions IA3] [sample solutions GP1]
  (the format for the GP1 is similar as for IAs: stapled papers, legible explanations, commented code. Of course the turned in solutions need to identify the group members, include a printout of the solution and some typical testcases, e.g., powerset [1,2,3] ==> ... )
• IA4: [Individual Assignment 4.pdf] [sample solutions IA4]
• GP2: [(Small) Group Project 2] [sample solutions (partial)]
• GP3: [Group Project 3] due Wed. March 14th before class; also check the webboard for additional hints for problem 2! [some comments]
• IA5: [(Small) Individual Assignment 5] Optional (extra credit); can be turned in by 4pm, Monday, March 19th, front desk (1st floor), SDSC, or BEFORE the review session on the same day [sample solutions]

Course Staff

Calendar and Lecture Notes

• (1) Mon, Jan 8: programming language design objectives and history: [Lecture Notes]

• (2) Wed, Jan 10: types: primitive, enumeration, composite, Cartesian products, mappings: [Lecture Notes]

• Mon, Jan 15: MLK holiday

• (3) Wed, Jan 17: arrays as mappings, associative arrays, higher-order functions, currying [Lecture Notes] (updated: Jan 22, 2001)

• (4) Mon, Jan 22: functions vs. relations (revisited), (tagged) union type vs. cartesian product, recursive types (lists and data constructors), introduction to Haskell: values and (polymorphic) types, higher order functions (map) [Lecture Notes]

• (5) Wed, Jan 24: strict/non-strict reduction strategies (leftmost innermost, leftmost outermost), example of type checking/inference, list comprehensions, quicksort in Haskell vs. C, zip function, infinite data structures in Haskell (list of Fibonacci numbers) [Lecture Notes] (updated: Jan 29, 2001)

• (6) Mon, Jan 29: type inference with the Hugs system (compile-time and runtime), function definitions: equations, guards, relevance of order, pattern matching [Lecture Notes] (updated: Jan 31, 2001)

• (7) Wed, Jan 31: programming with lists, higher-order functions (folding), introduction: abstract data types [Lecture Notes]

• (8) Mon, Feb 5: concrete vs. abstract data types, information hiding, encapsulation, ADT: polymorphic stack [Lecture Notes]

• (9) Wed, Feb 7: concrete vs. abstract syntax, expression/subsexpression structure, operator trees, datatypes as abstract syntax notations [Lecture Notes]

• (10) Mo, Feb 12: structural induction, expressions/definitions/commands, variables, formal/actual parameters, imperative vs. functional programming [Lecture Notes]

• Wed, Feb 14, 4:40-6pm: MIDTERM, Center Hall 115 [midterm.pdf] [sample solutions]

• Mon, Feb 19: President's Day

• (11) Wed, Feb 21: midterm review, ADTs in Java, bindings, nested environments [Lecture Notes]

• (12) Mon, Feb 26: variable bindings, static scoping, dynamic scoping [Lecture Notes]

• (13a+b) Wed, Feb 28: blockstructure, lifetimes and scoping of variables, parameter passing methods [Lecture Notes]

• Mon, Mar 5: discussion section (swapped with Feb. 28 lecture): [bindings, parameter passing]

• (14a+b) Wed, Mar 7: function/procedure calls, object-oriented programming, classes vs ADTs, inheritance, dynamic binding, multiple inheritance [Lecture Notes a] [Lecture Notes b]

• Mon, Mar 12: object-oriented programming, polymorphism [Lecture Notes]

• Wed, Mar 14: exception handling in general, in Java, and a potpourri [Lecture Notes]

• Mon, Mar 19, Warren Lecture Hall Room 2204: Review session, 7-9pm [Notes]

• Fri, Mar 23, 3-6pm: FINAL, SOLIS 107, CLOSED BOOK (2 sheets of handwritten notes ok)

  [RESULTS: FINALS and GRADE DISTRIBUTIONS]

Discussion Sections

• Wed, Jan 24: [Haskell examples: member, sort, ...]
• Wed, Jan 31: [Haskell example: tree traversal]
• Mon, Mar 05: [bindings, parameter passing]

Textbooks (and other reading material)

• Concepts of Programming Languages by Robert W. Sebesta, 4th edition (August 1998), Addison-Wesley, ISBN 0201385961.
• The textbook is "recommended" only, so purchasing is not required. However, you should be sure that you have easy access to the book throughout the course. Each project team of three students should possess at least one copy.
• The "required" text for CSE 130 are the instructor's online lecture notes. Several topics discussed in class will not be in the textbook, or will be explained differently. Therefore, attending lectures (and paying attenion, despite the hour...) is highly recommended!
• As the quarter progresses, it is your responsibility to locate relevant chapters of the textbook and to study them. (Examinations will be based mainly on the online lecture notes, but may ask questions that involve knowledge from the textbook.)

Functional Programming with Haskell

• The functional language Haskell will be used for several assignments (also see about-Haskell).
  (ML has strict evaluation an functions may have side effects; Haskell is a pure (side-effect free) and has lazy evaluation)
• The Haskell system used for the class is Hugs; it is freely available for many platforms. Also see the very good Hugs 98 user manual!
• The tutorial A Gentle Introduction to Haskell is highly recommended.
• Another very good and detailed source is the Haskell Companion, in particular, the principles section.
• Here is another Concise Introduction to Haskell (nicely summarizes the most important features of Hugs and Haskell)
• For those of you who want to learn more about the art of functional programming (not to be confused with hacking (Emacs) Lisp...which can be fun as well), I recommend Introduction to Functional Programming using Haskell by Richard Bird
• Programming it in Haskell gives advice and tips for how to start "thinking functional/Haskell" when attacking your programming problems.
• The FAQs of comp.lang.functional contain interesting background information and links.