Functional Programming Principles In Scala - EPFL
Functional Programming Principles in Scala Martin Odersky September 12, 2012
Programming Paradigms Paradigm: In science, a paradigm describes distinct concepts or thought patterns in some scientific discipline. Main programming paradigms: imperative programming functional programming logic programming Orthogonal to it: object-oriented programming
Review: Imperative programming Imperative programming is about modifying mutable variables, using assignments and control structures such as if-then-else, loops, break, continue, return. The most common informal way to understand imperative programs is as instruction sequences for a Von Neumann computer.
Imperative Programs and Computers There’s a strong correspondence between Mutable variables Variable dereferences Variable assignments Control structures memory cells load instructions store instructions jumps Problem: Scaling up. How can we avoid conceptualizing programs word by word? Reference: John Backus, Can Programming Be Liberated from the von. Neumann Style?, Turing Award Lecture 1978.
Scaling Up In the end, pure imperative programming is limited by the “Von Neumann” bottleneck: One tends to conceptualize data structures word-by-word. We need other techniques for defining high-level abstractions such as collections, polynomials, geometric shapes, strings, documents. Ideally: Develop theories of collections, shapes, strings,
What is a Theory? A theory consists of one or more data types operations on these types laws that describe the relationships between values and operations Normally, a theory does not describe mutations!
Theories without Mutation For instance the theory of polynomials defines the sum of two polynomials by laws such as: (a*x b) (c*x d) (x c)*x (b d) But it does not define an operator to change a coefficient while keeping the polynomial the same!
Theories without Mutation For instance the theory of polynomials defines the sum of two polynomials by laws such as: (a*x b) (c*x d) (x c)*x (b d) But it does not define an operator to change a coefficient while keeping the polynomial the same! Other example: The theory of strings defines a concatenation operator which is associative: (a b) c a (b c) But it does not define an operator to change a sequence element while keeping the sequence the same!
Consequences for Programming Let’s concentrate on defining theories for operators, minimize state changes, treat operators as functions, often composed of simpler functions.
Functional Programming In a restricted sense, functional programming (FP) means programming without mutable variables, assignments, loops, and other imperative control structures. In a wider sense, functional programming means focusing on the functions. In particular, functions can be values that are produced, consumed, and composed. All this becomes easier in a functional language.
Functional Programming Languages In a restricted sense, a functional programming language is one which does not have mutable variables, assignments, or imperative control structures. In a wider sense, a functional programming language enables the construction of elegant programs that focus on functions. In particular, functions in a FP language are first-class citizens. This means they can be defined anywhere, including inside other functions like any other value, they can be passed as parameters to functions and returned as results as for other values, there exists a set operators to compose functions
Some functional programming languages In the restricted sense: Pure Lisp, XSLT, XPath, XQuery, FP Haskell (without I/O Monad or UnsafePerformIO) In the wider sense: Lisp, Scheme, Racket, Clojure SML, Ocaml, F# Haskell (full language) Scala Smalltalk, Ruby (!)
History of FP languages 1959 1975-77 1978 1986 1990 1999 2000 2003 2005 2007 Lisp ML, FP, Scheme Smalltalk Standard ML Haskell, Erlang XSLT OCaml Scala, XQuery F# Clojure
Recommended Book (1) Structure and Interpretation of Computer Programs. Harold Abelson and Gerald J. Sussman. 2nd edition. MIT Press 1996. A classic. Many parts of the course and quizzes are based on it, but we change the language from Scheme to Scala. The full text can be downloaded here.
Recommended Book (2) Programming in Scala. Martin Odersky, Lex Spoon, and Bill Venners. 2nd edition. Artima 2010. A comprehensive step-by-step guide Programming in Scala Second Edition Updated for Scala 2.8 artima Martin Odersky Lex Spoon Bill Venners The standard language introduction and reference.
Recommended Book (3) Scala for the Impatient A faster paced introduction to Scala for people with a Java background. The first part of the book is available for free downlaod
Why Functional Programming? Functional Programming is becoming increasingly popular because it offers an attractive method for exploiting parallelism for multicore and cloud computing. To find out more, see the video of my 2011 Oscon Java keynote Working Hard to Keep it Simple (16.30 minutes). The slides for the video are available separately.
Functional Programming In a restricted sense, functional programming (FP) means programming without mutable variables, assignments, loops, and other imperative control structures. In a wider sense, functional programming means focusing on the functions. In particular, functions can be values that are produced, consumed, and composed.
Getting Started in Scala scala Runs compiled scala code Or without arguments, as an interpreter! scalac - compiles fsc - compiles faster! (uses a background server to minimize startup time) Go to scala-lang.org for downloads/documentation Read Scala: A Scalable Language
Written in Scala Extensive use of Functional Programming 19 114383 6025 50557 128826 Lines 293K Total Scala Scala (Unit tests) TDML Tests C. . Functional Programming Idiom for Compilers Johnsson, Thomas. (1995). Attribute Grammars as a Functional Programming Paradigm. LNCS. 274. 10.1007/3-540-18317-5_10.
Java Scala OO features Enough Scala functional features to use use the Scala API in Apache Spark Full-blown functional programming: Lambda calculus, category theory, closures, monads, functors, actors, promises, futures, combinators, functional design patterns, full type system, library construction techniques, reactive
Functional Programming Scala Reduced defects rate Easier maintenance (tests, refactoring) Local reasoning Mathematical rigor We're hiring great people We're still learning It's fun! Functional Programming Scala. Payment-processing Destination Queue - Transaction is
What Is Functional Programming? 165 Functions in Mathematics 166 Variables that Aren't 166 Functional Programming in Scala 167 Function Literals and Closures 169 Purity Inside Versus Outside 169 Recursion 170 Tail Calls and Tail-Call Optimization 171 Trampoline for Tail Calls 172 Functional Data Structures 172 Lists in Functional Programming 173
of functional programming (FP)—we use Scala as the vehicle, but the lessons herein can be applied to programming in any language. Our goal is to give you the . In this book, you will learn the concepts and principles of FP as they apply to every level of programming. We begin in this chapter by explaining what a pure function is, as well as .
from functions. This in turn allows for functional composition, and a virtue of Scala is that we can design using both functional composition and object composition, as we desire or as appropriate. Let's explore Scala's approach to functional programming with some examples. We'll start with some small examples that just manipulate numbers .
Thus it might seem that Scrum, the Agile process often used for software development, would not be appropriate for hardware development. However, most of the obvious differences between hardware and software development have to do with the nature and sequencing of deliverables, rather than unique attributes of the work that constrain the process. The research conducted for this paper indicates .
