Scheme - Friend or Foe

Scheme – Friend or Foe?
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 syntax from Lambda Calculus
“To use functions as arguments, one needs a notation for functions, and it seemed
natural to use the λ -notation of Church (1941). I didn't understand the rest of his
book, so I wasn't tempted to try to implement his more general mechanism for
defining functions.
Lisp:
Based on a few big ideas:
1) (Nearly) Everything is a list (LISt Processor)
2) REPL – Read Evaluate Print Loop
3) Non-mutability (“no” state)
Polish Notation:
Named after Jan Łukasiewicz
Used extensively in Lisp
Very simple concept –
2+3+23
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) Define a function “factorial” taking a
parameter “n”
(if (= n 0) 1

Scheme:
(define (factorial n) If N = 0 then return 1 else…
(if (= n 0) 1

Scheme:
(define (factorial n)
(if (= n 0) 1 Return N *
(* n (factorial (- n 1))))) 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:
I don’t see any of these big
ideas!!!
Based on a few big ideas:

1) (Nearly) Everything is a list (LISt Processor)
2) REPL – Read Evaluate Print Loop
3) Non-mutability (“no” state)
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:

Quote here tells the system “don’t try to
‘(1 2 3 4 5) 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
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 (=):
You compare two strings with (equal?):
(= 5 5) (equal? “5” “5”)
#t #t
(= 5 4) (equal? “5” “4”)
#f #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 Remember, no types!
Example fn is a function
ls is a list
(begin
))
Begin – do more than one thing; usually
Example considered bad form in Scheme

(begin
))
Higher Order Functions Call function fn passing in the car (first
Example element of) the list. If it returns true, print
the car plus a newline
(begin
))
If the cdr (the rest of the list) is not null,
Example then call printwhere on the rest of the list

(begin
))
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
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

Send 100,000 numbers to
each node along with the
“instruction” (lambda, pre-
Master Node defined function, etc) to
“sum”
Node Node Node Node Node Node Node Node Node Node
Each node returns the sum
of the numbers; master
Master Node node now can add those 10
numbers and divide by
1,000,000!
Node Node Node Node Node Node Node Node Node Node
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…

Scheme - Friend or Foe

Uploaded by

Copyright:

Available Formats

Scheme - Friend or Foe

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Scheme - Friend or Foe

Uploaded by

Copyright:

Available Formats

Scheme – Friend or Foe?

Invented the term Artificial Intelligence

Invented the term Artificial Intelligence

Notice the parenthesis – you will come to hate

Scheme and Lisp are very similar, but the

The > is just the prompt

A little recursive function

A little recursive function

A little recursive function

(* n (factorial (- n 1))))) the result of

A little recursive function

Based on a few big ideas:

Or let the compiler do it for you:

> '(1 2 3 (4 5 6) (7 8 9))

What will this give me?

> '(1 2 3 (4 5 6) (7 8 9))

What will this give me?

How else could you express the else clause?

>(let ((i 1) (j 2))

(define (printwhere fn ls)

(define (printwhere fn ls)

>(map + ‘(1 2 3) ‘(4 5 6))

> (for-each display '(1 2 3 4))

> (for-each (lambda (x) (let ((y (+ x 1)))(display y)))'(1 2 3 4))

A simple concept – lots of nodes do most of the work, then roll it up to

A simple example – you want to average a million numbers

And that’s what I will use to evaluate your code…

You might also like