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
(car ‘(1234)) 1
(cdr ‘(1234)) (2 3 4)
Car and cdr
Jozo Dujmović Functional Programming 14
Anonymous functions
• The following function is anonymous:
(lambda(n) ( * n n))
• A general form of applying an operator: (
• Applying an anonymous function to a single argument
> ((lambda(n) ( * n n)) 5)
> 25 (this is the returned value)
Jozo Dujmović Functional Programming 15
Scheme
• Scheme is a multi-paradigm language but the most important is its support of functional programming
• Developed by Guy L. Steele and Gerald Jay Sussman in the 1970s (1975)
• Successfully used in industry and commercial applications
• There are language standards (important for industrial software development)
Jozo Dujmović Functional Programming 16
First-class objects
• An object (data object, or a function) is first-class if it can be used in programs without restrictions:
– May be expressed as an anonymous literal value (constant) – May be stored in variables
– May be stored in data structures
– May be comparable to other objects for equality
– May be passed as parameter to procedures/functions – May be returned as result from procedures/functions – May be constructed at run time
– Is readable and printable
– It has intrinsic identity (independent of given name) – May be stored outside running processes
– May be transmitted among processes
• In Scheme all objects (including functions) are first-class. Elimination of restrictions contributes to the expressive power of languages.
Jozo Dujmović Functional Programming 17
What Scheme authors think about programming languages
• “Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.”
• Therefore, the main goals are: simplicity, generality, and small number of powerful fundamental concepts.
Jozo Dujmović Functional Programming 18
Scheme Standards
• Mostly based on the latest version of the “Revised Report on the Algorithmic Language Scheme”
• IEEE Scheme – IEEE standard, 1178– 1990 (R1995)
Jozo Dujmović Functional Programming 19
Scheme implementations
• Multiple free implementations are available on Internet
• MIT – GNU
• Texas Instruments
• University of Geneva Scheme
• Dr. Scheme
Jozo Dujmović Functional Programming 20
TI Scheme
• Can be installed by copying PCS.ZIP directory posted on iLearn
• Convenient for testing concepts and small programs
• Used in the Scheme part of the CSc 600 Reader
• Minimalistic features – just a DOS window
• Similar to the University of Geneva version
Jozo Dujmović Functional Programming 21
Texas Instruments Scheme
To start click PCS.EXE
Jozo Dujmović
Functional Programming 22
DrScheme
• Comfortable environment based on GUI
• Related to a free on-line book How to Design Programs
• Two windows: function definition window and function execution window
• A version with traditional query-based interpreter (MzScheme)
• SW distribution: http://planet.plt-scheme.org/ Jozo Dujmović Functional Programming 23
How to Design Programs
An Introduction to Computing and Programming
Matthias Felleisen Robert Bruce Findler Matthew Flatt
Shriram Krishnamurthi
Free Scheme book
The MIT Press
Cambridge, Massachusetts London, England
2001
Jozo Dujmović Functional Programming
24
Window for defining programs
Window for execution of programs
Jozo Dujmović Functional Programming 25
MzScheme
Jozo Dujmović Functional Programming 26