COS 333: Chapter 6, Part 2

Summary

This lecture delves into various data types, focusing on arrays and their operations across different programming languages. It discusses heterogeneous arrays, array types like jagged and rectangular, and introduces associative arrays. The lecture also explores record types, tuple types, and list types, highlighting their uses and differences. It touches on performance implications of dynamic versus static data access and concludes with a look at list comprehensions and their applications in functional programming languages.

Takeaways

• 📚 The lecture delves into various data types, continuing from the previous lecture, focusing on array types and their advanced operations.
• 🔍 It differentiates between standard arrays and special types like associative arrays, which use keys for indexing instead of numerical indices.
• 🌐 The concept of heterogeneous arrays is introduced, where elements can be of different data types, in contrast to the homogeneous nature of standard arrays.
• 🤖 Programming languages like Perl, Python, JavaScript, and Ruby natively support heterogeneous arrays, while others can simulate them through object-oriented techniques.
• 🧩 The lecture explains array operations across different programming languages, including APL, Ada, Python, Java, and Ruby, highlighting unique features like elemental operations.
• 📏 A distinction is made between rectangular and jagged arrays, with the latter allowing rows of varying lengths, a feature supported by languages like C, C++, and Java.
• 📉 The concept of array slices is explored, which allows for the extraction of substructures from an array, applicable mainly in languages that support rectangular arrays.
• 🔑 Associative arrays are described as unordered collections indexed by keys, often implemented using hash tables for efficient data retrieval.
• 🏷️ Records, or structs, are introduced as named fields aggregates, fixed in structure unlike the flexible key-value pairs in associative arrays.
• 🔄 Records can be manipulated with operations like assignment, comparison, and initialization, with some languages like Ada supporting complex nested record structures.
• 🔗 The lecture concludes with a discussion on list types, central to languages like Lisp, Scheme, ML, and F#, and the use of list comprehensions for sophisticated list initialization.

Q & A

What are the main topics covered in the second lecture on chapter 2 about data types?

The lecture continues the discussion on data types, focusing on special kinds of arrays, advanced array operations, associative arrays, record types, tuple types, and list data types.

What is a heterogeneous array and how can it be simulated in languages that do not natively support them?

A heterogeneous array is an array that can store elements of different data types. It can be simulated in other languages by using arrays that contain a generic data value, often through the use of polymorphism and object inheritance.

Can you explain the difference between rectangular and jagged arrays?

Rectangular arrays are two-dimensional structures where all rows and columns have the same number of elements, while jagged arrays allow rows to have varying numbers of elements, often represented as an array of arrays.

What is an array slice and in which types of arrays does it make sense to use it?

An array slice is a substructure of an array that retrieves part of the array as a single unit. It is applicable to rectangular arrays but not to jagged arrays due to their different internal representation.

How are associative arrays different from regular arrays?

Associative arrays are unordered collections of data elements indexed by keys, rather than having fixed numerical indices like regular arrays. They often use more complex data structures like hash tables for efficient data retrieval.

What are the two main design issues associated with associative arrays?

The two main design issues are the syntactic form of references to elements (how to specify the key for the value to be retrieved) and whether associative arrays have dynamic or static sizes.

What is a record type and how does it differ from an array?

A record type is a possibly heterogeneous aggregate of data elements referred to as fields, identified by names. Unlike arrays, records do not require elements to be of the same type, and access to fields is by name rather than by numerical index.

What is the purpose of the 'move corresponding' operation in the Ada programming language?

The 'move corresponding' operation is used to copy all fields from a source record to the corresponding fields in a target record. It does not require the two records to be of the same type, allowing for partial copying of data where only corresponding fields are copied.

Why is accessing fields within a record generally faster than subscripting in an array?

Accessing fields within a record is faster because field names are static and their memory locations are determined at compile time. In contrast, array subscripts are dynamic and require runtime computation to determine the memory location.

What are tuples and how do they differ from records?

Tuples are similar to records in that they store a number of fields, potentially of different types. However, the fields in a tuple do not have names associated with them, making tuples suitable for temporary storage of grouped values without the need for individual field access.

Can you describe the use of list comprehensions in Python and their advantage over regular list initialization?

List comprehensions in Python allow for sophisticated list initialization, including the ability to add conditions for the values to be placed into the list. This is more flexible and concise compared to regular list initialization, which often requires multiple steps and separate assignments.

Outlines

00:00

📚 Introduction to Advanced Data Types

The script begins the second lecture on chapter 2, focusing on data types. It recaps the concept of data types and the discussion from the previous lecture on primitive data types, character strings, user-defined ordinal types like enumerations, and an introduction to array types. The lecture will continue with an in-depth look at array types, including non-standard arrays and advanced operations, associative arrays, record types, tuple types, and list data types. The script also touches on the concept of heterogeneous arrays supported by scripting languages like Perl, Python, JavaScript, and Ruby, which contrast with the homogeneous nature of arrays in other programming languages.

05:02

🔍 Exploring Array Operations Across Languages

This paragraph delves into the array operations supported by various programming languages. It starts with APL, which has a wide range of operators for vectors, matrices, and scalars, including those for reversing, inverting, and transposing matrices. The Ada language is highlighted for its array assignment feature, which is a copy operation, and array catenation. Python's array assignments are discussed as reference changes without copying, and it is noted that Python, like Java, supports array catenation and element membership operations. Ruby's array operations, including catenation and elemental operations, are also mentioned, with an example of adding two arrays element-wise. The paragraph concludes with a discussion on the differences between rectangular and jagged arrays, explaining that rectangular arrays have uniform row and column sizes, while jagged arrays allow rows of varying lengths.

