CS计算机代考程序代写 DrRacket scheme data structure Java interpreter Lecture_16_Scheme

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