COS 333: Chapter 15, Part 1
Summary
TLDRThe lecture introduces the shift in focus to chapters 15 and 16 on functional and logic programming languages, emphasizing their significance in exams due to heavy weighting. It delves into functional programming, highlighting its theoretical underpinnings with mathematical functions, the avoidance of side effects for referential transparency, and the pure functional approach eschewing variables. The discussion transitions to LISP and Scheme, exploring their history, basic constructs, and function applications, setting the stage for deeper exploration in subsequent lectures.
Takeaways
- 📚 The course is focusing on chapters 15 and 16 of the textbook, which cover functional programming languages and logic programming, as these are heavily emphasized in exams.
- 🔄 The professor has reordered the chapters to allow more time for practicals and lectures on the critical chapters, enhancing understanding and preparation for assessments.
- 🎯 Students are urged to concentrate on the material in chapters 15 and 16, as they carry significant weight in the grading for both semester tests and the final exam.
- 💻 Practical tasks, especially coding implementations similar to examples in chapters 15 and 16, are crucial for exam preparation and should be thoroughly practiced.
- 🔗 Chapter 15 references earlier chapters (5-8), and students are advised to consult both the textbook and the slides for a comprehensive understanding.
- 🚫 The entire Chapter 15 will not be covered; the focus will be on specific functional programming languages: Lisp and Scheme.
- 💡 Functional programming is based on mathematical functions, aiming to provide a more natural and theoretical approach to programming compared to imperative programming languages.
- 🔗 In functional programming, the concept of 'side effects' is generally discouraged as it introduces ambiguity and complexity in program execution.
- 🌐 Referential transparency, a property where equivalent expressions can be substituted without affecting program behavior, is a key advantage of functional programming languages.
- 🔑 Scheme, a dialect of Lisp, is emphasized for its simplicity and modernity, and is the primary focus for the course's functional programming section.
- 📝 Scheme uses a universal function 'eval' for interpreting expressions, demonstrating the power and flexibility inherent in functional programming languages.
Q & A
Why has the order of chapters in the textbook been changed for the lectures?
-The order of chapters has been changed to allocate more lecture time and practical work to chapters 15 and 16, which are heavily emphasized in the semester tests and the exam.
What is the significance of focusing on chapters 15 and 16 in the course?
-Chapters 15 and 16 cover functional programming languages and logic programming, which are important due to their significant weight in the exams and their practical applications.
What is the expectation for students regarding the practical tasks related to chapters 15 and 16?
-Students are expected to complete all practicals related to these chapters, as the ability to implement code similar to examples given in these chapters may be required in exams.
How does the reference to earlier chapters in chapter 15 impact the preparation for the lectures?
-Students should refer to both the textbook and the slides when preparing for chapter 15, as the slides provide additional information on topics from earlier chapters that are referenced.
Why are only certain topics within chapter 15 being covered in the lectures?
-The lectures will focus only on Lisp and Scheme from chapter 15 because of their foundational importance in functional programming languages.
What is the fundamental concept behind functional programming languages?
-Functional programming languages are based on mathematical functions, aiming to provide a more natural and mathematical way of expressing programs.
What is the primary concern for imperative programming languages?
-The primary concern for imperative programming languages is efficiency, as they are designed to reflect the computing hardware they were made for.
What is a functional side effect and why are they generally considered bad?
-A functional side effect is any change outside the scope of the function, such as modifying a parameter by reference or a global variable. They are considered bad because they lead to ambiguity in program execution.
What are the two approaches to solving the problem of ambiguity introduced by functional side effects?
-The two approaches are disallowing functional side effects entirely, which increases language purity but reduces flexibility, and demanding a fixed operand evaluation order, which can limit compiler optimizations.
What is referential transparency and why is it important in programming?
-Referential transparency means that equivalent expressions can be substituted for one another without affecting the program's behavior. It is important because it simplifies program semantics and eliminates ambiguity.
What is the difference between a pure functional programming language and an imperative one in terms of variable usage?
-A pure functional programming language does not support variables at all, eliminating global variables and parameter modifications, whereas imperative programming languages rely heavily on variable management.
Why is the lack of support for variables in a pure functional programming language important?
-The lack of support for variables ensures the elimination of functional side effects and state-associated functions, enforcing referential transparency and simplifying program semantics.
What are the two types of atoms in Lisp and how do they differ?
-The two types of atoms in Lisp are symbols and numeric literals. Symbols are identifiers or names for concepts, while numeric literals are simply numeric values.
What is the significance of the list notation in Lisp and how is it used?
-List notation in Lisp is used to represent both data structures and function applications. It allows for an ambiguous but powerful representation where the same list can be interpreted as data or a function call.
How does the lambda notation work in Lisp and what is its purpose?
-Lambda notation in Lisp is used to define nameless functions. It specifies a set of parameters and an expression that defines what the function does, allowing for the creation of functions that can be used immediately where they are defined.
What is the relationship between Scheme and Lisp?
-Scheme is a dialect of Lisp that was developed to be a cleaner, more modern, and simpler version of Lisp. It retains the same basic atoms and lists as Lisp but introduces other features and improvements.
How does the eval function work in Scheme and why is it significant?
-The eval function in Scheme evaluates expressions. It is significant because it allows for the Scheme interpreter to be used as a function within the programming language, enabling powerful meta-programming capabilities.
What are the differences between the evaluation process for the define function and standard primitive functions in Scheme?
-The define function in Scheme does not evaluate its first parameter as standard functions do. This is because the first parameter is typically a name that has not been bound yet, and evaluating it would result in an error.
Why are explicit input and output considered theoretical anomalies in pure functional programming languages?
-Explicit input and output are considered anomalies in pure functional programming languages because input operations change the state of the program, and output operations can be seen as side effects, both of which contradict the stateless nature of pure functional programming.
How do arithmetic operations work in Scheme and what functions are provided for them?
-In Scheme, all arithmetic operations are implemented as functions. The language specification provides a set of primitive arithmetic functions such as addition (+), subtraction (-), multiplication (*), division (/), and others like absolute value, square root, remainder, and min/max functions.
What is the purpose of the define function in Scheme and how does it differ from variable assignment in imperative languages?
-The define function in Scheme is used to bind a name to a value or a lambda expression. It differs from variable assignment in imperative languages because once a name is bound to a value in Scheme, it cannot be rebound to a different value, making it more like a constant than a variable.
What are the built-in output functions provided by Scheme and how are they typically used?
-Scheme provides built-in output functions like display, which prints the result of an evaluated expression, newline, which prints a new line character, and print, which allows formatted output. However, these functions are often not used directly, as the interpreter's normal behavior is to print the result of any top-level function application.
Outlines
📚 Course Reordering and Emphasis on Functional Programming
The lecturer announces a change in the course syllabus to focus on chapters 15 and 16, which cover functional programming languages and logic programming, respectively. This reordering is strategic to allocate more time for these chapters, as they carry significant weight in both semester tests and the final exam. The emphasis is on Lisp and Scheme, the first functional programming languages, with a brief introduction to functional programming concepts and their theoretical underpinnings. The lecturer also clarifies that while chapter 15 refers to earlier chapters, necessary topics are expanded upon in slides and audio lectures to ensure comprehensive coverage.
🌐 Theoretical Foundations of Functional Programming
This section delves into the theoretical aspects of functional programming, contrasting imperative programming languages that mirror hardware architecture with functional languages grounded in mathematical functions. Functional programming is characterized by a solid theoretical foundation and a user-centric design that prioritizes natural mathematical expression over machine efficiency. The concept of 'function' in programming is explored, including parameterized computations and the avoidance of side effects for clarity and unambiguity in programming.
🔄 Ambiguity and Side Effects in Functional Programming
The potential for ambiguity in functional programming due to side effects is discussed. Side effects occur when a function alters a parameter by reference or modifies a global variable, leading to unpredictable outcomes based on the order of operand evaluation. Two solutions are presented: disallowing functional side effects to enhance language flexibility or enforcing a fixed operand evaluation order, which may limit compiler optimizations.
🔗 Referential Transparency and Its Significance
Referential transparency, a property where equivalent expressions can be substituted without affecting program behavior, is introduced. The breakdown of referential transparency due to side effects or differing function call outcomes is illustrated through examples. The advantage of referential transparency is its contribution to more comprehensible program semantics, which is particularly beneficial in functional programming languages.
🛠️ Pure Functional Programming and Its Principles
The concept of a pure functional programming language is introduced, where variables are entirely absent, eliminating functional side effects and state-associated complexities. Pure functional languages enforce referential transparency, simplifying program understanding. The fundamental difference between computation in imperative and functional programming is highlighted, with the latter avoiding variable management and associated ambiguities.
🌟 Introduction to the LISP Programming Language
The lecture provides an overview of LISP, the first functional programming language, focusing on its data objects and structures, namely atoms and lists. LISP's original typeless nature and its use of symbols and numeric literals are discussed. The notation for lists and function applications, which share a common list form, is explained, setting the stage for more advanced concepts in Scheme, a dialect of LISP.
📝 Function Definitions and Evaluation in LISP
This section covers how functions are defined in LISP using lambda notation, creating nameless functions applied to a set of arguments. The use of lambda expressions for both unnamed and named functions is demonstrated, highlighting the flexibility of LISP's functional approach. The historical context of LISP as a universal programming model is also briefly mentioned.
🚀 Scheme: A Modern Dialect of LISP
Scheme is introduced as a cleaner, simpler, and more modern dialect of LISP, developed in the 1970s. It retains LISP's atoms and lists but adopts static scoping and treats all elements as functions, including operators and statements. Scheme's function-first nature is emphasized, with functions being first-class entities that can be passed and returned from other functions, enabling the creation of meta-programming techniques.
📊 Evaluating Expressions and Arithmetic in Scheme
The evaluation process in Scheme is detailed, explaining how literals evaluate to themselves and function applications are handled by evaluating parameters without regard to order due to the absence of side effects. Arithmetic operations are presented as functions, with Scheme providing a set of primitive arithmetic functions that can be applied to multiple parameters, adhering to the functional programming paradigm.
🎛️ Lambda Expressions and Function Application in Scheme
Lambda expressions in Scheme are explored, allowing the definition of nameless functions with parameters and a body that determines the function's result. The process of applying lambda expressions and binding parameters to these expressions is demonstrated. The use of the 'define' function to associate names with values or functions is introduced, illustrating how constants and function names are created in Scheme.
📑 Output Functions and Theoretical Considerations in Scheme
Scheme's built-in output functions, such as 'display' and 'newline', are mentioned, along with the interpreter's default behavior of printing top-level results. The theoretical perspective on input and output in pure functional programming is discussed, noting that while they represent side effects, they are necessary for practical use and do not significantly compromise the purity of the language.
Mindmap
Keywords
💡Functional Programming Languages
💡Reordering of Chapters
💡Practical Implementation
💡Referential Transparency
💡Functional Side Effects
💡Pure Functional Programming Language
💡Lambda Notation
💡Scheme
💡First-Class Functions
💡Eval Function
💡Define Function
Highlights
The course material will focus on chapters 15 and 16, which cover functional programming languages and logic programming, due to their heavy emphasis in exams.
Practical implementation of code similar to examples in chapters 15 and 16 is essential for exam preparation.
Chapter 15 references earlier chapters, and the讲师 has expanded on these topics in slides and audio lectures.
Only specific functional programming languages, LISP and Scheme, will be in-depth discussed.
Functional programming is based on mathematical functions and is more theoretically solid compared to imperative programming.
Functional side effects, such as modifying parameters by reference or global variables, are generally discouraged due to ambiguity.
Referential transparency, where equivalent expressions do not affect program action, is a key concept in functional programming.
Pure functional programming languages enforce referential transparency by eliminating variables and side effects.
LISP, the first functional programming language, uses a typeless system with atoms and lists as its core data structures.
In LISP and Scheme, function applications and data representation share the same list notation, leading to powerful expressions.
Scheme, a LISP dialect, simplifies and modernizes LISP, emphasizing cleanliness and simplicity.
Everything in Scheme is a function, including operators and statements, which are first-class citizens.
Scheme's eval function allows for the evaluation of expressions provided by the programmer.
Arithmetic operations in Scheme are implemented as functions, differing from traditional operators in imperative languages.
Lambda expressions in Scheme define anonymous functions with bound variables, unlike variables in imperative languages.
The define function in Scheme binds names to values or functions, but unlike variables, these names are immutable.
Scheme provides built-in output functions like display and newline, but top-level expressions are typically printed directly by the interpreter.
Although input and output seem to violate the principles of pure functional programming, they are necessary for practical applications.
Transcripts
we will now skip ahead to chapter 15 of
the textbook which
covers functional programming languages
and we will spend the next
three lectures on this material we will
then move on to
chapter 16 which deals with logic
programming
and prologue after which we'll move back
to some of the earlier chapters
now the reason that i've reordered the
chapters in
this way is so that we can spend more
lecture time
on chapters 15 and 16 and also dedicate
more practical time to the concepts
covered in these chapters
the reason that this is important is
that both the semester tests as well as
the exam
focus quite heavily on chapters 15 and
16
and there are quite a lot of marks
dedicated to these chapters
so it's very important that you focus on
the material
in these chapters when preparing it's
also very important that you do
all of the practicals related to the
material
covered in chapters 15 and 16.
in particular please note that in the
semester tests
and the exam i can ask you to implement
code um similar to the examples that we
will be covering towards the end of
chapter 15
and the end of chapter 16. so be very
sure that you can
do the practical tasks that i set for
you
and those will prepare you well for the
semester tests and the exam
now because of this reordering chapter
15 does refer
to some shorter sections from some of
the earlier chapters
specifically chapters five to eight
i've addressed this by fleshing out
these topics
in the slides and accompanying audio
lectures
so when you are preparing chapter 15 be
sure
to refer to both the textbook as well as
the slides to make sure that you get a
good coverage
of all of the topics that we
look at also important to note at this
point
is that we won't be covering the whole
of chapter 15.
chapter 15 goes into quite a lot of
detail on a number of different
functional programming languages
and we will only be focusing on lisp
and scheme
these are the topics that we will be
talking about in today's lecture
we'll start off with a brief
introduction just setting the scene
for functional programming and why we
are interested in functional programming
we'll then move on to some of the
theoretical
underpinnings related to functional
programming languages
where we'll discuss mathematical
functions mathematical functions being
the basis
of functional programming languages
we'll then move on to
a few fundamental concepts that exist
across a variety of different functional
programming languages
and then we'll very briefly look at the
lisp programming language which we've
already
touched on in chapter 2 and lisp was the
very first
functional programming language we'll
then jump straight into scheme
which as we discussed in chapter 2 is
a dialect of lisp and this is
the primary functional programming
language that we will be focusing on
for this chapter so we'll start off by
looking
at where scheme came from we'll then
look at the scheme interpreter and how
that
operates then we'll look at function
evaluation because
scheme and all functional programming
languages are based on the notion of a
mathematical function
we need to know how mathematical
functions
are evaluated within scheme then we'll
look at
some of the functions that are provided
by
scheme in terms of the primitive numeric
functions which will allow
us to perform simple arithmetic
operations
we'll then look at how we actually go
about defining functions within scheme
and then we'll finish off this lecture
with a look
at output functions that allow us to
print results
to a terminal
as we saw in chapter one imperative
programming languages
are the most dominant kind of
programming languages
that we see in the world today and these
programming languages
are based directly on the computing
hardware that they were designed for
namely the von neumann architecture
now i won't go into any further detail
on the von neumann architecture again
because we've already discussed that but
the important points
to recall is that for these imperative
programming languages
efficiency is the primary concern and we
saw in chapter two
that this was very well illustrated by
the fortran programming language and
these languages
are very efficient because they are
essentially
direct reflections of what is happening
on a hardware level
so also then with imperative programming
languages because they
are designed with the computing hardware
in mind
the suitability of these programming
languages for software development
is far less important
so if we look then at functional
programming languages their design
is based on mathematical functions and
we'll discuss mathematical functions in
more detail in a moment
but because these functional languages
are based then
on mathematical principles they are
defined by a much
more solid theoretical basis than
imperative programming languages
are and they're also considered to be
far closer to the user
in the sense that mathematics is
developed for
people to understand rather than for
machines to understand
also in general functional programming
languages
are not very concerned with machine
architecture
they don't focus on things like
efficiency of
execution so they're very
programmer-centric they try to give the
programmer a much
more natural mathematical way of
expressing their programs
now we've seen that functional
programming languages are based on the
idea
of mathematical functions however we
need to define
what we mean when we talk about a
function
so a function is a kind of sub-program
and a sub-program is a collection of
parameterized computations
so we can think of a sub-program as a
package
of related computational operations and
the behavior of the computational
operations is modified by sending
different parameters
to our sub-program now a function
in particular produces results by means
of returning
a value now we also have the idea of
side effects that can be caused by a
function and we call
these functional side effects
so a functional side effect is any
change
that the function causes outside of the
scope
of the function and from a practical
perspective what this means
is that a functional side effect occurs
whenever a function
changes a parameter that has been sent
to the function
by reference or if it modifies a global
variable
now in general functional side effects
are considered to be
bad but why is this the case
well essentially this is because it
leads to ambiguity
when we have an expression that
references
a function and then the function
also modifies another operand within the
same expression
so let's look at a practical example
over here to illustrate
this concept here we have a variable a
which has a value of 10
assigned to it and then on the next line
we have
an expression which we can see over here
the expression has an addition operator
and this addition operator has two
operands
left operand which is just the value of
the variable a
and the right operand which is a call to
our function
fun and we can see that we have passed
through
this variable a as a parameter
to our function the ampersand over here
is c or c plus plus like notation
and that indicates that we are passing
through that variable
by reference so in other words if the
function
modifies that parameter that has been
sent through
then it is actually modifying the value
of the variable
a so then once we have a result for our
addition we then assign
that value to a second variable which is
called
b now a potential ambiguity then
arises when we consider the order that
the operands
of the addition operator are evaluated
in
so these operands can be evaluated in
any order because we just
need values for the two operands before
we can compute the result
of the addition now if we
evaluate the left operand first
then it will receive a value of 10
and that will then be the value for the
left operand the right operand then is
our function call and we again then pass
through the value of
a which is 10 and then we will assume
that this function then produces a
result but before
it produces that result by means of a
return
it also then modifies the value of
a and let's just say then that it
increments the value of
a for argument's sake so what will then
happen is after that function is called
then a's value will have been
incremented from 10 to 11.
however that increment does not affect
the
left operand because it already has a
value
of 10. so in other words the result
of the addition is then 10 plus
whatever has been returned from the
function let's say that the function
returns a value of 5
then we have a result of 15 which is
assigned to
b however now let's consider a situation
where the
right operand is evaluated first and
then the left operand is evaluated
so in this case we now call our function
and once again
our function will return a value of 5
however before it returns the value of 5
it then
modifies the value of a by incrementing
it so now a's value has been incremented
from 10
to 11. so this means then that the left
operand will now get a value of
11 because this value is determined
after this function call in the
right operand has taken place so in
other words we now have a result
of 11 plus 5 which gives us then the
value of 16
which is assigned to the variable b
so we can see then that the expression
evaluates to
a different value and then results in a
different value for the variable b
depending on the order that we evaluate
the operands
for the addition operation
and this ambiguity has arisen
specifically because
of the side effect that this function
occurs
which is the modification of the
parameter that has been sent
to the function by reference
so consider now a situation
where we have the same kind of
expression
however the function does not modify
a parameter that has been sent to it
instead
it modifies a global variable
so what i would like you to do at this
point is pause the video
and consider how that kind of situation
would result in the same kind of
side effect which would then result in
the same kind of ambiguity
there are two possible approaches we can
use to solve this problem of ambiguity
introduced by functional side effects
and both of these approaches
are based on the definition of the
programming language we are using
the first solution is that we can simply
disallow
functional side effects so this means we
have to disallow any mechanism that a
function can use
to modify a variable value outside of
the scope
of the function this implies that we
cannot have
any support for two-way parameters
for our functions and also we cannot
allow any non-local references within
functions
because a non-local reference implies
that a function can modify
a global variable so of course this
approach does work
because we've eliminated the two
possible ways that functional side
effects can occur
however the main disadvantage is that
this reduces
the flexibility of our programming
language
so we lose flexibility because we can
only then support one-way parameters in
other words we can only send data to a
function by means of parameters
we can't get data out of a function by
means of
parameters so in other words the only
way that a function can produce a result
is by means of its return value
secondly we also lose flexibility
because
we no longer have any support for
non-local references
the second approach we can use to solve
this problem of ambiguity introduced by
functional side effects
is that we can demand a fixed operand
evaluation order
so in other words we demand within the
language specification
that operands must at least appear to be
evaluated
in a particular order so java uses this
approach
the language specification requires that
operands must at least seem to be
evaluated from
left to right now the main disadvantage
of this approach
is that it limits some compiler
optimizations that could be performed
sometimes compiler optimizations will
result in operands being evaluated in a
different order
if that reordering of operand evaluation
will improve the performance
of the program's execution
so this kind of compiler optimization
then in certain cases will not be
possible
because we may have to evaluate
a left operand before a write operand
and we don't have any choice over that
in certain other situations where the
compiler can determine that no possible
side effect can occur
it may then allow the operands to be
evaluated out of order
and in that case a compiler optimization
can be performed
but the point is that compiler
optimizations cannot be performed
in every case where they would normally
be possible
a concept that is very closely related
to functional side effects
is the idea of referential transparency
now we can say that a program has
referential transparency
if any two expressions that are
equivalent
can be substituted for one another in a
program
and this substitution does not affect
the action of the program
one cause of referential transparency
breakdown
is functional side effects but there are
also other
causes so this definition may seem like
a bit of a mouthful
so let's illustrate it in terms of a
practical example
over here we have two programs
and let's look at the first program so
over here we have an expression
and we assign then the result of that
expression to
a variable called result one if we look
at the expression in detail we see that
there is
a division operator and it has a
left operand and a right operand
so if we look at the left operand we can
see that we have a call to a function
and we pass through a parameter which is
the variable a
we then take the value returned by our
function
and we add to that the value of another
variable
b if we look at the right operand of the
division we see
a fairly similar structure there so we
again
have a call to the function with the
same parameter the variable a
and then we take the result returned by
our function and we subtract from that
the value
of a variable a now
if we look at this expression we can see
that we have
two repetitions of exactly the same
function call
with the same parameter in each case
therefore it should be reasonable for us
to separate this function call out
as we do in the second program over here
take the result returned by that
function call and assign it to a
variable called
temp and then we just simply use
temp within exactly the same expression
rather than two separate calls to the
function
so what we have here now is two
expressions
this is the expression in our first
program
and this is the expression in our second
program
and these two expressions are equivalent
to one another because they describe
exactly the same
kind of arithmetic operation
so we now need to look at the values
of the variables result 1 and result
2. now if our function has no side
effects
then result 1 will be equal to result
2. however if result 1 and result
2 are not equal to each other due to a
side effect
then referential transparency has been
violated
right so how can referential
transparency then
break in this example right so let's
assume
first of all that our variable b
in this case is a global variable
and let's assume that the function in
its implementation
modifies this global b variable
so now let's look at our first
expression
here we have two calls to our function
and each of those calls modifies the
global
b variable so what this means then is
that b
has been modified twice in the second
example we call
our function only once meaning that it
will only modify
our global b variable one time
now we can see that the result of
our expressions in the two separate
programs depend on the value of
b so if b has been modified
twice in the first case but only once in
the second case
this then means that the values of the
two expressions must be different from
one another
meaning that result one and result two
have different
values and this means then that
referential transparency
has broken down another way
that referential transparency can break
down is if
we modify the parameter value
for the function so in our first example
over here we can see that we call
the function twice now if we assume
that the function then modifies its
parameter value
we can see that we will be modifying the
value of a
twice because we have two calls to the
function
in the second case we are calling the
function once
meaning that we are only modifying the
value of a
one time so again this then means
in the first expression we have modified
a
twice in the second expression we have
modified
a only once and therefore the
results of the two expressions will be
different and so
once again the values of result 1 and
result
2 will differ and we again have then a
breakdown
of referential transparency
so what i would like you to do at this
point is to pause the video
and try to determine if referential
transparency can break
in other ways so using this
same example we can then see
that we had a referential transparency
breakdown
occur because in the two
separate programs we had different
values
for b or a that occurred
due to the different number of function
calls that took place
so the only other way that breakdown of
referential transparency can occur
is if we have our function calls
and for some reason the second function
call
produces a different value than the
first
function call in that case what will
happen then
is that we will have a different value
for this function call in our first
example over here
whereas in the first case we will only
have
one call to our function meaning that
temp
will have the same value in both
positions that it is
used so what i would like you to do now
is to think of
ways that this kind of situation could
arise in other words how could the
second call to our function
produce a different return value
now that we've defined referential
transparency
what advantage is associated with it
well what we see is that if a
programming language enforces
referential transparency then programs
written in this language
have semantics that are much easier to
understand
so if we look at the example on the
previous slide
we saw that there was ambiguity in terms
of the value of the two expressions
even though the two expressions should
have been equivalent
to one another this kind of ambiguity
is completely eliminated if we use a
programming
language that ensures that referential
transparency
is maintained so this leads us directly
to
functional programming languages a pure
functional programming language
is a functional programming language
that strictly adheres
to the principles of functional
programming
now in a pure functional programming
language
there is no support for variables at all
now this may seem a little strange and
you
may even wonder whether it is possible
to write
programs without the use of variables
but as we will see
through the remainder of this chapter it
is entirely possible to write programs
without
using variables now why
is the lack of support for variables
important
in a pure functional programming
language
well let's consider a function that we
might implement now because variables
don't exist
global variables can't exist in the
first place
so in other words the function then
can't modify
global variables also parameters
are not variables which means that
parameter values cannot be modified by
the function
in other words they must be constant
values that are simply
passed into the function as inputs
so what this means then is that we have
eliminated the two possible sources
for functional side effects we also
see that functions cannot have a state
associated with them
and this is because state must always be
stored within
some kind of variable or set of
variables so what this then means is
that the value
that a function returns depends entirely
on its parameter values in other words
if we have
a function call and it receives
a particular set of parameter values and
then later we call the same
function with the same set of parameter
values then it is guaranteed that
both of those function calls will return
exactly the same
value so this relates then to the
question
that i asked at the end of our
discussion
for the previous slide
so in other words what this then means
is
that via the simple elimination of
variables from our programming language
we have actually then ensured that
these languages then enforce referential
transparency
which then as we've seen ensures that
the semantics of programs written in
these languages
are much easier to understand and follow
so we see that the objective of a
functional programming language's design
is to mimic mathematical functions
as closely as possible this means that
the basic process of computation
in a functional programming language is
fundamentally different
to what we see in an imperative
programming language
so in an imperative programming language
expressions are evaluated these
evaluations produce results
and then the results are stored in
variables and are used at a later stage
this means that the management of
variables then is a constant concern
and it results in a lot of complexity
associated with imperative programming
in a purely functional programming
language on the other hand
variables are not used and this is also
the case
in mathematics so this means then that
none of the complexities associated with
variables have to be dealt with we don't
need to manage variables
and we also don't need to deal with the
associated ambiguity
that stems from the use of variables
we'll now look fairly briefly at the
lisp programming language which will
lead us directly to
a more detailed discussion on scheme
which is
a dialect of lisp so lisp as you should
recall
from chapter 2 was the very first
functional programming language
unfortunately it's fairly difficult for
us to talk about lisp
in its original form because the
language has undergone
so many changes and there are so many
dialects of lisp
that have existed over the years so
we'll limit
our discussion to features that are
common within
most dialects of lisp so first of all we
need to talk
about the data that we can represent
within a
lisp program so we will talk about
data objects and data structures
now notice that we talk about data
objects and not data types
and this is because lisp was originally
a
typeless language so
data objects that we can manipulate
within
our lisp programs can only be either
atoms or lists
an atom is a single value that we can
work with
and there are two types of atoms namely
symbols
and numeric literals symbols have
identifiers in other words names such as
a and x now it's important to understand
that a symbol is not a character or a
string it's simply a
name for a concept that the program
can work with so a symbol may represent
an abstract
idea or it may represent some sort of
object
in an environment that lisp is
processing somehow now the reason
that we represent symbols in this way
is that this kind of abstract concept
processing
was central to artificial intelligence
research at the time that lisp was
developed
and as we saw in chapter 2 lisp was a
programming language designed for
artificial intelligence applications
the second kind of atom that we have is
the set of numeric literals and these
are simply numeric values such as 4.8
or 26 we then
have lists which are stored internally
as single linked lists and these linked
lists then store
sequences of atoms um
as well as sub-lists and we can have any
kind of mixture of different atoms
with sublists in any particular kind of
structure
that we would like so here's an example
then
of list form notation within
the lisp programming language we can see
that
the lists are delimited by means of
parentheses
so here we have the start of a list
and here we have the end of a list
so this list then contains four items
the first two are atoms
and they are symbolic atoms so we have
a and we have b and these are both
symbols then the third item
in the list is another list so we can
see that it's been again delimited by
means of these parentheses
and this nested list then contains once
again two
symbols and these symbols are
c and d in this case and then the fourth
element
contained in the outer list is again
then
a symbol and in this case it is the
symbol
e in lisp terminology
when we call a function we say that we
apply that function
now it turns out that data and function
applications
in lisp have exactly the same form and
they both
use a list notation so
if we have this list notation over here
which is
a list that contains three
symbols a b and c we can interpret this
either as data or as a function
application
if we interpret it as data then we have
a simple list containing three atoms
so in other words the list contains only
three atoms it doesn't include any
sub-lists
and then the three atoms that are
contained within the simple list
are the symbolic atoms a b
and c alternatively we can interpret the
same list
as a function application and in this
case
we are applying a function which is
named a
to two parameters and the parameters are
the symbolic atoms
b and c now
this ambiguous notation may seem
counterproductive
but we're going to see later on when we
look at
scheme that this in fact allows us
to do incredibly powerful things within
the
programming language next we need to
look at function definitions because of
course in a functional programming
language we have to be able to define
functions and in lisp we use lambda
notation in order to specify
function definitions so over here we
have
a lambda expression and this represents
a nameless function so this function has
no name associated with it
it is applied to a set of arguments and
in this case
we have n arguments they are separated
by
spaces we then have an
expression and this expression then
defines
what the nameless lambda function
actually
does in c plus terminology the
expression would be the body of the
function
now it may seem like a bit of a
pointless thing
to do to create functions that don't
have names
but very often these nameless functions
on their own
are fairly useful so sometimes we want
to
define a function and just simply use it
where we define it in this case we then
don't need to attach
a name to the function at all so we can
just simply
use the lambda expression now we can
also then attach a name to a lambda
expression and we would then
say that we are binding a name to a
lambda expression
which simply means that we are
associating
a name with the lambda expression so
over here we have
an example of what this kind of notation
would look like
we can see that we have our lambda
expression over here which defines a
nameless
function again this function is applied
to in arguments and we then have an
expression which defines
what the lambda function does we then
additionally specify
a function name and from this point on
when we use that name
we are now actually referring to this
lambda
expression now when we look
at the first implementation of a
lisp interpreter we see that
it was in fact implemented entirely just
to demonstrate the universality of
the functional programming model
so much in the same way as
turing machines were used to reason
about computability within imperative
programming languages
and one can define a universal turing
machine
that can be used to specify any other
turing machine
so we can also define a universal lisp
function that can evaluate any other
lisp function and so this universal
lisp function then demonstrates the
universality of the computation
that lisp can perform
we've now looked at lisp in fairly
superficial terms
and this is intentional because we will
now
transition into a much more detailed
discussion
on scheme and as we've previously
pointed out scheme
is a dialect of lisp so scheme was
developed in the mid-1970s and it was
designed to be
a much cleaner more modern and far
simpler version of lisp
than the contemporary lisp dialects that
were available
at the time now scheme uses exactly the
same
atoms and lists as lisp does
as far as atoms go scheme
also uses numeric atoms as well as
symbolic atoms exactly as we saw
with the lisp programming language
scheme
also uses static scoping exclusively
and static scoping is a very simple
intuitive approach
to scoping what's also important to
understand for scheme
is that everything within the
programming language
is a function so this includes things
that would
be operators or statements within an
imperative programming language so for
example we don't have
an edition operator in scheme we have an
addition function the same holds for
selection structures so instead of
having an if statement
we have an if function
functions in scheme are also first class
entities
so this means that expressions can
evaluate
two functions so we can have an
expression that can compute a function
in other words
functions can also be elements within a
list so we can have
a list which is a sequence of functions
and functions can also be passed as
function parameters so we can send a
function
to another function by means of a
parameter
and then finally functions can also be
returned
from other functions this is a very
powerful concept as we'll see
towards the end of our discussion on
this chapter
because it means that we can write
functions
that can build other functions
now scheme is an interpreted programming
language
in exactly the same way that the
original lisp implementations
were interpreted a scheme interpreter
typically provides an interactive mode
which is a kind of a
terminal mode that operates in an
infinite loop of
read evaluate and print operations
so in this interactive mode you would
type in
a scheme expression this expression
would be read and it would then be
evaluated
and then the result of the evaluation
would be printed out
the interpreter would then wait for you
to type in another expression and this
whole process
would repeat until eventually you
terminate the
interactive mode this form of
interpreter is also used by python
and ruby now most scheme interpreters
also accept source files as input and
in this case the source file is
interpreted in
a kind of a batch mode and this will be
the approach
that you will use for your practical
implementations related to scheme
now expressions in scheme are
interpreted
by a function called eval so what this
means is that the scheme interpreter is
actually available to the programmer
by means of a scheme function and this
is a very powerful
concept which we'll look at in more
detail later on
when we discuss the eval function in
more detail now literals in scheme
evaluate to themselves so if the
interpreter evaluates
the literal 4 then the result will just
be
the literal 4 itself if the scheme
interpreter
evaluates the symbolic atom
a for example then this will also
evaluate to the symbolic atom a
next we need to look at how the scheme
interpreter
evaluates function applications
so when a function application is
encountered
first of all all of the parameters that
the function
is applied to must be evaluated
and this parameter evaluation happens
in no particular order now in this
context
no particular order does not mean that
the parameters are evaluated in a random
order
rather it means that the order that the
parameters are evaluated in
is not important so why is this order
not
important well as we've seen a pure
functional programming language such as
scheme
has no functional side effects so what
this means then
is that none of the parameter
evaluations
can affect any other parameter
evaluations
each parameter evaluation therefore is
independent
and so the order does not matter
and cannot affect the final outcome of
the evaluation
so once all of the parameters have been
evaluated
we now have a value per parameter
and these values are then substituted
into
the function body the function body is
then evaluated
and then very importantly the value of
the last
expression evaluated in the body is the
value
that the function defines you can think
of the value that the function defines
as the value that the function returns
if we turn our attention to arithmetic
operations in scheme
we must remember that all of these
operations
are implemented as functions and this is
because
everything within scheme is a function
now the scheme language specification
provides a set of primitive
arithmetic functions so we have
addition subtraction multiplication and
division and these use the same notation
that we are used to from
imperative programming languages such as
c
plus we also have a function that can
compute
an absolute value of a parameter
a function that can compute the square
root
of a parameter a function that can
compute the remainder of
an integer division and then a
min and a max function that
will find respectively the minimum and
the
maximum value within a set of parameters
now also at this point note that the
notation that we will be using
for these function names where they
include alphabetic
characters will be all uppercase and
this is the convention that the textbook
uses
however a lot of scheme interpreters
use lowercase letters for these function
names
so just keep this in mind when
you get to actually implementing scheme
programs
so when we apply these functions we use
the standard
list notation that we saw when we were
discussing
the lisp programming language so over
here we have
a function application we are applying
the
plus function to two parameters where
the first parameter is five
and the second parameter is two the
result of this function application is
then simply the sum
of the two parameter values so in other
words this function application will
then
yield a value of 7.
now all of these primitive arithmetic
functions
can be applied to multiple parameters
except
for the absolute value and square root
functions
both of which can only be applied to a
single parameter value
so over here we have an example of the
application
of the addition function to
four parameter values and
the result of this function application
will then
just be the result of adding 5 2
8 and 9.
we can also define lambda expressions in
scheme
and the form of this definition is based
on lambda notation which we saw
previously
so over here we have a lambda expression
in
scheme you can see that we use the
lambda function followed by a
list of the parameters that the
nameless lambda function will be applied
to
after the list of parameters we have the
body of our lambda function and in this
case
the body then defines the result of
our lambda function which is the single
parameter value
multiplied by itself in other words what
we have defined here then
is a nameless function that is applied
to
a single parameter and it yields
that parameter value squared
so x then in this case is referred to
as a bound variable
x has a value bound to it when
this nameless lambda function is applied
to a parameter and this binding then
is unchanged from this point on so in
other words
x is not a variable in the sense that we
are used to in
an imperative programming language
because it can't be assigned
to after its initial binding
so let's look at how a lambda expression
then can be
applied so over here we have the
lambda expression that we previously
defined an unnamed function
that is applied to a single parameter
and this unnamed function
yields the parameter value multiplied by
itself
we now place this lambda expression
inside
another list starting there and ending
there and then we provide
after the lambda expression
the parameters that we want to apply
this nameless lambda function 2. so in
this case
we have provided then the single
parameter value which
is 7 and what this then means is that
the value
7 is bound to the bound variable x
over here we can now no longer change
the value of x after this point
and so the application then of the
lambda expression
yields 7 which is the value of x
multiplied by itself which then yields
a result of 49
now a lambda expression of course can
have any number of parameters
so over here we have a lambda expression
that defines
a nameless function which is applied to
three parameters and the parameters are
named a
b and x respectively and then over here
we have the
body of our nameless lambda function
the body computes a multiplied by
x squared over here and then
also b multiplied by x over there
and then it adds these two values by
an application of the plus function
so we've seen that we can define a
nameless function
using a lambda expression however
oftentimes we do want to associate
a name either with a value or with
a function in scheme and to do this
we use a special function provided by
the scheme
language system called define
so the define function can be used in
two different ways
the simplest way it can be used is to
bind a name
to the value of an expression so over
here we have two examples
of this usage over here we are applying
the define
function and we provide then first of
all a name and then secondly
an expression now in this first example
the expression is
simply a numeric literal 3.141593
so that value then is bound to the name
pi and what this means is from this
point on
in our scheme program the name pi means
the value 3.141593
so over here we have then a second use
of the define function again we provide
the function name define
and we provide a name in this case 2 pi
and then we provide an expression so
over here we can see that we have
an arithmetic expression it's an
application
of the multiplication function to
the parameters 2 and pi
so what this will then do is it will
retrieve the value 3.141593
for the name pi and it will multiply
that
by 2 producing a result which is the
value of that expression
and then that value is bound to 2
pi now what's important to understand is
that these name bindings only occur
once so in other words we cannot bind a
different value to pi
or to 2 pi so what this then
means is that these names do not work
like variables
in standard imperative languages like c
plus in those languages we can reassign
to a name if it is a variable
in the case of a name in scheme we
cannot
rebind a different value to it so in
other words these names behave
more like constants so
then the second use of the define
function
is to bind a name to a lambda expression
in other words we are binding a name
to a function and we're going to see
this use
of the define function repeatedly
through
the remainder of this chapter so here we
have
an example of that we apply
the define function and we provide then
first of all a list and this list
contains
the name that we want to bind to the
function
as well as the parameters that we want
the function to be applied to
in this case the function can only be
then applied
to one parameter then we have
the function body which is expressed
over here
so essentially what we are doing then is
we are binding the name
square to a function
which can be applied to a single
parameter
and the result of that function then
is the result of multiplying the
parameter
by itself so now
we can use the name in a function
application
which we do in this example over here so
here we are
applying the square function
and we have bound the name square
to the function that we've defined so we
are applying that function
to the parameter 5.
what this then means is that this
function application will be the result
of multiplying
5 by itself and so the result
of the function application will be 25.
now it's important to understand that
the evaluation process for define
is different to the standard primitive
functions that we've spoken about before
in the context of
arithmetic functions so the first
parameter is
not evaluated as it would be in a normal
function
and the reason for this is that if it
were evaluated then scheme
would find that it was undefined so for
example here if we were to evaluate the
define
function the way that we normally would
evaluate a function
then each of the parameters namely the
name pi
and then the value 3.141593
would need to be evaluated however
because the name
pi has not been bound yet this would
then be
an invalid evaluation and this would
produce
an error which would be reported by the
scheme
interpreter so it's important to
understand that define
is a special kind of function that does
not behave the way that
a normal function in scheme does
scheme also provides a number of built
in output functions
the first of which is display
so the display function is applied to
an expression and this expression
is evaluated and then the result of the
expression
is printed out to the screen there is
also
a function called newline and the
newline
function is not applied to any
parameters
and simply prints out a new line
character
to the screen scheme also has
a c like print if function which allows
you to produce
formatted output but we won't go into
any detail on this
function here in general however
these output functions are not used
and the reason for this is that programs
can simply use
the interpreter's normal output the
interpreter's normal output
behavior is that any top level function
in other words
a non-nested function that produces
a result will simply then have that
result
printed to the screen now
it's also important from a theoretical
perspective to understand
that explicit input and output should
not
actually be part of a pure functional
programming language
this is because input operations change
the state
of the program and as we've seen a pure
functional programming language should
not maintain any kind of state
secondly output operations can be seen
as
side effects because they are producing
a result
outside of the bounds of the functions
that are being executed
so in a sense then a pure functional
programming language is not really
possible
because input and output operations must
be included
for the programs to be useful however
in practice inputs and output operations
represent fairly benign
side effects that do not to drastically
affect the pure nature of a functional
programming language so that concludes
this lecture
in the next lecture we will continue
with our discussion on the scheme
programming language
5.0 / 5 (0 votes)