10:02

📈 Array Slices and Associative Arrays

The script introduces the concept of array slices, which are substructures of an array that can be extracted as single units, applicable to rectangular arrays. It explains that languages like C do not support slices due to their use of jagged arrays, while C++ simulates rectangular arrays through the 'valarray' class. Examples of array slicing in Fortran 95 for two-dimensional and three-dimensional arrays are provided. The paragraph then shifts to associative arrays, which are unordered collections of data elements indexed by keys. The differences in accessing data through keys versus traditional array indexing are discussed, and the use of hash tables as the underlying data structure for associative arrays is mentioned. Perl's implementation of associative arrays, called hashes, is used as an example to illustrate how key-value pairs are assigned, accessed, and deleted.

15:06

🏷️ Understanding Records and Their Syntax

This paragraph explores record types, which are heterogeneous aggregates of data elements identified by field names. It contrasts records with arrays and associative arrays, emphasizing that records have a fixed structure once defined. The paragraph discusses design issues related to records, such as the syntactic form of field references and whether records have dynamic or static sizes. Examples from COBOL, which uses level numbers for hierarchical record structures, and Ada, which supports nested records without enforced hierarchical structures, are provided. The discussion also covers how different programming languages reference fields within records, with COBOL using a nested notation and other languages like Ada using a dot notation.

20:08

🔄 Record Operations and Their Implications

The script discusses operations that can be performed on records, such as assignment, which copies corresponding fields from one record to another, and the requirement for matching record types on both sides of the assignment. It also touches on the concept of 'move corresponding' in the Global programming language, which allows for partial copying of data between records of different types based on matching fields. The paragraph concludes with a comparison between records and arrays, noting that arrays are typically used for homogeneous data and records for heterogeneous data, and that accessing fields in a record is generally faster than array element access due to the static nature of field names.

25:09

🎓 Records and Tuples in Various Programming Languages

This paragraph continues the discussion on data types by comparing records and tuples. It explains that tuples store heterogeneous data but differ from records in that their elements are not named. The use of tuples for temporary storage and their immutability in languages like Python is highlighted. Examples of tuple creation and manipulation in Python, ML, and F# are provided, showing how tuples can be created, accessed, and used in assignments and pattern matching. The paragraph also discusses the use of tuples in functional programming languages to return multiple values from functions.

30:11

📝 Diving into List Data Types and Their Operations

The script concludes the lecture by discussing list data types, which are ordered sequences of often heterogeneous values, typically represented as linked lists. It emphasizes the importance of lists in functional programming languages like Lisp, Scheme, ML, and F#, and provides examples of list operations in these languages, such as cons, car, and cdr equivalents. The paragraph also covers Python's list comprehensions, which allow for sophisticated list initialization with conditions and operations, and mentions the support for lists in C# and Java as generic heap dynamic collection classes.

Keywords

💡Data Types

Data types define the kind of data that can be stored in a variable and how the data is manipulated. In the context of this video, data types are the central theme, with various types such as primitive, character strings, enumerations, and arrays being discussed. The script delves into how different programming languages handle data types and the operations that can be performed on them, such as assignments and catenations.

💡Heterogeneous Arrays

Heterogeneous arrays are a type of array that can hold elements of different data types. The script mentions that languages like Perl, Python, JavaScript, and Ruby natively support these arrays, allowing for a mixture of element types within a single array structure. This is contrasted with the more common homogeneous arrays, which can only store values of one particular type.

💡Polymorphism

Polymorphism is a concept where a single interface can represent different underlying forms (data types). In the script, it is used to explain how languages that do not natively support heterogeneous arrays can simulate them using arrays of a generic data type, often an object type from which other classes inherit, allowing for the storage of any object that is a subtype of the object class.

💡Elemental Operations

Elemental operations refer to operations performed element-wise between corresponding elements of two arrays. The script provides an example of elemental operations in the context of Ruby, where the addition of two arrays results in a new array containing the sums of the corresponding element pairs from the original arrays.

💡Rectangular and Jagged Arrays

Rectangular arrays are two-dimensional arrays where all rows and columns have the same number of elements, while jagged arrays allow rows to have varying numbers of elements. The script explains that jagged arrays are internally represented as arrays of arrays, and languages like C, C++, and Java support them, contrasting them with the simpler rectangular arrays supported by FORTRAN and Ada.

💡Array Slices

Array slices are substructures of an array that allow a portion of the array to be referenced as a single unit. The script notes that array slices are useful in languages that treat arrays as single units, such as Fortran, and are not applicable to jagged arrays. It also explains that languages like C do not support slices because they only support jagged arrays.

💡Associative Arrays

Associative arrays, also known as hashes or dictionaries, are collections of data elements indexed by keys rather than numeric indices. The script discusses how these arrays are unordered and often implemented using hash tables for efficient data retrieval. Examples of associative arrays are given in Perl, where they are referred to as hashes.

💡Record Types

Record types are composite data types that allow the storage of multiple fields, each identified by a name. The script explains that records are fixed in structure once defined, with fields referred to by name rather than by index. It contrasts records with arrays, where elements are accessed by numeric indices.

💡Tuple Types

Tuples are similar to records in that they store a number of fields, potentially of different types, but differ in that the fields in a tuple are not named. The script mentions that tuples are often used for temporary storage in languages like Python and ML, where they allow functions to return multiple values easily.

