COS 333: Chapter 15, Part 3

Summary

This lecture concludes the chapter on functional programming languages, focusing on Scheme and its list operations, numeric predicate functions, and control flow. It delves into recursive function implementations, tail recursion, and the efficiency benefits of converting non-tail recursive functions. The power of first-class functions is demonstrated through 'map' and 'eval', and a brief comparison with Common Lisp is provided. The lecture also touches on real-world applications of functional languages, particularly in AI, and contrasts functional with imperative programming, highlighting their respective advantages.

Takeaways

• 📚 The lecture series concludes with a discussion on functional programming languages, focusing on Scheme and its capabilities for list operations and recursion.
• 🔍 The script delves into numeric predicate functions, control flow, and list data structure functions in Scheme, emphasizing the language's pure functional nature without loop constructs.
• 📝 An in-depth look at the 'equal?' and 'equal-simp' functions illustrates how to recursively compare elements in lists, highlighting base cases and recursive cases in Scheme.
• 🔧 The 'append' function is explored, demonstrating how to concatenate lists in Scheme using recursion and the 'cons' function, rather than appending atom by atom.
• 🔄 Tail recursion in Scheme is mandatory for the compiler to optimize recursive calls into iterative constructs, improving efficiency and reducing memory usage.
• 🛠️ The 'apply-to-all' functional form showcases the power of first-class functions in Scheme, allowing functions to be passed as parameters and returned as results.
• 🤖 Common Lisp is contrasted with Scheme, presenting a more complex language with additional features like iterative control structures and a rich set of data structures.
• 🏢 Applications of Lisp and Scheme are discussed, including their historical use in AI, knowledge representation, machine learning, and natural language processing.
• 🏫 Scheme's role in education is highlighted, being used to teach introductory programming concepts in universities and colleges.
• 💡 A comparison between functional and imperative programming languages is made, noting the simplicity and mathematical nature of functional languages versus the efficiency and complexity of imperative ones.
• 📝 The script provides guidance for students preparing for tests and exams, emphasizing the importance of understanding the provided code examples and practical exercises.

Q & A

What is the main focus of the third and final lecture on chapter 15?

The lecture concludes the discussion on functional programming languages, specifically focusing on Scheme functions, tail recursion, first-class functions, and a brief overview of Common Lisp and real-world applications of functional programming languages.

What are predicate functions in Scheme?

Predicate functions in Scheme are functions that evaluate to a boolean result, typically used for testing certain conditions or properties of data.

How does Scheme handle control flow within its functions?

Scheme handles control flow through the use of recursion, as it is a pure functional programming language and does not have traditional loop structures.

What is the purpose of the 'equal simp' function in Scheme?

The 'equal simp' function is used to compare two simple lists (lists containing only atoms, no nested sublists) and returns true if the lists are equal in terms of their elements, and false otherwise.

What is tail recursion and why is it important in Scheme?

Tail recursion is a form of recursion where the recursive call is the last operation performed in a function. It is important in Scheme because the language definition requires all tail recursive functions to be automatically converted to iterative structures, making them more efficient in terms of speed and memory usage.

How can a non-tail recursive function be converted into a tail recursive function in Scheme?

A non-tail recursive function can be converted into a tail recursive function by introducing an additional parameter, often called an accumulator or a 'partial' result, which carries the ongoing result through each recursive call, allowing the recursive call to be the last operation.

What is the significance of first-class functions in Scheme?

First-class functions in Scheme mean that functions can be treated like any other data type. They can be passed as arguments to other functions, returned as results, and assigned to variables. This feature is demonstrated through functions like 'map car' and 'adder', which utilize functional forms.

What is Common Lisp and how does it differ from Scheme?

Common Lisp is a dialect of the Lisp programming language that combines features from many popular Lisp dialects in the early 1980s. It is a large and complex language with a rich set of data structures and powerful I/O capabilities, unlike Scheme, which is designed to be simple and easy to understand.

What are some real-world applications of functional programming languages?

Functional programming languages have been used in various fields such as artificial intelligence for knowledge representation, machine learning, and natural language processing. They have also been used in end-user software systems like the Emacs text editor and the Maxima mathematics system.

What are the advantages of functional programming languages over imperative programming languages in terms of concurrency?

Functional programming languages naturally divide programs into functions, which can be executed concurrently or in a distributed fashion without the programmer having to explicitly manage mutual exclusion locks or other concurrency control mechanisms.

What type of questions can be expected in tests and exams related to functional programming languages?

Tests and exams may include theory questions, questions asking for the result of provided Scheme code, analysis and correction of Scheme code, and implementation of Scheme functions with a complexity level similar to the examples covered in lectures.

Outlines

00:00

📚 Concluding Functional Programming Languages

This paragraph wraps up the discussion on functional programming languages, focusing on Scheme's capabilities with list and predicate functions, control flow, and recursive operations. It introduces the concept of tail recursion and its efficiency benefits, as well as first-class functions, which are a cornerstone of Scheme's power. The paragraph also briefly mentions Common Lisp and real-world applications, concluding with a comparison between functional and imperative programming languages, highlighting functional programming's advantages.

05:00

🔍 Deep Dive into Scheme's equal? Function

