COS 333: Chapter 6, Part 3

Summary

This lecture delves into advanced data types, focusing on unions, pointers, and references, and their implications on memory management and type safety. It distinguishes between free and discriminated unions, highlighting the dangers of type-unsafe operations in C and C++. The lecture also explores strong versus weak typing, type equivalence, and the role of type checking in preventing errors, concluding with a brief introduction to data type theory and its significance in programming language design.

Takeaways

• 📚 The lecture concludes the discussion on Chapter Six, covering advanced topics like union types, pointer and reference types, type checking, strong versus weak typing, type equivalence, and data type theory.
• 🔄 Union types allow a variable to store different data types at different times but only one value can be set at a time, sharing the same memory space for all fields.
• 🛠️ Unions are useful for conserving memory space when only one of multiple variables is in use at a time, but they are less useful in modern programming due to the abundance and affordability of memory.
• ⚠️ Free unions do not support type checking and can lead to unsafe programming practices, while discriminated unions, supported by languages like Ada, include type checking for safety.
• 🔬 Discriminated unions use a 'discriminant' or 'tag' to track the type of data stored, preventing errors associated with accessing the wrong fields.
• 👀 Pointers store memory addresses and can be used for indirect addressing and dynamic memory management, but they can introduce complexity and potential errors like dangling pointers and memory leaks.
• ➡️ Pointer arithmetic allows for the manipulation of memory addresses to access different parts of memory but requires careful handling to avoid out-of-bounds access.
• 🔐 References in languages like C++ and Java provide a safer alternative to pointers for indirect addressing, as they cannot perform pointer arithmetic and must always be initialized.
• 🔄 Coercion can weaken typing in programming languages by automatically converting types to match operators, potentially masking type mismatches.
• ⚖️ Strong typing ensures that type errors are always detected, leading to more reliable code, while weak typing may allow certain type errors to go undetected.
• 📘 The lecture touches on type theory, distinguishing between practical type theory relevant to commercial programming languages and abstract type theory, which is of more interest to theoretical computer scientists.

Q & A

What is a union type in programming?

A union type is a type that can store values of different types at different times during execution. It is characterized by the fact that only one of its fields may contain a value at a time, and all fields within a union share the same storage space.

Why are unions considered less useful in modern programming languages?

Unions are considered less useful in modern programming languages because they were particularly useful in the early days of computing when memory was scarce and expensive. Today, with large and comparatively cheap memory, the need for conserving memory space through unions has diminished.

What are the two design issues that arise when implementing unions in a programming language?

The two design issues are whether type checking should be required for unions and whether unions should be embedded within records or be a separate type on their own.

What is the difference between free unions and discriminated unions?

Free unions do not support type checking, leaving it to the programmer to track which type is stored. Discriminated unions, on the other hand, support type checking through the use of a discriminant or tag that helps check the type of the union and detect errors when invalid fields are accessed.

Why are pointers considered dangerous in programming?

Pointers are considered dangerous because they can lead to issues like dangling pointers and lost heap dynamic variables. They also increase the number of routes to access a specific line in a program, similar to the 'go-to' statement, which can complicate program flow and make it harder to understand.

What are the two fundamental operations that must be supported for pointers in a programming language?

The two fundamental operations for pointers are assignment, which allows setting a pointer's value to a memory address, and dereferencing, which retrieves the value stored at the location a pointer refers to.

What is pointer arithmetic, and how is it used?

Pointer arithmetic allows the addition of values to pointers to compute offsets from a specific memory location. It is used to access elements in arrays or to navigate through memory addresses.

What is the difference between a pointer and a reference in programming?

A pointer stores the memory address of a value it refers to, while a reference is an alias for another value. Pointers can be manipulated as addresses, whereas references are treated as the values they refer to and cannot perform pointer arithmetic.

Why are references considered safer than pointers?

References are considered safer than pointers because they cannot be used for pointer arithmetic, which prevents errors like accessing memory beyond the bounds of an array. Additionally, references must always be initialized to an existing object, avoiding the issue of uninitialized or dangling references.

What is type checking, and why is it important?

Type checking is the process of verifying that the operands of an operator are of compatible types. It is important because it helps ensure that operations are performed on the correct types of data, preventing type errors that could lead to unexpected behavior or program crashes.

What is the difference between static and dynamic type checking?

Static type checking is performed at compile-time and can catch type errors before the program runs. Dynamic type checking occurs at runtime and may result in runtime type errors if the types are not compatible.

What does it mean for a programming language to be strongly typed?

A strongly typed programming language is one that always detects type errors, ensuring that all variable misuses causing type errors are caught, typically at compile-time.

What is type equivalence in the context of programming languages?

Type equivalence defines when operands of two types can be substitutable with no coercion taking place. It sets the rules for which types are acceptable for all operators and can be based on either name type equivalence or structure type equivalence.

What are the potential drawbacks of implementing structure type equivalence in a programming language?

Implementing structure type equivalence can be complex and may lead to potential problems such as difficulty in differentiating between types with the same structure but different meanings, and the need to answer a multitude of questions regarding how types should be considered equivalent.

What is data type theory, and what are its branches?

Data type theory is a broad area of study concerned with data types and their properties. It has two main branches: practical type theory, which deals with data types in commercial and real-world programming languages, and abstract type theory, which often involves typed lambda calculus and is of interest mainly to theoretical computer scientists.

Outlines

00:00

📚 Lecture Overview and Union Types

This paragraph introduces the final lecture of Chapter 6, summarizing topics such as union types, pointer and reference types, type checking, strong versus weak typing, type equivalence, and data types theory. The focus then shifts to union types, explaining them as a storage mechanism for values of different types at different times, with a unique characteristic of shared storage space among fields. The paragraph highlights the use of unions in memory conservation and their reduced utility in modern computing due to abundant and affordable memory.

05:03

🔍 Design Issues and Examples of Unions

The paragraph delves into the design considerations for implementing unions in programming languages, such as type checking requirements and whether unions should be distinct or part of records. It contrasts free unions, which lack type checking and can lead to unsafe memory access, with discriminated unions, which include a type indicator for safer usage. Examples in Fortran, C, and C++ are provided to illustrate the concepts, emphasizing the importance of programmer awareness in tracking the current value in a free union.

10:04

📘 Discriminated Unions and Memory Efficiency

This section provides a detailed explanation of discriminated unions, which include a discriminant or tag for type checking. An example using a 'figure' union in Ada demonstrates how this type can store data for different shapes with shared memory space, making storage more efficient. The memory layout for a 'figure' union is described, showing how the discriminant guides the storage and retrieval of data for shapes like circles, triangles, and rectangles.

15:05

🚫 Drawbacks of Unsafe Unions and Pointers

