COS 333: Chapter 15, Part 2

Summary

This lecture delves into functional programming with Scheme, focusing on numeric predicate functions, control flow, and list operations. It explains how predicate functions return boolean values and introduces control structures like 'if' and 'cond' in Scheme. The lecture also covers list manipulation functions such as 'quote', 'car', 'cdr', and 'cons', highlighting their importance in functional programming. Additionally, it discusses recursion as the method for repetition in Scheme, due to its lack of loop support, and provides an example of implementing the 'member' function recursively to check for an element within a list.

Takeaways

• 📚 The lecture continues the discussion on functional programming with a focus on the Scheme programming language, building upon concepts introduced in the previous lecture.
• 🔢 Introduction to numeric predicate functions in Scheme, which are functions that return a boolean result and operate only on numeric literal values, not symbolic literals.
• 🌐 Scheme's approach to control flow is explored, highlighting the absence of traditional loops due to its pure functional nature and the use of recursion for repetition.
• 📈 The 'if' function in Scheme is detailed, emphasizing its role as a selector function akin to 'if' statements in imperative languages, with a unique application to three parameters based on a predicate result.
• 🔄 The 'cond' function is presented as Scheme's method for multiple selections, similar to a 'switch' statement, evaluating predicates in sequence until one is found to be true.
• 📝 The importance of list operations in Scheme is underscored, with functions like 'quote', 'list', 'car', 'cdr', and 'cons' being fundamental for list manipulation.
• 🔑 The 'quote' function is explained as a means to prevent evaluation of list parameters, allowing them to be treated as literal data rather than function applications.
• 🔍 Predicate functions for lists, such as 'list?' and 'null?', are introduced as essential for determining the nature and state of list structures within Scheme programs.
• 🔗 The 'cons' function is described as a critical tool for constructing lists, allowing for the creation of new lists with elements added in a specific order.
• ⚖️ The 'eqv?' and 'eq?' functions are contrasted, with 'eqv?' performing value comparisons and 'eq?' performing pointer comparisons, affecting how equivalence is determined.
• 🛠️ The 'let' function is introduced as a way to create local bindings within Scheme, allowing for the evaluation of expressions in the context of these bindings.

Q & A

What is the main focus of the second lecture on Chapter 15?

The main focus of the second lecture is to continue the discussion on Scheme programming language within the context of functional programming, specifically covering numeric predicate functions, control flow, and list operations.

What is a predicate function in Scheme?

A predicate function in Scheme is a function that produces a boolean result, either true or false.

How does Scheme represent true and false values?

In Scheme, 't' represents a true value, '#f' represents a false value, and an empty list is also interpreted as false, while a non-empty list is interpreted as true.

What are some of the numeric comparison functions provided by Scheme?

Scheme provides comparison functions such as 'equals', 'less than', 'greater than', 'not equals', 'greater than or equal to', and 'less than or equal to'.

How does Scheme handle control flow for selection and loops?

Scheme handles control flow using functions like 'if' for two-way selection and 'cond' for multiple selections. It does not provide loop structures because it is a pure functional programming language without support for variables, so repetition is handled through recursion.

What is the purpose of the 'quote' function in Scheme?

The 'quote' function in Scheme is used to avoid parameter evaluation, ensuring that lists are treated as literal data rather than function applications.

What are the 'car' and 'cdr' functions in Scheme used for?

The 'car' function is used to access the first element of a list, and the 'cdr' function is used to access the rest of the list after the first element.

What is the 'cons' function in Scheme and how is it used?

The 'cons' function in Scheme is used to construct a new list by placing its first parameter as the first element and appending the elements of the second parameter list to it.

What is the 'let' function in Scheme and how does it work?

The 'let' function in Scheme is used to create local bindings for names with associated expressions. It evaluates the expressions, binds the values to the names, and then evaluates the body using these bindings.

Can you provide an example of a recursive function in Scheme?

The 'member' function is an example of a recursive function in Scheme. It checks if an atom is contained within a list by recursively comparing the atom to each element of the list and eliminating one element at a time until a match is found or the list is empty.

What is the importance of the order of base cases and recursive case in a 'cond' expression in Scheme?

The order in a 'cond' expression is important to ensure that base cases are checked first before the recursive case to avoid non-terminating recursion. Additionally, checking for an empty list with 'null' should come before checking for equality to prevent unnecessary evaluations.

Outlines

00:00

📚 Introduction to Scheme Programming and Functional Concepts

This paragraph introduces the second lecture on Chapter 15, focusing on functional programming with the Scheme programming language. The lecture builds on general functional programming concepts and the Lisp language, then delves into Scheme's basic numeric functions, custom function definitions, and output functions. The speaker outlines the lecture's agenda, which includes numeric predicate functions, control flow, list operations, and implementing a Scheme function from scratch. Predicate functions in Scheme are discussed, highlighting their boolean results and the use of 't' for true and '#f' for false, with lists also playing a significant role in boolean logic.