The second paragraph provides an in-depth look at Scheme's 'equal?' function, which compares two lists element by element. It discusses the function's implementation using recursion and the 'cond' expression to handle base cases, including mismatches and list exhaustion. The paragraph also explains the recursive case, where elements are compared, and the function is reapplied to the remaining lists. The explanation includes the handling of both simple lists ('equal?') and lists with nested structures.

10:03

📝 Implementation of Scheme's append Function

This paragraph discusses the 'append' function in Scheme, which combines two lists into one. It explains the strategy of prepending elements from the first list to the second in reverse order. The paragraph details the recursive implementation of 'append', which involves eliminating elements from the first list one by one until an empty list is reached, serving as the base case. It also poses questions to the viewer about the limitations of appending lists atom by atom and suggests experimenting with the 'list' function as an alternative to 'cons'.

15:06

🔄 Tail Recursion in Scheme

The fourth paragraph delves into tail recursion, explaining its importance in functional programming due to its efficiency and the potential for compilers to convert tail recursive functions into iterative constructs. It contrasts this with the general inefficiency of recursive solutions and provides a practical example of converting a non-tail recursive 'factorial' function into a tail recursive version using a helper function, demonstrating how this can improve performance and resource usage.

20:07

🤖 First-Class Functions and Functional Forms in Scheme

This paragraph explores the concept of first-class functions in Scheme, where functions can be passed as parameters and returned as results. It introduces 'mapcar', a functional form that applies a given function to every element in a list, constructing a new list with the results. The paragraph also discusses the power of functions being able to build and execute code, using 'eval' to interpret lists as Scheme code, illustrating the flexibility and expressiveness of Scheme.

25:08

🤹‍♂️ Common Lisp and Applications of Functional Programming

The sixth paragraph provides an overview of Common Lisp, highlighting its complexity and rich feature set, which includes data structures, IO capabilities, and packages. It contrasts Common Lisp with Scheme in terms of simplicity and ease of understanding. The paragraph also touches on the application areas of Lisp and Scheme, particularly in artificial intelligence, knowledge representation, machine learning, and natural language processing, as well as their use in end-user software systems like the Emacs text editor and Lisp machine.

30:08

🏢 Real-World Usage of Lisp and Scheme

This paragraph discusses the real-world usage of Lisp and Scheme, noting their prevalence in academic settings for teaching programming concepts. It also mentions the historical use of Lisp in AI and its application in various fields such as robotics and algebraic processing systems. The paragraph emphasizes the influence of Lisp's design on its suitability for low-level operations and its adaptability for concurrent execution.

35:11

📉 Comparative Analysis of Functional and Imperative Programming

The eighth paragraph compares functional programming languages with imperative programming languages, focusing on their underlying philosophies, execution efficiency, and approach to concurrency. It points out the simplicity and mathematical nature of functional languages versus the complex semantics and syntax of imperative languages, which are more closely tied to hardware. The paragraph also addresses the ease of implementing concurrency in functional languages due to their natural division into independently executable functions.

40:12

📝 Study Guide for Functional Programming Concepts

The final paragraph serves as a study guide, advising students on how to prepare for tests and exams related to functional programming. It emphasizes the importance of understanding the provided code examples and completing practical exercises. The paragraph reassures students that exam questions will not exceed the complexity of the examples covered in the lectures and encourages the use of additional notes and resources for a deeper understanding of the material.

Keywords

💡Functional Programming Languages

Functional programming languages are a category of programming paradigms that treat computation as the evaluation of mathematical functions and avoid changing-state and mutable data. In the video, the theme revolves around discussing various aspects of these languages, particularly Scheme, and their application in programming tasks such as working with lists and implementing recursive functions.

💡Scheme

Scheme is a minimalist, general-purpose, multi-paradigm programming language that supports functional programming. The script delves into Scheme's approach to handling control flow, list processing, and recursion, showcasing its unique features such as first-class functions and tail recursion optimization.

💡Predicate Functions

Predicate functions are functions that return a boolean value, typically used for evaluating conditions. In the script, numeric predicate functions are mentioned, which are used to evaluate to a boolean result within the context of Scheme programming language, playing a crucial role in control flow and decision-making within programs.

💡Control Flow

Control flow refers to the order in which individual statements, instructions, or function calls are executed or evaluated in a program. The script discusses how Scheme, lacking traditional loop structures, manages control flow within its functions using recursion and conditional expressions like 'cond'.

💡First-Class Functions

First-class functions are a concept in programming languages where functions are treated as first-class citizens, meaning they can be passed as arguments, returned from other functions, and assigned to variables. The script illustrates the power of first-class functions in Scheme through examples like 'mapcar' and 'apply to all', emphasizing their flexibility and utility.

💡Tail Recursion

Tail recursion is a specific form of recursion where the recursive call is the final operation in the function. The script explains the importance of tail recursion in Scheme, noting that it allows for more efficient execution by enabling the compiler to convert recursive calls into iterative loops, thus saving memory and improving performance.

💡List Data Structures

List data structures are used in Scheme to organize collections of elements. The script provides examples of functions that operate on lists, such as 'equal?', 'equal-simp', and 'append', which manipulate and compare list structures, demonstrating Scheme's capabilities in handling complex data manipulations.

💡Recursion

Recursion in programming is a method where a function calls itself to solve smaller instances of the same problem. The script discusses the use of recursion in Scheme for tasks such as list processing and factorial computation, emphasizing the need for a recursive approach due to the absence of loop structures in the language.

