Functional Programming
The key idea:
Solving problems using functions
But, don’t all programming languages allow you to write functions?
Yes, but they provide only calls for functions and not a functional paradigm. What is the difference?
1
Functional Programming
So, what is functional programming?
• Like mathematical functions, the functions we write should depend only on their inputs and not on the program state.
• A FPL thus allow you to model computations as evaluations of functions. Similar to?
2
12
Functional vs Imperative Style
Imperative languages: Composed of step- by-step instructions for the computer (“authoratively” telling it what to do).
Functional languages: Everything is a function. In other words, a function is a first-class object that you can manipulate in its own right
3
Functional Programming
An Example:
Consider writing a program to test if a number is prime or not.
Algorithm – check to see if the number is divisible by any number between 2 and itself. If it is, it is not prime, otherwise yes. Try writing it!
4
34
Import java.util.Scanner;
Public class PrimeTest
{ public static void isPrime (int n)
{ boolean prime = true; If (n < 2) prime = false; for (int i=2; i < n; i++)
{ if (n%i==0)
{ prime = false; break; }
}
if (prime)
What did you see?
System.out.printf(“%d %s\n”, n, “is a prime number”) else
System.out.printf(“%d %s\n”, n, “is not a prime number”) }
Public static void main (String[]args)
{ Scanner sc = new Scanner (System.in);
Sytem.out.println( “enter a number to check if its prime or not”) int num = sc.nextInt();
isPrime (num);
}
5
#include
Main() {
int n, c;
printf(“Enter a number\n”); scanf(“%d”, &n);
if (n==2) printf(“Prime number.\n”); else
{
for (c=2; c<=n-1; c++) {
if (n%c==0) break; }
if (c !=n) printf(“Not prime.\n”);
else printf(“Prime number.\n”); }
Return 0;
What did you see?
6
56
1
LISP
(defun is-prime (n) (isnot-divisible-between-n-2 n (- n 1)))
(defun isnot-divisible-between-n-2 (n d) (or (= d 1)
(and (/= (rem n d) 0) (isnot-divisible-between-n-2 n (- d 1)))))
What did you see?
7
#include
Main() {
int n, c;
printf(“Enter a number\n”); scanf(“%d”, &n);
if (n==2) printf(“Prime number.\n”); else
{
for (c=2; c<=n-1; c++) {
if (n%c==0) break; }
if (c !=n) printf(“Not prime.\n”);
else printf(“Prime number.\n”); }
Return 0;
Print results
?8
2 states: type integer
Read & check state
Manipulate states
78
9 10
#include
Main() {
int n, c;
printf(“Enter a number\n”); scanf(“%d”, &n);
Need to declare integer
if (n==2) printf(“Prime number.\n”); else
{
Are these part of solving the problem?
for (c=2; c<=n-1; c++) {
if (n%c==0) break; }
Need to break a loop
if (c !=n) printf(“Not prime.\n”); else printf(“Prime number.\n”);
} Return 0;
Instead of a boolean var, use the count
9
LISP
(defun is-prime (n) (isnot-divisible-between-n-2 n (- n 1)))
(defun isnot-divisible-between-n-2 (n d) (or (= d 1)
(and (/= (rem n d) 0) (isnot-divisible-between-n-2 n (- d 1)))))
What did you see? 2 functions!
10
Functional Programming
One advantage of FP is that there are no side effects - one’s program is said to be cleaner – easier to understand and to predict its behavior. Why?
From a practitioner’s point of view, I love this paradigm because it allows me to focus on solving the problem and not on thinking about how to write a program!
Recall: coding vs problem solving
11
Functional Programming
Henceforth,
Instead of asking how do I write a program that given a number will decide if it is a prime number or not, I ask how could I write a function that given a number will decide if it is a prime number or not. In other words, what is the abstract algorithm that allows me to do so?
12
11 12
2
Functional vs Imperative Style
When writing a program using an imperative language, what do you do?:
You think of the variables needed, their declarations, and then you write functions that manipulate their states until the job is done.
Re-emphasizing again, in FP, you go directly to develop the functions needed.
13
The beauty of LISP
How then does LISP handle the different variables so often needed in a programming task?
LISP use a simple list to hold all variables/data.
LISP stands for LISt Processing
14
13 14
The beauty of LISP
A list in LISP represents:
1. Amemoryforholdingitsdata
2. Likethephysicalmemoryinacomputer, it is unconcerned with data type
3. LikeaTuringMachine,alistcanbeof an infinite length
All a LISP programmer need to do is to write functions for solving problems using list.
15
The beauty of LISP
An ingenious idea:
LISP functions are also stored in the same memory i.e. as a list
After all, programs and data are kept in the same physical memory and at the memory level, these are just bits of information.
16
15 16
The beauty of LISP
Hence, both are a list of 4 elements: (a b c d)
(defun fun (x) (if (odd x) ’odd ‘even))
Functions and data are represented in the same way – creating the use of a uniform data structure.
The basic unit is of course, an atom
17
The beauty of LISP
Hence, both are a list of 4 elements: (a b c d)
(defun fun (x) (if (odd x) ’odd ‘even))
Recall that in Church’s l-calculus, we have (M N) where the list could be a list of l-terms or a function definition or a function application. LISP is modelled after l-calculus.
18
17 18
3
The beauty of LISP
As such, LISP’s underlying process looks like:
Read Eval
LISP is always smiling at you!
Input (a list)
Output (a list)
19
The beauty of LISP
Compare with imperative languages, we have:
I/O
Main Program
Supporting functions
Variables and data structures
20
19 20
Evaluation in LISP
Ø (defun fun (x) (if (oddp x) ‘odd ‘even)) FUN
Defun allows you to add a function definition to a symbol
In LISP symbols, they have a property list for storing function definition, value, etc.
21
Evaluation in LISP
Ø (defun fun (x) (if (oddp x) ‘odd ‘even)) FUN
Ø8 8
Ø x
(a b c)
; assuming x has been ; assigned a value
22
21 22
Evaluation in LISP
Ø (+ 5 6) 11
Ø (a b c) ?
In LISP, everything is evaluated and thus (a b c) is treated as a call to function “a” with arguments “b” and “c”
23
About evaluation in LISP
If you type in LISP:
()
(+ 1 2)
(fun 3)
LISP evaluates this as an empty list. It can represented as () or nil
LISP always evaluate the first argument as a function and here it makes sense – it is an add function.
LISP evaluates fun and returns odd
24
23 24
4
About evaluation in LISP
But what about:
This is a list with an empty list. LISP evaluates its first arg which is an empty list and it is not a function. So, it returns an error.
((())) Similarly, this is an error
(())
25
Evaluation in LISP
What if you want (a b c) to be treated as data and not as a function?
Ø (a b c) (a b c)
You need to suppress evaluation using quote or ‘:
Ø‘(a b c) (a b c)
Evaluating ‘ means take whatever following it as the result
26
25 26
About QUOTE in your last tutorial
If you type in LISP:
LISP tries to evaluate this and since it has no value, it returns error
The quote means no need to evaluate this and return as it is i.e. abc
abc ‘abc
‘abc Equivalent to (quote abc) = the identify function in lambda calculua
27
LISP itself
LISP is like a virtual computer. It has:
A list = Memory
An eval function = CPU/State table
What else is missing?
Machine codes = basic instructions for driving the computer
28
27 28
LISP itself
The “machine” codes for LISP are the basic instructions needed for manipulating lists + a couple of other basic functions.
What basic functions do we need?
29
Basic functions in LISP
For accessing elements in a list:
Car, cdr, first, second, caadr, cdadr
(a b c d e f g)
a car/first (bcdefg) cdr/rest
car/cdr: two basic instructions for access
30
29 30
5
Basic functions in LISP
For accessing elements in a list:
Car, cdr, first, second, caadr, cdadr
(a b c (d e) f g)
c caddr/third
e (cadr (cadddr
max 4
31
Basic functions in LISP
For constructing new lists:
cons Put something in a list
list Put everything in a list
append Combine lists into a single list
Write lisp expressions using them.
32
31 32
Basic functions in LISP
Other standard functions:
setf (for assigning values) defun
T (or anything nonNIL), Nil cond, when, if, unless equal, =
listp, numberp, atom, evenp, oddp and, or, not
member, reverse, null, length
33
33
6