6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 11.1 Slide ll1.1 Elements of a Data Abstraction For the past few lectures, we have been exploring the topic of data abstractions, and their role in modularizing complex systems. We have particularly looked at the relationship between data structures and the procedures that manipulate them Today we are going to add a new aspect to this topic, by introducing the idea of mutation. This is the idea of changing or altering an existing data structure, rather than simply making a copy of it. We are going to look at two examples of useful data structures and show how while mutation carries some hazards 60015e with it; it also supports very efficient implementation of such structure Elements of a Data Abstraction Slide ll1.2 a data abstraction consists of To set the stage for our exploration, lets first review what we know about data abstractions First we know that a data structure has a constructor, a way of gluing pieces together Typically the definition of the constructor also involves a designation of the type contract of the constructor: what kind operations and how many objects are glued together Associated with the constructor are sets of accessors or selectors that get pieces of the object back out. These governed by a contract with the constructor, designating the 1001 SICP behavior by which pieces glued together can be pulled apar and we typically had a set of operations that used the data structures without actually using the details of the implementation. The standard form is to use the selectors to get pieces of an existing object, manipulate these pieces to create new components, then reassemble these using the constructor into a new version of the data abstraction The new thing we are adding is a mutator. This is something that will change an existing data object, that is, go into the exist structure and alter pieces of that structure in place, rather than constructing a new version of the object with copies of the parts. This is the topic to which we now turn6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 11.1 Slide 11.1.1 For the past few lectures, we have been exploring the topic of data abstractions, and their role in modularizing complex systems. We have particularly looked at the relationship between data structures and the procedures that manipulate them. Today we are going to add a new aspect to this topic, by introducing the idea of mutation. This is the idea of changing or altering an existing data structure, rather than simply making a copy of it. We are going to look at two examples of useful data structures, and show how while mutation carries some hazards with it; it also supports very efficient implementation of such structures. Slide 11.1.2 To set the stage for our exploration, let's first review what we know about data abstractions. First, we know that a data structure has a constructor, a way of gluing pieces together. Typically the definition of the constructor also involves a designation of the type contract of the constructor: what kind and how many objects are glued together. Associated with the constructor are sets of accessors or selectors that get pieces of the object back out. These are governed by a contract with the constructor, designating the behavior by which pieces glued together can be pulled apart. And we typically had a set of operations that used the data structures without actually using the details of the implementation. The standard form is to use the selectors to get pieces of an existing object, manipulate these pieces to create new components, then reassemble these using the constructor into a new version of the data abstraction. The new thing we are adding is a mutator. This is something that will change an existing data object, that is, go into the exist structure and alter pieces of that structure in place, rather than constructing a new version of the object with copies of the parts. This is the topic to which we now turn