The paragraph evaluates the safety of unions, particularly unsafe free unions, and compares them to discriminated unions supported by languages like Ada. It suggests avoiding free unions for reliability and points out that modern languages like Java and C# do not support unions due to safety concerns. The discussion then transitions to pointers and references, explaining their roles in indirect addressing and dynamic memory management, and the associated design issues that programming languages must address.

20:05

🔄 Pointer Operations and Dynamic Memory Management

The focus shifts to pointer operations, specifically assignment and dereferencing, which are fundamental to working with pointers in languages like C and C++. The paragraph illustrates how pointers can be assigned memory addresses and how dereferencing retrieves values from those addresses. It also touches on the dangers of pointers, such as dangling pointers and memory leaks, and the importance of careful management of dynamic memory allocation and deallocation.

25:07

🛠️ Practical Use of Pointers in C and C++

This section discusses the practical implementation of pointers in C and C++, highlighting their flexibility and potential dangers. Pointer arithmetic is introduced, along with the explicit use of dereferencing and address-of operators. The paragraph also explains the concept of void pointers, which can point to any data type after being cast, and how this affects type checking in these languages.

30:08

🔬 Deeper Look at Pointers and References

The paragraph provides a deeper analysis of pointers and references, emphasizing the safety of references over pointers due to the inability to perform pointer arithmetic on references. It also discusses the memory conservation benefits of references, as they do not require copying values. However, it notes that references can still lead to dangling references and memory leaks, which are common issues with pointers.

35:08

🏭 Evaluation of Pointers in Programming Languages

The paragraph evaluates pointers in the context of programming language design, noting the problems associated with pointers, such as manual heap management and the potential for type errors during casting. It compares the handling of pointers in different languages, like Java, C#, and the observation that pointers are akin to go-to statements in terms of increasing the complexity of program flow.

40:10

🔍 Type Checking and Language Typing Strength

This section introduces type checking, explaining how it ensures operand compatibility for operators and the difference between static and dynamic type checking. It discusses the concept of strong typing, where type errors are always detected, and provides examples of strongly typed languages like ML and F#. The paragraph also covers the impact of type coercion on typing strength and the reliability of programming languages.

45:11

🔄 Coercions and Type Equivalence in Programming

The paragraph explores type coercion and its effects on programming language typing, illustrating how coercions can lead to undetected type mismatches. It compares languages like C++, Java, and Ada in terms of their coercion rules and typing strength. The concept of type equivalence is introduced, explaining name type equivalence and structure type equivalence, and the challenges associated with implementing each approach.

50:12

📚 Conclusion and Introduction to Data Type Theory

The final paragraph concludes the lecture by briefly introducing data type theory, which encompasses practical and abstract aspects of type systems in programming languages. It outlines the broad scope of type theory, touching on its relevance to fields like mathematics, logic, computer science, and philosophy, and sets the stage for the next lecture on expressions and assignment statements.

Keywords

💡Union Type

A union type is a data structure that can store values of different types at different times during execution. It is characterized by the feature that only one value can be set at a time, and all fields within a union share the same storage space. In the context of the video, unions are discussed as a way to conserve memory space by allowing multiple variables to be represented within the same memory location, which was particularly useful in the early days of computing when memory was a premium resource.

💡Pointer

A pointer is a variable that stores the memory address of another variable. It is used for indirect addressing and dynamic memory management. Pointers can point to any variable regardless of its allocation time or location, and they can be used to access dynamically created storage on the heap. The video script explains the dangers associated with pointers, such as dangling pointers and memory leaks, and how they require careful management due to their flexibility and potential for misuse.

💡Reference Type

A reference type in programming is an alias for another value. Unlike pointers, references do not store the memory address of a value but instead provide a means to access the value indirectly without the need for dereferencing. The script mentions that references are safer than pointers because they cannot be used for pointer arithmetic, which prevents errors such as accessing memory beyond the bounds of an array.

💡Type Checking

Type checking is the process of verifying that the operands of an operation are of compatible types. This can be done statically at compile-time or dynamically at runtime. The video emphasizes the importance of type checking in ensuring the reliability of a program, as it can detect type errors that might otherwise lead to unexpected behavior or runtime crashes.

💡Strong Typing

Strong typing refers to a programming language's ability to detect type errors at compile time, thus preventing certain types of bugs before the program runs. The video script discusses the concept of strong versus weak typing, noting that strongly typed languages like ML and F# are more reliable as they minimize the risk of type-related errors.

💡Weak Typing

Weak typing, in contrast to strong typing, allows for more flexibility in how types can be used and converted. This can lead to type errors only being detected at runtime, if at all. The script points out that languages like C and C++ are weakly typed due to their extensive use of coercions and lack of strict type checking, which can lead to less reliable code.

💡Type Coercion

Type coercion is the automatic conversion of one data type to another. For example, an integer can be coerced into a floating-point number. The video script explains how coercion can weaken the typing strength of a language, as it may allow operations between incompatible types to proceed without errors, potentially leading to unexpected results.

💡Type Equivalence

Type equivalence defines when two types can be considered the same for the purpose of an operation, without needing coercion. The script discusses two approaches to type equivalence: name type equivalence, which requires the types to have the same name, and structure type equivalence, which considers types equivalent if their structures are the same, regardless of their names.

💡Dangling Pointer

A dangling pointer is a pointer that refers to memory that has been deallocated or is no longer in use. The video script warns about the dangers of dangling pointers, as they can lead to undefined behavior and program crashes when dereferenced, because the memory they point to may no longer be valid.

💡Memory Leak

A memory leak occurs when a program allocates memory but fails to release it back to the system after it is no longer needed. The script discusses how memory leaks can occur with both pointers and references if the allocated memory is lost and cannot be deallocated, eventually leading to a depletion of available memory resources.

💡Dynamic Memory Management

Dynamic memory management is the process of allocating and deallocating memory during the runtime of a program. The video script explains how pointers are used for this purpose, allowing programs to have a flexible memory usage that can grow and shrink as needed. However, it also highlights the responsibility placed on the programmer to manage this memory correctly to avoid leaks and other issues.

Highlights

Lecture concludes the discussion on chapter six, covering advanced data types and concepts.

Introduction to union types, which can store values of different types at different times.

Explanation of how unions differ from records or tuples, specifically that only one value can be set at a time in a union.

The shared storage space characteristic of union fields, leading to memory space efficiency.

Historical context of unions' utility in early computing due to limited and expensive memory.

Modern computing context where unions are less useful due to abundant and cheaper memory.

Design issues in implementing unions, including type checking and embedding within records.

Discriminated unions supported by Ada, providing type safety through a type indicator or tag.

Free unions versus discriminated unions, with the latter being safer due to built-in type checking.

Pointers and references as fundamental building blocks for managing memory and indirect addressing.

Pointer operations, including assignment and dereferencing, and their implications for memory management.