💡Cons Function

The 'cons' function in Scheme is used to create a new pair or add an element to the front of a list. The script explains how 'cons' is used in the context of the 'append' function to build a new list by prepending elements from one list to another in a specific order, illustrating the fundamental operations on lists in Scheme.

💡Lambda Expression

A lambda expression is a way to create anonymous functions, i.e., functions without a name. In the script, a lambda expression is used in the 'mapcar' function to apply an operation to each element of a list, demonstrating the flexibility of defining and using short-lived, unnamed functions in Scheme.

💡Eval Function

The 'eval' function in Scheme evaluates the Scheme expression passed to it. The script shows an example where 'eval' is used to interpret and execute Scheme code that has been constructed as a list, highlighting the meta-programming capabilities of the language where code can be dynamically created and executed.

Highlights

Concluding the discussion on functional programming languages with a focus on Scheme.

Introduction to numeric predicate functions and control flow in Scheme functions.

Exploring list data structure operations and predicate functions for object equivalence in Scheme.

The 'let' function and its role in Scheme's recursive list operations.

Three examples of Scheme functions demonstrating functional programming concepts.

Tail recursion in Scheme and its implications for efficiency.

Conversion of non-tail recursive functions to tail recursive for improved performance.

First-class functions in Scheme and their applications in 'map' and 'apply to all' functions.

Building and executing code with Scheme functions, illustrating the power of first-class functions.

Brief overview of Common Lisp as another dialect of the Lisp programming language.

Real-world applications of functional programming languages in various domains.

General comparison between functional and imperative programming languages.

Advantages of functional programming highlighted in the comparison.

Detailed implementation of the 'equal simp' function for list equality in Scheme.

Recursive approach to the 'equal' function handling both atoms and nested sublists.

Implementation and strategy of the 'append' function in Scheme.

Discussion on the inefficiency of non-tail recursive solutions and the benefits of tail recursion.

Conversion of a non-tail recursive 'factorial' function to a tail recursive version.

The 'map car' function as an example of a functional form in Scheme.

Constructing and executing code with the 'eval' function in Scheme.

Common Lisp's features and its contrast with Scheme's simplicity.

Applications of Lisp in artificial intelligence, knowledge representation, and machine learning.

Scheme's use in education for teaching introductory programming concepts.

Differences in philosophy, efficiency, and concurrency between functional and imperative programming languages.

Study advice for tests and exams, including the use of provided slides and practical exercises.

Transcripts

this is the third and final lecture

on chapter 15 where we will conclude our

discussion

on functional programming languages

in the previous lecture we continued our

discussion on the scheme

programming language we looked at

numeric

predicate functions where predicate

functions

are functions that evaluate to

a boolean result we then looked

at how scheme deals with control flow

within its functions and then we looked

at a number of functions

including predicate functions which work

with list data structures in scheme

we then looked at some predicate

functions

for testing equivalence between

different objects

in scheme and then we considered the

let function we finished the lecture off

by looking at our first example of

a fully implemented scheme function

that performs recursive operations on

a list in this lecture we

will further continue our discussion on

scheme

we'll look at three more examples of

scheme functions

and then move our discussion on to tail

recursion in scheme

and what tail recursion implies as well

as how to convert

a non-tail recursive function into a

tail

recursive function we'll then look at

and apply to all function as well as

functions that build code and

these two demonstrations will illustrate

the power of first class

functions within scheme then we'll look

very briefly

at common lisp which is another dialect

of the lisp

programming language and we'll also

consider some real-world applications

of functional programming languages

right at the end of this lecture

we will look at a general comparison

of functional and imperative programming

languages

we will highlight some of the advantages

associated with functional programming

so let's jump straight into our next

complete scheme function implementation

and again this function like the member

function that we discussed in the

previous lecture

will perform operations on

list structures so this function is

called equal simp

and it is applied to two parameters list

one

and list 2 and both of these parameters

are simple lists so again this means

that the lists contain only atoms

in other words neither list contains

nested sub-lists

the equal sim function should yield a

true result

if the two lists are equal in other

words both lists contain

the same elements and false otherwise

so how will we approach this problem

well

again the problem specification implies

that we need

to work through both of our lists

element by element so this implies then

some kind of repetitive structure

and again as we know scheme is a pure

functional programming language

which means that it has no loop

structure

and therefore we must approach the

problem in a

recursive fashion so we will recursively

then work

through both lists and we will compare

elements within the two lists to each

other so there are pairs of elements

that we compare

and we then yield a true result

if both of the lists are exhausted

simultaneously so in other words

we have a series of matches between

element pairs

and we reach the end of list 1 and list

2

at the same time we yield a

false result if we find any mismatch

between a pair of elements or

if we run out of elements in one of the

two lists

before running out of elements in

the other list so this implies then that

we have

four base cases we have a

case where we find a mismatch

a case where we run out of elements in

the two lists at the same time

and then two cases for either list one

or list two

running out of elements before the other

list

does so over here we have

a definition for this function here

we've used again

the define function to bind a

name to our function the name is equal

simp and the two parameters are list one

and list two we then have a

cond in the body of our function and

again

the cond will decide whether one of the

four base cases

are executed or the recursive case

is executed so over here then

we have three of the base cases

handled two of the base cases are

handled by

one condition so first of all we use the

