advertisement

Functional Programming - Introduction

27 %
73 %
advertisement
Information about Functional Programming - Introduction
Education

Published on February 20, 2014

Author: uyar

Source: slideshare.net

Description

Programming paradigms, imperative programming, functional programming, side effects.
advertisement

Functional Programming Introduction H. Turgut Uyar 2013-2014

License © 2013-2014 H. Turgut Uyar You are free to: Share – copy and redistribute the material in any medium or format Adapt – remix, transform, and build upon the material Under the following terms: Attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. NonCommercial – You may not use the material for commercial purposes. ShareAlike – If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. For more information: https://creativecommons.org/licenses/by-nc-sa/4.0/ Read the full license: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Programming Languages syntax: rules for writing a “grammatically correct” program how expressions, commands, declarations and other constructs must be arranged to make a well-formed program semantics: how the program should be “interpreted” how the program may be expected to behave when executed on a computer

Programming Languages syntax: rules for writing a “grammatically correct” program how expressions, commands, declarations and other constructs must be arranged to make a well-formed program semantics: how the program should be “interpreted” how the program may be expected to behave when executed on a computer

Idioms knowing the syntax and understanding the semantics is not sufficient to master a programming language standard library other libraries tools: debugging, testing, profiling documenting style: code formatting, variable naming, . . . idioms: patterns for using language features

Idioms knowing the syntax and understanding the semantics is not sufficient to master a programming language standard library other libraries tools: debugging, testing, profiling documenting style: code formatting, variable naming, . . . idioms: patterns for using language features

Universality universal: capable of expressing any computation any language that supports iteration or recursion is universal Church-Turing Thesis (from Wolfram MathWorld) Any real-world computation can be translated into an equivalent computation involving a Turing machine. It can also be calculated using general recursive functions.

Universality universal: capable of expressing any computation any language that supports iteration or recursion is universal Church-Turing Thesis (from Wolfram MathWorld) Any real-world computation can be translated into an equivalent computation involving a Turing machine. It can also be calculated using general recursive functions.

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Imperative Programming based on the Turing machine a program is a list of instructions for a von Neumann computer contents of memory constitutes the program state statements update variables (mutation) assignment and control structures Alan Turing (1912-1954) natural model of hardware

Imperative Programming based on the Turing machine a program is a list of instructions for a von Neumann computer contents of memory constitutes the program state statements update variables (mutation) assignment and control structures Alan Turing (1912-1954) natural model of hardware

Imperative Programming Example greatest common divisor (Python) def gcd(x, y): r = 0 while y > 0: r = x % y x = y y = r return x x y r -------------9702 945 0 945 252 252 252 189 189 189 63 63 63 0 0 63

Milestones in Imperative Programming Languages Fortran (1957) ALGOL (1960) C (1972) Ada (1983) Java (1995) John Backus (1924-2007)

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Functional Programming based on λ-calculus a program is a function application the same inputs should produce the same output the function also changes the context → side effect avoid mutation higher order functions Alonzo Church (1903-1995)

Functional Programming based on λ-calculus a program is a function application the same inputs should produce the same output the function also changes the context → side effect avoid mutation higher order functions Alonzo Church (1903-1995)

Functional Programming based on λ-calculus a program is a function application the same inputs should produce the same output the function also changes the context → side effect avoid mutation higher order functions Alonzo Church (1903-1995)

Functional Programming Example greatest common divisor (Python) def gcd(x, y): if y == 0: return x else: return gcd(y, x % y) gcd 9702 945 |- gcd 945 252 |- gcd 252 189 |- gcd 189 63 |- gcd 63 0 63 63 63 63 63

Side Effects sources of side effects: global variables factor = 0 def multiples(n): global factor factor = factor + 1 return factor * n

Side Effects sources of side effects: function state, object state class Multiplier: def __init__(self): self.factor = 0 def multiples(self, n): self.factor = self.factor + 1 return self.factor * n

Side Effects sources of side effects: input/output def read_byte(f): return f.read(1)

Side Effects sources of side effects: randomness import random def get_random(n): return random.randrange(1, n + 1)

Problems with Side Effects harder to reason about programs harder to test programs harder to parallelize programs could we write programs without relying on side effects? or, at least, could we constrain side effects?

Problems with Side Effects harder to reason about programs harder to test programs harder to parallelize programs could we write programs without relying on side effects? or, at least, could we constrain side effects?

Milestones in Functional Programming Languages Lisp (1957) ML (1973) Haskell (1990) John McCarthy (1927-2011)

Object Orientation object orientation is about data abstraction type hierarchies these can be achieved in both paradigms Ocaml, F# Scala modern imperative languages support functional features Ruby, Python Java, C# what makes a language functional or imperative? higher order functions most code written in functional style

Object Orientation object orientation is about data abstraction type hierarchies these can be achieved in both paradigms Ocaml, F# Scala modern imperative languages support functional features Ruby, Python Java, C# what makes a language functional or imperative? higher order functions most code written in functional style

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Expressions expression: a construct that will be evaluated to yield a value primitive expressions: literals, constants, variables combining expressions: operators statement: a construct that will be executed to update a variable