The dangers of pointers, such as dangling pointers and memory leaks, and the need for careful usage.

C and C++ support for pointers, including flexibility and the associated risks.

Pointer arithmetic in C and C++, allowing for offsets computation from specific memory locations.

Introduction to references in C++, providing an alternative to pointers with automatic dereferencing.

Java's support for references but not pointers, impacting the language's safety and reliability.

C#'s approach to supporting both pointers and references, with pointers requiring 'unsafe' program context.

Type checking mechanisms, including static and dynamic type checking, and their role in detecting type errors.

Strong versus weak typing, with languages like Java and C# being more strongly typed than C and C++.

Type coercion and its impact on the strength of a programming language's type system.

Type equivalence, defining when operands of different types can be substitutable without coercion.

Name type equivalence and structure type equivalence, their implications for type matching and program reliability.

Data type theory, encompassing practical and abstract type theories, and their relevance to programming language design.

Transcripts

this is the third and final lecture on

chapter six of the textbook

in the previous lecture we finished off

our discussion on arrays and also looked

at associative arrays and then we also

covered records tuples and lists

we will now be finishing the remaining

work in chapter six

this is an overview of the topics that

we'll be discussing in today's lecture

we'll start off with union types then

we'll move on to pointer and reference

types

then we'll look at how type checking

works

and then related to type checking we

will discuss strong versus weak typing

we'll then also look at type equivalence

which is also related to type checking

and then we'll finish off with a

discussion on theory and data types

the first of the data types that we'll

look at in this lecture is the union

type

so what is a union well a union is a

type that can store values of different

types at different times during

execution

now if we consider only this part of the

definition then a union sounds as though

it's the same thing as a record or

possibly a tuple in the sense that it

consists of multiple values and these

values can have different types

what sets a union apart however is that

only one of these values may be set at a

time

so let's assume that we have a union and

this union has three fields within it

only one of these three fields may

contain a value at a time

what's also very important to understand

is that the storage space for all of the

fields within a union is shared

so

for example if we have a union with

three fields

then let's assume that the first field

has a value

now assume that the second field is set

so what this will result in is that the

memory space that was occupied by the

first fields value will now be

overwritten with the second fields value

and this is why only one of the fields

at a time may have a value

so what are unions used for

well what i would like you to do at this

point is to pause the video and try to

think of a scenario in which a union

would be useful

so in general unions are used in

situations where memory space is at a

premium and the programmer wishes to

conserve memory space

and the programmer may for example

identify that there are a number of

variables that exist within a program

but only one of these variables at a

time is ever in use

in this case the programmer can then

create a union that packages these

variables together

and this will then ensure that all of

these variables can be represented

however they share the same memory space

this will then result in a lot less

memory being used than if these separate

variables were each separately allocated

in memory so this is generally the

scenario in which a union would be used

as a result of this unions were very

useful in the early days of computing

when memories were very small and memory

was also very expensive but in a modern

context where computers typically have

very large memories and memory is

comparatively cheap unions have become

less and less useful and as a result a

lot of modern programming languages

don't support unions anymore

now the two design issues that arise

when we decide to implement unions in a

programming language

firstly should type checking be required

and we'll look in a moment at how type

checking can be implemented for unions

secondly should unions be embedded

within records or should they be a

separate type unto themselves

now broadly speaking two different

categories of unions exist discriminated

unions and free unions we'll start off

by looking at three unions which are

supported in fortran c and c plus plus

so free unions are unions that do not

support type checking and it is

therefore up to the programmer to keep

track of which of the types is stored in

other words which of the fields is the

field that is currently storing the

value

right so here we have an example then

here a union is defined and we can see

that it has very similar structure to a

record so our union is called flex type

and we can see that there are two fields

within our union

firstly intel which is of type int and

then float l which is of type float

now it's important to understand that

only one of these two fields intel or

flotel can be occupied at a time and

that they share memory space

so here we have then a

union um that has been defined we're

defining a variable

that is of type flex type again we need

to specify that it's a union and we are

calling this variable u1

so now we can set intel by using this

dot notation

on u1 and we can set that value to 12.

so at this point intel then contains the

value 12 float l has no value associated

with it

then we can update flotell and we do

that by assigning 22.8

to float l

in union u1

so what this now means is at this point

float l now has a value of 22.8 and

intel is no longer defined

so then we can also retrieve a value

from a union and that's exactly what

we're doing here we're accessing union

u1 and we are accessing the field float

l within that and then assigning this to

a float variable x

so what this will result in is that x

will receive a value of 22.8

now let's look at the last line of our

example code over here

here we are now accessing

u1

and the intel field within union u1

now notice that we haven't set intel's

value

now because this is a free union there's

no type checking that will raise an area

at this point that will tell us

no we've actually only set a value for

float l there isn't a valid value for

intel

what will happen then in this case is

that the runtime system

will look at the memory space that is

occupied by both of these fields

and this memory space contains on a bit

level the floating point value

22.8

what will then happen is that it will

access the into value and it will simply

assume that the binary data that is

stored within the union is for this

integer field

so what will then happen is it will read

the required number of bits from memory

and it will then assign that as an

integer value to the variable y

however because this value isn't an

integer value what will be retrieved

will then just be garbage it will be the

beginning of the floating point value

interpreted as though it was an integer

so it's important to understand that we

won't get the value 22 back we'll get

some other integer value that is

equivalent to the first couple of bits

within the floating point value so this

thing means that no type checking can be

performed we can't determine whether in

this example intel or float l is

occupied it's up to the programmer to

know which one of the fields has a value

stored for it

what this means is that free unions are

relatively unsafe to use because errors

are not raised when we access the

incorrect fields instead we'll just get

invalid data back

next we have discriminated unions so

these are unions that support type

checking and as a result are much safer

to use than free unions

so discriminated unions are supported by

ada

now and please note that discriminated

unions are only very briefly mentioned

in the textbook so please refer to this

part of the discussion

and the slides that i will post

on the course website

for further detail on how discriminated

unions work

so discriminated unions then have an

additional type indicator which is

called a discriminant or a tag

the discriminant is used to check the

type of the union

and to detect errors if invalid fields

are accessed

so in order to make the concept of a

discriminated union concrete let's look

at an example

here we will define a union called

figure

and figure can store data related to

either a circle a triangle or a

rectangle however it's important to note

that it can only store data related to

one of these things at a time

so in other words the memory storage

space within the union is shared

for the data related to a circle the

data related to a triangle and the data

related to a rectangle

so we will then create a discriminant in

our union and we'll call this

discriminant form

and the value of form can be either

circle triangle or rectangle

so depending then on the value of the

form discriminant

only the appropriate data then for

either a circle a triangle or a

rectangle can be stored

right so let's look at the code

here to begin with we have an

enumeration called shape

and shape can take on one of three