null function to check

whether list one is empty

now if list one is empty then one of two

things might be the case

either list two might also be empty in

which case we've exhausted the elements

in both lists at the same time

all is 2 might not be empty in which

case we've run

out of elements in list 1 before running

out of elements

in list 2. so what

this then means is that the result

is dependent on whether list two

is null if list2 is null in other words

this predicate evaluates to true

then this means that we've exhausted

elements in both lists at the same time

and therefore we can conclude that the

result

of the cond as well as the result of the

equal simp function should then be

true if this predicate ends up being

false so in other words we

have an empty less one but a non-empty

list

two then it means that we've run out of

elements

in list one before running out of

elements in list two

therefore this predicate will evaluate

to false which means the entire cond

evaluates to false

and therefore the equal simp function

application will also evaluate to false

so that's two of our four base cases out

of the way

then we move on to the next condition

over here which deals

with a further third base case

and this test then is to see whether

list two is null in other words empty

now we've already eliminated the case

where

list one is null or empty so this means

that list one contains at least one

element so therefore

if list two is null in other words empty

then this means that we have run

out of elements in list two before

running out of elements in

list one in this case we can then simply

conclude that the result is false and

again

this then means that the entire con

devaluates to false

which means that our equal sim function

application also

evaluates to false so

next we have our recursive case and then

lastly we deal with our fourth base case

so the recursive case then finds the car

of each of the two lists so in other

words the element at the head of

each list and it compares those two

elements

to each other if they are equivalent to

each other

then we know that we have found a match

so we need to then

continue matching pairs between the two

lists

we then recursively apply equal simp

but we apply it then to the cuda of list

one

and the cuda of list two that will then

eliminate

the elements that we found that do match

in other words the cause of the two

lists

and we then continue searching on the

remainder

of the two lists finally

we reach the else so this else will then

be

reached if we still have

elements to compare but we have now not

had

a successful match between the cause

of the two lists meaning that we found

a mismatch and in this case we can then

terminate our search we don't need to go

any further through the two lists and we

can simply then conclude with

a false result again the entire cond

will then evaluate

to false and the entire application of

the equal simp

function will evaluate to false

now of course there are a couple of

different ways that we can specify the

base cases

so we could obviously rewrite this

function

to swap these two

first tests um for one another but of

course

then we would have to initially check

whether list two is null

and then the result would be where the

list one is null and then our second

test would test to see whether list one

is null and would conclude false in that

case

the next function implementation we'll

look at is for a function

named equal the equal function does the

same thing as the equal simp function

we've just discussed and the difference

is

that the equal function is applied to

two general list parameters so in other

words list one and list two

can both contain a mixture of atoms

as well as nested sublists

so how will we approach solving this

problem well over here we have an

implementation

for the equal function and we will be

using the same core strategy

as we used in the equal simp function so

in other words

we will recursively compare pairs of

elements from the two lists

and we have again four base cases

one for if we find a mismatch between a

pair of elements

one for if we exhaust both lists

at the same time one for if we

exhaust the first list before the second

list

and a final case where we exhaust the

second list

before the first list so

we can see then in our cond we have

these two conditions over here

and these deal with three of those base

cases once again

so in exactly the same way as we saw in

the equal

simp function and then our final case

where there is a mismatch between

a pair of elements is handled by this

else over here again so so far

we have exactly the same implementation

as the

equal simp function our recursive case

is also almost exactly the same as the

equal simp function so again

we compare the cause of the two lists to

each other in other words the first

elements within each of those two lists

are compared

and if they are found to be equal then

we recursively

apply the function to the cuda of

each list thus eliminating the first

element in each list

and continuing the matching process

now where the equal function has to

differ is that this comparison

between the two cars has to work

for both atoms as well as

nested sublists so how will we

address this part of the problem well

we know that the equal function is

capable of comparing

two lists to each other so if we use

the equal function itself in order to

perform the comparison

between the cause of the two lists

then we know that we can deal with a

situation where

these elements that we are comparing are

in fact

lists so this only leaves the situation

where the car

of each list is then an atom

or where one of the cause of the two

lists

is an atom so we essentially then

need to extend the implementation of the

equal simple function

so that it can also deal with atoms

so this is where the first two

additional

conditions within the cond come in and

essentially what we have to do

here is test to see whether one of

the two parameters is a

list or not so we can use then

the list predicate in order to do this

and the list predicate will then yield

a true result if the list that is being

checked is in fact a list

and if it is not it will yield a false

result

so in other words a false result will be

produced

if we have a situation where either one

of the two parameters

is not a list and is in other words an

atom

of some sort so first of all

we check to see whether list one is

not a list so if this is the case then

we know that list one

must be an atom so in this case we can

then perform

an equality check between the two lists

now what we've seen with our built in

equality predicates

is that they will yield a true result

if we are comparing two atoms to each

other and those atoms are the same

and a false result will be produced if

the two atoms are not the same

or if we are comparing an atom to a list

or a list

to an atom so we know at this point

that list one must be an atom

which means that this equality check

will only produce

a true result if list two is the same

atom if it's not

then we will get a false result and if

list two

is a list then again we will get a false

result because we are comparing an atom

to a list next we have this condition

over here

so at this point we've eliminated the

first condition

so we then know that list one must be

a list so in this case we can then check

to see whether list

2 is not a list