💡List Types

List types, as discussed in the script, are ordered sequences of potentially heterogeneous values, often implemented as linked lists. The script highlights the importance of lists in functional programming languages like Lisp, Scheme, ML, and F#, where they are central to the language's operations and can be manipulated with functions like 'cons', 'car', and 'cdr'.

Highlights

Introduction to advanced data types, including array types, associative arrays, record types, tuple types, and list data types.

Discussion on heterogeneous arrays and how they differ from homogeneous arrays found in some programming languages.

Explanation of how scripting languages natively support heterogeneous arrays and the simulation of such structures in other languages.

Overview of array operations across different programming languages, including APL, Ada, Python, Java, and Ruby.

Introduction to the concept of elemental operations in array manipulation, as demonstrated with Ruby.

Differentiation between rectangular and jagged arrays, with examples and language support explanations.

The concept of array slices and their utility in languages that manipulate arrays as single units.

Associative arrays explained, focusing on their unordered nature and indexing by keys.

Design issues related to associative arrays, including syntactic form and dynamic or static sizes.

Support for associative arrays in scripting languages like Perl, Python, Ruby, and Lua.

Introduction to record types, their structure, and how they differ from associative arrays.

The use of level numbers in COBOL for hierarchical record structure and its impact on language evaluation criteria.

Orthogonal records in Ada and their implementation without enforced hierarchical structure.

Discussion on record field references and elliptical references in programming languages.

Operations on records, including assignment, comparison, and initialization with aggregate literals.

Comparison between arrays and records in terms of use cases, access speed, and simulation of records with arrays.

Introduction to tuple types, their similarities to records, and their use for temporary storage in functional programming languages.

Explanation of tuple immutability in Python and their use in functions returning multiple values.

List data types discussed, including their ordered sequence nature and representation as linked lists.

Support for lists in functional programming languages like ML, Lisp, Scheme, and their operations.

Python lists as heterogeneous arrays and their mutability compared to lists in other languages.

List comprehensions in Python, Haskell, and F# for sophisticated list initialization.

Support for lists in C# and Java as generic heap dynamic collection classes.

Transcripts

this is the second lecture on chapter 2

which deals with data types

in the previous lecture we introduced

the concept of data types and looked at

a number of primitive data types

we also covered character string types

user-defined ordinal types where we

specifically looked at enumerations

and then finally we began our discussion

on array types in this lecture we will

continue with our discussion on data

types

this is an overview of what we'll be

talking about in this lecture

we'll begin by continuing our discussion

on array types focusing on specific

kinds of arrays

that deviate slightly from the standard

arrays that we looked at in the previous

lecture and then we'll also look at some

of the more advanced operations that are

valid for array types

we'll also then look at a special kind

of array referred to as an associative

array which departs quite substantially

from standard arrays

then we'll move on to record types

tuple types and then we'll finish the

lecture off with a coverage of list data

types

so we saw in the previous lecture that

arrays are homogeneous in nature

meaning that they can store values of

one particular type and each value in

the array must have the same type so

some programming languages notably

scripting languages such as perl python

javascript and ruby will natively

support what are referred to as

heterogeneous arrays and these are

arrays in which the elements do not need

to be of the same type so in other words

these arrays can store a mixture of

elements each of which can have a

different data type

now

these scripting languages that i

mentioned before natively supports

heterogeneous arrays but it is also

possible to simulate this kind of array

structure in a programming language that

doesn't natively support them

the reason for this is that these

heterogeneous arrays are actually

implemented as homogeneous arrays that

contain a generic data value of some

sort so for example we may have an array

that contains object values

now because

we would typically have a situation

where we have an object class

and then a large number possibly all of

the remaining classes in the programming

language would inherit from this object

class so what this means is if we create

an array that contains instances of

objects

then this means that one can store any

particular object that inherits from the

object class in this array so this is a

mechanism that is used then by means of

polymorphism to simulate a heterogeneous

array even though the array is actually

behind the scenes still storing values

that are all of exactly the same type

we'll now take a brief look at the array

operations that are supported in a

variety of different programming

languages

first of all we'll look at the apl or

apple programming language which we have

already discussed earlier in this course

so there we saw that apl or apple

supports a very wide variety of

different operators in fact there are so

many operators

that

additional characters are required to

represent these operators and these

characters do not appear on a standard

keyboard

so apl or apple supports a very powerful

set of operations for

vectors matrices and scalars and these

are all considered to be array

operations so for example there's a

single operator that can reverse column

elements

within a matrix there are also operators

for inverting or transposing matrices

for instance

then if we look at the ada programming

language we see that it supports array

assignment now in ada array assignment

is a copying operation

so for instance if we assign an array b

to an array named a

then the result of this will be that the

contents of b will be copied into array

a

it also supports array catenation so

this is an operator that allows two

arrays to be joined to create a new

array which contains the union of the

elements in the two previously existing

arrays

the python scripting language also has

array assignments however in the case of

python these assignments are only

reference changes so in this case

if we assign an array b to an array a

then a will simply be an alias that

refers to b

and there is no copying operation that

is performed through the assignment

operation

python also supports array catenation

and element membership operations

in a similar fashion to python which

we've just discussed java also supports

array assignments which are reference

changes

now if one wishes to create a copy of an

array then java provides a clone method

which can be called on an existing array

and this will then create a duplicate

copy of this array and this will be a

deep copy that's entirely separate of