values

circle triangle or rectangle

then we have another enumeration called

colors and colors has three values that

are legal for it red green and blue

so now we can get on to actually

defining our

union

so here we are defining figure and then

we specify that we have a discriminant

and this discriminant then has a type of

shape so in other words it can be either

circle triangle or rectangle and the

discriminant is referred to by the name

form

so we can see also that this is

specified as a record

and so it uses the same form as a

standard record the only difference is

that we are

storing a discriminant

right so then we have fields that we can

specify for our figures so we have two

regular fields and for these fields we

don't have any shared memory space it's

already presented in the standard way

um with separate memory spaces allocated

for each one exactly the way that fields

would be allocated within a normal

record

so we have then fold which has the type

of boolean and we have color which has

the type of colors so color can either

be red green or blue

now we have a case which begins up here

and ends at the bottom where we see the

end case

and we then base this on form so this is

like a switch statement effectively and

depending on what value form has where

the form is a circle triangle or

rectangle

we will then

execute one of the when clauses here so

we have a when clause for each of the

values that form can take on

for circle

for triangle and for rectangle

so if form is a circle then we have

defined for our figure

a diameter and the diameter is a

floating point value

if the form is triangle then we have a

left side and a right side both of which

are integer values and we also have an

angle which is specified to be a

floating point value and finally if form

is rectangle then we have two sides side

one and side two and these are both of

type

integer

our case then ends and then we end our

record off

so to complete our example let's now

look at what our discriminated union

will look like in memory

so this is then the memory that is

occupied by a full figure

and we can see that our first two fields

are represented over here so we have

fold first and then we have color notice

that these memory spaces are entirely

separate from each other they don't

overlap because they are just regular

fields within our union

then we have our discriminant over here

and this discriminant is named form as

we saw on the previous slide

and this can then have a value of either

rectangle circle or triangle

now we can see that the memory space

that is reserved for the data related to

a circle rectangle or triangle is shared

so if the discriminant has a value of

circle then we store only the diameter

if the discriminant has a value of

rectangle then we store our two sides so

that will then be this memory space

notice that the first part of the memory

space overlaps the memory space that

would be used to store the diameter of a

circle

and then finally if the discriminant is

set to triangle then we store the left

side right side and the angle so that is

then stored in this memory space over

here and notice that this overlaps with

the memory space that would be used for

the two sides of our rectangle or

alternatively also then the diameter of

our circle so the memory space then is

shared for the data related specifically

to the shapes and this then makes the

storage space that is taken up by our

union more efficient

so here we have an example of how an

instance of figure could be declared

so here we are defining a variable

called if underscore one its type is

figure so we know that this is in a

union and then we can assign to f1 and

then we specify what each of the fields

values should be

so here we specify that fold must be

true that will set then this value in

memory over here to true

color has been set to blue

so that means that this memory space

over here will contain the value blue

then we set our discriminant so we're

setting form to circle so that means

that circle will then occupy this space

in memory

and then finally we need to set the data

related to a circle so we set then the

diameter to a value of

1.3

that means that this memory space for

the diameter over here will be occupied

by the value 1.3 the remaining memory

space is unused

so um also then note that because this

is a discriminated union this is type

safe so if we were to attempt

um in this declaration that we looked at

before here

to set for instance side 1 or side 2 or

in fact left side or right side or angle

then there would be a compilation area

that would be raised and the reason for

that is that those fields are not

defined

for

the discriminant being circle only a

diameter is defined so that is all that

we can set so this then means that

discriminated unions as they are

supported in ada are much safer than the

free unions that we discussed before

because we cannot accidentally access

fields that we shouldn't

based on the value of the discriminant

so let's finish off our discussion on

unions with an overall evaluation of the

data type

now as we've seen three unions unsafe

and this is because they don't allow any

kind of type checking

as a result if we want a programming

language to be in any way reliable then

we should avoid

providing support for free unions

now some modern programming languages

such as java and c-sharp don't support

unions at all and this is because they

consider unions to be unsafe and also

there isn't much of a use for unions in

a modern context anymore as i previously

pointed out

so this lack of support for unions

reflects growing concern for safety

within programming languages and as a

consequent

result increased reliability

now as we've seen ada supports

discriminated unions and these are type

safe

what i would like you to do at this

point is to pause the video

and see if you can think of a

disadvantage associated with ada's

discriminated unions

the next two data types that we'll look

at in this lecture are related to one

another and they are pointers and

references

so we'll begin with pointers

a pointer variable is a variable that

stores values which are memory addresses

and these memory addresses reference a

particular memory cell

there's also generally a special value

referred to as a null or a null value

and this indicates that the pointer

doesn't refer to a memory cell it is

essentially an uninitialized pointer

now there are two possible uses for

pointers firstly they provide for

indirect addressing

so this means that we are providing a

mechanism for referring to a variable

using a different name so the variable

itself has a name but then we have a

pointer which also has a name and this

then refers to the variable hence

creating a second name that can be used

to get to the variable's value

the second use of pointers is that they

provide a mechanism to manage dynamic

memory so pointer can be used to access

a location in memory

where storage is dynamically created

during runtime and this area in memory

is referred to as the heap

there are a number of design issues

related to pointers which must be

decided on if a programming language is

going to provide support for pointers

so firstly we need to decide on the

scope and lifetime that a pointer

variable will have

now notice that this is the scope and

lifetime of the pointer itself and not

the scope and lifetime of the value that

is being pointed to by the pointer

then secondly

if pointers are to be used for dynamic

memory management then what is the

lifetime of a heap dynamic variable

then in the third place

is there some kind of restriction that

is applied to the type of the value to

which a pointer can refer

then in the fourth place our pointers

used only for dynamic storage management

or only for indirect addressing or

pointers used for both purposes

and then finally should the programming

language support only pointer types or

only reference types or should both

pointers and references be supported

next let's look at operations that are

defined for pointers so there are two

fundamental operations that must be

supported if pointers are represented in

a programming language the first is

assignments and the second is

dereferencing

now assignment allows a programmer to

set a pointer variables value to a

memory address and by doing that set the

pointer up to refer to another memory

location

now if the variable isn't on the heap

then there needs to be some sort of

mechanism to get the address of the

variable

the reason that heap variables are

excluded is that any value that is

allocated on the heap is typically

referred to by a memory address in any

case

so here we have an example of what this

kind of assignment operation would look

like in c plus

what we are doing here is we are

defining a variable called p and the

type of p is an integer pointer or we

can alternatively understand it as the

memory address of an integer value

so now we assume that we have an integer

variable called val and then we use this

ampersand operator which is the address

of operator and this will then retrieve

the memory address for the variable val

that memory address is then assigned and

stored in the variable p

which as we've seen is a pointer

variable

next let's move on to dereferencing so

dereferencing yields the values stored

