Programming Language Theory

Takashi Hattori

October 20, 2017


1. Introduction
1.1. About this course
1.1.1. Evaluation
1.2. Questions
1.3. Definition of a language
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. History of programming languages
1.7. Reasons to study the theory of programming language
2. Syntax and Semantics
2.1. Brief introduction to the formal language theory
2.1.1. Definition of formal languages
2.1.2. BNF notation
2.1.3. Parse tree
2.1.4. Ambiguous grammar
2.2. Glance at the semantics theory
2.2.1. Operational semantics
2.2.2. Axiomatic semantics
2.2.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
3.5. Bindings of functions
4. Variables
4.1. What is a variable?
4.2. Type
4.3. Left value
4.4. Memory management
4.4.1. Static data area
4.4.2. Stack
4.4.3. Heap
4.5. Extent
5. Types
5.1. What is a type?
5.1.1. Why use types?
5.1.2. Type systems
5.2. Various types
5.2.1. Enumerated type
5.2.2. Subrange type
5.2.3. Union type
5.2.4. Pointer type
5.2.5. Function type
5.3. Type conversion
5.3.1. Implicit conversion
5.3.2. Explicit conversion
5.4. Type checking
5.4.1. Type declaration
5.4.2. Type compatibility
5.5. Type inference
5.6. Polymorphism
6. Mid-term paper
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. Esoteric languages
2. Various syntax for iteration
3. An example of tokens
4. Simple grammar
5. Simple arithmetic expression
6. Parse tree of A*(B+C)
7. An example of ambiguous grammar
8. Dangling else
9. Fortran has no reserved word
10. Namespace in C++
11. Importing a module in Python
12. TinyBASIC
13. Variable declaration in Java
14. Anonymous function in JavaScript
15. Anonymous function in Lisp
16. Alias statement in Ruby
17. EQUIVALENCE statement in Fortran
18. Static scoping in Pascal
19. Dynamic scoping in pseudo code
20. Closure in Ruby
21. Closure in JavaScript
22. Virtual functions in C++
23. Static local variables
24. Variables in a closure
25. Colors
26. Upper case letters
27. Range of an array
28. Circles and rectangles
29. Linked list in Pascal
30. Function type in Haskell
31. Arithmetic operation
32. String concatenation
33. Cast
34. Number constant in Haskell
35. Type compatibility in Ada
36. Type inference in ML
37. `+' operator in Java
38. Template in C++
39. Polymorphic function in Haskell
40. Precedences of arithmetic operators
41. Associativities of arithemtic operators
42. Precedence and associativity in APL
43. Evaluation order of arithmetic operations
44. Side effect and evaluation order
45. Logical operators
46. `range' in Python3.x
47. Loop in early Basic and Pascal
48. Catch and throw in Ruby
49. Exception handling in PL/I
50. Exception handling in Java
51. Parameters in Ada
52. Passing parameters in Ada
53. Passing parameters in Pascal
54. Side effect and pass-by-name
55. Fiber in Ruby
56. Floating point numbers
57. Stack package
58. New methods for integers in Ruby
59. Controlling Access in Smalltalk
60. Controlling Access in C++
61. Controlling Access in Java
62. Inheritance in Java
63. Type checking in Java
64. Competition
65. Dining philosophers problem
66. Producers-consumers problem (without mutual exclusion)
67. Producer-consumer problem (with mutual exclusion)
68. Producer-comsumer problem in Concurrent Pascal
69. Higher order function
70. Infinite list
71. Appending lists
72. Append two lists
73. Infinite loop