the original array

ruby also provides a variety

of array operations including array

catenation

now fortune is relatively interesting in

that it provides what are referred to as

elemental operations

so elemental operations are operations

between pairs of array elements

so for example if we use the addition

operator to add two arrays then the

result of this will be a third array

which contains the sum of the element

pairs in the two arrays that are being

added

so over here we have an example of a

simple addition operation which is an

elemental operation between two arrays

here we have declared three arrays a b

and c

and we've specified that these arrays

contain integer values and that they

contain spaces for a total of three

elements in each of these arrays

so here we then initialize arrays a and

b a contains the values 3 8 and 5

whereas b contains the values 2 1 and 3.

then finally we perform an addition

operation between arrays a and b and

this addition is an elemental operation

we assign the result to c and what this

will then produce is an array which will

be stored in c and this array will

contain the values 5 9 and 8. 5 is

produced by adding three and two

together

nine is produced by adding eight and one

together and finally eight is produced

by adding five and three to each other

the next distinction we need to make is

between rectangular arrays and jagged

arrays

now both rectangular and jagged arrays

relate to two-dimensional array

structures in other words matrices the

concepts can be extended to higher

dimensional array structures but for

simplicity we will assume

two-dimensional structures for this

discussion

so as the name suggests a rectangular

array is a two-dimensional matrix

structure

in which all of the rows have the same

number of elements and all of the

columns have the same number of elements

and rectangular arrays are supported in

fortran and ada

now in contrast a jagged array or a

jagged matrix is a two-dimensional array

structure in which rows can have a

varying number of elements

now behind the scenes a jagged array is

actually represented as an array

containing other arrays where each of

the contained arrays will then represent

one row in the matrix structure

so languages that support jagged arrays

are c c plus plus and java and you

should be relatively familiar with how

multi-dimensional array structures are

dealt with in these programming

languages

now what's important to understand is

that it is obviously possible to use a

jagged array structure in order to

represent a rectangular matrix the

difference between a rectangular array

and a jagged matrix is that a

rectangular array is a single syntactic

unit

so in other words it is a single data

structure that represents a

two-dimensional

matrix structure in memory it does not

consist of an array containing other

arrays which represent the rows

in the grid structure

now some programming languages such as c

sharp and if shop support both jagged

and rectangular arrays

so these languages give you maximum

flexibility in terms of how these grid

structures can be represented

related to the rectangular arrays we've

just discussed

we also then have the concept of array

slices

so a slice is then a substructure of an

array so very simply an array slice is a

referencing mechanism that retrieves

part of an array as a single unit

now array slices are only actually

useful in languages that manipulate

arrays as single units so in other words

they're only really applicable to

rectangular arrays and do not make sense

in the context of jagged arrays

for this reason the c programming

language doesn't support slices so what

i would like you to do at this point is

to pause the video and try to explain

for yourself

why it doesn't make sense for erase

slices to be supported in a programming

language like c

that supports only jagged arrays

right c plus does then support slices

however this is only in the context of

the vowel array class and the vowel

array class is used to simulate

rectangular arrays so c plus doesn't

directly support rectangular arrays

but through a class that is provided

known as the vowel array class it can

simulate the operation of rectangular

array structures

slices are then supported for instances

of this class

in order to illustrate how array slices

work here we have a few examples in

fortran 95

so our first two examples at the top

over here

illustrate two-dimensional array

structures in other words simple

matrices

so over here we have an array slice we

are assuming that the two-dimensional

array structure is named matte

and then we specify first of all the

subsection of rows and then the

subsection of columns that we want to

extract from our matrix

so here we are specifying that we want

to extract rows one two three

and then column 2

so that will then be the shaded portion

of this matrix

the next example

over here illustrates a similar array

slice so here we are again generating a

slice of our matrix mat

and we are specifying that we want to

retrieve rows two and three

and then columns one two three so that

will then be this shaded

portion of our matrix structure

we can also create array slices of

three-dimensional array structures in

other words cubes so here we're assuming

that we have a three-dimensional array

structure named cube

so again we then need to specify rows

and columns just as we did with the

two-dimensional matrices but we

additionally then need to specify a

depth or a z-axis dimension

so over here we are then accessing row 2

which we can see

in this face of our cube we are

accessing row two

and then columns one two three so that

will then be these three columns over

here and then as far as the depth goes

we're looking at the z-axis

one to 4 which then gives us this plane

cut through the center of our cube

our last example over here again

performs a slicing operation on our

three-dimensional array structure named

cube

here we are accessing rows one two three

and columns one two three so this will

then be an entire

face of our grid structure but in terms

of depth

we then look at

depth or z-axis two to three so that

gives us in

these two faces

over here which will be accessed through

the slicing operation on our cube

the next concept that we'll look at is

associative arrays

so an associative array is in an

unordered collection of data elements

which are indexed by an equal number of

values where these values are referred

to as keys

now it's important to understand that

unordered in this context is a little

bit of a misnomer there obviously must

be some ordering to how the keys and

their associated values are organized

the point is that there isn't an

intrinsic order you can't for example

extract key and value pairs in the order

that they were inserted and they also

aren't indexes that are available to

access a specific position within an

associative array

instead

what happens is behind the scenes there

is an organizational scheme

but this organizational scheme is

designed to allow for very efficient

retrieval

and

accessing and manipulation of the data

that is stored in the associative array

so in general a more complex data

structure will be used behind the scenes

in order to handle the storage of keys