at a location that is represented by a

pointers value now dereferencing can

either be explicit or implicit

so in c plus explicit dereferencing is

used and this uses the referencing

operator which is an asterisk so over

here we have an example of this in

practice we will assume

that

j is a variable of an appropriate type

for

the

pointer that we have and we assume then

that we have a point

named ptr so let's assume that the

pointer's type is an integer pointer or

an integer memory address in that case j

would then have to be an integer and we

want to retrieve the value that the

pointer refers to so in this case we

then apply

this asterisk operator the dereferencing

operator and what this does is it then

retrieves the value that the memory

address stored in pointer refers to

and that value will then be assigned to

the variable j

so that is then an example of an

explicit dereferencing it's explicit

because we are actually using a b

referencing operator

implicit pointers are automatically

dereferenced whenever they are used

so for example in this assignment if gtr

was

not an

explicit pointer we would then not have

to provide some sort of operator in

order to

dereference that pointer

the runtime system or the compiler would

automatically determine that you are

attempting to assign to an integer value

and therefore the pointer needs to be

dereferenced first in order to retrieve

the value it is referring to

so let's look at our previous example in

terms of a memory diagram to more

clearly illustrate this concept

so we will assume that our pointer which

is named ptr

stores memory address which is 7080

we then assume that we have an integer

value of 206 that is stored at memory

address

7080

so over here we can then see that

arrangement in memory we have our

integer value which is 206 and that is

stored at memory location 708

our pointer is over here and this stores

then the memory address value 7080

which then means we have a reference

that points from our pointer to memory

location 7080

and the value stored at that location is

206.

so now we are performing this assignment

over here we're assuming that j

is an integer variable and we are now

dereferencing our pointer

so what this then means is we look at

the memory address that is stored

in our pointer variable ptr and we

de-reference that meaning that we follow

our pointer to memory location 7080

and then we de-reference that by

retrieving the value

206. this value is then assigned to the

variable j so here we have our variable

j and the value 206 is then stored in

this location in memory

so essentially what we have done is we

have performed a copy from the original

memory location into a new memory

location

now in general pointers are considered

to be relatively dangerous

and unreliable and the use therefore

should be limited as far as possible

now why is this well one reason that

textbook doesn't go into too much detail

on is that pointers provide support for

aliases so in other words we can use

pointers to create a mechanism whereby

multiple names can refer to the same

value in memory what this means then is

that we have multiple avenues through

which this value in memory can be

modified and therefore we have potential

roots open through which the value can

be corrupted

unexpectedly if we use only one name to

refer to a value in memory then if we

have control over that name there's no

way that the value that stored in memory

can be accidentally corrupted or

modified in some way

now

much more dangerous than this drawback

is the problem of dangling pointers and

also the problem of lost heap dynamic

variables

so dangling pointers

are

pointers

that refer to the allocated heap dynamic

memory variables

so in other words we would have a

situation where we have a pointer

referring to some space in memory that

has been allocated dynamically at

runtime and this will have been

allocated from the heap

we then potentially through another

point to de-allocate this memory space

but our first pointer is still pointing

to the location where the allocated

memory was

so why is this dangerous

well i'll give you a moment to pause the

video and to answer this question for

yourself

so essentially this is dangerous because

we might then use the pointer to refer

to what we think is memory that is still

allocated

but has in fact been deallocated

this referencing then potentially could

cause an error depending on the

programming language or it may result in

us referring to memory that we are not

supposed to refer to

which may not then cause a runtime error

but will cause us to be working with

data that we're not supposed to be

working with

now the next major drawback is lost heap

dynamic variables

and here we have an allocated heap

dynamic variable that is no longer

accessible to the user program and this

is often referred to as garbage

so let's look at an example of how this

could occur in practice

here we have a pointer this point is

referred to as p1 and this pointer

refers to some allocated space that has

been dynamically allocated from the heap

so now what we do is later on in the

program we allocate more space on the

heap which is represented at the bottom

over here

we then set p1 to refer to this

allocated space in memory

and at this point then of course

the linkage between p1 and the

originally allocated heap space has been

broken

now if we have no other pointer that

refers to this initially allocated heap

space then what we have is a lost heap

dynamic variable there's no way to refer

to that heap dynamic variable to that

space that has been allocated on the

heap

what this means then is that space is

effectively lost because it can never be

de-allocated and reclaimed and over time

if we keep doing this we may fill up the

whole of our allocated heap memory space

that is available for our program's

so this process then is sometimes

referred to as memory leakage and it can

result in very

difficult to debug errors

because in general this memory space is

just slowly disappearing and at some

points the program will then terminate

with some sort of fatal error because it

has run out of memory

so let's now look at pointers from a

practical perspective in terms of how

they are implemented in the c

and c plus plus programming languages

so in both of these languages pointers

are incredibly flexible but they're also

quite dangerous to work with for the

reasons that i've previously discussed

and therefore they should be used with

care

so pointers can point to any variable

regardless of when or where the variable

was allocated you can use a pointer to

point to a local variable inside a

function

or some sort of global variable you can

use it to point to stack allocated

variables or heap allocated variables

there's no limitation at all that cnc

plus

impose on the use of pointers in this

regard

now pointers are also used for both

dynamic storage management and indirect

addressing

so this again points to the fact that

there are relatively dangerous to work

with particularly because

pointers are used for dynamic storage

management

and we saw the drawbacks to that on the

previous slide when we were talking

about

lost heap dynamic variables and dangling

pointers

now pointer arithmetic is also possible

we'll look at what pointer arithmetic is

in a moment

but essentially this allows one to add

values to pointers and you can use this

to compute offsets um from a specific

memory location

and cnc plus plus also both use explicit

dereferencing and address of operators

so you explicitly need to indicate when

you are declaring a pointer and if

you're getting the address of a variable

you need to use

an operator

in order to do that there is no implicit

dereferencing

so also what's quite interesting in cnc

plus plus is that the domain type for a

point doesn't need to be fixed so what

this means is we don't necessarily need

to declare that a pointer points to an

integer address or a floating point

address or a boolean address or whatever

the case may be we can instead use a

void pointer and this thing indicates

that we are declaring a pointer that can

point to a value of any particular type

that we want so a void pointer can then

point to an integer or a float or a

boolean or any other type for that

matter

however there are some limitations on

the use of void pointers so you can't

de-reference a void pointer as is

you first need to perform a cast which

converts the void pointer to a pointer

for a specific type so for example you

might cast a void point to an integer

pointer for example

so what i would like you to do at this

point is pause the video and try to

explain why it makes sense that pointers

need to be cast

to a specific type before they can be

dereferenced if they are void pointers

to begin with

now what i'd like you to also do at this

point is again pause the video

and try to explain how support for void

pointers affects the type checking in c

and c plus

so in other words is type checking

