Topics Listed in Approximate Order of Presentation

Text and reference books referred to below are (S) Sethi, R., Programming Languages: Concepts and Constructs, Addison Wesley, second edition, 1996. and (ASU) Aho, A.V., Sethi, R., and Ullman, J. D., Compilers: Principles, Practices and Techniques, Addison-Wesley, 1986. Copies of ASU are on permanent reserve in the Math Library. Recall that Rutgers University Libraries subscribe to both the ACM and IEEE Computer Society Digital Libraries, so that many of these articles are available electronically (although we cannot point into these resources). All 'on reserve' books listed below are subject to confirmation that they are in the Rutgers Library collection.

Review of Top Down and Bottom Up Parsing

LR(k): SLR, LR, LALR parsing;

ASU Ch 4.5,4.7-4.9.

Attribute Grammars.

Top down and bottom up evaluation schemes, categorization by ease of parsing, syntax-directed code generation.

ASU Ch 5.1-5.6, S Ch 13.1-13.2

Prolog

Examples, lists, recursive functions, model of Prolog execution, search trees, unification, most general unifier.

S Ch 11,13.3

on reserve:
R. Davis, "Logic programming and prolog: a tutorial", IEEE Software, vol 2, no 5, Sept 1985, (available from the IEEE Digial Library, maybe);

R. Kowalski, Algorithm = Logic + Control, in Programming Languages, edited by Horowitz;

W.F. Clocksin and C.S. Mellish, Programming in Prolog, Springer-Verlag, 1987 (or the newer edition of this book);

other sources include:
J. Cohen, ``Describing Prolog by its Interpretation and Compilation'', CACM, December 1985 (see ACM Digital Library);

L. Stirling and E. Shapiro, The Art of Prolog:Advanced Programming Techniques, MIT Press, 2nd edition, 1994;

Online Prolog:

• Tutorials
  • Introductory level
    Tutorial
    Tutorial2
    A tutorial for Linguists
    
  • Intermediate to advanced level
    Tutorial 3
• Sicstus Prolog Manual
• A website listing free Prolog interpreters, including some written in Java, for PC, Linux, Mac (no guarantees).

Prototyping compilers with Prolog

Lecture based on article on reserve:
D.H.D. Warren, "Logic Programming and Compiler Writing", Software Practice and Experience, vol 10, 1980; See also the errata sheet for this paper.

ASU Ch 8.1,8.3-8.6

other sources:
J. Cohen, and J. Hickey, Parsing and Compiling Using Prolog, ACM TOPLAS, Vol 9 no 2, April 1987.(see ACM Digital Library)

Types and Type Systems

Type resolution systems, a simple type system, type equivalence, type checking, polymorphism (classification), type variables, unification and substitution, non-standard types used for analysis.

ASU Ch 6, S Ch 4

other sources:
L. Cardelli, and P. Wegner, ``On Understanding Types,Data Abstraction, and Polymorphism'', ACM Computing Surveys, December 1985, (see ACM Digital Library).

Lambda Calculus and functional programming

Function definition and application, curried functions, substitution rules, beta-reduction, alpha-reduction, normal form, Church-Rosser property, call by name vs call by value, fixed point operator, defining recursive functions.

S Ch 13.6, 14.1-14.4

on reserve:
Glaser et.al, Principles of Functional Programming, Ch 3.1-3.3 (exerpts).

G. Michaelson, "An Introduction to Functional Programming Through Lambda Calculus", Addison-Wesley, 1989, Ch 4 on recursion;

Standard ML (SML) and Higher-order Programming languages

Strongly typed functional programming language, tuple, list, record, user defined type, constructors, destructors, functions, parametric types, refs, equality checks, functional programming with closures, continuations, streams, strictness, lazy evaluation.

S Ch 8, 9

Online SML:

• online repository of tutorials
• a gentle introduction to SML
• Bob Harper's Programming in SML notes
• a site with papers from the SML group including the useful M. Tofte, "Tips for Computer Scientists on SML"
  

On reserve:

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

Data Abstraction in CLU.

Mutability, Iterators, semantics of data abstraction: abstraction function and representation invariant, generics, specification.

on reserve:
B. Liskov and J. Guttag, Abstraction and Specification in Program Development, McGraw Hill, 1986, exerpts (book is now out of print).

OOPLs -- Inheritance

Models of inheritance (multiple/mixin/single), challenges of implementing dynamic binding, Implications for compilation.

S Ch 6, 7.1-7.3, 7.6

on reserve:

T. Budd, Understanding Object-oriented Programming with Java (updated edition), Addison-Wesley, 2000, exerpts.

Online Java:

• Tutorial on Java: SUN's tutorial
• Java development kit packages
  
• Page with info about Java IDEs and installing Java on your home computer.

Call graph construction algorithms -- Java

Type-based and flow-based compile-time estimation of the program call graph.

other sources:

D. Bacon and P. Sweeney, "Fast Static Analysis of C++ Virtual Functions Calls", in Proceedings of ACM SIGPLAN Conference on Object-oriented Programing Systems, Languages and Applications (OOPSLA'96), 324-341, October 1996 (see ACM Digital Library)

F. Tip and J. Palsberg, "Scalable Propagation-based Call Graph Construction Algorithms", in Proceedings of OOPSLA'00, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'00), pages 281-293, October 2000, (see ACM Digital Library).

A. Rountev, A. Milanova, B. G. Ryder, "Points-to Analysis for Java using Annotated Constraints", Proceedings of ACM SIGPLAN Conference on Object-oriented Programing Systems, Languages and Applications (OOPSLA'01), 43-55, October 2001, (see ACM Digital Library)

A. Milanova, A. Rountev, B. G. Ryder, "Parameterized Object Sensitivity for Points-to Analysis for Java" in ACM Transactions on Software Engineering Methodology, Volume 14, Number 1, pp 1-41, January 2005 (see ACM Digital Library).

Non-standard types for Java -- Confined Types

other sources:

Tian Zhao, Jens Palsberg and Jan Vitek, "Type-based Confinement", Journal of Functional Programming, (to appear) 2005.

Boris Bokowski and Jan Vitek, "Confined Types for Java", Software Practice and Experience, 31(6), 2001

Christian Grothoff, Jens Palsberg and Jan Vitek, "Encapsulating Objects with Confined Types", Proceedings of the 2001 ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA'01)

James Noble, John Potter and Jan Vitek, "Flexible Alias Protection", Proceedings of the European Conference on Object Oriented Programming (ECOOP'98), 1998.

Aspect-oriented Programming

What are aspects and how are they useful?

on reserve:

G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. Lopes, J-M Loingtier, J. Irwin, , "Aspect-oriented Programming", ECOOP 1997.

papers from the October 2001 special issue of Communications of the ACM on aspects (available in the ACM Digital Library)

G. Kiczles, E. Hilsdale, J. Hugunin, M. Kersten, J. Palm, W. Griswold, "An Overview of Aspect J", ECOOP 2001.

the Eclipse AspectJ project

G.C. Murphy, A. Lai, R.J. Walker, M.P. Robillard, "Separating Features in Source Code: An Exploratory Study", ICSE 2001 (see the ACM Digital Library).

Dynamic Analysis of OOPLs

Other sources

T. Ball and J. Larus, "Efficient path profiling", Proceedings of MICRO96, pp 46-57, December 1996.

B. Dufour, K. Driesen, L. Hendren, and C. Verbrugge. "Dynamic Metrics for Java". in OOPSLA'03. October 2003, (see ACM Digital Library).
get a source for JVMPI