05:02

🔢 Scheme's Numeric Predicate Functions and Control Flow

The paragraph explains Scheme's numeric predicate functions, which are used for comparisons and include 'equals', 'less than', 'greater than', and others. It emphasizes that these functions operate on numeric literals and not symbolic literals. The paragraph also covers Scheme's control flow, noting the absence of traditional loops due to the language's pure functional nature. Instead, Scheme uses 'if' for two-way selection and 'cond' for multiple selections, with examples provided to illustrate their usage. A divide function example demonstrates the application of 'if' in handling potential division by zero errors.

10:04

🔄 Scheme's List Operations and Recursion

This section discusses list operations in Scheme, a core data structure in the language. It introduces the 'quote' function, which prevents evaluation of lists as function applications. The 'list' function is explained for constructing new lists, and the 'car' and 'cdr' functions are described for accessing the first element and the rest of the list, respectively. The paragraph also touches on the immutability of lists in Scheme and the importance of proper list processing to avoid errors, especially when reaching the end of a list.

15:06

🔧 List Manipulation with 'cons', 'list?', 'null?', and 'eqv?'

The paragraph delves into the 'cons' function, which creates new lists by adding an element to the front of a list without modifying the original list. It also introduces the 'list?' predicate function for checking if a parameter is a list and the 'null?' function for checking if a list is empty. Additionally, the 'eqv?' function is explained for testing the equivalence of two values, applicable to both symbolic and numeric atoms, but not for lists. The importance of using 'eqv?' over 'eq?' for value comparison is highlighted, especially when dealing with different data types like floats and integers.

20:08

📝 The 'let' Function and Recursive List Operations in Scheme

This paragraph introduces the 'let' function in Scheme, which allows for local binding of names to expressions within its body. It provides examples of using 'let' to perform computations with bound names and emphasizes that these names are not variables in the traditional sense, as their values are bound only once. The paragraph also presents the 'member' function, an example of a Scheme function implemented recursively to search for an atom within a simple list. The recursive nature of the 'member' function is explained, along with its base cases for an empty list and when the atom is found, and the recursive case for continuing the search through the list.

25:11

🔍 Recursive Function Implementation and 'cond' Order Importance

The final paragraph concludes the lecture by summarizing the recursive implementation of the 'member' function, which checks for the presence of an atom in a list. It discusses the importance of the order of cases in the 'cond' function, where base cases must precede the recursive case to ensure termination of the recursion. The paragraph also highlights the significance of performing the 'null?' check before the equivalence check to avoid unnecessary evaluations. The speaker invites the audience to consider the consequences of reversing these orders and ends the lecture with a preview of upcoming topics on recursive functions and list operations.

Keywords

💡Functional Programming

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. In the video, this concept is central as the lecture delves into Scheme, a functional programming language, discussing its features and how it differs from imperative programming languages.

💡Scheme Programming Language

Scheme is a minimalist, general-purpose, multi-paradigm programming language that supports functional programming. The script focuses on Scheme, exploring its functions, control flow, and list operations, which are fundamental to understanding the language's capabilities and usage.

💡Predicate Functions

Predicate functions are functions that return a Boolean value, typically used to test certain conditions. In the script, numeric predicate functions in Scheme are discussed, which are crucial for understanding how to perform comparisons and tests within the language.

💡Control Flow

Control flow refers to the order in which individual statements, instructions, or function calls are executed or evaluated. The script explains how Scheme handles control flow without traditional loop constructs, instead using recursion and functions like 'if' and 'cond' for decision-making.

💡List Operations

List operations are functions that manipulate list data structures. The script discusses Scheme's functions for performing operations on lists, such as 'car', 'cdr', and 'cons', which are essential for working with this core data structure in Scheme.

💡Recursion

Recursion is a method of solving problems where a function calls itself as a subroutine. Since Scheme does not support loops, recursion is used for repetition and is highlighted in the script as a fundamental concept for implementing iterative processes in Scheme.

💡Quote Function

The 'quote' function in Scheme is used to prevent the evaluation of expressions, allowing the programmer to treat lists as data rather than code. The script explains its importance in avoiding the interpreter's default behavior of evaluating all parameters.

💡Cons Function

The 'cons' function in Scheme is used to create a new list by adding an element to the front of an existing list. The script illustrates how 'cons' is used in list construction and emphasizes the importance of using it with lists as the second parameter.

💡Car and Cdr Functions

In Scheme, 'car' and 'cdr' are functions that access the first element and the rest of the elements in a list, respectively. The script explains how these functions are used to manipulate and access list elements, which is crucial for understanding list processing in Scheme.

💡Let Function

The 'let' function in Scheme is used to create local bindings of identifiers to expressions, allowing for the creation of block-scoped variables. The script demonstrates how 'let' is used to bind names to values for a limited scope within a function body.

💡Member Function

