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
• Family of Lisp languages (main dialects):
– Common Lisp (general purpose, industrial strength)
– Scheme (minimalistic approach to purified functional programming)
– DrScheme (initial nonstandard expansion of Scheme)
– DrRacket (a computational environment evolving from DrScheme, general purpose and quickly expanding)
• 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
• Schemeisamulti-paradigm language but the most important is its support of functional programming
• DevelopedbyGuyL.Steeleand Gerald Jay Sussman in the 1970s (1975)
• Successfullyusedinindustryand commercial applications
• There are language standards (important for industrial software development)
Scheme
©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
• Racket (former Dr. Scheme) also called PLT Scheme (dialect of Lisp and expanded descendant of 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
DrRacket (former 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 racket (MzScheme)
• SW distribution: Racket v6.1 (OCT 2014) http://racket-lang.org/download/
©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
©Jozo Dujmović Functional Programming 26
MzScheme > racket
©Jozo Dujmović Functional Programming 27
– More – Guide
Documentation
• http://racket-lang.org/learning.html
• Resources: – Quick
• How to design programs
• Programming Languages: Application and Interpretation (all materials are free pdf)
©Jozo Dujmović Functional Programming 28
SCHEME highlights
©Jozo Dujmović Functional Programming 29
6
256
Function returns a value
(
(+ 1 2 3)
; list
; function definition
(define (square x) (* x x))
(square 16)
( (lambda (n) (* n n)) 5)
; anonymous function
; function of two variables
25
(define (tri a b) (sqrt (+ (* a a) (* b b))))
(tri 3 4) 5
©Jozo Dujmović Functional Programming 30
Nesting functions in functional programming
(fun1 arg1 arg2 arg3)
In pure functional programming all expressions and all functions return a value. This also includes control structures begin, if, cond, case and do.
(fun2 (…) (…)…(…) … (…)(…)(…))
( fun3 (…) (…) … (…) … (…) (…) (…))
If, in addition to returning a value, a function modifies some state, it is said to produce a side effect.
©Jozo Dujmović
Functional Programming 31
Results
A goal of functional programming is to eliminate (or minimize) side effects.
Functions should not make other effects (modify state variables).
Function that returns a function
> (define s (read)) (lambda(n) (* n n)) >s
‘(lambda (n) (* n n)) > ((eval s) 5)
25
> (define d (read))
(lambda(n) (* 2 n))
> ((eval d) 5)
10
> (define (test a b) (if (> a b) (eval s) (eval d))) ; This function
> ((test 5 2) 7) ; returns a function 49
> ((test 5 9) 7)
14
©Jozo Dujmović Functional Programming 32
Functions that accept an arbitrary number of arguments
> (define (sumlist lst)
(if (null? lst) 0 (+ (car lst) (sumlist (cdr lst)))))
> (sumlist ‘(1 2 3 4))
10
> (define (slist . x) (sumlist x))
>(slist1234) ; x=’(1 2 3 4)
10
> (define slst (lambda x (sumlist x)))
> (slst 1 2 3 4) ; (
10
©Jozo Dujmović Functional Programming 33
Functions with mandatory and optional arguments
> (define (sumlist lst)
(if (null? lst) 0 (+ (car lst) (sumlist (cdr lst)))))
> (sumlist ‘(1 2 3 4))
10
> (define mean (lambda (x . y)
(/ (+ x (sumlist y)) (+ 1 (length y)))))
> (mean 1 2 3 4 5) 3
> (mean 1) 1
> (mean)
mean: arity mismatch; the expected number of arguments does not match the given number; expected: at least 1, given: 0
> (define mean (lambda(x y . z) ; x and y are mandatory args, and z is optional
(/ (+ x y (sumlist z)) (+ 2 (length z)))))
> (mean 1 2 3 4 5) 3
> (mean 1)
mean: arity mismatch; the expected number of arguments does not match the given number; expected: at least 2; given: 1
©Jozo Dujmović Functional Programming 34
Composed functions f(g(x))
> (define compose (lambda ( f g)
(lambda (x) (f (g x))))) ; compose returns a function of one argument (x) > ((compose log exp) 123.456)
123.456
> (map (compose log exp) ‘(1 2 3 4 5 6))
‘(1.0 2.0 3.0 4.0 5.0 6.0)
> (map (compose exp log) ‘(1 2 3 4 5 6))
‘(1 2.0 3.0000000000000004 4.0 4.999999999999999 6.0) > (define compose
(lambda (f g)
(lambda args ; args = sequence of arguments
(f (apply g args))))) ; compose returns a function of many arguments
> ((compose sqrt +) 9 5 5 6) ; sqrt(9+5+5+6) 5
> ((compose (lambda(n) (* n n)) +) 1 2 3 4) 100
©Jozo Dujmović Functional Programming 35
Weighted power means (1/2)
> (define wpm (lambda ( r)
(lambda (x y)
(expt (+ (* 0.5 (expt x r)) (* 0.5 (expt y r))) (/ 1. r)))))
> (define ari (wpm 1.)) > (ari 1 3)
2.0
> (define har (wpm -1.)) > (har 1 3)
1.5
> (define quad (wpm 2)) > (quad 1 3) 2.23606797749979
©Jozo Dujmović
Functional Programming 36
Weighted power means (2/2)
> (define wpm (lambda ( r)
(if (= r 0)
(lambda (x y) (sqrt (* x y)))
(lambda (x y) (expt (+ (* 0.5 (expt x r)) (* 0.5 (expt y r))) (/ 1. r))))))
> (define geo (wpm 0)) > (define ari (wpm 1))
> (define quad (wpm 2)) > (define har (wpm -1.)) > (har 1 4)
1.6
> (geo 1 4) 2
> (ari 1 4)
2.5
> (quad 1 4) 2.9154759474226504
©Jozo Dujmović
Functional Programming 37
> (define compose (lambda (f g)
Composed functions
(lambda args
(f (apply g args)))))
> ((compose sqrt *) 1 4) 2
©Jozo Dujmović
Functional Programming 38
• Nestedfunctions(()(()())())
• Each control structure returns a value
• No side effects
• The use of anonymous functions
Summary
• Scheme uses a small number of powerful basic concepts
• Simple syntax based on lists: (oprator opnd opnd …)
• Everything is first class
• Easy recursive programs based on tail recursion
• Functions can have arbitrary number of arguments
• Arguments can be mandatory, optional, or missing
• Functions can be composed using multiple levels of composition and all types of arguments
• Functions can be returned from expressions and from other functions
©Jozo Dujmović Functional Programming 39