Programming Paradigms: Lecture Notes

• Exercise tutor
  • Room: EDIT 6120A
  • E-mail: enache (chalmers.se)

• Exercise tutor
• Contact:
  • Room: EDIT 5…
  • E-mail: frolov (chalmers.se)

• Exercise tutor
• E-mail: rarash (student.chalmers.se)

• Course responsible & lecturer
• Contact:
  • Room: EDIT 6126
  • E-mail: bernardy (chalmers.se)
• CV:
  • 1996-2000: Master in CS (Free University of Brussels)
  • 2000-2007: Software engineer (Various places)
  • 2007-2011: PhD (Chalmers)

• Pass the exam
• That's it!

• Do the exercises
• Participate in the exercises correction sessions: see below for details.
• Attend the lectures
• Prepare lectures by reading lecture notes (this document) and follow relevant links.
• IMPORTANT. Subscribe to the course here https://docs.google.com/spreadsheet/viewform?hl=en_GB&formkey=dDBUT1FtVWgyelBXdFZCQkRUNzFWOHc6MQ#gid=0 (we can't get an accurate list from the administration) This is so you get assigned to groups, get exercise sheets, important announcements, etc.

• The lecture notes (this document) can be accessed at the URL http://www.cse.chalmers.se/~bernardy/pp/Lectures.html
• You can also use the source if you fancy emacs org-mode.
• Please interrupt me during lectures!

• Prepare exercises.
  • This means that you must have a written copy of your solution with you.
  • To be able to follow the discussion, you should also bring a printout of the questions.
  • See the schedule for which exercises you need to prepare for each session.
• Go to session
• Subscribe
  • Write down which exercises you are confident enough to present to the class.