The 'member' function is a Scheme function discussed in the script that checks if an element is part of a list. It illustrates the use of recursion in Scheme to perform operations that would typically require loops in other languages.

Highlights

Introduction to the second lecture on Chapter 15 focusing on functional programming and the Scheme programming language.

Continuation from the previous lecture, emphasizing basic numeric functions and defining custom functions in Scheme.

Explanation of numeric predicate functions in Scheme that return boolean results.

Discussion on Scheme's handling of control flow without traditional loops, utilizing recursion instead.

Introduction of the 'if' function in Scheme, acting as a selector similar to 'if' statements in imperative languages.

Use of the 'cond' function for multiple selections, analogous to switch statements.

Coverage of list operations, fundamental to Scheme as a core data structure, with functions like 'quote', 'list', 'car', 'cdr', and 'cons'.

The 'quote' function's role in avoiding parameter evaluation, with shorthand notation using an apostrophe.

Description of the 'car' and 'cdr' functions for accessing list elements and their implications for list processing.

The 'cons' function for constructing new lists and its importance in recursive list processing.

Predicate functions for lists, such as 'list?' for checking if a parameter is a list and 'null?' for checking if a list is empty.

Differences between 'eqv?' and 'eq?' functions for testing value and object equivalence, respectively.

The 'let' function for local bindings within Scheme and its evaluation process.

Recursive implementation of the 'member' function to search for an atom within a simple list.

Importance of the order of base and recursive cases in recursive functions to prevent non-terminating recursion.

The significance of checking for an empty list before performing equality checks in recursive list processing.

Conclusion and preview of the next lecture, which will cover more examples of recursive functions on lists.

Transcripts

this is the second lecture on

chapter 15 where we'll continue with our

discussion

on functional programming specifically

once again focusing on the scheme

programming language

in the previous lecture we covered some

underlying concepts related to

functional programming in general and we

briefly touched on the

lisp programming language we then moved

on to the main focus

of these lectures which is the scheme

programming language

we looked at some basic numeric

functions which we can use to perform

arithmetic operations then we looked at

how to define

our own functions and we finished off by

looking

at some basic output functions

in this lecture we'll continue with our

discussion on scheme

starting off with some coverage

on numeric predicate functions a

predicate function in scheme

is essentially a function that produces

a boolean result we'll then take a look

at how scheme deals with control flow

after which we'll move on to some

functions that perform operations

on lists these functions are very

important

for some of the function implementation

examples that we'll look at right

towards the end of this lecture

and in the next lecture

we'll then look at some predicate

functions for

lists after which we'll look at some

additional predicate

functions that are used to test for

equivalence between values

we'll then look at the let function and

finally we'll look at our first example

scheme function which we will implement

from scratch

we'll start by discussing numeric

predicate functions

in scheme but before we can do this we

need to talk about

predicate functions in general and how

they are handled within scheme

so as i've previously mentioned the

predicate function is simply a function

that defines

a boolean value in other words a true or

a false value now of course scheme also

provides literal boolean

values so in scheme t is

a true value and hash f is

a false value an empty listing scheme is

also interpreted as a false value

and then a non-empty list in other words

a non-null list

is interpreted as a true value now

in general we won't be using these list

conventions

we will in most cases be using t

or hash f to represent a literal boolean

value

so scheme provides a number of built-in

predicate functions

for numbers and it's important to

understand that all of these functions

work

only for numeric literal values not

for symbolic literals

so we have then a number of comparison

functions

and again please note that as with

everything in scheme

these are functions they are not

operators

as they would be in an imperative

programming language

such as c plus so we have the equals

function

which tests for equality of its

parameters

less than greater than which is the not

equals function

greater than less than greater than or

equal to

and less than or equal to

so these functions should be applied to

at least

two numeric parameters but they can also

be applied to

more parameters so for example if we

were to apply

the equals function to five parameters

then all five of those parameters would

have to have equal values

for the equals function to define

a true value in a similar fashion the

not equals function if it were applied

to

multiple parameters would then require

all of those parameters to not be equal

to each other

in order to define a true value

if we look at the remaining

inequalities so for example let's look

at

the less than function if that were to

be

applied to multiple parameters then it

would mean that the first parameter has

to be less than

all of the remaining parameters the

second parameter would have to be

greater than the first parameter but

less than all of the remaining

parameters

and so on and so forth we also then

have four functions that are applied to

a single numeric value we have even

which of course produces a true value if

the parameter is even

odd does the same thing but for odd

values

0 will define a true value if the

parameter

is a zero value and negative will

produce a true value if the parameter is

a negative value also note the question

marks at the end

of the function names there

now scheme also provides a not function

and this is applied to a boolean

parameter

and it simply inverts the logic

of the boolean expression that is its

parameter

so if the parameter evaluates to

a true value then not will produce a

false result and vice versa

we'll now move on to control flow and

how it is handled in

scheme so scheme only provides functions

for selectors in other words

functions that operate like if

statements

or switch statements in an imperative

language

