Scheme – Friend or Foe?
Scheme – Friend or Foe?
Recursion
A recursive function calls itself. It’s “that easy”.
The “tricks” to recursion:
Deciding how/when to use it
Stopping it from getting out of control
Debugging…
Let’s look at an example…
You remember from basic math that multiplication is repeated adding?
5 * 3 = 5 + 5 + 5, right?
int multiply (int a, int b) {
if (b == 0) return a;
return a + multiply(a,b-1);
}
Stop when we are done
What can we use recursion for?
Recursion can be used any time you would use a loop. In fact, it is provably true that recursion can be replaced with a loop and a loop can be replaced with recursion.
int multiply (int a, int b) {
if (b == 0) return 0;
return a + multiply(a, –b);
}
int multiply (int a, int b) {
int total;
for (int i=b;i>0;i–)
total += a;
return total;
}
Using recursion to process a list (C#)
int sum(IEnumerable
{
if (a.Count()==0) return 0;
return a.First() + sum(a.Skip(1));
}
Debugging recursion to process a list (C#)
int sum(IEnumerable
{
console.writeline (“Entering sum with “ + string.Join(“,”,a.ToArray()));
if (a.Count()==0) return 0;
return a.First() + sum(a.Skip(1));
}
Entering sum with 5,4,3,2,1
Entering sum with 4,3,2,1
Entering sum with 3,2,1
Entering sum with 2,1
Entering sum with 1
Entering sum with
15
Recursion Summary
Recursion is “just” a loop. It’s just written as function calls, not a “for” or “while” – the computer’s stack is the loop variable!
The best way to debug a recursion is printing out what happened on each pass through.
Now, on to Scheme…
As always, lets look at some history
Sigh. Do we have to do this every time?
John McCarthy, inventor of Lisp
John McCarthy:
Invented the term Artificial Intelligence
Invented Lisp, the first functional language
Invented time sharing
Invented the space fountain
John McCarthy:
Invented the term Artificial Intelligence
Invented Lisp, the first functional language
Invented time sharing
Invented the space fountain
Lisp:
Created in 1958
One year younger than Fortran (1957)
One year older than Cobol (1959)
Based on Lambda Calculus
Lisp:
Based on a few big ideas:
(Nearly) Everything is a list (LISt Processor)
REPL – Read Evaluate Print Loop
Non-mutability (“no” state)
Polish Notation:
Named after Jan Łukasiewicz
Used extensively in Lisp
Very simple concept –
2 + 3 + 2 3
Operator first instead of in the middle
Helps with parsing – the parser knows what to expect right away
Lisp:
Let’s look at a simple example
( + 2 3)
5
Notice the parenthesis – you will come to hate love parenthesis
Scheme:
Scheme and Lisp are very similar, but the syntax on more complicated things is a little different, so let’s “switch” to Scheme syntax.
Scheme:
> ( + 2 3)
5
The > is just the prompt
Simple syntax is the same!
Scheme:
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
A little recursive function
Scheme:
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
A little recursive function
Define a function “factorial” taking a parameter “n”
Scheme:
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
A little recursive function
If N = 0 then return 1 else…
Scheme:
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
A little recursive function
Return N *
the result of
factorial of
N – 1
Same Method in C#/Java
double factorial(double n)
{
if (n == 0) return 1;
return n * factorial (n-1);
}
Big Ideas:
Based on a few big ideas:
(Nearly) Everything is a list (LISt Processor)
REPL – Read Evaluate Print Loop
Non-mutability (“no” state)
I don’t see any of these big ideas!!!
Lists
Some of the instructions are … archaic for this stuff because history
Construct a list:
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ‘())))))
Or let the compiler do it for you:
‘(1 2 3 4 5)
Quote here tells the system “don’t try to evaluate this list, just allocate for it and use it as data”
Lists
Take the first item from a list:
car (contents of address register)
>(car `(1 2 3 4 5))
1
Take the second through the end of the items from a list:
cdr (contents of the data register)
>(cdr `(1 2 3 4 5))
(2 3 4 5)
Lists
You can make lists of lists!
> ‘(1 2 3 (4 5 6) (7 8 9))
(1 2 3 (4 5 6) (7 8 9))
What will this give me?
>(car (cdr (cdr (cdr ‘(1 2 3 (4 5 6) (7 8 9))))))
Lists
You can make lists of lists!
> ‘(1 2 3 (4 5 6) (7 8 9))
(1 2 3 (4 5 6) (7 8 9))
What will this give me?
>(car (cdr (cdr (cdr ‘(1 2 3 (4 5 6) (7 8 9))))))
(4 5 6)
Definitions!
You can define names and assign “things” to them:
>(define mylist ‘(1 2 3 (4 5 6) (7 8 9)))
>(car mylist)
1
Isn’t this Functional Programming?
Where all my functions at?
Definitions!
You can also define functions. Remember our old friend factorial?
>(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
Built ins
So now we have an idea how to define functions, we need to know how to DO something. There are some basic Boolean built-ins:
#t – true #f – false
null? – returns #t or #f if a list is empty (null? ‘()) #t
and – takes any number of arguments and returns #f if any are #f, otherwise it returns the last argument:
(and 1 2 3 4) 4 (and 1 2 #f 3 4) #f
or – takes any number of arguments and returns the first non #f, otherwise it returns #f:
(or 1 2 3 #f 4) 1 (or #f #f) #f
not – takes one argument and return #f UNLESS the argument was #f
(not 34) #f (not #f) #t
Built ins
cond – takes any number of conditions, returns the first true one
>(cond
(( > 1 2) “false 1”)
(( > 4 5) “false 2”)
(( < 6 7) "true 1")
(else "else"))
”true 1”
How else could you express the else clause?
Built ins
cond – takes any number of conditions, returns the first true one
>(cond
(( > 1 2) “false 1”)
(( > 4 5) “false 2”)
(( > 6 7) “true 1”)
(#t “else”))
”else”
Built ins
There are TONS of built-ins:
odd? even? positive? negative? zero?
You have seen the < > = operators
list? – is the parameter a list?
pair? is the parameter a list with at least one cons (item)?
null? is the parameter an empty list?
(display x) – prints x to the screen
Built ins
Things you can do with lists:
(reverse ‘(1 2 3)) (3 2 1)
(length ‘(4 5 6)) 3
(member 4 ‘(1 2 3 4 5 6)) (4 5 6) – cdr starting at search element
(append ‘(1 2) ‘(3 4)) (1 2 3 4)
Many more (read the documentation!)
Equality
You compare two numbers with (=):
(= 5 5)
#t
(= 5 4)
#f
You compare two strings with (equal?):
(equal? “5” “5”)
#t
(equal? “5” “4”)
#f
Local Variables
It isn’t true that Functional Languages have NO variables, they just aren’t global…
>(let ((i 1) (j 2))
(+ i j))
3
Notice, though, the scoping rules – i & j are only valid WITHIN the let ”statement”.
Lambda – IMPORTANT IDEA
A lambda is an unnamed function. These are really handy for those cases where you need to define a function and use it only once. Otherwise you end up filling your program with functions that you can’t reuse and don’t care about but that you have to look through when you
>(
(lambda(n)
(+ n 1)
)
5
)
6
Local Variables
Functions can also be assigned to a local variable!
>(define (quadruple x)
(let ((double (lambda (y)
(+ y y))))
(double(double x))))
Higher Order Functions – IMPORTANT IDEA
Higher order functions are functions that take other functions as a parameter
Higher Order Functions
Example
(define (printwhere fn ls)
(begin
(if (fn (car ls )) (begin (display (car ls))(newline) ))
(if (not (null? (cdr ls))) (printwhere fn (cdr ls)))
))
Higher Order Functions
Example
(define (printwhere fn ls)
(begin
(if (fn (car ls )) (begin (display (car ls))(newline) ))
(if (not (null? (cdr ls))) (printwhere fn (cdr ls)))
))
Remember, no types!
fn is a function
ls is a list
Higher Order Functions
Example
(define (printwhere fn ls)
(begin
(if (fn (car ls )) (begin (display (car ls))(newline) ))
(if (not (null? (cdr ls))) (printwhere fn (cdr ls)))
))
Begin – do more than one thing; usually considered bad form in Scheme
Higher Order Functions
Example
(define (printwhere fn ls)
(begin
(if (fn (car ls )) (begin (display (car ls))(newline) ))
(if (not (null? (cdr ls))) (printwhere fn (cdr ls)))
))
Call function fn passing in the car (first element of) the list. If it returns true, print the car plus a newline
Higher Order Functions
Example
(define (printwhere fn ls)
(begin
(if (fn (car ls )) (begin (display (car ls))(newline) ))
(if (not (null? (cdr ls))) (printwhere fn (cdr ls)))
))
If the cdr (the rest of the list) is not null, then call printwhere on the rest of the list
Higher Order Functions
A few built in examples:
>(map + ‘(1 2 3) ‘(4 5 6))
(5 7 9)
> (for-each display ‘(1 2 3 4))
1234
> (for-each (lambda (x) (let ((y (+ x 1)))(display y)))'(1 2 3 4))
2345
Higher Order Functions in Other Languages
C#:
void Main()
{ Example.MyWhere(new int[] { 1,2,3,4,5,6,-2,-3,0},x=>x>0).Dump(); }
public static class Example {
public static IEnumerable
{
List
foreach (var item in source)
if (predicate(item)) output.Add(item);
return output;
}
}
lambda!
Higher Order Functions in Other Languages
C:
int compare (const void * a, const void * b)
{
return ( *(int*)a – *(int*)b );
}
int main ()
{
int values[] = { 40, 10, 100, 90, 20, 25 };
qsort (values, 6, sizeof(int), compare);
for (int n=0; n<6; n++)
printf ("%d ",values[n]);
return 0;
}
qsort is part of the standard library!
Map/Reduce
Not a new idea (has roots in mergesort from the 40’s!), but Google made it more famous recently
A simple concept – lots of nodes do most of the work, then roll it up to some master nodes who finish the work
A simple example – you want to average a million numbers
Master Node
Node
Node
Node
Node
Node
Node
Node
Node
Node
Node
Send 100,000 numbers to each node along with the “instruction” (lambda, pre-defined function, etc) to “sum”
Master Node
Node
Node
Node
Node
Node
Node
Node
Node
Node
Node
Each node returns the sum of the numbers; master node now can add those 10 numbers and divide by 1,000,000!
Questions?
What tool to use?
There are several scheme interpreters out there.
I used:
https://download.racket-lang.org/
And that’s what I will use to evaluate your code…
/docProps/thumbnail.jpeg