Wrap Up

"The removal of much of the accidental complexity of programming means that the intrinsic complexity of the application is what's left."
- Security Engineering, Ross J. Anderson (2001)

"If you want people to do something the right way, you must make the right way the easy way."
- Traditional saying

Other paradigms

• This section describes two additional computation models (which are related to each other).
• We did not cover all the computation models, and new models will be created in the future.

Relational programming

• A procedure in declarative model uses its input arguments to calculate the values of its output arguments.
  • For a given set of input argument values, there is only one set of output argument values.
• A relational procedure is more flexible in two ways:
  • there can be any number of results to a call - either zero (no results), one, or more
  • which arguments are inputs and which are outputs can be different for each call
• Relational programming is well-suited for databases, parsers, and for enumerating solutions to complex combinatoric problems.
• Relational programming extends declarative programming with a new kind of statement called "choice".
  • The choice is implemented with search, which enumerates the possible answers.
• Relational programming is practical:
  • when the search space is small
  • as an exploratory tool
• To use search in other cases (when brute force exploration is not possible in real space/time), more sophisticated techniques are needed (e.g., constraint-solving algorithms, optimizations based on the problem structure, and search heuristics).

Constraint programming

• Constraint programming consists of a set of techniques for solving constraint satisfaction problems.
  • A constraint satisfaction problem (CSP) consists of a set of constraints on a set of variables.
    • "X is less than Y" or "X is a multiple of 3"
• Constraint programming is close to the ideal of declarative programming: to say what we want without saying how to achive it.
• Propagate-and-search (a general approach for tackling CSPs) is based on three important ideas:
  • Keep partial information -> During the calculation, we might have partial information about a solution (e.g., "in any solution, X is grater than 100").
  • Use local deduction -> Each of the constraints uses the partial information to deduce more information. For example, combining the constraint "X < Y" and the partial information "X > 100", we can deduce that "Y > 101" (assuming Y and X are integers).
  • Do controlled search -> When no more local deductions can be done, then we have to search. The idea is to search as little as possible: we will do just a small search step and then try to do local deduction again.
• Constraint programming is a type of logic programming.

Conclusion

• There exist many computation models that differ in how expressive they are and how hard it is to reason about programs written in them.
  • The declarative model is one of the simplest, however, it has serious limitations for some applications.
  • There are more expressive models that overcome these limitations, at the price of sometimes making reasoning more complicated.
  • Rule of least expressiveness: When programming a component, the right computation model for the component is the least expressive model that results in a natural program.

Computation models

• Declarative sequential model -> This model encompasses strict functional programming and deterministic logic programming. It extends the former with partial values (dataflow variables) and the latter with higher-order procedures.
• Declarative concurrent model -> This is the declarative model extended with explicit threads and by-need computation (lazy evaluation). It includes lazy functional programming and deterministic concurrent logic programming.
• Message-passing concurrent model -> This is the declarative model extended with communication channels (ports). This removes the limitation of the declarative concurrent model that it cannot implement programs with some nondeterminism.
• Stateful model -> This is the declarative model extended with explicit state (mutable variables). This model can express sequential object-oriented programming. In this model components have history.
• Shared-state concurrent model -> This is the declarative model extended with both explicit state and threads. This model contains concurrent object-oriented programming. Reasoning with this model is the most complex since there can be multiple histories interacting in unpredictable ways.
• Relational model -> This is the declarative model extended with search. It encompasses nondeterministic logic programming. This model is a precursor to constraint programming.

---

< ^