scheme does not provide any support for

loops

because as we've previously seen loops

require loop control variables

and scheme is a pure functional

programming language

which means that it doesn't support any

variables

at all so first of all scheme provides

an

if function and once again note that

if is a function it is

not a statement as it would be in an

imperative programming language

so the if function then is used

for two-way selections and we

apply then the if function to

three parameters the first parameter is

a predicate

so it must evaluate to a value which is

either true or false and then we have

two expressions the then expression

and the else expression and these

are then evaluated as you would expect

in a regular if statement so if the

predicate

is true then the entire if function

evaluates to the value of the

then expression if the predicate is

false

then the entire if function evaluates

to the value of the else expression

so here's an example then of how we

would use

the if function first of all we have

this define function application and as

we've seen in the previous lecture

this simply creates an

unnamed function and then binds a name

to that function

so we are creating a function called

divide

and it is applied to two parameters the

first parameter is called numa

and the second parameter is called denom

then we have the body of the function

and this is then

a single application of the if function

and here we have our predicate so here

we've used then

the basic not equals function

which is applied to two numeric

parameters firstly there's the nom

and then the second parameter is zero

so this will then only evaluate to true

if the denominator is not equivalent

to zero if this is the case then we get

to our then expression and we can see

that this is another

function application in this case the

divide

function which is then applied to two

parameters

numa and denom so this will then

actually

perform the division between the two

values

and then the entire if function will

evaluate to the result

of that division which means that the

application of our divide function will

then also

evaluate to the result of that division

however

if our predicate is false

in other words the denominator is

zero then in that case we have a

situation where the division would have

produced an

error so in that case we then move on to

our else expression over here

and we can see that our else expression

is a simple value

in this case a numeric atom

which is zero so in other words if the

predicate

then evaluates to false then the entire

if function

will evaluate to zero which means the

application

of our divide function will also then

evaluate to 0. so in other words what

we've done is we have defined a function

that receives two parameters

and if the denominator is zero

then the function will evaluate to zero

if

it is not zero then the first parameter

is divided by

the second parameter

scheme also provides support for

multiple selection

by means of the conf function and the

operation of the khan function

is similar to that of a switch statement

in an imperative programming language

so over here we can see the syntax of

the

cond function we can see that cond is

applied

to a number of parameters and the number

of parameters is not fixed so we can

have

any number of parameters where each

parameter then

is a pair the first

part of the pair is a predicate so

this must be something that evaluates to

a true or a false value and then

following the predicate

we have an expression so the semantics

for a cond then involves the evaluation

of each predicate from top to bottom

and once the first predicate is found

that evaluates to true

then its accompanying expression is

evaluated

and then the result of that expression

becomes the result

of the cond function now of course it's

possible

that none of the predicates may be true

and in this case we then have the

optional else expression at the bottom

here

so here we have then else which is

essentially a predicate that is

always true and then we have an

expression that

is paired with that so in a situation

where

none of the predicates are true then the

expression

paired with the else will be evaluated

and then the result of that expression

becomes the result

of the cond if no else

is provided and none of the predicates

evaluate

to true then the result is unspecified

and this generally then causes an error

so in general we will always provide

an else expression in

any con that we implement within scheme

so we've looked at selection and

multiple selection in scheme

the last remaining kind of control flow

is repetition

which in an imperative programming

language is handled by means

of a loop now as we've seen scheme is a

pure functional programming language so

this means

it does not support variables in any

form

and therefore as a result we can't have

loop control variables

and therefore we can't have loop

structures

so because of this scheme does not

provide

any kind of loop function instead all

repetition is handled by means

of recursion and we'll see this in terms

of

the example function implementations

that will get to

at the end of this lecture and then the

beginning of the next lecture

we've so far looked at numeric predicate

functions

and how scheme deals with program

control flow

we'll now move on to functions that

perform

operations on lists and as we've seen

previously

lists are a core data structure within

the scheme programming language

and therefore functions that perform

operations on these lists

are crucial now the first function that

we'll look at is a primitive function

provided

by scheme and this function is called

quote

for us to understand how the quote

function works we need to look back at

two

concepts that we discussed in the

previous lecture

so first of all we need to look at the

scheme interpreter and how it deals with

function

applications and what we saw in the

previous lecture

was that the scheme interpreter will

always

evaluate all of the parameters for

a function application

next we need to remember that lists and

functions have exactly the same form in

scheme

so over here we have a list that

contains

three symbolic atoms as elements

and these symbolic atoms are a b and c

over here we have a function application

so this is an application of the member

function

to two parameters the symbolic atom a

and something called list

now as far as scheme is concerned it

can't

tell these two apart from each other so

it is equally valid to interpret this

list as the application of a function

called

a to two parameters b and c

and we can also then interpret this

function application

as a list that contains three elements

member

a and list

so what this means then is that whenever

we want

to use a list as a parameter

for a function application then we have

to

prevent the scheme interpreter from