and associated values within an

associative array and a fairly commonly

used approach is to use a hash table

data structure

now obviously an associative array must

then store the keys as well as the data

element values

so this requires the additional storage

to be allocated for the keys that will

be associated with the values

the

indexes are then effectively the keys

and there aren't then implicit indices

the way that there are with regular

arrays that we've spoken about

previously

so there are two main design issues that

are associated with these associative

arrays

firstly what is the syntactic form of

references to elements in other words

how do you specify the key

for the value that you want to retrieve

and then the second design issue is do

associative arrays have dynamic or

static sizes

again this relates then to a similar

question that arises with regular array

structures as to whether they will be

static or dynamic in nature

now associative arrays are very commonly

supported in scripting languages so we

see that there's built-in support for

associative arrays by means of a

specific type in perl python ruby and

lua

now in lua associative arrays are

supported by means of the table data

structure whereas in perl these are

referred to as hashes

on this slide we have a few examples of

how associative arrays are handled in

the perl programming language

so in perl any name that begins with a

percentage symbol

is then considered to be a hash and in

other words an associative array we can

then perform an assignment to our hash

so in this case we have a hash named

high teams

and we can then assign to that in

parentheses a set of key value pairs so

first we list the key then we have an

arrow operator and then the value

associated with that

so in this associative array we then

have three key value pairs

the first key is the string man and

associated with that is the value 77

which is a numeric value the second key

is 2 and associated with that we have

the value 79 and then finally we have

the key weight which again is a string

and associated with that we have the

value 65.

now subscripting is then done by means

of braces within which we list the key

that we want to access

so over here we are working with our

high temps

hash or associative array

we use a dollar symbol to indicate that

we are referring to a scalar value

within

our hash

we then specify in braces the key that

we want to access which in this case is

the string width and then we can assign

a value to that so in this case

we are then replacing the initial value

associated with the key weight which was

65

and we are replacing that with the value

83

we can also remove elements using the

delete special word

so this will then delete a key as well

as its associated value so in this case

we are accessing the high temps hash

again we use a dollar symbol because we

are referring to a scalar value within

this hash

we then use the delete special word and

we specify then in braces the key that

we want to delete so this will then

delete the key 2 as well as the value 79

associated with that key

the next data type that we'll look at is

the record type

so a record is a possibly heterogeneous

aggregate of data elements now what sets

the support from arrays is that the data

elements are referred to as fields and

they are identified by means of names

a record does not have the same kind of

structure as an associative array which

we've just discussed because associative

arrays may have any number of key value

pairs

once a record has been defined to

contain a certain number of fields with

specific individual names for those

fields then the record is fixed with

that structure

now there are two design issues that

arise if we decide to implement records

in a programming language

firstly what is the syntactic form of a

field reference so in other words what

kind of syntactic notation is used in

order to refer to a field within a

record

and then secondly our elliptical

references allowed now we'll get to what

exactly elliptical references are in a

moment

now kobold was the first high-level

programming language to support records

and in fact to support nested record

structures

so in kobold level numbers are used to

show the hierarchical structure of

record

so in this example

at level one we have our employee record

the employee record consists of two

fields and these are both at level two

so firstly we have the employee name

and then we have the hourly rate and the

hourly rate then has a type associated

with it which indicates that it is then

a decimal value

and this specifies the format of the

decimal value

the employee name then consists of three

nested fields and each of these are then

at level five

so we have then the field first the

field middle and the field last each of

these also will then have a type

associated with it so here we are

specifying the length of the string in

other words the number of characters

and so first then has space for 20

characters middle has space for 10 and

last has space for 20 characters

now what i would like you to do at this

point is to pause the video and try to

answer what effect on the language

evaluation criteria does the use of

level numbers in cobol have

as an alternative to the nested record

structure

that we discussed in the context of

cobol

we have orthogonal records

so these are supported by most languages

that

provide support for records

other than kerbal

and what we see here is that we use

records that are contained within

existing records so in other words we

don't have an enforced hierarchical

structure with level numbers

so here we have an example of this in

ada first of all we need to define the

types that we'll be working with so the

first type

is referred to as employee name type and

this is defined as a record and we can

see that this consists of three fields

namely first middle and last each of

which is a string with a particular

length associated with it

we then end that record definition and

then move on to our next type definition

which specifies a record named employee

record type

so employee record type then has an

hourly rate associated with it which is

a floating point value but more

importantly we have another field named

employee name and the type of this field

is employee name type

so employee name type as we saw was

defined up here and this means that we

then have a nested record structure we

have one entirely self-contained record

namely the employee name type which is

nested inside another record

which is the employee record type

so what we can then do is we can define

a variable named employee record and we

specify that its type is employee record

type this will then allow us to set the

fields as well as the nested records

fields within the employee record

variable

now we'll move on to the two design

questions for records

so firstly we need to consider the form

of record field references

now cobol uses this kind of notation

over here which relates to the previous

example that we've just discussed

and here the of special word is used to

indicate

records and how they relate to one

another

now in cobol we start with the innermost

field and then move outwards so here we

are specifying that we want to access

the middle field which is contained

within the employee name field which is

contained inside the employee record

now other programming languages other

than kobold use a dot notation and this

works in the opposite direction to

cobol's field references

so we start off with the containing

record and then move inwards until we

reach the field that we want to access

so here we are accessing the employee

record and then we use the dot notation

over here and specify that we are trying

to access the field named employee name

within the employee record

within the employee name

which is in a field which references a

