Programming Language Theory

Takashi Hattori

January 15, 2016


1. Introduction
1.1. Some questions
1.2. Software development process
1.3. Relation between application fields and languages
1.4. Differences among languages
1.4.1. Character
1.4.2. Grammar
1.4.3. Paradigm
1.5. Definition of "good" programming language
1.6. Reasons to study the theory of programming language
1.7. History of programming languages
2. Syntax and Semantics
2.1. Definition of a language
2.2. Brief introduction to the formal language theory
2.2.1. Definition of formal languages
2.2.2. BNF notation
2.2.3. Parse tree
2.2.4. Ambiguous grammar
2.3. Glance at the semantics theory
2.3.1. Operational semantics
2.3.2. Axiomatic semantics
2.3.3. Denotational semantics
3. Names and Bindings
3.1. Names in a program
3.2. Namespace
3.3. Bindings
3.3.1. Definition of bindings
3.3.2. Anonymous and alias
3.4. Scope
3.4.1. Static scoping
3.4.2. Dynamic scoping
3.4.3. Closure
4. Variables
4.1. What is a Variable?
4.2. Type
4.3. Memory
4.3.1. Static data area
4.3.2. Stack
4.3.3. Heap
4.4. Extent
5. Mid-term paper
6. Types
6.1. What is a type?
6.2. Various types
6.2.1. Enumerated type
6.2.2. Subrange type
6.2.3. Union type
6.2.4. Pointer type
6.2.5. Function type
6.3. Type conversion
6.3.1. Implicit conversion
6.3.2. Explicit conversion
6.4. Type checking
6.4.1. Type declaration
6.4.2. Type compatibility
6.5. Type inference
6.6. Polymorphism
7. Expressions
7.1. Precedence and associativity of operators
7.2. Order of evaluation
7.3. Short-circuit evaluation
7.4. Lazy evaluation
8. Control structures
8.1. Structured programming
8.2. Non-local exits
8.3. Exceptions
8.3.1. What is exception?
8.3.2. Exception handling
9. Subprograms
9.1. What is a subprogram?
9.2. Parameters
9.3. Passing parameters
9.3.1. Direction of passing
9.3.2. Evaluation strategy of parameters
9.4. Coroutine
10. Object Oriented Programming
10.1. Abstraction and Modularization
10.2. Abstract data type
10.3. Package in Ada
10.4. Object oriented languages
10.5. Designing object oriented languages
10.5.1. How pure the language is object oriented?
10.5.2. Class-based or prototype-based?
10.5.3. What kind of information hiding is possible?
10.5.4. Single inheritance or multiple inheritance?
10.5.5. How types are checked?
11. Concurrent Programming
11.1. Concurrent and parallel
11.2. Synchronization
11.3. Deadlock and starvation
11.4. Semaphore
11.5. Monitor
11.6. Channel
11.6.1. Occam
11.6.2. Go
12. Functional Programming
12.1. Referential transparency
12.2. Lisp
12.3. Haskell
12.3.1. Static type checking and type inference
12.3.2. Lazy evaluation
12.3.3. Monad
13. Logic Programming
13.1. Features of logic programming
13.2. Prolog
13.2.1. Definition of programs
13.2.2. Query
13.2.3. Program execution
13.3. Problems of Prolog
13.3.1. Order of resolution
13.3.2. Negation

List of Examples

1. Just joking
2. Various syntax for iteration
3. An example of tokens
4. Simple arithmetic expression
5. Parse tree of A*(B+C)
6. An example of ambiguous grammar
7. Dangling else
8. Fortran has no reserved word
9. Namespace in C++
10. TinyBASIC
11. Variable declaration in Java
12. Anonymous function in Lisp
13. Anonymous funciton in Ruby
14. EQUIVALENCE statement in Fortran
15. Static scoping in Pascal
16. Dynamic scoping in pseudo code
17. Closure in Ruby
18. Closure in JavaScript
19. Static local variables
20. Variables in a closure
21. Colors
22. Upper case letters
23. Range of an array
24. Circles and rectangles
25. Linked list in Pascal
26. Function type in Haskell
27. Arithmetic operation
28. String concatenation
29. Cast
30. Type compatibility in Ada
31. Type inference in ML
32. `+' operator in Java
33. Template in C++
34. Polymorphic function in Haskell
35. Precedences of arithmetic operators
36. Associativities of arithemtic operators
37. Precedence and associativity in APL
38. Evaluation order of arithmetic operations
39. Side effect and evaluation order
40. Logical operators
41. `range' in Python3.x
42. Loop in early Basic and Pascal
43. Catch and throw in Ruby
44. Exception handling in PL/I
45. Exception handling in Java
46. Parameters in Ada
47. Passing parameters in Ada
48. Passing parameters in Pascal
49. Side effect and pass-by-name
50. Fiber in Ruby
51. Floating point numbers
52. Stack package
53. New methods for integers in Ruby
54. Controlling Access in Smalltalk
55. Controlling Access in C++
56. Controlling Access in Java
57. Inheritance in Java
58. Type checking in Java
59. Competition
60. Dining philosophers problem
61. Producers-consumers problem (without mutual exclusion)
62. Producer-consumer problem (with mutual exclusion)
63. Producer-comsumer problem in Concurrent Pascal
64. Higher order function
65. Infinite list
66. Appending lists
67. Append two lists
68. Infinite loop