evaluating this list as a

function application

so this is then where the quote

primitive function

comes in so the quote primitive function

is used

to avoid parameter evaluation whenever

it

is not appropriate the quote function

takes one parameter and it returns this

parameter

without any evaluation

so here we then have an example let's

look at the scheme code over here

and this is then an application of the

foo function to a parameter

which is a list containing three

elements

a b and c now

if we were to provide the code as it

appears

here to the scheme interpreter then the

scheme interpreter will first

try to evaluate the parameter of the

foo function and this evaluation will

then involve the application of a

function called

a to two parameters b and c

now what will normally happen in this

case is that a function called a

does not exist and therefore the

interpreter will produce an

error saying that you are attempting to

apply a function

that it doesn't recognize so instead

we should then use the quote function as

we see over here

so once again we are then applying the

foo function to one parameter but now we

are applying the quote function

to this list over here and what this

will do then

is it will ensure that the list is not

evaluated by the interpreter

and therefore it's dealt with simply as

a list that contains

three elements and that will then be

the parameter to which the foo

function will be applied now of course

it's quite a mouthful and a lot of

typing to

have to provide the full

function name quote every time that we

want to do this and of course we will be

using the quote function fairly

regularly in our programs

so as a result of this scheme then

provides a

shorthand notation so the application

then of the quote function

to a parameter in this case a list

containing two elements a and b

can be abbreviated as you can see over

there with a single apostrophe

and then followed by the list

so in general from this point on we will

be using this

shorthand apostrophe notation rather

than

the full function name quote

next we have the list function and the

list function

is used to construct a new list

so the list function is applied to any

number of parameters

and then it simply constructs a new list

and it places the parameters in order

into the list as elements so over here

we have two examples

of the use of the list function over

here

we are applying list to three parameters

and these parameters are symbolic atoms

now notice that we have quoted each of

those parameters

and the reason that we have to quote

them is that if we don't

they are interpreted as names

so a name would have been bound using

the define function which we discussed

in the previous lecture

of course a b and c have probably

not been defined as names with values

bound to them

and therefore the scheme interpreter

would

again report an error so if we

then quote these symbolic atoms it means

they shouldn't be

evaluated in other words they shouldn't

be interpreted as names

which means that they are then simply

placed into

the new list which is yielded by the

application of the list function

so the result of this thing would be a

list containing the

three symbolic atoms a b and c

over here we have another use of the

list function so again

we've applied this function to three

parameters the first two parameters

are again symbolic atoms and once again

they

need to be quoted then the third

parameter

is a list and of course we have to quote

this list otherwise

it will be interpreted as a function

application

of a function named c which is not

defined

so this thing yields the following list

over here so we can see that we have

then two symbolic

atoms as the first and second elements

within this list

and the third element is then a nested

list next we have two very important

list functions

the first is named car which is usually

pronounced

car the second is named cdr which is

usually pronounced

cuda or kada i will be saying kuda for

the remainder of this lecture

and the next lecture now as to where the

names of these functions come from they

are

abbreviations that refer to hardware

related details

for the ibm 704 computer which the lisp

programming language was

first designed to run on so

car stands for content of address part

of register

and cdr stands for content of decrement

part

of register now these details are not

important for our purposes

i simply mentioned them in case you are

curious as to where the function names

come from

so the car and cuda functions are both

applied to a single parameter

which should be a list the car function

yields the first element of its list

parameter

so over here we have a couple of

applications

of the car function here we have car

applied to a simple list that contains

three symbolic atoms

note that we have to quote this list and

this is to prevent the scheme

interpreter

from evaluating the list as though it

were

a function application so the result

then

of applying card to this list is the

symbolic atom a

which as we can see is the first element

contained within this list

note that we are not yielding

a pointer or a reference into the

parameter list

this is an entirely separate value that

is produced as a result

over here we have an application of the

car function to another list but this is

a slightly more complex list

the first element in the list is a sub

list or a nested list

so the result of this application then

is

a list containing the symbolic

atoms a and b and that is because the

first element in the parameter list is a

list containing the symbolic atoms a

and b now notice that applying the car

function to anything

that is not a list in this case a

symbolic atom will produce an error

also if we apply a card to an empty list

then an error will be produced

next we have the cuda function and the

cuda function

performs essentially the opposite

operation

to the car function so cuda

yields the remainder of its list

parameter after the first

element has been removed again it's

important to understand

that an entirely new list is produced as

a result

it's not a reference into the parameter

list also important to

note at this point is that lists in

scheme

are immutable so in other words

we are not modifying the parameter list

we are returning an entirely new list as

a result

so over here we have then a couple of

applications of the cuda function

here we are applying cuda to the

list containing three symbolic atoms a b

and c

so we then ignore the first element a

and

only consider the tail elements b and c

and we then yield a list containing

those

elements so the result then is a list

containing the symbolic atoms

b and c here we have cuda applied

to a more complex list and again the

first element

