COS 333: Chapter 15, Part 3
Summary
TLDRThis 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
📚 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.
🔍 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.
📝 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'.
🔄 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.
🤖 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.
🤹♂️ 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.
🏢 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.
📉 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.
📝 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.
Mindmap
Keywords
💡Functional Programming Languages
💡Scheme
💡Predicate Functions
💡Control Flow
💡First-Class Functions
💡Tail Recursion
💡List Data Structures
💡Recursion
💡Cons Function
💡Lambda Expression
💡Eval Function
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
5.0 / 5 (0 votes)