if it is not a list then it means list 2

must be

an atom so in this case we are then

comparing a

list which is list one to an atom

which is list two and so in this case

we obviously then have a mismatch and

the

result that we evaluate to is then a

false

so essentially what we've now done is

we've modified the

equal simp function so that it can

compare

both atoms and lists and then we've

changed our recursive case

so that the comparison between two

elements is performed by the equal

function itself

which we know can now deal with both

atoms

and lists

the last function implementation we'll

look at

in this lecture is for a function named

append

the append function is again applied to

two parameters

and both of these parameters are lists

we will once again refer to these lists

as list 1

and list 2 respectively the append

function

should then yield a new list and this

new list should contain all of the

elements of

list 1 followed by all of the elements

contained

in list two so

over here we have an implementation for

our append function we can see that it's

a fairly short function

but the logic underlying it is a little

more complex

so what strategy then will we use to

perform

this appending operation so we'll

prepend

elements in list one one by one

to list two but we'll do so in

reverse order so in other words we will

prepend

the last element in list one to list two

then we will prepend the second last

element in list one

then the third last element in list one

and so we will continue

and the very last prepending operation

will perform

is for the first element in list one

so let's look at this example at the

bottom here here we are performing an

append

between two lists we have the list that

contains the atoms a

and b and a list that contains the atoms

c and d so our strategy

will then prepend the atom b

to the list cd creating the list

bcd and then it will prepend the atom a

to the list bcd to produce the list abcd

so how will we then actually go about

implementing this

strategy well let's look at our function

implementation

again the body of this function is a

cond

and we'll start off by looking at the

recursive

case which is included in the

else condition within our cond

so this else condition then recursively

applies the append function

and it applies the append function to

the cuda

of list one and list two

so the cuda of list one is the tail of

list one

in other words we discard the first

element

in list one we then

assume that this append function will

generate the correct result

so the result then of this entire

recursive call

will be the remaining elements in list

one

excluding the first element followed by

the elements within list two all

contained within

a new list all that we then need to do

is add the first item in list one

so we do that by retrieving the car of

list

one which is then the first element

contained in that list

and then we use an application of the

cons function

to add this first element

in list one to the result of appending

the cuda of list one and list

two this will then produce a

fully appended list containing all of

the elements in list one

and list two so

it's important then to understand that

the procedure that we will be following

is we will eliminate elements from list

one one at a time so we will eliminate

the first element

then the second element then the third

element and so on

until eventually we end up with

a list containing a single element

now recall when we were discussing the

cuda function

that the cuda of a list containing only

a single element

is an empty list i mentioned that we

should think about

lists in scheme as containing a series

of elements and then implicitly

there is a last element which is an

empty list so if we then

find the cuda of this list containing a

single element

the result of that will then be an empty

list

and this then gives us the

base case for our append function

so the base case then is if the first

list

is empty in other words it is null so we

can determine that

by an application of the null function

in this case the result of the

recursive call is then simply list

2. so let's look at how this append

function

would operate based on our example

so first of all we apply our append

function to

the list a b and the list

cd now we perform

a recursive call to the append

function because we don't have an empty

list as the first list yet

and we eliminate the first element

namely

the atom a which leaves us then

with the list containing only a single

atom

namely b in that case we then perform

another recursive call to the append

function

and this then eliminates the first

element within

our first list in other words the atom b

and it leaves

us with an empty list so now we are

appending an

empty list and the list cd and

this is then our base case over here

because

our first list is now null and the

result

of this is just then simply the second

list in other words the list

c d in this case now we need to

unwind our call stacks so we return to

the previous call which we've done over

here

and we now have as a result

of the append between the empty list

and the list cd the

list cd over here so now we need to

perform

a cons between that list

and the first element of our first list

which is then the atom b in that case

so this const will then produce the list

b c

d we've now again finished

a recursive call execution so we unwind

our call stack

again and we then return to the first

call

and here we then perform a const between

the

car of the first list which is then a

as we can see over there and we are

performing

the cons with the result of the previous

recursive call

which as we've seen is the list b c d

so the result of this const will then be

the list

a b c d and that is then our

final result for the appending of the

lists

a b and c d

right so that's how our append function

will then execute

i'd like you now to think about two

questions

and try to answer them pause the video

if you need to at this point

first of all why can't we append list

two to list one atom by atoms if we look

at our example over here

can we append to the list a b

the atom c to produce the list abc

and then finally append the atom d to

the list

abc to produce the list abcd

so the answer to that question is no we

can't and what i'd like you to answer is

why is that the case as a

clue look at how the cons

function application will work so in

this case

the cons function application will be

between a list and then as the second

parameter of the cons

we will have an atom so look back at the

previous lecture and see how the cons

function

behaves if we attempt to cons

a list and an atom as the second

parameter

try to determine what the result of this

series of cons operations will be

through the series of recursive calls

on our example lists and then

if you are still not sure of the result

implement

this append function and see what the

result is when you execute it

secondly i would like you to consider

the use of

the list functions so again from the

previous lecture

recall that the list function can be

used

to build up lists so here what i am

asking

is is it possible to use the list

function instead of the cons

function over here again try to

determine what the result

of that modification would be and if you

can't answer that question then try

implementing the append function in that

way

and see what the result is and try to

explain

why you get that result

next let's take a look at tail recursion

within scheme