• Bonus points (about 10% of the exam) awarded according to the number of exercises above; to redeem on the FIRST written exam (ie. not in re-exams; in particular you lose them if you don't take the exam).
• No cheating
  • Make sure you understand all your submissions. The best way to make sure you understand is to do the exercise yourself. Don't copy somebody else solution and hope for the best.
  • Submit only serious attempts. Make sure your solution passes basic sanity checks. Example: if you submit a program, test it on at least of few inputs. (If you write pseudo-code, do the compiler/interpreter job by hand.)
  • A good idea if you decide to work with a friend: attempt both each exercise; cross-check each other's result afterwards.
  • Punishment: all your bonus points erased (including those earned in previous sessions).

See: https://student.portal.chalmers.se/en/studies/pages/courseevaluation.aspx And: https://document.chalmers.se/workspaces/chalmers/hogskolegemensamma5051/internt/kursutvarderingar/vad-ar-detta2740

• See Designated representatives in Schedule

• Unfortunately, I do not know of a single textbook covering all the material in a suitable way. Therefore, this document is the "master" source for the course. Still…
• Do follow the links scattered across this document
• Single most relevant textbook: probably
  • "Programming Languages – Application and Interpretation", Shriram Krishnamurthi.

  http://www.plai.org/

  • but
    • uses different structure
    • uses scheme (LISP) syntax
    • is written with MS and PhD students in mind
  • Relevant parts
    • Part I (To understand the point of view of the author)
    • Shreds of part II
    • Parts III, IV, VI, VII
    • Part X (Ch. 24, 25)
    • Part XI
• Note that the exercises (file:All.pdf) are also part of the course material.
• Other relevant books
  
  • "Essentials of Programming Languages", Friedman, Wand and Haynes (http://www.eopl3.com/)
  • "Concepts, Techniques, and Models of Computer Programming", Van Roy (http://www.info.ucl.ac.be/~pvr/book.html)
  • …

Paradigm: "A philosophical and theoretical framework of a scientific school or discipline within which theories, laws, and generalizations and the experiments performed in support of them are formulated; broadly: a philosophical or theoretical framework of any kind"

http://www.merriam-webster.com/dictionary/paradigm

see also: http://en.wikipedia.org/wiki/Programming_paradigm

            Programming paradigm 
                       = 
The basic structuration of thought underlying the programming activity

eg. when you think of a programming problem, what are you thinking of?

• the sequence of actions to perform (first download the file, then display it)
• how to divide the problem-space into sub-tasks (to compute the spanning tree, i can divide the graph arbitrarily in two, and then …)
• what are the agents involved (sensors, a simulator, a renderer, …)
• what data do we need to handle? do we need intermediate representations? what are the relations between the different forms?

Note that the same way of thinking is not adapted to all problems.

How do you think of your computer?

• Memory + instructions (von Neumann model)
• Rewriting engine
• (evaluator of) Mathematical functions
• …

• (Do not reveal:) Discussion: What languages do you know?
  

  Regexp / Excell formulas / sql queries / Haskell / C / Asm / …

  ⟶ clouds / recognise paradigms / discussions

  • Paradigms build on top of features
  • Languages implement features

  http://www.info.ucl.ac.be/~pvr/paradigmsDIAGRAMeng108.pdf

• PL Features
  
  • Structured data / Records
  • Naming and abstraction (2nd order, etc).
  • Memory (cell) / State
  • Processes
  • Communication channels
  • Recursion
  • Search

Eventually, all programming may revolve around a number of patterns; the old ways are abandonned. This is the paradigm shift: a new way of thinking appears. Eventually, a new programming language may be developed to support the "patterns" directly.

digraph G {
   "Programming habits" -> "(Design) patterns" -> "New Paradigm"
}

file:shift.svg

• Ability to think "big thoughts"
  
  • Anecdote: MULTICS
  • "Language as thought shaper", from http://soft.vub.ac.be/~tvcutsem/whypls.html

    To quote Alan Perlis: "a language that doesn't affect the way you think about programming, is not worth knowing."

    The goal of a thought shaper language is to change the way a programmer thinks about structuring his or her program. The basic building blocks provided by a programming language, as well as the ways in which they can (or cannot) be combined, will tend to lead programmers down a "path of least resistance", for some unit of resistance. For example, an imperative programming style is definitely the path of least resistance in C. It's possible to write functional C programs, but as C does not make it the path of least resistance, most C programs will not be functional.

    Functional programming languages, by the way, are a good example of thought shaper languages. By taking away assignment from the programmer's basic toolbox, the language really forces programmers coming from an imperative language to change their coding habits. I'm not just thinking of purely functional languages like Haskell. Languages like ML and Clojure make functional programming the path of least resistance, yet they don't entirely abolish side-effects. Instead, by merely de-emphasizing them, a program written in these languages can be characterized as a sea of immutability with islands of mutability, as opposed to a sea of mutability with islands of immutability. This subtle shift often makes it vastly easier to reason about the program.

    Erlang's concurrency model based on isolated processes communicating by messages is another example of a language design that leads to radically different program structure, when compared to mainstream multithreading models. Dijkstra's "GOTO considered harmful" and Hoare's Communicating Sequential Processes are pioneering examples of the use of language design to reshape our thoughts on programming. In a more recent effort, Fortress wants to steer us towards writing parallel(izable) programs by default.

    Expanding the analogy with natural languages, languages as thought shapers are not about changing the vocabulary or the grammar, but primarily about changing the concepts that we talk about. Erlang inherits most of its syntax from Prolog, but Erlang's concepts (processes, messages) are vastly different from Prolog's (unification, facts and rules, backtracking). As a programing language researcher, I really am convinced that language shapes thought.

  • When a paradigm is well supported, you can "think big" and have the compiler check that you're on the right track.
• Altenative paradigms in the industry:
  
  • "Excell is the most used programming language"
  • SQL is mostly functional (relational)
  • F# officially supported by MicroSoft
  • Exponential growth of Erlang / Haskell

Can I teach you 5 differrent ways of thinking in 7 weeks? Each of these would require major rewiring of your brain. Difficult! But fear not… Other courses are available:

• Functional ("introduction to functional programming" TDA555)
• Imperative ("machine-oriented programming" EDA480)
• Concurrent ("concurrent programming" TDA381)
• Object oriented ("Object oriented programming" DAT042)
• Logic (?) – partly covered in Formal Methods

• Awareness of multiple paradigms
  First questions of the design phase: "How should I think about this problem? (Do I know a paradigm suitable to express the solution?)"
• Recognise "encoded" thoughts:
  
  • what is the natural paradigm
  • decode them

  From this point of view, this course teaches "design patterns", in reverse.

• Encode thoughts expressed in a paradigm in another one
  
• The exam questions will be similar to exercises
  Note in particular that exercises are integral part of the course material.