Expressions expression: a construct that will be evaluated to yield a value primitive expressions: literals, constants, variables combining expressions: operators statement: a construct that will be executed to update a variable

Expression Example conditional statement (Python) if x < 0: abs_x = -x else: abs_x = x conditional expression (Python) abs_x = -x if x < 0 else x conditional expression (Haskell) abs_x = if x < 0 then -x else x

Expression Example conditional statement (Python) if x < 0: abs_x = -x else: abs_x = x conditional expression (Python) abs_x = -x if x < 0 else x conditional expression (Haskell) abs_x = if x < 0 then -x else x

Expression Example conditional statement (Python) if x < 0: abs_x = -x else: abs_x = x conditional expression (Python) abs_x = -x if x < 0 else x conditional expression (Haskell) abs_x = if x < 0 then -x else x

Expression Example if age < 18: minor = True else: minor = False minor = True if age < 18 else False minor = age < 18

Expression Example if age < 18: minor = True else: minor = False minor = True if age < 18 else False minor = age < 18

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Definitions binding: an association between an identifier and an entity environment: a set of bindings definitions (Haskell) name :: type name = expression in a pure functional language, redefining a variable is not allowed

Definitions binding: an association between an identifier and an entity environment: a set of bindings definitions (Haskell) name :: type name = expression in a pure functional language, redefining a variable is not allowed

Definition Examples diameter :: Float diameter = 4.8 circumference :: Float circumference = 3.14159 * diameter diameter = 15.62 -- multiple declarations

Local Definitions a local definition can be used only within the expression where it is defined name = expression where name1 :: type1 name1 = expression1 name2 :: type2 name2 = expression2 ... example area = 3.14159 * r * r where r :: Float r = diameter / 2

Local Definitions a local definition can be used only within the expression where it is defined name = expression where name1 :: type1 name1 = expression1 name2 :: type2 name2 = expression2 ... example area = 3.14159 * r * r where r :: Float r = diameter / 2

Topics 1 Programming Paradigms Programming Languages Imperative Programming Functional Programming 2 Basic Concepts Expressions Definitions Functions

Functions in imperative languages, the body of a function is a block special construct for sending back the result: return in functional languages, the body of a function is an expression

Functions in imperative languages, the body of a function is a block special construct for sending back the result: return in functional languages, the body of a function is an expression

Function Parameters formal parameter: an identifier through which a function accesses an argument declared at function definition actual parameter: an expression which yields an argument defined at function application

Function Parameters formal parameter: an identifier through which a function accesses an argument declared at function definition actual parameter: an expression which yields an argument defined at function application

Function Definitions -- function definition name :: t1 -> t2 -> ... -> tk -> t name x1 x2 ... xk = expression -- function application name e1 e2 ... ek

Function Examples square :: Integer -> Integer square x = x * x -- square 21 -> 441 -- square (2 + 5) -> 49 sumOfSquares :: Integer -> Integer -> Integer sumOfSquares x y = square x + square y -- sumOfSquares 3 4 -> 25 -- sumOfSquares (a + 1) (a * 2)

Function Example sumOfCubes :: Integer -> Integer -> Integer sumOfCubes x y = cube x + cube y where cube :: Integer -> Integer cube n = n * n * n

References Required Reading: Thompson Chapter 1: Introducing functional programming Chapter 2: Getting started with Haskell and GHCi

Add a comment

Related presentations

Related pages

Introduction to Functional Programming | edX

The aim of this course is to teach the foundations of functional programming and how to apply them in the real world.
Read more

Introduction to Functional Programming - GitHub Pages

INTRODUCTION TO FUNCTIONAL PROGRAMMING Richard Bird Programming Research Group, Oxford University Philip Wadler Department of Computer Science,
Read more

A practical introduction to functional programming

Many functional programming articles teach abstract functional techniques. That is, composition, pipelining, higher order functions. This one is different.
Read more

Introduction to Functional Programming in F#

This section contains topics that demonstrate some of the features of F# that support functional programming. You do not need to know functional ...
Read more

Functional programming - Wikipedia

Functional programming Programming paradigms; Action; Agent-oriented; Array-oriented; Automata-based; Concurrent computing. Relativistic ...
Read more

Functional Programming in Haskell - Free online course

Get an introduction to Haskell, the increasingly popular functional programming language, with this University of Glasgow course.
Read more

Overview: Introducing F# and Functional Programming

F# is a programming language that combines the succinct and expressive functional programming style with the robustness of the .NET Framework.
Read more

Introduction to Functional Programming

Preface These are the lecture notes accompanying the course Introduction to Functional Programming, which I taught at Cambridge University in the academic year
Read more

Introduction to Functional Programming using F# - Part 1 ...

Introduction. In this article, I am going to explain the fundamental concepts behind functional programming and advantages of these languages ...
Read more