easier or is it more difficult because

of the inclusion of void pointers

so let's look at how pointers in c and c

plus can be used for dynamic storage

management let's first of all look at c

plus which is the more modern of the two

programming languages

and in order to dynamically allocate

storage from the heap we use the new

special word

so this is an example of some code that

would allocate memory space from the

heap at runtime

and then assign the memory address of

the first

value that has been allocated to a

pointer p

so we must use pointers in order to work

with memory that has been allocated on

the heap

so here we are declaring a variable p p

is a pointer it's a pointer to an

integer value

then on the right hand side of our

assignment we perform the actual dynamic

storage allocation using the new special

word and then we indicate the type of

value that we want to allocate on the

heap which in this case

is an integer type

now if we had just left at that we would

have allocated space for a single

integer but in this instance we don't

want to do that we want to allocate

space for 10 integers consecutively in

memory so we then specify in square

brackets the number of integer values

that we want to allocate from the heap

so this will then allocate space for 10

integer values on the heap the memory

address of the first integer value in

that sequence of 10 will then be

assigned to the pointer p

so p then points to newly allocated heap

dynamic memory

now i've mentioned previously that with

dynamic storage management it is the

programmer's responsibility

to the allocate

memory that has been allocated from the

heap or at least this is the case in cnc

plus plus some programming languages do

use garbage collectors so java for

instance is an example of this but in

the case of cnc plus plus because

they're relatively low level you

actually have to then handle the

allocation manually yourself so this is

done fairly simply using the delete

special word so here we are deleting our

pointer p and this then instructs our

runtime system to find the memory that p

points to and de-allocate that thus

returning that memory space for the ten

integers that we've allocated back to

the heap and then they can be

reallocated at some later stage

now c also then has the concept of

allocating and deallocating heap memory

however c doesn't use the new and delete

special words instead c uses functions

which are provided by a library and it

uses the malloc function to allocate

heap memory and then the free function

to deallocate heap memory again both

malloc and free will

receive pointer values to the dynamic

memory that has been allocated

now as i've previously mentioned

pointers in c and c plus plus support

pointer arithmetic so we'll now

illustrate how pointer arithmetic works

with a few examples

so let's assume that we start off with

this program code over here

and what we are doing first of all is we

are declaring a variable named stuff and

this variable is an array that contains

floating point values and we've

indicated that we want to store 100

separate floating point values in our

stuff array

next we have a pointer that we define

our point is named p

and the type of this pointer is a float

pointer so in other words p points to a

floating point value or alternatively we

could say that p is the memory address

of a floating point value

now notice that p hasn't been

initialized to any value yet so it's

essentially an uninitialized pointer

and then we perform an assignment so we

are now setting p's value meaning that

we need to assign a memory address to p

so on the right hand side of the

assignment we see that we have the name

of the array stuff that appears

and when we just simply use the array's

name on its own without any index or

subscript indicated then the name of the

array is an alias for the memory address

of the first element contained in that

array so in other words stuff on the

right hand side here will be the memory

address of the first floating point

value contained in the stuff array

so we then assign that memory address to

p

p now has the memory address of the

first element in the stuff array so

essentially what we've done is we've

created an alias

and p then is a pointer and can be used

as a substitute for the name of the

array namely stuff both p and stuff now

contain the memory address of the first

element in the stuff array

all right so now we can move on to some

actual pointer arithmetic which is

exactly what we are doing over here

and here we are adding 5 to our pointer

p so what does this mean well it means

we are adding 5 floating point memory

offsets to p

so a memory offset is the size in memory

of a particular type so we are adding

five

spaces that are the size of a floating

point value 2p

so what this thing means is we are

accessing the sixth element in the stuff

array because as we've seen p is an

alias four staff

and the first element in the stuff array

will be at offset zero so if we add five

offsets we're then getting the memory

address of the sixth element in our

stuff array so we place that then in

parentheses and then we use the asterisk

operator to dereference

the memory address that we have computed

and this will then give us the sixth

value that is stored in the stuff array

now there are alternative notifications

that we or notations rather that we can

use

for example we can access our p array at

subscript 5 and this essentially will

then perform

exactly the same pointer arithmetic that

we did before and this is just a shorter

hand notation

that we can use for this alternatively

we can use the stuff array and we can

also access that at index or subscript

five so all three of those approaches

are then equivalent to one another

we can also use a variable so in this

case we've got exactly the same pointer

arithmetic that we're performing except

instead of using a literal value of 5 we

now use a variable's value i

and this will then allow us to specify

exactly which element we want to access

in the stuff array by means of i's value

so again this is then equivalent to

accessing the stuff array at index or

subscript i

or using the pointer in the same way

i previously mentioned that c plus

supports a reference type in addition to

a pointer type

so we will introduce and discuss

references using c plus as an example

so references are very similar to

pointers the difference is that while a

pointer stores the memory address of a

value that it is referring to a

reference is simply an alias for another

value so both are used for indirect

addressing however a point is a memory

address whereas a reference is a value

so let's look at some example program

code over here here we are declaring a

variable named v and it is of an integer

type and we set its initial value to 10

so now we perform an assignment now on

the left hand side of the assignment we

have a declaration for a variable and

this variable is ref and this ampersand

character over here indicates that ref

is a reference variable and specifically

it's a reference variable to an integer

value

so now we assign v to this reference and

what this means is after this assignment

ref then

is an alias another name

for v so in other words it directly then

references the value 10 which is stored

in memory so notice that we don't have a

memory address that we are working with

directly here

now what are references used for in

practice well they're used primarily for

formal parameters and they give the

benefits of both pass by reference and

pass by value so what does this mean

well let's look at that in terms of this

code example over here

so here we are declaring a function

called if its return type is void

meaning it doesn't return a value

we receive then as a parameter a single

parameter named p and we can see because

of this ampersand it is a reference and

specifically it is a reference to an

integer value we then have the body of

our function which we've omitted for the

purpose of this example

so effectively what this thing means is

that p is another name or an alias for

whatever parameter value has been passed

through in a call to f and therefore any

modification any change that is

performed in the body of the function to

p

will then also modify the parameter

value

so let's now assume that we have this

code over here

which appears somewhere else in our

program possibly in the main function

here we are declaring a variable called

val its type is int and its initial

value is set to 12.

we then call f and we pass through val

as a parameter here so what this means

then is that p

is an alias another name

for vowel

so if we then perform some modification

to p in the body of our function f over

here

let's say for example we increment p's

value then we are actually incrementing

val's value and that will then be

incremented from 12 to 13.

so effectively then what we've done here

is we've created a reference p

to a parameter and it works like an

integer variable so that is in the

advantage of pass by value because we

don't need to dereference p at all in

the body of our function we just simply

use it directly as though it were a

value

but we don't need then to dereference

this

