COS 333: Chapter 15, Part 1

Summary

The 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

00:00

📚 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.

05:02

🌐 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.

10:02

🔄 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.

15:04

🔗 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.

20:06

🛠️ 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.

25:07

🌟 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.

30:10

📝 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.

35:13

🚀 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.

40:14

📊 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.

45:14

🎛️ 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.

50:16

📑 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.

Keywords

💡Functional Programming Languages

Functional programming languages are a category of programming paradigms that treat computation as the evaluation of mathematical functions and avoid changing-state and mutable data. In the video, the instructor emphasizes the importance of understanding functional programming languages, particularly LISP and Scheme, due to their significant role in chapters 15 and 16 of the textbook and their focus in exams.

💡Reordering of Chapters

The concept of reordering chapters refers to the instructional strategy of changing the sequence of textbook chapters to allocate more time and emphasis on certain topics. The script mentions that chapters 15 and 16 are reordered to allow for a deeper dive into functional and logic programming, which are heavily weighted in the exams.

💡Practical Implementation

Practical implementation in this context involves applying theoretical knowledge to execute tasks, such as writing code. The script stresses the importance of completing all practicals related to chapters 15 and 16, as the ability to implement code similar to the examples given is a requirement in the semester tests and the exam.

💡Referential Transparency

Referential transparency is a property of a function or expression in which the expression can be replaced with its value without changing the program's behavior. The script explains that referential transparency is crucial for ensuring the predictability and reliability of a program, and it is a fundamental aspect of functional programming languages.

💡Functional Side Effects

Functional side effects are changes that occur outside the scope of a function, such as modifying a global variable or a parameter passed by reference. The script discusses the problems caused by functional side effects, such as ambiguity in the order of operand evaluation, and how they can be mitigated in functional programming languages.

💡Pure Functional Programming Language

A pure functional programming language is one that strictly adheres to the principles of functional programming, including the absence of mutable state and variables. The script explains that in pure functional programming languages like Scheme, functions rely solely on their inputs to determine their outputs, which enforces referential transparency.

💡Lambda Notation

Lambda notation is a way of defining anonymous (nameless) functions in functional programming languages. The script describes how lambda notation is used in LISP and Scheme to create functions on-the-fly, which can then be used immediately or passed as arguments to other functions.

💡Scheme

Scheme is a dialect of the Lisp programming language, designed to be a cleaner and simpler version of Lisp. The script discusses Scheme extensively, highlighting its features such as the use of atoms and lists, first-class functions, and its role as a primary focus for the lectures.

💡First-Class Functions

First-class functions are a concept where functions are treated as first-class citizens in a programming language, meaning they can be assigned to variables, passed as arguments, and returned from other functions. The script explains that in Scheme, functions are first-class entities, allowing for powerful programming constructs.

💡Eval Function

The eval function in Scheme is a built-in function that evaluates expressions. The script mentions that the Scheme interpreter uses the eval function to interpret expressions, demonstrating the reflective and meta-programming capabilities of Scheme.

💡Define Function

The define function in Scheme is used to bind a name to a value or a lambda expression, effectively creating named constants or functions. The script illustrates how define is used to create named functions and emphasizes that names bound using define cannot be rebound, akin to constants rather than variables.

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