PoPL 2006
Programming Languages = Fun::Conceptual Structures-->Insights
and Fun() uses Labs::Insights-->Conceptual Structures!
Midsem exam: Tuesday 12 sept,
2:30-4:30 A1/A2.
Endsem exam: Wed 22 nov. 2:30-4:30
A1/A2.
Coverage
Types:
-- types as sets
-- primitive types
-- sets of primitive elements
-- composite types
-- product types
-- power types
-- mappings types
-- recursive types (lists)
-- subtyping
-- for primitive types (set/subset)
-- for record types
-- width rule
-- depth rule
-- permutation rule
-- for function types --} the notion of covariance and
-- for object types --} contravariance
-- the notion of top and
bottom types
-- polymorphism
-- adhoc/syntactic
-- universal polymorphism
-- interpretations of + operator through adhoc polymorphism
-- why is segmentation fault
a typing error
Core ideas from Object Oriented Programming Languages
-- shared vs. embedded
method implementation
-- significance of the
this/self reference
-- why is it needed?
-- inheritance
-- single and multiple
-- method search
-- difference between the type of a variable
and object which is refers to
-- polymorphism: dynamic binding of a method name to an
implementation
-- dispatch table implementation
-- super references and binding rules
-- diamond inheritance
problem
-- multiple copies of variables
-- ambiguous function implementations
-- class-less languages
-- method slots
-- parent pointer and delegation
-- creation by definition and creation by cloning
-- class Object
-- metaclasses
-- significance of the idea of metaclasses
-- instance-of relation
-- classes as objects
-- class Class
-- brief look at meta-class hierarchy in smalltalk
-- what are static members
in C++/Java
Storage Bindings and Scoping rules
variables and location
bindings
type binding and storage
binding
pointer types and some
tricky examples from C.
assignment statement
lvalues and rvalues
table of bindings as
implementation of 'environment'(i.e. set of
all bindings)
implementing scoping rules
to identify which binding to be used
static scoping
dynamic scoping
dynamic scoping
Parameter Passing
call by value
call by constant value
call by result
call by value result
call by reference
call by name
lazy and eager evaluation of parameters
Activation records
Imperative style control constructs
early ideas in structured
programming
primitive structured
programming constructs
their structured
representations in terms of flow charts
goto -- is harmful
alternatives to goto --
java's way
-- break
-- labeled break
-- continue
-- labeled continue
object oriented control constructs
conditional
conditional
repeat
n timesRepeat
implementations through Block, Boolean and Integer classes
Escape procedures and Continuations
Concurrency and Nondeterminism
guarded commands
guarded regions
implementing synchronization through
guarded commands and
guarded regions:
semaphores and monitors
concurrency and synchronization:
threads and monitors
Lambda calculus
lambda abstractions, application
syntactic conventions
beta reduction
applicative style: computation as
reduction of application
free and bound variables
alpha renaming
eta reduction
closed terms or combinators
higher order functions
functions with multiple
parameters and currying
Church Booleans
logical operators
conditional statement
Pairs
Church numerals
successor
addition, multiplication, subtraction
Evaluation order:
normal order reduction
call by name reduction
call by value
reduction
full beta reduction
Recursion
fix point
operator
y combinator
Logic Programming
declarative style
introduction to prolog
computing with objects and relations:
facts, rules and goal queries
horn clauses
backtracking
infinite recursion problems in prolog
some uses of cuts
+ problem solving sessions: problems from last
year's question sets
Reading material:
- David Watt, Programming Language
Concepts and
Paradigms
- Benjamin Pierce: Types and Programming Languages (published by PHI: Indian edition available)
- Fischer & Grodzinsky, The Anatomy of Programming
Languages
- Kenneth Louden,
Programming Languages: Principles & Practice
- a couple of chapters from Goldberg's book on Smalltalk
- Clocksin and Mellish: Programming in Prolog, Springer.
- Selected Articles as mentioned in class