however it is a reference even though we

aren't directly working with the memory

address and dereferencing the value so

this gives us the advantage of pass by

reference

what this means then is that we're not

actually copying val into the parameter

and therefore the body of this function

we are just working with a reference

so what this then means is that memory

is conserved because we're not creating

unnecessary copies of values

now another big advantage associated

with reference types is that you can't

perform pointer arithmetic on them and

therefore they're much safer than

pointers

for example if we

look at the example we worked through on

the previous slide where we were using

pointer arithmetic in order to access a

particular value in an array of floating

point values we could accidentally add

an offset that is too large and this

would then cause us to access a value

beyond the bounds of the array this kind

of thing isn't possible with reference

types and the reason for that is that we

can't perform pointer arithmetic on

references

it is important to note however that we

can still have dangling references and

we can also have memory leaks that are

caused through the use of references so

those two disadvantages associated with

pointers are not eliminated by the use

of references

java also supports references which are

an extended form of c plus references

and in fact only references are

supported and not pointed

now references can refer only to objects

and not to primitives such as integers

or floats or boolean values

so what i would like you to do at this

point is pause the video and try to

think how these two factors

that we've discussed related to java's

references affect the programming

language evaluation criteria that we've

been using through this course

c-sharp

includes support for both pointers and

references so again we see c-sharp

trying to be as general as possible

and supporting as many features

and from both java and c plus as

possible

so the references that c-sharp supports

very similar to those that we see in

java

and the pointers are quite similar to c

plus plus pointers but one can only use

them in such programs that the

programmer has explicitly marked as

unsafe so what i would like you to do

again at this point is pause the video

and try to answer how these details

related to c sharps pointers and

references affect the programming

language evaluation criteria we've been

using

specifically

focus on the fact that subprograms must

be marked as unsafe if pointers are used

within them

let's look at a general evaluation of

pointers

from an overall perspective

so there are a couple of problems

associated with pointers and with

references however these problems more

detrimentally affect pointers than

references

so we've discussed problems related to

pointers and most importantly there we

saw that we have the problems of

dangling pointers and lost heap dynamic

variables these are major drawbacks to

the use of both pointers and references

now if pointers are used for dynamic

memory management in other words

they are used to refer to heap memory

that has been dynamically allocated by

the programmer then manual heap

management is necessary one needs to

allocate and de-allocate memory that one

is working with on the heap so what i

would like you to do at this point is

pause the video and try to answer how

this manual heap management

affects the programming language

evaluation criteria that we've been

using through this course

now the textbook makes quite an

interesting observation it states that

pointers are like the go-to statement in

a lot of ways

so why does the textbook say this well

if we use a go-to statement then this

means that there is an increase in the

number of routes that one can use in

order to access a specific line or

statement within our program

and this is because with a go to label

we can jump

to it from any line within our program

effectively

so in a similar fashion

pointers then increase or widen the

range of memory cells that are

accessible by a particular variable

now

unfortunately dynamic data structures

things like linked lists and trees and

graphs and so on

require dynamic memory management

because these are data structures that

can grow and shrink over time as nodes

or elements within the data structure

are added and removed

so support for dynamic data structures

does require the pointers or references

and so we can't completely avoid them so

in general the majority of modern

high-level programming languages must

support at least references in order to

allow for rich data structures to be

supported

we'll now move on to the concept of type

checking

now type checking involves operators and

operands

so we'll of course then consider

operators and operands in their normal

sense for example if we are adding two

values together then we have an addition

operator and then the values that appear

on the left and right hand side of the

addition operator are the operands

however type checking also applies to

both sub-programs and assignments so we

also then generalize the idea of

operators and operands to work in these

contexts as well so if we have a

subprogram call such as this over here

where we're calling a subprogram called

if and we're passing through a parameter

of 1.2

then we consider the operator to be if

because this is the thing doing the

actual

computation and the operand in other

words the data that the operator works

with would be the parameter value of 1.2

in a similar fashion with an assignment

here we have an example assignment then

the operator is the assignment operator

or the symbol that's used for the

assignment and the operands will then be

the values that appear on the left and

right hand side so on the left hand side

we have a variable a and on the right

hand side we have a literal integer

which represents the value of 43.

so if we now consider operands and

operators to be as i've just defined

them and that's only for this section

that we will consider operators and

operands

according to this wider definition

then type checking is the activity that

ensures that the operands of an operator

of compatible types and if there are

compatible types then the operation can

proceed

so a compatible type in this context

is then a type that is either legal for

the operator

or it is allowed under the language

rules to be implicitly converted in

other words coerced by the compiler to a

legal type for the operation

so for example compatible types will

exist if we are adding two integer

values together

that will then be a legal use of types

in relation to the addition operator

alternatively we can add an integer and

a floating point value and in that case

the integer will then be automatically

converted by means of coercion to a

floating point value so that the

addition can then proceed

so in both of these cases we then have

compatible types for our operands

now a type error then arises

if we

apply an operator to an operand of an

inappropriate type and this will then

generally cause some kind of error it

might be a compilation error or it might

be a runtime area depending on the

specific programming language

now type checking can either be static

or dynamic if we have static type

checking then type checking can be done

before runtime and it will be picked up

then by a compiler

if we have

dynamic type checking then type checking

needs to occur at runtime and there may

therefore be a runtime type error that

may occur

so if all of our type bindings are

static then almost all of our type

checking can also be done statically

and conversely if our type bindings are

dynamic

in nature then our type checking must be

dynamic as well

so what i would like you to do at this

point is pause the video and try to

explain why this is the case

for both static type bindings and for

dynamic type bindings

alright so we can then refer to a

programming language as strongly typed

if it will always detect type errors

now the advantage of this is that all

variable misuses that cause type errors

can then be detected

now usually we can't refer to a

programming language as being purely

strongly typed or purely weakly typed

usually we need to describe the strength

of the typing in a relative fashion so

comparing one programming languages type

system to another programming languages

type system so we can then say something

like language a is more strongly typed

than language b

let's now look at strong versus weak

typing in the context of actual concrete

programming language examples so c and c

plus are not very strongly typed at all

despite the fact that types are

statically bound in these programming

languages

now there are a variety of reasons why

cnc plus are not very strongly typed one

of them is that in early versions of c

so these are versions of c that come

before the c99 standard parameter type

checking could be completely avoided

so this would allow one to write for

example a function that would receive an

integer value as a parameter

and one could then pass some other value

to the function for example a floating

point value

now what would happen then in this case

is that the value would not be cast to

an integer as one would expect in a

modern programming language but instead

the value that had been passed through

as a parameter for instance a floating

point value would simply be interpreted

as an integer on a bit level so this

would then not raise a type error

instead we would simply then

get some kind of unexpected value back

instead of something resembling the

float value that we had actually passed

to the function