so we've seen that scheme is a pure

functional programming language

and amongst other things this means that

any repetition within a scheme program

must be achieved by means of recursion

now in general we know that a recursive

solution

is much slower than an equivalent

iterative

solution and also uses a lot more

memory now the reason for the

execution of a recursive solution being

slower

is that there are a variety of

operations that need to be performed

each time that

a function is called there are a number

of bookkeeping operations

as well as memory allocation operations

that have to take place

and of course these operations take up

time

and therefore cumulatively over a series

of recursive

function calls the entire recursive

solutions

execution is slowed down

additionally each time that a function

is called

a stack frame is allocated for that

function

and stack frames take up space in memory

and so therefore each recursive function

call

will use up some additional memory

iterative solutions are not subject to

these problems so this brings us then to

the idea

of a tail recursive function and a tail

recursive

function is a function in which the

recursive call

is the last operation performed

now the implication of tail recursive

functions

is that a compiler can automatically

convert

these into an iterative construct

so this then makes the function much

faster

and more resource efficient if this

conversion

takes place and it turns out that the

scheme language definition requires

all tail recursive functions to be

automatically converted

to iterative structures so therefore

it's worthwhile for us to take a look at

tail recursive functions in scheme

and how to convert non-tail recursive

functions

into tail recursive functions which are

then much

more efficient and will execute much

faster and use less memory

so let's look at a practical example of

a non-tail recursive function and how we

would convert it into a

tail recursive function so over here we

have

a function implementation we've defined

a function called factorial

and it is applied to a single parameter

which we assume is a numeric value

inside the body of the factorial

function we have an application of the

if function and the if function selects

between the base case

or the recursive case we could have also

used a cond in the if functions place

as we did in the previous examples

so then our if function is

used to define a factorial in

the usual way that a factorial is

defined in mathematics

so the factorial of zero is one

and the factorial of any other value

greater than zero

is that value multiplied by

the factorial of the value minus

1. so let's look at how this function

would execute

in terms of an example which we have

over here

here we are computing the factorial of

three

so this then results in our recursive

step

being executed which means that we are

computing

three multiplied by the factorial of two

but we need to know what the factorial

of two is so this results

in a recursive call where we compute the

factorial of 2

which is 2 multiplied by the factorial

of

1. again we need to know what the

factorial of 1 is so we perform

another recursive call computing the

factorial of 1

which is then 1 multiplied by the

factorial of

0. at this point we've reached our base

case

so we know that the factorial of 0 is

1 and now we return

to the previous recursive call so the

previous recursive call was computing

the factorial of one

we now have a result for the second

parameter

so we are now computing the result of

one multiplied by

one which is one we now return

to the previous recursive call which was

computing the factorial of two

and so now we have the multiplication

of two and one which produces a result

of 2. finally we return to our first

call

2 factorial which was computing the

factorial of 3

and now we have the multiplication of 3

and 2 which produces a result of

6. this is then the final answer to

our initial call

so is this implementation of the

factorial function

tail recursive or not well if we look at

the implementation we first of all have

to compute the result of the subtraction

then we use the result of the

subtraction to compute

the result of the factorial functions

application and then the result

of the factorial functions application

is used

in the multiplication so in other words

the last function that is called in the

recursive

case is the multiplication function not

the recursive application of the

factorial function

what this thing means is our

implementation of the factorial function

is not tail recursive and this then

implies that the function will execute

slowly

and it will require a lot of memory

resources

we can also see that this function is

not tail recursive because

the result is computed as the

stack unwinds through our series of

recursive calls

so how can we then convert the factorial

function

to a tail recursive function

well we have such an implementation over

here

and very often the conversion of a

non-tail recursive function to a tail

recursive function

requires the assistance of a helper

function

so that's exactly what we've done over

here fact helper is our helper function

and down here we've defined our

factorial function

once again applied to a single numeric

parameter

in and then we apply the

fact helper function to in

and one as parameters now if we look at

our

fact helper function over here we see

then that we have two parameters

in and partial in is used as

a kind of counter so we will start off

with n

being equivalent to the value that we

are attempting to compute

the factorial of and then with each

recursive call

we decrement that value by one so in our

example over here when we start

by computing the factorial of three then

in will initially have a value of three

on the next

recursive call it will have a value of

two and then

finally one at which point we then reach

our base case

our base case then simply returns the

second parameter which is called partial

now partial acts as a means

of transmitting the partial solution for

the factorial

computation from one recursive call

to the next so

when we look then at our recursive case

over here we are applying fact helper

to first of all as a first parameter

in minus one so that decrements are

counted by

one moving it closer to one

and then we compute a new partial result

which is in multiplied by the old

partial

result so let's look at how this

factorial function works

here we are again computing the

factorial of three

this then results in us applying fact

helper to the parameters

three and one which is this initial

application of the fact helper function

so this then results in the recursive

case being

executed so now we are applying fact

helper

to the parameter 2 which is the previous

in parameter

minus 1 and then the second parameter

is 3 multiplied by 1 where 1

is the previous partial result

so this then results in an application

of the fact helper function to the

parameters 2

and 3 and this then once again results

in

the recursive step being executed which

means we are then applying fact helper

to the first parameter of one which is

the

decrement of the previous in parameter

which was two

and then the second parameter our new

partial

is 2 multiplied by 3 where 3 was

