8 Programming Paradigms
  CS 381 • Programming Paradigms                                               1
                 Why Study Different Paradigms?
                             Higher-level         int a[10];                     C                  Learn about different, more 
                                                  int s = 0;
        int a[10];            description         int i;                                               powerful programming 
        int s = 0;         of computation         for (i = 0; i < 10; i++) {                                 abstractions 
        s += a[0];                                  s += a[i];
        s += a[1];                                }
        s += a[2];                                                                    ➙Encapsulation of 
        s += a[3];                                                                   recursion schemes & 
        s += a[4];                                 sum []     = 0                      control structures        s = fold (+) 0 a
        s += a[5];                                 sum (x:xs) = x + sum xs
        s += a[6];
        s += a[7];                                 s = sum a                                  ➙Partial function application
        s += a[8];                                                     Haskell                ➙Infinite data structures
        s += a[9];
                                                                                                                     (not quite correct!)
                    ➙Use of abstraction           sum([],0).                                                        sum(A,9).
                       ➙Scalable                  sum([X|XS],S) :- sum(XS,N), S is X+N.
                       ➙Reusable                  sum(A,S).                                           ➙Inverse computation
                       ➙Less error prone                                                 Prolog
   CS 381 • Programming Paradigms                                                                                                          2
                                                           Granularity of Classification
                                                                                                                                                                record                                                                                                                                                                     Explanations
                                                                                                                                                              Descriptive       The principal programming paradigms See "Concepts, Techniques, and Models of Computer Programming".
                                                                                                                                                              declarative
                                                                                                                                                             programming                                                                                                                                          The chart classifies programming paradigms according to their kernel
                                                                                                                                                                     XML,                        "More is not better (or worse) than less, just different."                                                       languages (the small core language in which all the paradigm’s
                                                                                                                  Data structures only                               S−expression                                                                                                                                 abstractions can be defined).  Kernel languages are ordered according to
                                                                                                                                                                                                                                                                                                                  the creative extension principle: a new concept is added when it cannot be
                                                                                                                   Turing equivalent                                 + procedure                                                                                             v1.08 © 2008 by Peter Van Roy        encoded with only local transformations.  Two languages that implement
                                                                                                                                                                                                                                                                                                                  the same paradigm can nevertheless have very different "flavors" for the
                                                                                                                                                              First−order                                                                                         + cell (state)                                  programmer, because they make different choices about what
                                                                                                                     Observable                                functional                                                                                                             Imperative
                                                                                                                  nondeterminism? Yes No                     programming                                                                                                            programming                   programming techniques and styles to facilitate.
                                                                                                                                                                                                                                                                                             Pascal, C            When a language is mentioned under a paradigm, it means that part of
                                                                                                                                                                     + closure                                                                                         Imperative                                 the language is intended (by its designers) to support the paradigm
                                                                                                                                                               Functional                                                                                                search      + search                     without interference from other paradigms.  It does not mean that there
                                                                                                                                                             programming                                                                                              programming                                 is a perfect fit between the language and the paradigm.  It is not enough
                                                                                                                              + unification                           Scheme, ML                           + name                                              SNOBOL, Icon, Prolog                               that libraries have been written in the language to support the paradigm.
                                                                                                                                (equality)                                                                   (unforgeable constant)                                                                               The language’s kernel language should support the paradigm.  When
                                                                                                                       Deterministic                                            + continuation                                                                                   + cell                           there is a family of related languages, usually only one member of the 
                                                                                                                    logic programming                                    Continuation                   ADT          + cell        ADT                           + port         (state)      + closure            family is mentioned to avoid clutter.  The absence of a language does
                                                                                                                                                                                                     functional                 imperative                         (channel)                                      not imply any kind of value judgment.
                                                                                                                                                                         programming                programming                programming                                            Sequential
                                                                                                                              + search                                  Scheme, ML               Haskell, ML, E            CLU, OCaml, Oz                 Event−loop               object−oriented                State is the ability to remember information, or more precisely, to store a
                                                                                                                    Relational & logic     + by−need                            + thread                                                                 programming                programming                   sequence of values in time.  Its expressive power is strongly influenced by
                                                                                                                       programming          synchron.                           + single assign.           + nondeterministic         + port                     E in one vat          Stateful                   the paradigm that contains it.  We distinguish four levels of expressiveness,
                                                                                                                              Prolog, SQL             Lazy                Monotonic                          choice                     (channel)                + thread             functional                  which differ in whether the state is unnamed or named, deterministic or
                                                                                                                              embeddings           functional              dataflow                Nonmonotonic                Multi−agent                                          programming                   nondeterministic, and sequential or concurrent.  The least expressive is
                                                                                                                              + solver            programming            programming                  dataflow                   dataflow                 Multi−agent                       Java, OCaml           functional programming (threaded state, e.g., DCGs and monads:
                                                                                                                                                                                                                                                         programming                                              unnamed, deterministic, and sequential).  Adding concurrency gives
                                                                                                                     Constraint (logic)                  Haskell          Declarative               programming                programming                                                  + thread
                                                                                                                       programming                                        concurrent              Concurrent logic          Oz, Alice, AKL              Message−passing                                           declarative concurrent programming (e.g., synchrocells: unnamed,
                                                                                                                                                                                                                                                           concurrent                Concurrent                   deterministic, and concurrent).  Adding nondeterministic choice gives
                                                                                                                              CLP, ILOG Solver                           programming                programming                                          programming               object−oriented                concurrent logic programming (which uses stream mergers: unnamed,
                                                                                                                              + thread                                          Pipes, MapReduce           Oz, Alice, Curry, Excel,                              Erlang, AKL        programming                   nondeterministic, and concurrent).  Adding ports or cells, respectively,
                                                                                                                                                       + thread      + by−need                             AKL, FGHC, FCP                                                            Shared−state                 gives message passing or shared state (both are named, nondeterministic,
                                                                                                                        Concurrent         + single assignment         synchronization                                                                           + local cell                                     and concurrent).  Nondeterminism is important for real−world interaction
                                                                                                                        constraint                                                                         + synch. on partial termination                                            concurrent
                                                                                                                                                                 Lazy                                                                                     Active object             programming                   (e.g., client/server).  Named state is important for modularity.
                                                                                                                       programming                                                               Functional reactive
                                                                                                                              LIFE, AKL                         dataflow                        programming (FRP)                                        programming                        Smalltalk, Oz,        Axes orthogonal to this chart are typing, aspects, and domain−specificity. 
                                                                                                                                                             programming                                                                               Object−capability                    Java, Alice
                                                                                                                              + by−need synchronization                                          Weak synchronous                                                                                                 Typing is not completely orthogonal: it has some effect on expressiveness. 
                                                                                                                                                                 Lazy                               programming                                          programming                        + log                 Aspects should be completely orthogonal, since they are part of a
                                                                                                                     Lazy concurrent                          declarative                                  FrTime, SL                                   CSP, Occam,                    Software                   program’s specification.  A domain−specific language should be definable
                                                                                                                        constraint                             concurrent                                                                                E, Oz, Alice,               transactional                in any paradigm (except when the domain needs a particular concept). 
                                                                                                                       programming                           programming                                   + instantaneous computation               publish/subscribe,            memory (STM)
                                                                                                                   Oz, Alice, Curry                       Oz, Alice, Curry                       Strong synchronous                                  tuple space (Linda)         SQL embeddings                   Metaprogramming is another way to increase the expressiveness of a
                                                                                                                                                                                                    programming                                                                                                   language.  The term covers many different approaches, from higher−order 
                                                                                                                        Logic and                                                              Esterel, Lustre, Signal         Dataflow and                                                                       programming, syntactic extensibility (e.g., macros), to higher−order 
                                                                                                                        constraints                           Functional                                                     message passing            Message passing              Shared state                 programming combined with syntactic support (e.g., meta−object 
                                                                                                                                                                                                                                                                                                                  protocols and generics), to full−fledged tinkering with the kernel language 
                                                                                                                                                                                                  Nondet. state                                                                                                   (introspection and reflection).  Syntactic extensibility and kernel language
                                                                                                                                       Unnamed state (seq. or conc.)                                                                                    Named state                                               tinkering in particular are orthogonal to this chart.  Some languages, such
                                                                                                              More declarative                                                                                                                                                        Less declarative            as Scheme, are flexible enough to implement many paradigms in almost
       CS 381 • Programming Paradigms                                                                                                                                                                                                                                                                             native fashion.  This flexibility is not shown in the chart. 
                                                                                                                                                                                                                                                                                                                                                 3
                8 Programming Paradigms
                        What is a Programming Paradigm?
                        Imperative Programming
                        Functional Programming
                        Logic Programming
                        Object-Oriented Programming
  CS 381 • Programming Paradigms                                               4