contained record we then want to access

the field middle

now as far as support for elliptical

references go we first need to discuss

what the alternative is to elliptical

references

so a fully qualified reference is then a

reference to a field where all of the

record and field names

must be listed explicitly so this is the

case in most programming languages that

support records for example in ada if we

want to access the field middle then we

would need to go through the employee

record first and then the employee name

there is no shortcut

now kobold supports elliptical

references and this is a shorthand

notation and this allows a programmer to

leave out record and field names if the

reference is unambiguous

so for example in cobol each of these

three will be equivalent as long as

first is unique and unambiguous so we

can just directly access first as long

as there is no conflicting

occurrence of the field name first we

can then just access it directly we

don't need to qualify it in terms of

further fields and record names

and we can also then

access first within employee name and

thus leaving out employee record or we

can access first within employee record

thus leaving out employee name

so what i would like you to do at this

point is to pause the video and try to

determine

what language evaluation criteria are

affected either positively or negatively

by allowing support for elliptical

references

now of course there are a variety of

operations that can be executed on

records

of these operations assignment is

probably the most common

and this will then copy corresponding

fields from a source record to a

destination record

so the record on the left side of the

assignment will receive the data from

the

record fields of the record on the right

hand side of the assignment

now in general the types on both sides

of the assignment must be identical so

in other words the record type on the

left side of the assignment must match

the record type on the right side of the

assignment

so what i would like you to do at this

point is to pause the video and try to

explain why it makes sense

that the record types on both sides of

the assignment should be equivalent to

one another

and then also try to

explain

how a programming language would

implement

a situation where records of different

types are allowed on the two sides of

the assignments in other words the

record types on the left side and the

right side of the assignment do not

match

the answer to this second question will

be dealt with in more detail later on in

our discussion on this chapter where we

talk about type equivalence

now the ada programming language allows

for records to be compared to one

another and again here the corresponding

fields in the records are compared to

one another one at a time

if all of the fields match then the

records are considered to be equivalent

to one another and if not then the

records are considered to not be

equivalent to one another

it also allows for record initialization

with aggregate literals so essentially

what this means

is something similar to array

initialization where in the declaration

of the record

an assignment can then

be placed and this assignment will then

allow a series of literals to then be

assigned into the fields of the record

in one go so this is in contrast to most

other programming languages

where

we would have to explicitly set the

values for each of the record fields by

means of separate assignments until

eventually we have then assigned to all

of the fields within a record

obviously this latter approach where we

perform a series of assignments is much

more verbose and requires more code than

simply using an initialization

where the values of all of the fields

are set in one go

now the global programming language

provides a move corresponding operation

and this is similar to an assignment it

copies all of the fields of the source

record to the corresponding fields in

the target record however it is not

necessary that the two records be of the

same type

so in other words what might happen is

we might have a record that contains

information related to a bank account

and there may be a field in the record

amongst other fields which is

called name

we might then also have an employee

record and the employee record may also

have a field called name

so what would then happen with a move

corresponding is that the name field

would be then copied from the source

record to the destination record in

other words from the bank account record

to the employee information record

this filling takes place for all

corresponding fields

and fields that don't match between the

two records will not be copied

so in other words the then result in a

partial copying of data

where all of the relevant data that

corresponds between two records will be

copied across but the rest of the data

will be left as is

so what i would like you to do at this

point is again pause the video

and try to explain why the move

corresponding operation makes sense

for the cobol programming language in

particular think about what the cobol

programming language was intended for in

terms of its original design and what it

is still used for today

to finish off our discussion on records

let's compare them to arrays

so in general one would use arrays when

the values that one wants to store are

homogeneous in other words of the same

type and one would use records when the

data values that one wants to store are

heterogeneous

now it's also important to note that

array element access is a bit slower

than accessing fields within a record

the reason for this is that subscripts

are dynamic and they can be for example

variables

where the values of the variables can

change through the course of runtime and

therefore computing the location in

memory that a particular subscript

refers to must be dynamic and must occur

during runtime

on the other hand field names are static

in nature

and this is because the fields within a

record are fixed at compile time in

other words prior to run time

so what this means then is because

dynamic operations are in general slower

than static operations subscripting is

slower than accessing fields directly

now subscripts in an array can be used

to simulate record fields dynamically

and here then array subscripts need to

refer to heterogeneous values that are

stored within an array

so what i would like you to do at this

point is to pause the video and try to

answer how you would go about achieving

this kind of approach with an array

where an array is effectively used to

simulate a record

right well quite simply we would either

use a heterogeneous array structure if

it is provided by the programming

language alternatively if we have an

object-oriented programming language

then we can create an array that stores

objects

where our object class would then be the

superclass that all other classes that

we can use would inherit from

so this would then mean that we can then

store in the array any object that has a

class which inherits from the object

class

now there are two main drawbacks

associated with this kind of approach

firstly it disallows type checking so

what i would like you to do at this

point is to pause the video

and try to explain why using a

heterogeneous array

in order to simulate a record would

disallow type checking

now secondly of course as far as

drawbacks go this approach would be much

slower and the reason of course is that

we are using an array rather than a

record

so this means that we are then accessing

data values

at runtime dynamically as opposed to

statically and as i've previously

explained dynamic operations are

generally slower than static operations

so therefore using a heterogeneous array

in order to simulate a record will in

general be somewhat slower in terms of

execution time

the next data type that we'll look at is

the tuple type

so tuples are fairly similar to records