is a sub list and then that is followed

by two symbolic atoms

c and d as we can see there so we then

discard the first element which is the

nested list

and therefore the result is a list

containing the two symbolic atoms

c and d now interestingly if we apply

cuda to a list that contains a single

element

then the result is an empty list

so in other words we should think of

lists

in scheme as a sequence of

elements and then implicitly there is a

last element which

is an empty list now

this kind of behavior may seem strange

but

it's very useful in determining when we

have processed

through all of the elements in a list

parameter

so typically what will happen is in

a function that processes a list we will

discard

elements from the list one by one and we

can then determine once we've

reached the last element in the list

when a cuda on that list yields an

empty list as a result this means then

we have one single element

left to process now also

as with the car function if we apply

cuda to anything other than a list in

this case

a symbolic atom then an error will be

produced

and also if we apply cuda to an empty

list

then an error will be produced now this

last example is quite important

because it is the source of quite

common errors related to list processing

and so if you are processing through all

of the elements within a list

but then there's an error that is

generated for the last element

this generally means that the base case

for your recursive processing of the

list

is incorrect you are eliminating the

last element in the list

and then still continuing to process

beyond that

the next list function we'll look at is

the cons function

and this is again a very important

function which we will see

used repeatedly in the coming examples

so the cons function is applied to two

parameters

the first parameter can either be an

atom or a list

and then for our purposes the second

parameter will be

a list it is possible to use an atom

as the second parameter but as we'll see

this doesn't yield a result that is

useful

to us so the cons function

then generates a new list

and it places its first parameter into

the new list as the first element and

then the elements

in the second parameter list are

inserted as the remaining elements

in the new list it's important to note

that the result

of the cons function application is

a new list so we do not modify

the second parameter list

so over here we have some applications

of the cons function

here we are applying const to two

parameters the first parameter is a

symbolic atom

a and the second parameter is a list

containing the symbolic

atoms b and c so over here we have then

the result of this application of the

cons

function we can see that the symbolic

atom a has been inserted as the first

element

and the remaining elements are the

symbolic atoms b

and c which were originally contained in

the second parameter list

here we have another application of the

cons function this time to

two lists and this is the result that is

produced so

notice that the first parameter which

is a list is inserted as the

first element within the resulting list

so in other words we have created

a complex list where the first element

is

a nested list note that c

and d are the remaining elements within

the list

and those are the elements that were

contained in

the original second parameter list

here we have an application of the cons

function once again to two lists

but the first parameter is an empty list

and we see that the result produced then

has the empty list as the first element

within that list so this empty list in

other words then is not discarded

and ignored it is inserted as an element

but this element is a list that contains

nothing now notice

that we then in general only use

lists as the second parameter for

the cons function here are

examples where we apply the const

function

to a second parameter which is a

symbolic

atom so here we are are applying const

to

two symbolic atoms a and b and this

yields what's referred to as

a dotted pair and this is what the

dotted pair looks like

so we have a and b but we have this dot

symbol

between them so a dotted pair

is not a normal list that we would

generally

work with in scheme a dotted pair

is specifically a pair of

two elements that are grouped together

as a whole

over here we have another application of

the cons function

this time again to two parameters where

the first parameter is a list

but the second parameter is a symbolic

atom

c in this case and again this yields a

dotted pair because the second parameter

is not a list and this is what the

dotted pair looks like so in general

if you are writing a function that

constructs

a list element by element and you see

that the

result has full stops contained in it

it means in general that you are

probably applying the

cons function to some element that you

are inserting

into what you think is a list but the

thing that you are inserting into is in

fact

an atom this is generally an incorrect

result

so you will need to debug your program

in order to ensure that you are only

applying cons

to a second parameter which is a list

in all cases

we'll now move on to two predicate

functions

that are intended for lists

the first predicate function is the list

function

note again that it has a question mark

at the end of its name

and the list function is applied

to one parameter it yields

a true result if the parameter is a list

and a false result otherwise

a more useful function for our purposes

is the null function again note that it

has a question mark

at the end of its name and the null

function

is again applied to a single parameter

and yields a true result if the

parameter

is an empty list otherwise it yields a

false result now it's important to note

that the parameter must be completely

empty in order to yield

a true result so if we

apply null to a single empty list

as we see over there then the result

will be

true however if we apply it to

a list containing an empty list we are

no longer applying it

to an empty list and therefore the

result

will be false now this

null predicate function is again fairly

often used

as a base case for recursive functions

that perform processing

on lists in general at least one of the

base cases would be

if the list is empty

next we will look at two predicate

functions

that are used to test the equivalence of

two things so first of all we have the

eqv function notice the question mark at

the end of the function

name and this predicate function is

applied to two parameters and yields

a true result if the values of the two

parameters

are the same so note that this is a

value comparison it's not a pointer or

reference comparison so in other words

we are testing to see where the two

values are equivalent to each other not

whether the two parameters

are in fact the same object in memory

