Lecture_16_Scheme
An Introduction to
Scheme
CSCI 3136: Principles of Programming Languages
Agenda
• Announcements
• Lectures are being recorded
• Assignment 7 is out and due July 2.
• Test 2 is on Monday July 5
• Readings:
• Lecture Contents
• Why Scheme?
• Overview: Atoms, Lists, Functions, Expressions
• Function calls
• Expressions in Scheme
• Lists and list manipulation
• Variables: define and let
• Conditionals: if
• Defining functions
• Recursion
2021-06-23 8:50 AM 2
Keywords
Scheme
Atom
• Literal
• Identifier
• Quote
List
• Pair
Function
• Argument
• First-class object
Expression
• Evaluation
Variable
Conditional
Special Form
Recursion
Scheme Functions
• if
• let
• lambda
• define
• car
• cdr
• cons
• equal?
2021-06-23 8:49 AM 3
End of this Part
CSCI 3136
42021-06-23 8:46 AM
Where are we?
CSCI 3136
52021-06-23 8:46 AM
Why Scheme?
• Scheme is a simple language based on the
functional programming paradigm
• Is used as a scripting language in some software
projects
• Easy to learn (minimalist syntax)
• Allows us to use it to discuss and exemplify various
language features and constructs
• Introduces you a different programming paradigm
that is becoming more popular
2021-06-23 8:45 AM 6
Running Scheme
• Scheme is an interpreted language
• Where can I run Scheme?
• FCS Unix server: timberlea.cs.dal.ca
• Invoke scheme on the command line to run interactive mode
• Invoke scheme file.scm to run the code in file.scm
• Download and install scheme on your machine
• Chez Scheme: https://github.com/cisco/ChezScheme/
• DrRacket: https://racket-lang.org
• Run in a web browser
• REPL.IT: https://repl.it/languages/scheme
• Code will be tested on: timberlea.cs.dal.ca
2021-06-23 8:45 AM 7
https://github.com/cisco/ChezScheme/
https://racket-lang.org/
https://repl.it/languages/scheme
The Functional Paradigm
• In the functional paradigm computation occurs by
evaluating expressions instead of executing statements
• In a pure functional model
• Expressions yield a value
• Have no side effects:
• The only change in program state is the returned value of the expression
• E.g., evaluating an expression multiple times will yield the same result
(assuming the values of the variables do not change)
• In the imperative model
• Computation occurs at the level of statements
• Statements do not yield a value but do produce side-effects
• A side-effect is the modification of an existing variable or memory
location
• Performing the same statement can result in different side-effects
2021-06-23 8:45 AM 8
count * faults / total
count = count + 1;
End of this Part
CSCI 3136
2021-06-23 8:45 AM 9
Scheme Basics
CSCI 3136
2021-06-23 8:45 AM 10
Scheme’s Building Blocks
• Scheme programs are composed of
• Atoms : individual values and identifiers
• E.g., counter, “Hello World”, 42, 3.14, #t, ()
• Lists : a linear collection of atoms and lists
• E.g. (counter 42 #t (3.14 0))
• Functions : procedures that return a value
• A function call is a list consisting of the function
to be called and a list of arguments
• e.g. (display “Hello World!”)
• Expressions : a list or an atom that can be evaluated
• A Scheme program runs by evaluating
expressions
2021-06-23 8:45 AM 11
float
empty list
boolean
integer
string
identifier
function
call
argument
function
expression
Function Calls
• Everything in Scheme is done with functions
Examples
• (+ 1 2)
• (display “Hello World”)
• (list “a” “b” “c”)
• A function call consists of three steps:
• Evaluate arguments
• Call the function
• Return the result
• E.g. (+ (* 12 4) (- 10 5))
The above has three function calls:
• A call to * to compute 12 * 4
• A call to – to compute 10 – 5
• A call to + to compute the sum of 12 * 4 and 10 – 5
• The above is an example of an expression
Function call in Java Function call in Scheme
foo(s, 2, “hi”) (foo s 2 “hi”)
2021-06-23 8:45 AM 12
Useful Built-In Functions in Scheme
Function Purpose Example Output
display Display the result of
an expression (print)
(display “Hello”)
(display ‘ (1 2 3))
“Hello”
(1 2 3)
newline Display a newline (newline) \n
exit Exit the interpreter (exit)
define Define a variable See next slides
let Define local variables See next slides
if Perform conditional
evaluation
See next slides
lambda Create a function See next slides
2021-06-23 8:45 AM 13
Expressions
• A Scheme program consists of an evaluation of one or more
expressions
• The evaluation of an expression returns a result that can
then be used in other expressions
• An expression is either
• An atom:
• A literal: literals evaluate to themselves
• E.g., 42 evaluates to 42, “Hello” evaluates to ”Hello”
• Identifiers (variables) evaluate to what they are defined
• E.g., if count contains 42, then the evaluation of count is 42
• A list:
• A list is evaluated by treating it as a function and performing a function call
• A quote ’ followed by a list or an atom:
• The evaluation of ‘ is whatever follows the ‘ but not evaluated
• E.g. the evaluation of ‘ (count 42 #t) is (count 42 #t)
2021-06-23 8:45 AM 14
Examples of Expressions
Expression Evaluation
“Hello” “Hello”
42 42
(+ 1 2) 3
(< 1 2) #t
‘() ()
() error
(equal? “Hello” “World”) #f
(* 2.5 4.5) 11.25
(< (* 6 5) (+ 13 17)) #f
(string-append "Hello " "World!") “Hello World!”
(/ 10.0 0) +inf.0
2021-06-23 8:45 AM 15
End of this Part
CSCI 3136
2021-06-23 8:45 AM 16
Scheme Operations
CSCI 3136
2021-06-23 8:45 AM 17
Lists and List Manipulation
• The fundamental data structure in Scheme is a linked list.
• Each node in a list is called a pair (first, rest)
• A list typically has the following structure
• The list above corresponds to (42 13 27 99)
• Standard list manipulation functions:
• car : returns first item in the list
• (car ‘(42 13 27 99)) yields 42
• cdr : returns rest of the list
• (cdr ‘(42 13 27 99)) yields (13 27 99)
• cons : prepends an item to the list
• (cons 7 ‘(42 13 27 99)) yields (7 42 13 27 99)
2021-06-23 8:45 AM 18
42 13 27 99 ()
Empty list
Variables
• Variables can be declared in several ways
• We will look at just two for now: define and let
• New variables can be defined using a define
expression
• Format:
(define variable-name expression)
• variable-name: is the variable to be defined
• expression: is the expression to be evaluated and the result
bound to variable name
• Example:
(define pi 3.14)
2021-06-23 8:45 AM 19
Creating local variables with let
• Local variables can be created using the let expression
• Format:
(let ((var1 exp1) (var2 exp2) … )
expression1
expression2
…
expressionk
)
• vari: is name of a local to be defined
• expi: expression to be evaluated and result bound to the vari
• expressionj: expressions to be evaluated using the defined variables.
• Evaluation: The evaluation of a let expression is the evaluation of the last
expression (expressionk)
• Example:
(let ((dx (- x1 x2)) (dy (- y1 y2))
(let ((dx2 (* dx dx)) (dy2 (* dy dy))
(sqrt (+ dx2 dy2))
)
)
2021-06-23 8:45 AM 20
Variable cannot be assigned
after creation (for now)
Special Forms
• Observe that define and let expressions are not like
normal Scheme functions
• Arguments passed to define and let are not evaluated
before they are passed!
• These are called special forms and are used to implement
various control structures in Scheme
• Examples of special forms:
• define : define a variable
• let : define local variables
• lambda : create a function
• if : conditional statement
• Others that we will see along the way
• Other functions such as car, cdr, cons, +, -, *, etc, are
normal functions.
2021-06-23 8:45 AM 21
Conditional Evaluation: if
• Conditional execution (or evaluation) is one of the pre-requisites for any
programing language.
• The if expression allows conditional evaluation in Scheme
• Format:
(if boolean-expression
if-true-expression
if-false-expression
)
• boolean-expression: that is evaluated to determine which expression to evaluate next
• if-true-expression: expression to be evaluated if boolean-expression evaluates to true
• if-false-expresssion: expressions to be evaluated if boolean-expression evaluates to false
• Evaluation: The evaluation of a if expression is the evaluation of if-true-
expression or if-false-expression
• Example: Compute absolute difference of a and b
(if (< a b)
(- b a)
(- a b)
)
2021-06-23 8:45 AM 22
Most operators in Scheme are
same as in other languages: <
>, equal? + – * / …
Google what you do not know
End of this Part
CSCI 3136
2021-06-23 8:45 AM 23
Functions and Recursion
CSCI 3136
2021-06-23 8:45 AM 24
Defining Functions in Scheme
• The creation of programmer
specified functions is another of the
pre-requisites for any programing
language.
• The lambda expression is a special
form that is used to specify a
function
• To bind the function to an identifier,
use define along with lambda
• Format Explanation:
• parami: is name of the i’th parameter
• expressionj: expressions to be
evaluated when the function is called.
• Evaluation:
• The evaluation of a lambda expression
is a function
• Functions are 1st class objects
• The evaluation of the function is the
last expression (expressionk)
• Format:
(lambda (param1 param2 … paramk)
expression1
expression2
…
expressionk
)
• Example: Define a function abs that
computes absolute difference of a and b
(define abs (lambda (a b)
(if (< a b)
(- b a)
(- a b)
)
)
2021-06-23 8:45 AM 25
Recursion: No loops in Scheme
• Scheme, like most functional languages has no traditional loop construct.
• For any kind of loops we use recursion.
• Recall that a recursive function consists of
• A base case (when to stop recursion)
• A recursive case (when to continue)
• Example: Count the number of items in a list:
(define list-size
(lambda (lst)
(if (equal? lst ‘())
0
(+ 1 (list-size (cdr lst)))
)
)
)
2021-06-23 8:45 AM 26
Get rest of list
Compute size of rest of the list
Add 1 to the result
End of this Part
CSCI 3136
2021-06-23 8:45 AM 27
Comments and Input
CSCI 3136
2021-06-23 8:45 AM 28
Comments
• Line comments in Scheme begin with a ;
• Example: ; This is a comment
• This is the same as the // comments in Java
• Multiline are delimited by #| comment |#
• Example:
#| Hi ho hi ho
Off to work we go
|#
• Please use comments where appropriate
2021-06-23 8:45 AM 29
Reading input in Scheme
• Reading input in Scheme is a bit of a pain.
• I have provided two functions for you to use to
read in input.
• getline : returns a single line of input from the console
(keyboard)
Example:
(display (getline))
Reads in a single line of input and displays it
• getlist : reads in a list of lines, terminated by “end” from
the console (keyboard)
Example:
(getlist)
Reads in a list of lines and returns the list.
2021-06-23 8:45 AM 30
Input Resulting list
1 2
3
4 5
end
(“1 2” ”3” “4 5”)
Loading Provided Code
• I provide you with a file called “io.scm”, which
contains the two functions getline and
getlist
• To load the code use the scheme function load
• Example: (load “io.scm”)
• Once loaded, you can use the above functions in
your program.
• Please feel free to look at the code to see how it
works.
2021-06-23 8:45 AM 31
More examples to work through
• Factorial
• Fibonacci
• Towers of Hanoi
• Reverse a list
• Binary Search
• Binary Tree Insert
2021-06-23 8:45 AM 32
End of this Part
CSCI 3136
2021-06-23 8:45 AM 33
References
• By User:Luks - The Greek alphabet, Public Domain,
https://commons.wikimedia.org/w/index.php?curi
d=502579
2021-06-23 8:46 AM 34
https://commons.wikimedia.org/w/index.php?curid=502579