they in other words store a number of

fields and these fields can have

different types so they allow you to

store heterogeneous data however the

difference between a tuple and a record

is that in a tuple the elements are not

named in other words the fields don't

have names associated with them

so as a result of this tuples are

generally used for temporary storage

where a number of values need to simply

be grouped together and handled as a

single unit

and one doesn't need to individually

access the fields within the tuple

now tuples are often used in scripting

languages for instance they're supported

in python

but also in the ml functional

programming language and the f-sharp

functional programming language

in all of these languages they are used

by functions in order to return multiple

values so again here what we see then is

a number of values are grouped together

as a single package and this package is

then returned by a function which

effectively allows them multiple values

to be returned but once these values

have been returned the tuple is no

longer necessary and one can then just

simply retrieve the data from the tuple

and then use it as necessary

so let's focus on python then for a

moment

and in python tuples very closely

resemble lists however lists are mutable

so in other words the values contained

in a list can be changed whereas tuples

in python are immutable in other words

once the values have been set then they

can no longer be changed

so again this then highlights the fact

that tuples 19 to justice temporary

storage mechanisms

now

but we can create a tuple in python

using a tuple literal

in this example over here this is the

tuple literal so we have a tuple that

contains three values

three which is an integer value 5.8

which is a floating point value and then

the string apple

so once these values have now been set

they cannot be changed and this is then

assigned to a variable called my tuple

which will then hold the tuple that has

been created

now referencing to the values contained

in a tuple you use subscripts in a

similar fashion to arrays

so for instance if we access my tuple at

index or subscript 1 then this refers to

the first value contained in the tuple

namely the value 3 which as we've seen

is an integer value

we can also concatenate tuples together

using the plus operator

and this allows us thing to add two

tuples to one another a new tuple is

then created and this tuple contains the

elements from both of the tuples that

appeared on the left and the right hand

side of the addition operator

now as i've previously mentioned tuples

in python are immutable so it's not

possible to remove individual items from

tuples

however there is a double operation

which deletes a tuple completely

the ml programming language is

relatively similar to python in terms of

its support for tuples

so this is the notation that is used

when a tuple is created you can see that

it's relatively similar to python's

approach

again we have a literal that defines the

values that are stored in the tuple once

again we store the values 3 5.8 and the

string apple

and then we assign this to

my tuple

which is in a name that will refer to

the tuple that has been created

notice that ml is functional programming

language so again we don't use the

terminology variable

we just simply refer to a name for a

value

now in order to access the first element

in my tuple this is the notation that

would be used so we use a hash symbol

notation once again with the number

referring to the specific

value within the tuple that we want to

access once again this will then access

the first value in the tuple namely

three

now we can also define a tuple type

and that's done using this kind of

notation over here

so here we are creating a new type that

is called into real and we specify then

that the interval type is a tuple and

this tuple stores an integer value and a

real value

we can now use this interval type

wherever a type can appear

within ml so for example we can use

interview as the type

of a function parameter for instance

f-sharp as we've previously mentioned

also supports tuples

and this is the notation that is used

for creating a tuple you can see it's

relatively similar to what we saw

before in ml and in python

so here we are associating the name type

with a tuple that contains three values

namely three five and seven

now we can in f sharp perform an

assignment and from a tuple to a tuple

pattern and that's done in this example

over here so here we're taking our

existing tuple that contains the values

three five and seven

and we are then assigning it to

this tuple pattern over here so we can

see that there are three names in our

tuple pattern a b and c

the result of this is that the values

contained in our tuple namely 3 5 and 7

will then be assigned in order to each

of the names in our tuple pattern so in

other words a will receive the value 3

b will receive the value 5 and c will

receive the value 7.

now we'll move on to the final data type

that we will be discussing in this

lecture namely the list type

so a list is an ordered sequence of

values where the values are oftentimes

heterogeneous in nature in other words

the values have different types

and typically a list is represented as a

linked list data structure behind the

scenes

now of course as we've previously

mentioned lists are very central to the

lisp and scheme programming languages

and we've discussed how lists are

represented and the operations that are

legal for lists

in our discussion on chapter 15. so i'm

going to reiterate

that information here

in order to refresh your memory please

refer to the lectures on chapter 15.

the ml programming language is a

functional programming language just

like lisp and scheme and therefore also

supports list types which are fairly

central to the programming languages

operation

so lists are then written inside square

brackets

and the elements within the square

brackets are then separated by means of

commas

however it's important to note that list

elements

are all have to be of exactly the same

type

so ml has an equivalent operation to

schemes cons function

and this is the binary double colon

operator

so this is the way that the operator

would be used we can see on the left

hand side there's numeric literal three

and on the right hand side we have a

list

and this will then perform a cons like

operation which will then insert the

value 3 at the head of the list and the

result will then be this list with the

additional element in the first position

in the list

there are also equivalents for schemes

car and cuda functions in ml

these are named hd and tl respectively

so this is an example of how the

hd operation would be used in ml we can

see that we apply hd

to a list five seven and nine and this

will then extract the first element in

the list namely the value five

which the entire application then of

head would evaluate too

tl is used in a fairly similar fashion

so here we are applying tl

to a list containing the values five

seven and nine this will then extract

the first element namely 5

from our list and then as a result will

then evaluate to the remaining values in

the list so we get then as a final

result the list containing the values

seven and nine five is not included in

that resulting list

if sharp is also a functional

programming language and as such also

supports lists in much the same way as

the previously discussed functional