our previous partial result

so now we have an application of the

fact helper function

to the parameters one and six we now see

that we have matched our base case

so now the result of this function

application

is simply partial which in this case is

six

so that is then the result of our

final recursive call we now need to

unwind the stack but now we see that we

are not

computing our solution as we unwind the

stack

we now just simply return the value six

from one call to the next until

eventually we get back to

our original application of the

factorial function

to the value of three the result of that

function application

then is 6. so essentially what we've

done

here is we've simulated the operation

of a loop as it would work in

an imperative programming language we

have simulated

a loop counter variable by means

of the n parameter over here which is

decremented with each recursive call

and then we have a result which is

accumulated by means of the second

parameter

which is partial now what's important to

understand here is that

our solution by means of implementing

the fact helper function

is not iterative it is still a recursive

solution

however the scheme interpreter can then

automatically behind the scenes

convert this implementation into a

standard loop structure and this will

then be much more efficient to execute

and will also use less memory

in the first lecture on this chapter we

briefly touched on the fact that

functions in scheme are first class

entities

now amongst other things this means that

functions can be passed as parameters to

other functions

and functions can also return functions

as a result so we'll illustrate the

power of this concept by means

of two functions the first of which is

the

apply to all functional form so a

functional form then

is simply a function that either takes

one or more

functions as parameters or yields

a function as a result or alternatively

does both of these things so the apply

to all functional form then

is a functional form that

receives a function as a parameter

and applies that function to every

element

within a list and builds up then

a new list out of the results of these

function

applications so let's look at what an

implementation of an apply to all

functional form would look like

here we have one which is a function

named map car and it is applied

to two parameters the first parameter

is the function that we want to apply to

the elements

of our list and our list is specified as

the

second parameter so because we are

attempting to

apply the function to each element

within the

list this implies that we need to

perform repeated operations

on the list which means that we have to

recursively process the list so that's

exactly what we do with the conf

function

over here and the base case of the conf

function

is when the list is empty so we use the

null function in order to test this

if the list is empty then the result is

simply an empty list which of course

makes sense over here in the

else part of the cond function

we have the recursive case so the

recursive case

then simply applies the function that

has been passed through

as the first parameter for map car

to the car of the list the core of the

list is of course the first element

within the list

so this will simply result in the

function whatever it is

being applied to that first element

we then recursively apply the map car

function

using the same first parameter in other

words the same

function that has been passed to map car

and we

apply map card to the cuda of

the list so this means we then eliminate

the

first element the car of the list

considering

only the remaining elements in the list

and we then

recursively process those once we have

recursively processed the remainder of

the list

all that remains for us to do is to

apply the cons function

so that we can add the result

of applying the function to the car of

the list

to the result of applying map car

to the remainder of the list

so let's look then at how we would use

the map car function

over here we are applying map car to

a function and in this case the function

is a

lambda expression so in other words it

is a nameless

function we then have

as our second parameter a list of values

and note that we have to quote this list

of values

again and these values then are the

numeric

atoms 3 4 2 and 6.

so our lambda function then doesn't

require a name because we are not going

to

reuse it we're simply applying this

function

to each of the numbers contained within

our list

and our lambda function then is applied

to a single parameter

which is called num and the result of

the function application

is num multiplied by itself so in other

words

this lambda function squares its

parameter

so the result of this thing is that this

lambda function will be applied to each

value

in turn within the parameter list

over here and then the map car function

will

evaluate to a list containing the

results of those

squaring operations so in other words

the result will be

a new list which will contain the values

9 16 4

and 36

next we'll look at a simple example of

a function that constructs code

so a scheme function can actually build

scheme code

and then request the interpretation of

this built scheme code

and this is possible and in fact very

easy

because functions are simply represented

as

lists as we've previously seen and lists

can be

returned as results of function

applications

so therefore we can write functions that

can

return lists and the interpreter

is also a built-in function called

eval which the programmer can

actually directly invoke

over here we have a simple example of a

function

that builds code and then requests its

execution by the interpreter

so we define a function over here this

function is named adder and it is

applied to a single parameter

called lis we assume that this list

contains only numeric atoms

so now we have in the body of our add a

function a

cond and the first condition within our

cond

is triggered if the list is empty

or null in other words so if the list is

then empty then the result

of the adder function application is

simply zero

this of course makes sense because there

are no values

to add so this case is a trivial case

but in all other cases we then trigger

the

else here so this will be triggered

whenever there are

numeric elements within the list

what we then do is we apply the cons

function

to the symbol plus and the list that has

been passed through as a parameter

to the adder function so

notice that the plus symbol over here is

quoted

this is to prevent the scheme

interpreter

from thinking that it is the function

named plus which is built into scheme so

in other words we are simply dealing

with the

symbol plus so the result then of this

cons

is that the plus symbol is added to the

front

of the list so for example if the list

contains the numeric values

2 4 and 8 then the result of the const

would be

plus 2 4 8. now of course

that is a valid scheme

function application it is in the form

of

a list but we can apply the interpreter

to it

in order to actually compute then the

result of that edition

so this is done then by applying the

eval function to the results of the cons

the cons has built up a valid function

application and therefore eval when it

is executed on that list

will then actually execute the

interpreter

and the result of that will then be that

all of the numeric atoms contained

within the list

will then be added together and we will

get a single numeric value

