- Automaton. The plural of "automaton" is "automata."
- Language. (You may have thought you knew this one!)
- Grammar. (You probably thought you knew this one, too!)
- Turing Machine.
- Universal Turing Machine. A machine that can do anything that any machine in this or any other universe could possibly do. But, rather slowly!
- NP-complete. Almost everyone in computer science has heard this term, but few can give a precise definition.
- There are problems that are undecidable. There are propositions that are true but for which there is no proof. I don't mean no one has found a proof yet, I mean that no proof can exist at all! There are problems, such as the halting problem, which cannot be solved by any algorithm. No future genius with a finite intellect will ever find one, not in this (or any other) universe, ever, and I will prove that to you.
- Computable Functions. There are functions which cannot be computed by any machine that could ever be built.
- P = NP? The most famous open question in all of computer science. What does this mean? What does it mean in practical terms?
Detailed description of the CYK algorithm.Homework and tests from prior semesters are available.
bendy at purdue.edu
Office Hours: Tuesday 3:30-5:00, LWSN 2116M
gopals at purdue.edu
Office Hours: Monday+Wednesday 4:00-5:00, HAAS 264
This is a course on the principles of programming languages and their application. The emphasis is on ideas and techniques relevant to practitioners, but includes theoretical foundations crucial for deeper understanding: abstract syntax, formal semantics, type systems, and modularity. Work in the course involves exploring programming languages and features both as a user (by writing programs in those languages), as a language designer (by implementing interpreters for those languages), and as a scholar (by proving mathematical properties of them). We will investigate approaches to modularity such as data abstraction, inheritance, and polymorphism independent of their realization in any particular language. The course will also offer a historical perspective on the evolution of programming languages and why some designs thrive while others fail. Upon successfully completing this course, students will be able to:
- Write efficient and correct programs in a functional programming language, Haskell.
- Precisely formulate the syntax and runtime behavior of a programming language.
- Specify different notions of type safety for a programming language and reason about a programming language's semantics via mathematical induction.
- Distinguish between different approaches to modularity and abstraction provided by programming languages.
The course is structured into five sections, the first four of which roughly align with these topics. The final section will consider the realization of some of these ideas in Rust, a modern systems programming language.