programming languages do

now lists in f-sharp are fairly similar

to those in ml so again square brackets

are used to delimit the beginning and

the end of a list

however elements are separated by means

of semicolons rather than commas

now the binary double colon operator is

also provided in if sharp and works

exactly the same way as in ml

now there is also an equivalent to the

car

function in scheme as well as the kuder

function in scheme

please note that the notation that's

used here is correct for standard

f-sharp

and

what is published in the textbook is

incorrect so please take note of this

when studying for

tests or for the exam

so the equivalent thing to the car

function in scheme

is list dot head and here we've applied

that to a list containing the values one

two and three so this will again extract

then the first element in the list and

the application of list dot head will

then evaluate to this value namely one

in this example

the equivalent of the cuda function in

scheme is similar to list dot head it's

list dot tail here we have applied this

to a list containing the values one two

and 3. so this will evaluate to the

remainder of the list with the head

element

removed so in other words only the

values 2 and 3 will then be included in

the resultant list that is produced by

the application of list dot tail

the python scripting language also

supports lists and in python lists are

the same thing as heterogeneous arrays

now python's lists are mutables in other

words the values that are contained

within the list can be changed

and this is unlike lists in the scheme

common lisp ml and if sharp programming

languages all of which have immutable

lists in other words values cannot be

changed within lists in these

programming languages

now elements in python lists can be of

any type

and one can also create a list by means

of an assignment so that's done in this

example over here here we are assigning

a series of values notice that we use

square brackets in order to denote the

beginning and the end of the list

and then my list as a variable will then

store a list containing these three

values

notice that the values are all of

different types so we have an integer

value as the first element a floating

point value is the second element and a

string as the third element

list elements in python lists are

referenced by means of array-like

subscripts so this explains why we said

previously that lists in python are the

same thing as heterogeneous arrays

indices begin at zero much like regular

arrays in most programming languages so

for example if we want to set the

variable x to contain the second value

in the my list list

then we would access this list at

subscript one using the square brackets

notation this would then retrieve the

value 5.8 from the list and then assign

that to the variable x

list elements can also be deleted in

python and here we use the dell special

word this is an example over here so

this would then delete the second

element contained within our list namely

5.8 once again

now we mentioned in the previous lecture

that array initialization in python is

handled by means of list comprehensions

so now we will actually discuss what a

list comprehension is essentially a list

comprehension allows us to perform an

initialization of a list but do this in

a fairly sophisticated fashion where we

can attach for instance conditions to

the values that will be placed into our

list

so over here we have an example of an

assignment to a list comprehension the

list comprehension is this latter part

over here in square brackets and this

list comprehension will then generate a

list for us which we will then assign to

the variable named list

so how do we then evaluate this list

comprehension well first of all we have

a variable x

and we consider then x values in a range

defined by the value 12. so what this

means is that x will take on the values

0 to 12 inclusive of 12.

now we have a condition which is

optional and this is associated with the

x values

and so we only consider x values

where x mod 3 is equivalent to zero so

in other words we are only taking values

in the range 0 to 12

where the value is divisible by 3. so in

other words x will then take on the

values 0 3 6 9 and finally 12.

now what we do is we can then

perform an operation on these x values

and that is the first part of the

comprehension over here

where we are computing x asterisk

asterisk two so this operation in python

is x raised to the power of 2.

so what we then do is we take each of

these values that x will take on 0 3 6 9

and 12

and we then raise those to the power of

two

these values are then placed into the

list that is then assigned to the

variable named list

so in other words zero squared will give

us a result of zero three squared will

give us a result of 9 6 squared gives us

36 9 squared gives us 81 and 12 squared

gives us 144.

so now each of these results the

squaring operation will be placed into a

new list which is then assigned to the

variable

list and therefore list will contain the

values 0 9 36 81 and 144

so we can see here then that list

comprehensions allow for a very

sophisticated initialization of the

values contained in our list and this is

much more complex than for instance

regular array initialization would allow

in the majority of programming languages

list comprehensions are also supported

in the haskell

and if sharp programming languages

haskell once again is a functional

programming language so this is an

example of a list comprehension in

haskell

and essentially what we are doing here

is using in as our index variable and in

takes on values ranging from 1 to 5

inclusive of both of those values we

then compute the square of each of those

values and that will then be placed in a

new list

so in other words this list

comprehension then defines a list

containing these values over here the

way we arrive at these values is that

one squared gives us a result of one

two squared gives us a result of 4

3 squared is 9 4 squared is 16 and 5

squared is 25.

list comprehensions in if sharp can be

used in order to create arrays and the

notation is seen in this example over

here

so here we are associating the name my

array with the result of this list

comprehension over here

and we

then have values of i which will be our

index variable

and these then

are generated in the range 1 to 5

inclusive of both of those values and

then we compute the square of i in each

case so once again that will then result

in a list containing the same values

that we saw in our previous example

where we were looking at haskell

this will then

associate the resultant list with the

name

my array

finally both c-sharp and java's support

lists

both of these programming languages the

lists are implemented as generic heap

dynamic collection classes so they're

implemented as linked lists which are

generic in nature in other words they

store a generic type t which can take on

within any particular type that is

stored in the linked list

in c sharp the class is the list class

and the arraylist class is used in java

all right so that concludes then our

discussion for this lecture in the next

lecture we'll be finishing off the

chapter and we'll discuss unions

pointers and references

the concepts underlying type checking

strong versus weak typing type

equivalence and then finally type theory