CSE614 (Spring`08)
Advanced Programming Languages

Course description: This course is officially an advanced graduate level course, but the materials are for anyone who likes or dislikes algorithms/programming/problem-solving, for good reasons, but who would like to (1) get better at them, by learning a systematic method, (2) see applications in security policy frameworks, database applications, web applications, program analysis, and many more, and (3) be exposed to cool languages, such as Python. Each student will do a project that involves designing and implementing an advanced database/web/security application, experimenting with program analysis, developing a general optimization method, or any other task that exploits or extends the methods studied. Good projects can also lead to research projects and publications. | Prerequisites: a programming language or compiler course, an algorithm course, a database course, and skills for programming in a high-level language such as Java; or permission of the instructor. | Credits: 3.

Instructor: Annie Liu | Email: liu@cs.sunysb.edu | Office: Computer Science 1433 | Phone: 632-8463.

Hours: Wed 10:30AM-12:50PM, in Computer Science 1441 | Office hours: after class, by appointment, or stop by any time I'm around.

Textbook: There is no textbook for the course; relevant materials and additional references will be given as the course proceeds. Taking good lecture notes is an important part of the course.

Grading: Weekly homework and a course project, each worth 50% of the grade. Homework is always due in class the following Wednesday. Reduced credit for late submissions, 20% per day.

Course homepage: http://www.cs.sunysb.edu/~liu/cse6914, containing all course-related information.

1. Overview: problems, application domains, challenges, outline of methods and languages.

2. A language: Python.

3. An "application": role-based access control (RBAC), an ANSI standard.

4. Loops and arrays --- incrementalize.

5. Set expressions --- incrementalize and implement.

6. An "application": relational database query implementation.

7. Recursive functions --- iterate and incrementalize.

8. Logic rules --- iterate, incrementalize, and implement.

9. An "application": querying complex graphs.

10. Project discussion.

11. Object abstraction --- incrementalize across object abstraction.

12. Overall: iterate, incrementalize, implement.

13. More on applications and implementations.

14. Project presentations.

Handout Q: Questionnaire

Lecture notes for week 1, motivation and overview.

ANSI Standard for Role-Based Access Control, ANSI INCITS 359-2004, 2004.

Making Specifications Simpler and Clearer: A Case Study of Role-Based Access Control, by Y.A. Liu and S.D. Stoller. (This is a slightly revised version of Role-Based Access Control: A Corrected and Simplified Specification, In Department of Defense Sponsored Information Security Research: New Methods for Protecting Against Cyber Threats, pages 425-439, John Wiley & Sons, 2007.)

Slides for optimizing arithmetic and array computations by incrementalization.

Lecture notes for week 4, incrementalizing expensive arithmetic and array computations in loops.

Finite Differencing of Computable Expressions, by Robert Paige and Shaye Koenig. ACM TOPLAS 1982.

Slides for efficient implementations by transformations for core RBAC.

Lecture notes for weeks 5 and 6, efficient implementation of set expressions.

Slides for optimizing recursive functions.

Slides for transforming recursion to iteration.

Lecture notes for weeks 7 and part of 8, optimizing recursive functions, recursion to iteration, dynamic programming.

Slides for generating efficient implementations from Datalog rules.

Slides for querying complex graphs.

Lecture notes for weeks 8 and part of 9, generating efficient implementations from Datalog rules.

Slides for incrementalization across object abstraction.

Lecture notes for week 11, incrementalize across object abstraction.

Slides for an overview/summary: iterate, incrementalize, and implement.

Viewing a program transformation system at work, by Robert Paige. Joint 6th PLILP and 4th ALP, 1994.

Handout P: Presentation evaluation

Python Tutorial | Library Reference | Language Reference
Python | Python Documentation (v2.5) | Python 2.5 Quick Reference

Core RBAC executable specification in Python

Core Role-Based Access Control: Efficient Implementations by Transformations, by Liu et al. ACM PEPM 2006. (pdf)

This course is officially an advanced graduate level course, but you do not need to have taken other graduate-level courses; the most important prerequisites are programming skills, knowledge of algorithms and data structures, and motivation for studying a systematic method for developing correct and efficient algorithms and programs.

You should learn all information on the course homepage. Check the homepage periodically for Announcements.

Do all course work. The homeworks and projects are integral parts of the course as they provide concrete experiences with the basic concepts and methods covered in the class.

Academic honesty: Homeworks and projects must be done individually, unless specified otherwise; you may discuss with others and look up references, but you must write up your solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating discovered will have a permanent consequence in your university record. For more comprehensive information on academic integrity, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

Disability: If you have a physical, psychological, medical or learning disability that may have an impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.