as a result so the important thing to

understand here

is that we use very basic operations to

construct

lists which have the form of a function

application

and then we can very easily apply the

eval function

to these lists and the result will then

simply be that the function applications

will be

evaluated as if they had been provided

by the programmer

we'll now take a quick look at common

lisp which we touched on very briefly in

our discussion on

chapter two of the textbook so common

lisp

combines a lot of the features that were

included

in the popular lisp dialects that were

being actively used in the early 1980s

because it takes features from a large

number of different programming

languages

it's a very large and very complex

language

so in a sense it's the opposite of

scheme because scheme was designed to be

a very stripped down simple and easy to

understand

programming language common lisp

includes

a large number of features it has a

fairly rich set

of data structures which include records

arrays and complex numbers which we'll

talk about a little bit

later on in this course and then also

character strings

it also provides a set of very powerful

io capabilities

we saw that scheme provides a fairly

simple set

of output functions and then common lisp

also provides packages

which are used to organize functions and

data that are related to one another and

packages are also used

for access control in common lisp

common lisp also provides iterative

control structures

so in a sense it breaks to

a degree the concept of a

pure functional programming language

which

scheme does not do because it doesn't

include iterative control

structures if we look at

application areas for functional

programming languages

we see that functional languages are

typically

fairly general purpose languages and

therefore can be applied

to many of the same problem domains

as imperative programming languages can

be

in general however we see that fewer

software development

projects are implemented in functional

languages than imperative languages

and this is largely because imperative

programming languages are much

more popular than functional languages

we also saw that pure functional

programming languages

are in general a little less efficient

than

imperative programming languages and

this is another factor that has impacted

on their use in the real world

more modern functional programming

languages have attempted to address this

problem by

incorporating features from imperative

programming

such as loop structures

if we look at the lisp programming

language we see that most of its

application areas have historically been

in the field of artificial intelligence

and this

is because artificial intelligence is

the problem domain

that lisp was designed for so lisp has

been used

for things such as knowledge

representation which is where we

represent knowledge in some way that a

computer

can process and attempt to understand

this was also been used for machine

learning applications

and then also for natural language

processing

in natural language processing we try to

get a computer

to understand and interpret natural

language as it is written

and spoken by humans lisp has also been

used

for modeling speech and vision in

certain application areas such

as robotics we see that lisp has also

been used

for a few end user

software systems so if we look for

example at the emacs

text editor we see that this text editor

provides functionality for the user to

modify the text editor and add

additional functionality this

functionality

is added by means of a lisp dialect

we also have the maximum mathematics

system which

is an algebraic processing system

similar to

the more modern mathematica and this

is also programmed using a

lisp-like syntax the

lisp machine is a hardware platform in

which

all of the system software is

implemented in

lisp and this demonstrates that lisp can

be used for

fairly low level operations such as the

implementation

of operating system components

then if we look at the scheme

programming language as i've previously

mentioned

it has been designed for teaching

purposes

and as such it is used in a lot of

universities and colleges to teach

introductory programming concepts

finally let's take a look at functional

programming languages

versus imperative programming languages

so we saw in the previous slide that the

application areas

for imperative and functional languages

are relatively

similar to each other however the

underlying philosophy behind

imperative programming languages is

fairly different to the philosophy

of functional languages so imperative

languages

are characterized by very efficient

execution and this is because they are

largely

direct reflections of the underlying

hardware that they

are meant to execute on the

semantics and syntax for imperative

programming

languages are fairly complex and this is

due to their reliance on variables

also concurrency is not very easy to

implement

in imperative programming languages and

has to be

designed by the programmer so the

programmer has to worry about things

like mutual exclusion locks

and so on if we now look at functional

programming languages we see

that the semantics and syntax for such

languages are fairly simple

and this is because they use a much more

natural approach to describing programs

which is much more mathematical

rather than machine based however the

execution of programs written in

functional programming languages is

generally a lot less efficient

than for imperative programming

languages and this

is due to the reliance on

recursive execution of functions

in functional programming languages we

also see that concurrency

is fairly simple and this is because

programs can be

automatically made to be concurrent

this is due to the fact that we

naturally divide our programs up

into functions and these functions can

then

be split up to be executed concurrently

or in a distributed fashion

so that concludes our discussion on

functional programming

i'd now like to close with a couple of

additional notes

related to tests and exams

so firstly please note that the slides

that i

have used for these lectures have been

posted

on the course website these slides

contain

additional notes which are fairly

extensive

particularly in relation to the examples

that we discussed within these lectures

so if you need some additional

explanation for these examples please

refer

to these notes where you will find

step-by-step

execution traces and a very detailed

explanation

then in tests and exams related to

this chapter i can ask a couple of

things

so i can firstly ask theory questions

these will

not be in the majority because

this course focuses more on insight and

application i can also provide you with

some scheme code and then

ask you what the result will be either

in terms of

output or in terms of the execution

of the scheme code i can also ask you to

analyze scheme code and potentially

correct

it as well and then finally very

importantly i can ask you to

implement scheme functions now

in these kinds of questions the

implementations will

not be more complex than the examples

that we've covered

in these lectures so be sure that you

understand all of the code examples that

we've covered

and also be sure to do the practical on

functional programming which includes

a number of exercises and these serve as

good examples of the kinds of questions

that you can expect

in tests and exams