CSC302 2006S, Class 28: Declarative Programming
Admin:
* Post-mid-semester examination distributed.
* Sick family + spring cleaning + exam writing = no grading. Sorry.
* One of you argued that Saturday's Harris Party should count for EC.
* Talk tomorrow at 4:30. EC. Class at 11:00. EC.
* The reading for Wednesday will be announced this afternoon.
* Absent: Dimitar
Overview:
* Admin
* About the examination.
* About the project.
* Declarative
* What is a declarative language?
* Common forms of declarative languages.
* Why have declarative languages?
Language paradigms
* Imperative - Algorithms are sequences of instructions
* Functional - Algorithms are defined by definition, application, and composition of functions
* Object-Oriented - Algorithms are defined in terms of interacting objects
* Declarative - Algorithms are collections of facts and questions
* Declarative algorithms specify *what* we want to compute and a context, but as little as possible about *how* to compute it
What are some key declarative languages?
* Regular expressions - Specify *what* to match, but not how to match it.
^((a*b)*|(ababc))$
* Create an NFA
* Convert it to a DFA
* Turn the DFA into simple code.
* SQL and other relational database languages
SELECT name,id from PEOPLE where id < 100;
* Of course, real SQL programmers consider the efficiency of their code
* Predicate logic languages (Prolog)
* Make statements in predicate logic and ask questions
* if X is a man then X is human
* if X is a human then X will die
* Sam is a man
* will Sam die?
* X is the sorted version of Y if X is a permutation of Y and X is sorted
* What is the sorted version of [34,1,2,6,2]?
* Pure functional programming (Haskell; Equations)
* It shouldn't matter which order the functions are evaluated in
* Church-Rosser Thm: If there is a way to compute a solution, then outermost/lazy evaluation will compute it
Why have these things?
* Rely on language designer to do the work for you
* For certain types of algorithms, more "efficient"