now the eqv function works for both

symbolic

and numeric atoms so here we have some

examples of how the eqv function would

be used

here we are applying the eqv function to

two numeric atoms and the first

is three and the second is three so of

course the values of these two

parameters

are the same which means that eqv

then yields a true result

here we have an application of the eqv

function

again to two parameters which are atoms

but in this case we have symbolic atoms

we are comparing a to a and again these

two values are the same

so the result of this function

application

is true here we are again

performing an eqv test on

two symbolic atoms but here they are

different so the first

is a and the second is b of course

here the two values are then different

so

the result of this function application

is then false

finally we have a more complex

application of the eqv

function so here the first parameter is

the numeric atom 3.4 and the second

parameter

is a function application of the

plus function the plus function is

applied to two parameters

these are both numeric atoms 3 and 0.4

and so of course the result of this

addition function

application is 3.4 which is the same

value

as the value of the first

parameter so because these two values

then are equivalent

the result of this eqv function

application

is true again now it's important to note

that the eqv

function does not work for lists so here

we are

applying the eqv function to two lists

and we can see that

both lists contain the same

elements namely the

symbolic atoms a and b even though these

two lists are equivalent to each other

the result that is produced by the

function application

is false so in other words the eqv

function should never be used for

comparing

where the two lists contain the same

elements

now it's important also to note that

floats

and integers are different values

so if we apply the eqv function

to 3.0 as the first parameter

and three as the second parameter

because we are comparing

a float value to an integer

value we are comparing two different

values

and therefore the result is false

so in general we should rather use

the equals function when we are

comparing numeric values

to take care of cases where we may be

comparing floats to integers or

vice versa so in this case here we have

an application of the equals function

to 3.0 and 3 as the parameters

and in this case the result that is

yielded

is a true value

the second equivalence predicate we'll

consider

is the eq function again notice

the question mark at the end of the

function name

and the eq function like the eqv

function

is applied to two parameters

now the eq function will only yield

a true result if the two parameters

are the same object in memory so in

other words this is a pointer comparison

not a value comparison so here are some

examples of the application of the eq

function here we are comparing

two symbolic atoms to one another

and the symbolic atoms are the same so

we have the symbolic atom a

compared to the symbolic atom a so

it turns out that scheme then will store

the same symbolic atom as the same

object within memory

and so the result of this comparison

is a true value

if we compare two symbolic atoms that

are different from one another so here

we're comparing a

to b then the result is false because

these will obviously be

two separate objects in memory

and here we have a third application

where we are comparing a symbolic atom

to a list obviously these two must be

different values in memory

so the result produced by this function

application

is false now notice

that for two list parameters the result

is

not reliable so if we apply for example

the eq

function to two lists where the two

lists contain

the same values then this may yield

a true or a false result

this depends largely on the specific

context within the

program that eq is being used and it

also depends

on the scheme interpreters

implementation

so essentially the result of this kind

of comparison

is unreliable also

the eq function is not reliable for

numeric atoms so over here we have the

eq function applied

to 3.4 as the first parameter

and then an application of the addition

function

to 3 and 0.4

so these values then are of course the

same

but this may then be a case

where the two values are represented as

separate objects in memory

or possibly the same object so

again the result is unreliable and this

function application may yield

a true or a false result

so in general due to this uncertainty

in multiple instances

the eqv function is usually more

appropriate than the eq function

so the bottom line is if you use the eq

function in a scheme program you must be

very sure that this is the function that

you intend to use

and that you know what you are doing

with this function's application

the next function we'll look at is the

let function

also provided by scheme itself

and this is the general syntax

of the let function so we apply the let

function

to a list followed by a body

and the first list then contains

a series of pairs where we have

a name and an associated expression

within each pair we can have as many

pairs

as we wish so the way that the slit

function

then is evaluated is that the

lists of names and expressions

is run through from top to bottom each

expression

is evaluated and then the value

of that expression is bound to the name

that it is associated with

so in this example we would first

evaluate expression one

and then the value of that expression

would be bound

to name one then we would move on to

expression two which would be

evaluated and then the value of that

expression is bound to

name two and so on and so forth

then finally the body is evaluated after

all of the name bindings

have occurred and the body can then use

any of the names included in the first

part of the let function

finally the lit construct then yields a

result

and that result is the value

of the body once it has been evaluated

here we have two examples of how the let

function could be used

so we'll start by looking at the left

example

in this example we use the define

function to create

a named function which is called

computation

and this is applied to four parameters

a b c and d in the body

of our function we have an application

of the

lead function and the first portion

of the let function performs a series of

bindings

so first of all we add parameter a

to parameter b and the result of that

addition

is then bound to the name top

secondly we then apply the subtraction

function to the parameters

c and d and the result of this

subtraction is then bound to the name

button so again it's very important to

understand that top and bottom are not

variables as one would use

them in an imperative programming

language instead

they are only names the value

that is bound to each of those names is

