SCHEME
and functional programming
Dr. Jozo Dujmović
Jozo Dujmović Functional Programming 1
Programming paradigms
• Paradigm = fundamental style of programming.
• Main computer programming paradigms are:
1. Procedural (imperative) programming
2. Nonprocedural (declarative) programming
3. Logic programming (subset of declarative programming)
4. Functional programming (subset of declarative programming)
5. Object-oriented programming
Jozo Dujmović Functional Programming 2
Multi-paradigm languages
• Some languages strictly support only a single paradigm (Fortran, Cobol, Algol, Basic, PL/1, Pascal, C: mostly procedural)
• Some languages support multiple paradigms (C++ supports both procedural and object-oriented paradigm)
Jozo Dujmović Functional Programming 3
Imperative vs. Declarative
• Imperative programming is a programming paradigm that describes computation in terms of a program state (values of variables) and statements that change the program state. It is based on algorithms.
• Declarative programming specifies what the program should accomplish without describing control flow and algorithmic steps.
Jozo Dujmović Functional Programming 4
The concept of side effect
• A function or expression is supposed to return a value (and make no other effects).
• If, in addition to returning a value, a function modifies some state, it is said to produce a side effect.
• A goal of functional programming is to eliminate (or minimize) side effects
• Imperative programming uses side effects to produce program results.
Jozo Dujmović Functional Programming 5
Side effects and safety
• A “safe operation” is free of side effects
• Functions that use side effects may generate unexpected results and create unsafe programs.
int cube(int x)
{ // g = a global variable
g -= x; // Change of state = side effect
return x*x*x; }
cube(2)*cube(g) != cube(g)*cube(2) due to side effects Jozo Dujmović Functional Programming 6
Mutable vs. immutable objects
• Mutableobjectisanobjectwhichcanbe modified after it is created (can change the state); e.g. int n;
• Immutableobjectisanobjectwhosestate cannot be modified after it is created (e.g. const double pi=3.14;)
• Advantagesofimmutableobjects:noneedto copy objects (which can be large), but only their reference (address, or pointer) – that improves performance. (Passing by value or reference)
• OOlanguages(e.g.Python,Ruby,Java)access objects using references.
• Somelanguagessupportbothmutableand
immutable objects
Jozo Dujmović Functional Programming 7
Functional programming
• One of fundamental programming paradigms
• Main properties:
– Programming is organized as evaluation of functions
– Avoiding mutable objects
– Avoiding states, and changes of state
– Avoiding side effects (function output depends only on arguments and not on state: f(X) always returns the same value for same X)
• Theoretical roots of functional programming are in lambda calculus
Jozo Dujmović Functional Programming 8
Lambda calculus
• Formal system that investigates function definitions, applications and recursion
• Can be interpreted as a minimalistic programming language capable of expressing any algorithm
• Uses unnamed (anonymous) functions without side effects
• Functions can accept as arguments and return as results other functions
Jozo Dujmović Functional Programming 9
• LIStProcessinglanguage
• DesignedbyJohnMcCarthy
LISP
• FirstimplementedbySteveRussellonanIBM 704 computer (first Lisp interpreter)
• Thesecondoldestlanguageinwideusetoday (FORTRAN [1957], LISP [1958])
• Favorite language for AI research
• Based on lambda calculus (Alonzo Church)
• IntroducedmanyCSconcepts(dynamictyping, tree data structures, recursive functions, OO programming, etc.)
Jozo Dujmović Functional Programming 10
LISP is a family of languages
Two main dialects of Lisp:
– Scheme
– Common Lisp
• There are many implementations of both Scheme and Common Lisp
• Both Scheme and Common Lisp have language standards
Jozo Dujmović Functional Programming 11
Main characteristics of LISP
• Main data structures are linked lists
• LISP source code is made of linked lists
• Recognizable fully parenthesized syntax
• Interchangeability of programs and data
• LISP programs can manipulate source code (can create new syntax and specific new languages embedded in LISP)
Jozo Dujmović Functional Programming 12
List notation
• Program statement:
(function arg1 arg2 … argN)
• Listcontainingdata(“quotedlist”): ‘(data1 data2 … dataN)
• Headandtailextractionfunctionshavearchaic names inherited from first two implementations of Lisp for the IBM 704:
– Head: car (contents of the address part of register) – Tail: cdr (contents of the decrement part of register)
Jozo Dujmović Functional Programming 13