also both c and c plus plus

include support for unions and as we've

seen before these unions are free unions

and can therefore not be type checked

so what i would like you to do at this

point is to pause the video once more

and think of other reasons that c or c

plus plus are strongly typed

think of some of the previous

discussions that we've had through the

course of our treatment on this chapter

now if we look at java and c sharp we

see that implicit type areas will always

be detected however explicit casting can

result in type areas

so for instance we can have an object

reference and then this object reference

can be cast to an invalid

class instance this will then generate a

type error but this will only be

detected at run time

and an exception then will be thrown in

this case which one would then have to

catch and potentially handle in some way

although generally speaking these kinds

of casting errors

are areas that one cannot recover from

so as a result of this and c sharp are

much more strongly typed than c and c

plus plus but they are still not

perfectly strongly typed

now ml and f sharp are very strongly

typed much more strongly typed than java

and c-sharp are in practice

type coercion can be considered to

weaken typing in a programming language

so we've already touched on coercion a

moment ago

but to recap on that coercion is an

automatic conversion of operands to the

same type so that they work for a

particular operator

now coercion can cause accidental type

mismatches to go undetected so let's

look at this in terms of an example

let's assume that we have two variables

a and b and the types of these variables

will be int in both of those cases we

also then have a third variable d and

its type is float

so now assume that the programmer

intends to add a and b together both of

which are integer variables but they're

typing quickly so they mistype b

as d

now the compiler or the interpreter

depending on the programming language if

it supports coercions will see this

mismatch in type and will convert the

integer

operand which will be a

to a floating point value so that it

matches with the type of d

so the mistyping error then won't be

detected the compiler won't raise an

error indicating that you've perhaps

made a mistake because one of the

operands is a floating point value and

not an integer value or vice versa

so let's look at how coercions affect

typing in some actual concrete language

examples

so c plus plus is a very large set of

coercions that can take place and this

then means that it is fairly weakly

typed

and it is also then as a result a lot

less reliable

now ada has very few coercions in fact

it has almost no coercions at all so

this means that ada is much more

strongly typed than c plus plus is and

therefore much more reliable

jarvis is somewhere in between so it has

about half of c plus its assignment

coercions

so therefore it is more strongly typed

in c plus but still less strongly typed

than ada which has almost no coercions

at all

so this brings us to a related concept

which is type equivalence

so what is type equivalence well it

defines when operands of two types can

be substitutable with no coercion taking

place

so

what type equivalence then does is it

defines the types of operands that are

acceptable for all operators

now for the predefined scalar types

things like integers for instance

um

these rules are very simple and rigid so

usually a type is only equivalent to

itself so for instance we can only add

one integer to another integer if no

coercion is going to take place if any

other type value is used in the addition

then there must be a coercion that takes

place however for struct types and some

user-defined types the type equivalence

rules are more complex and we're going

to look at two ways that type

equivalence can be handled

the easiest and most straightforward

approach to dealing with type

equivalence is referred to as name type

equivalence so with name type

equivalents two variables are considered

to have equivalent types if they both

have exactly the same type

we're not looking at the structure of

the two variables at all

so this will then be the case if either

both variables appear in exactly the

same declaration in which case they both

have the same type or they appear in

separate declarations but both of these

two declarations then have exactly the

same type name

now name type equivalence is very easy

to implement

for instance if we have two variables

and both of those variables are record

variables then the two variables are

only equivalent if they are both exactly

the same record type

however we don't look at the structure

of these records at all so therefore

it's very efficient and very

straightforward to implement however

name type equivalence is very

restrictive because it requires an exact

match between the types

so for example if we are looking at

user-defined ordinal types in other

words we are looking at enumerations

then an enumeration is not equivalent to

an integer type and vice versa we saw

when we were discussing enumerations

that they are

interpretable as integer values however

if we implement name type equivalents

then because an integer type is not the

same thing as

an enumeration type those types are then

not equivalent to each other this would

then for example restrict us from

assigning an integer value to an

enumeration type variable or vice versa

also if we're looking at subprograms

such as functions then the formal

parameters must be exactly the same type

as their corresponding actual parameters

the second and more complex approach to

type equivalence is referred to as

structure type equivalence

so here two variables are considered to

have identical types if their types have

identical structures now this is much

more flexible for example we can assign

a variable of one record type to a

variable of another record type and

these can be different record types as

long as the fields contained within the

records have exactly the same types and

typically appear in exactly the same

order

however structure type equivalence is

much harder to implement and the reason

for this is we're not simply looking for

a match between two types when that we

now actually have to pass through the

internal content of each of the

variables in order to determine whether

they are structurally equivalent to one

another

the complexity of structure type

equivalence leads to potential problems

and a large number of questions that

need to be answered by the programming

language designers

so here are a few few examples of some

of these questions and potential

drawbacks that we might encounter

firstly if we're working with record

types then are two records considered

equivalent if the fields are exactly the

same

and they have exactly the same types and

appear in the same order but the names

of the fields are different this is a

question that needs to be answered at

language design time

and secondly if we're working with array

types then our two array types concept

to be equivalent if they are exactly the

same in other words they store exactly

the same type and they have the same

number of values however their base

subscripts differ so for example

would

array 1 and array 2 in this example be

considered equivalent we can see that

both of them contain 10 integer values

however array 1 is indexed from index 1

to index 10 whereas array 2 is indexed

from index 0 to index 9. should these

two arrays be considered structurally

type equivalent to one another then if

we're working with enumeration types

should two enumeration types be

considered equivalent if they differ

only in the names of their constants in

other words they have exactly the same

number of constants but the constants

are named differently should they be

considered equivalent to each other or

not

now with structure type equivalence as

we've seen the compiler or the

interpreter can't differentiate between

types with exactly the same structure

and this is by definition

so for example if we have a floating

point value that represents miles per

hour and then a separate floating point

value that represents kilometers per

hour the compiler or the interpreter

can't tell these apart from each other

only the programmer can actually tell

them apart so these are all potential

questions that need to be answered and

possible drawbacks associated with

implementing structure type equivalence

in a programming language

finally we'll conclude this lecture by

very briefly looking at data type theory

so type theory is a very broad area of

study and it exists within multiple

fields

including mathematics logic computer

science and even philosophy

so the two branches of type theory

firstly there's practical type theory

and this is concerned with data types in

commercial

real world programming languages and

then there is abstract type theory which

often concerns itself with typed lambda

calculus and in general abstract type

theory is only really of interest to

theoretical computer scientists

now broadly speaking a type system then

in the context of data type theory is

considered to be a set of types and then

the rules that govern the types as they

are used in programs

so essentially what we've been

discussing through this chapter has been

been type systems

all right so that then concludes our

discussion on chapter six in the next

lecture we'll start with chapter

we will look at expressions and

assignment statements