only bound once and it is impossible to

bind

another value to top or bottom after

this first

binding has taken place so

after the bindings we then have the body

of

our lead function which is over there

and here we then can use the

names that we've bound to in the first

part of the late function

so here we use top and bottom and we

divide top by bottom the result of this

division

then becomes the result of the entire

lead function application and then

because the let function is the

only function application that occurs in

the body of

our computation function the result of

the division then is also

the result of the application of our

computation

function now it is also possible to have

multiple function

applications in the body of our lead

function

and in this case these function

applications are evaluated in sequence

and then the let construct yields the

value

of the last function application

so that is illustrated in the second

example

on the right over here here again we are

defining a function called computation

and applying it to four parameters a b c

and d and inside the body of our

function we only have an application of

the let function again we perform

the same bindings to top and bottom as

we saw

in the previous example however now we

can see that there are three

function applications in the body of

our lit so first of all we have an

application of the display function

and this then will display the result

of performing a division where top

is divided by bottom then we have

a new line so this will then print a new

line

out to the terminal so so far we've

printed out

then a division result and a new line

and then we get this final function

application which is an application of

the multiplication function

and we multiply top and bottom which

again

are the two names that we have bound to

in the first part

of our lit now note that this last

function application

is not printed out by means of a

display function instead this

is the last function application and

therefore

the entire let evaluates to the result

of this multiplication and because the

let

is again the only function in the body

of our computation function

the application of our computation

function then

also evaluates to the result of this

multiplication

finally we'll look at our first full

implementation

of scheme function in which we will

recursively operate on a list

this function is called member and it is

applied to

two parameters the first parameter is an

atom

while the second parameter is a simple

list a simple list is a list that

contains

only atoms in other words it doesn't

contain

any nested sub-lists the member function

should produce a true result if the atom

is contained within the list

and a false result otherwise

so this specification implies that we

need to work

through the list one element at a time

and in an imperative programming

language we would use

a loop in order to do this however as

we've seen

scheme is a pure functional programming

language

which means that it doesn't provide any

loop

structure in other words when we work

through the list

we must do so recursively

so how will we attack this problem well

we will recursively

compare the atom provided as the first

parameter

to the member function to each atom

contained within the list eliminating

one atom from the start of the list at a

time

we then have two base cases the first

base case is if we find a match between

the atom that is the first parameter

of the member function and the current

atom

in the list that we are considering

if this is the case then we know that we

have

found the atom and therefore we don't

need to search the remainder of the list

we can then simply produce a true result

now if we process through the entire

list without having found

any matches between the atom parameter

and any atom contained within the list

then we

know that the atom is not contained in

the list at all

and in this situation we can then

evaluate to a false result

so over here we have the implementation

of our member function

we use a define and we specify that the

name of the function

is member and there are two parameters

atm and lis atm is the atom that we are

searching for

and lis is the list that we are

searching

now note that we don't provide any types

for these parameters at all

the type of each parameter is implied by

means of how the parameter is used

within the function

so then we have a cond the cond

is our selection structure and this is

responsible

for deciding whether we execute one of

the two base

cases or the recursive case

over here we have our first base case

here we are testing to see whether our

list is empty by means of the

null function so if this predicate then

evaluates

to true it means that we have reached

the end of our list without having found

a match and in this case we can then

just produce

a false result the entire cond will then

evaluate to false

which means that the application of our

member function

will also evaluate two false

our second base case is over here so

here we perform

an equivalence comparison between

the atom provided as the first parameter

and the car of our list the car of the

list will be

the first element within the list so if

we find a match between that

and the atom that we've provided as the

first parameter of our member function

we know that we have found our atom

and therefore we can terminate our

search

and simply then produce a result of

true finally in the else portion of the

cond

we have our recursive step and here

we then execute our member function

recursively

with the same atom as the first

parameter we obviously don't want to

change the atom that we

are searching for but then the list that

we perform

the search on must have the first

element removed and this is because at

this point we know that there isn't a

match between the first element

and the atom provided as the first

parameter for

our member function so we then use the

cuda function

in order to get the tail of the list

discarding the

first element and this will then

continue the search

with the next element within the list

so this then overall is our member

function definition however let's look

at our cond in a bit more detail

so in our cond the order

of our cases is important

we must provide all of our base cases

first before our recursive case

and so what i'd like you to do is to

think

about what would happen if we provided

the recursive case

first and the base cases following the

recursive case

what would occur is we would have a

non-terminating recursion

but i want you to think about why this

would be the case

next the order of our base cases is also

important we must provide

our null check first and then

our equality check after that

so what i would like you to do again

here

is think about what would happen if we

performed the quality check

first and then the null check after that

and as a hint consider what would happen

to

this application of the car function

if we were to place this second base

case

first all right so

that then concludes our discussion

for this lecture in the next lecture we

will move on to

a few more examples of

recursive functions that perform

operations on

lists and we will then conclude the

rest of this chapter