Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 58 page Class Notes was uploaded by Vito Kilback on Wednesday September 23, 2015. The Class Notes belongs to CS550 at Drexel University taught by JeremyJohnson in Fall. Since its upload, it has received 29 views. For similar materials see /class/212431/cs550-drexel-university in ComputerScienence at Drexel University.
Reviews for ProgrammingLanguages
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
MASSACHVSETTS INSTITVTE OF TECH OLOGY Department of Electrical Engineering and Computer Science 3001 Structure and Interpretation of Computer Prog ams Sample assignment Obj ectoriented program ming Reading Section 41 Languages for ObjectOriented Programming This problem set is probably the most dif cult one of the semester but pa adoxically the one that asks you to write the least amount of code and for which you should haye to spend the least time in lab provided that you prepare be IUTY you Home to rt1 Instead of asking you to do a lot of implementation we are asking you to assume the role of language designer and to think about and discuss some issues in the design of languages for objectioriented prog amming Note especially that there is a signi cant part of this problem set to be completed after you haye nished in the lab This problem set has been designed so that the interpreter you will be dealing with is an extension of the metacircular eyaluator in chapter 4 of the book The implementation below is described with reference to the prog ams in the book In order to understand what is going on it will be necessary to work through section 41 before starting on this assignment Although Objectioriented prog amming has become yery popular the design of languages to sup port Objectiorientml programming is still an area of actiye research In this problem set you will be dealing with issues that are not welliunderstood and around which there are major disagreL ments among language designers The questions in this problem set will not ask you to supply right answersquot Instead they will ask you to make reasonable design choices and to be able to defend these choices We hope you will appreciate that once you haye come to grips with the notion of an interpreter you are in a position to address major issues in language design eyen issues that are at the forefront of current researchl Tutorial exercise 1 Do exercise 42 of the notes Don39t actually go to lab to implement this Just be able to explain precisely what procedures need to be modi ed what new procedures need to be written and what the code must do l39I39hisz problem set was developed by Hal Abelson lreg Mcliaren and David liaMacchia It draws2 on a Scheme implementation ofquot Oaklisp by Mcliaren and a Scheme implementation ofquot ylan by Jim Miller The organization ofquot the generic l39unction code follows2 the presentation ofquot the Common liisp Object stem CIAOS in 39I39hc r lr oft1c Uclaobjcc Protocol by Gregor Kiczales Jim des liivicres and Dan Bobrow MII Press2 l99l 6 001 Sample assignment Objectroriented programming 2 1 Issues in objectoriented language design VVe39ye already seen two different 1 1 to i 1 i 1 generic 1 One is data rlirmitml pmarannning which relies on a table to dispatch based on the types of arguments The second method quotLuggagenuwing represents objects as procedures with local state As we saw in problem set 33 these objects can be ar anged in complex inheritance relationships uch as a troll is a kind of personquot One d awback with both of these approaches is that they make a distinction between generic ope ations and ordinary procedures or between messagLpassing objects and ordinar 39 data This makes it awln39ard for example to extend an ordinary procedure so that it also works as a generic operation on new types of data For instance we might like to extend the addition operator so that it can add two yectors rather than haying to de ne a separate vectoradd procedure Recent experiments with bjectioriented languages haye attempted to integrate objects into the core of the language ather than uilding an object s that everything in the languz tem on top of the language The idea is ge is an object and all procedures are generic operations Two such languages both based upon Scheme are Orr lisp deyeloped in 1986 by Keyin Lang and Barak Pearlmutter at CML and Dylanu39l Dynamic Language currently under deyelopment at the Apple Research Center in Cambridge The language we will implement in this problem set is called MIT TOOL Tiny Object Oriented Language It is essentially a yer simpli ed yersion of Dylan designed to make the implementation an eas extension of the metacircular eyaluator of chapter 4 11 Classes7 instances7 and generic functions The framework we39ll be using in TOOL which is the same as in many objectioriented systems includes basically the same ideas as we39ye already seen although with different terminology An object39s behayior is de ned by its lilacs the object is said to be an instantiu of the class All instances of a class haye identical beha ior except for information held in a set of speci ed sluts which proyides the local state for the instance Following Dylan we39ll use the conyention of naming classes with names that are enclosed in angle brackets for example ltaccountgt or ltnumbergtf The defineclass special form creates a new kind of class You specify the name of the clas the class39s 311i1 tilrrcs and the names for the slots ln TOOL eyery class has a superclass whose behayior and slots it inherits There is a prede ned class called lt0bjectgt that is the most gene al kind of object Eyery TOOL class has lt0bjectgt as an ancestor Once you haye de ned a class you use the special form make to create instances of it Make takes the class as argument together with a list that speci es yalues for the slots The order in which the slots and Values are listed does not matter since each slot is identi ed by name For example we can specify that a quotcatquot is a kind of object that has a size and a breed and then create an instance of cat Note the use of the getslot procedure to obtain the Value in a designated slot 2Keep in mind that this use of bracket in question mark is a naming convention only like naming predicates with names that end 6 001 Sample assignment Objectroriented programming 3 TDDL gt defineclass ltcatgt ltobjectgt size breed defined class ltcatgt TO0Lgt define garfield make ltcatgt size 6 breed weirdgtgt undefined as in Scheme define returns the undefined value TO0Lgt getslot garfield breed weird Procedures in TOOL are all genericfunct ions de ned with the special form makegenericfunct ion TDDL gt definegenericfunction 4legged defined generic function 4legged You can think of a newly de ned generic function as an empty table to be lled in with methods You use definemethod to specify methods for a generic function that determine its ehayior on Various classes TDDL gt definemethod 4legged x ltcatgtgtgt added method to generic function 4legged TO0Lgt definemethod 4legged x ltobjectgtgtgt Whoknows added method to generic function 4legged TO0Lgt 4legged garfield t TO0Lgt 4legged Hal whoknows The list in definemethod following the generic function name is called the list of 8ilftifbltiai1 8 for the method This is like an argument list except that it also speci es the class of each argument In the rst example aboye we de ne a method for 4legged that talies one argument named x where x is a member of the class cat In the second example we de ne another method for 4legged that talies one argument named x where x is a member of the class ltobjectgt Now 4legged will return true if the argument is a cat and will return whoknows if the argument is an object Notice that garfield is an object as well as a cat because lt0bjectgt is the superclass of ltcatgt Yet when we call 4legged with garfield as an input TOOL uses the method for nmtwrl that cat and not the method for ltobjectgt In general TOOL uses the must spunquot applies to the inputs In a similar w f we can de ne a new generic function say and giye it a method for cats and subclasses of cat 39 3See the code below for a definition ofquot quotmost speci c methodquot 39I39his is one ofquot the things that language designers tlrggtlt39 ziltgttt 6 001 Sample assignment Objectroriented programming 4 TDDL gt definegenericfunction say defined generic function say TO0Lgt definemethod say cat ltcatgt stuff ltobjectgt print meow print is TO0L s procedure for printing things print stuffgt added method to generic function say TO0Lgt defineclass lthousecatgt ltcatgt address defined class lthousecatgtgt TDDL gt define fluffy note that a house cat is a cat and therefore make lthousecatgt has slots for breed and size as well size tinygt as for address TO0Lgt getslot fluffy breed undefined we never initialized fluffy s breed gt say garfield feed me feed me TO0Lgt say fluffy feed megt meow I feed me TO0Lgt say hal feed me No method found quot APPLY39GENERIC39FUNCTIDN In the nal example TOOL giyes an error mess ge when we apply say to the symbol hal This is because hal is a symbol not a cat and there is no say method de ned for symbols We can go on to de ne a subclass of ltcatgt TO0Lgt defineclass ltshowcatgt ltcatgt awards defined class ltshowcatgtgt TDDL gt definemethod say cat ltshowcatgt stuff ltobjectgt print stuff rint I am beautifulgtgt added method to generic function say TDDL gt define CorneliusSilverspoontheThird make ltshowcatgt size large breed Cornish Rexgt awards prettiest skingtgtgt undefined TO0Lgt say corneliussilverspoontheThird feed me feed me i am beautiful TO0Lgt definemethod say cat ltcatgt stuff ltnumbergt rint cats never discuss numbersgt added method to generic function say TO0Lgt say fluffy 37 cats never discuss numbers As the nal example illustrates TOOL picks the appropriate method for a generic function by examining the classes of all the arguments to which the function is applied This differs from the 6 001 Sample assignment ObjecrrorienTed programming 39 HIPS achpassing model where the dispatch is done by a single object Notice also that TOOL liIIOVVS that 37 is a member of the class ltnumbergt In TOOL wary data object is a member of some class The classes ltnumbergt ltsymbolgt list and ltproceduregt are prede ned with lt0bjectgt as their superclass Also wary procedure is a generic procedure to which you can add new methods The following generic procedures are prede ned each initially with a single method as indicated by the specializer ltnumbergt ltnumbergtgt ltnumbergt ltnumbergtgt ltnumbergt ltnumbergtgt ltnumbergt ltnumbergtgt ltnumbergt ltnumbergtgt gt ltnumbergt ltnumbergtgt lt ltnumbergt ltnumbergtgt sqrt ltnumbergt cons ltobjectgt lt0bjectgtgt append ltlistgt ltlistgt car ltlistgt cdr ltlistgt null ltobjectgt print ltobjectgt getslot ltobjectgt ltsymbolgtgt setslot ltobjectgt ltsymbolgt lt0bjectgtgt Tutorial exercise 2 Show how to i L tquot i yector milllnn kit in TOOL by extending the generic functions and which are already prede ned to work on numbers De ne a class ltvectorgt with slots xcor and ycor Arithmetic should be de ned so that adding two yectors produces the yector sum and multiplying two yectors produces the dot product rm1 It2112 v gt rut2 11112 Multiplying a number times a yector o a yector times a number should scale the yector by the number Adding a yector plus a number is not de ned Also de ne a generic function length such that the length of a yector is its length and the length of a number is its absolute r39alue 2 The TOOL Interpreter A complete listing of the TOOL interpreter is appended to this problem set This section leads you through the most important parts describing how they differ from the Scheme eyaluator in chapter 4 EVAL and APPLY VVe39ye named the e r39al procedure tooleval so as not to confuse it with Scheme39s ordinary eval The only di erence between tooleval and the eval in chapter 4 are the new cases added to handle the new special forms definegenericfunction definemethod defineclass and 6 001 Sample assignment Objectroriented programming 3 make Each clause dispatches to the appropriate handler for that form Note that we have deleted lambda all TOOL functions are de ned with definegenericfunction define tooleval exp env cond selfevaluating exp exp quoted exp text ofquotation exp variable exp lookupvariablevalue exp env definition exp eval definition exp env assignment exp evalassignment exp env lambda exp makeprocedure exp env We don t need lambda conditional exp evalcond clauses exp env genericfunctiondefinition exp DEFINEGENERICFUNCTIDN evalgenericfunctiondefinition exp env methoddefinition exp evaldefinemethod exp env DEFINEMETHOD 39 39 39 p al d ll la exp env DEFINECLASS instance39creation39 exp eval make exp env MAKE application exp toolapply tooleval operator exp env map lambda operand tooleval operand env operands exp else error quotUnknown expression type EVAL gtgt quot exp la ex Apply also gets an extra clause that dispatches to a procedure that handles applications of generic functions define toolapply procedure arguments cond primitiveprocedure procedure applyprimitiveprocedure procedure arguments compoundprocedure procedure evalsequence procedurebody procedure L arguments procedureenvironment procedure genericfunction procedure applygenericfunction procedure arguments else error quotUnknown procedure type APPLYquot New data structures A 311133 is represented by a data structure that contains the class name a list of slots for that clas and a list of all the ancestors of the class For instance in our cat example above we would have a class with the name lthousecatgt slots address size breed and superclasses ltcatgt lt0bjectgt Note that the slot narnes include all the slots for that class ie including the slots for the superclass Sirnila ancestors the list of ancestors of a class includes the superclass and all of its A gunm it mtititm is a data structure that contains the name of the function and a list of the methods de ned for that function Each method is a pair the specializers and the resulting procedure to use The specializers are a list of classes to which the arguments rnust belong in order 1 quot l l The 1 is as an ordinarjv39 Scherne procedure 1 for the method to be 39 L L AOmitting lambda takes2 away our ability to have unnamed procedures as we do in Scheme You might want to think about how to add such a feature to 3910 Hi 6 001 Sample assignment Objectroriented programming 1 An instance is a structure that contains the class of the instance and the list of r39alues for the slots See the attached code for details of the selectors and constructors for these data structures De ning generic functions and methods The special form definegenericfunction namc is handled by the following procedure define evalgenericfunctiondefinition exp env let name genericfunctiondefinitionname exp let val makegenericfunction name gt definevariable name val env list defined generic function namegtgt This procedure extracts the mum portion of the expression and calls makegenericfunction to create a new generic function Then it binds mum to the new generic function in the giyen enyironrnent The r39alue returned is a message to the user which will be printed by the readieyali print loop Evaldefinemethod handles the special form definemethod gcncricfunction pararmmdchmch body for example definemethod say cat ltcatgtgt stuff ltnumbergtgtgt print cats never discuss numbers In general here gmmrM nuithm is the generic function to which the method will be added pumme budlilm SHb is a list of parameters for this method and the classes to which they must belong and burly is a procedure body just as fo an ordinary Scherne procedure The syntax procedures for this form include appropriate procedures to select out these pieces see the code Evaldefinemethod rst nds the generic function Notice that the grMarnifunnthm piece of the expression must be eyaluated to obtain the actual generic function Evaldefinemethod disasi sernbles the list of pmmnsrindtilussus into separate lists of parameters and classes The pa arneter the burly and the enyironrnent are combined to form a procedure just as in Scheme The classes the method is installed into the generic function become the specializers for this method Final 539I39he dot before the word quotbodyquot signifies that we can put more than one expression in the body just as with ordinary Scheme procedures 6 001 Sample assignment Objectroriented programming define evaldefinemethod exp en let gf tooleval methoddefinitiongenericfunction exp env if not genericfunction gf error quotUnrecognized generic function DEFINEMETHDD gtgt quot ethoddefinitiongenericfunction exp let params methoddefinitionparameters exp installmethodingenericfunction map lambda p paramlistelementclass p env ams r makeprocedure makelambdaexpression extract the parameter names from the paramlist map paramlistelementname params methoddefinitionbody exp nv list added method to generic function genericfunctionname gf Tutorial exercise 3 Evaldefinemethod calls paramlistelementclass in order to nd the cl sforez ach parameter Without looking at the attached code predict whether paramlistelementclass should call tooleval Now look at the code and see if you were ht Giye a careful explanation of why tooleval is or is not called and what difference this malies De ning classes and instances The special form defineclass nann xupanaxx xh x is handled by define evaldefineclass exp env let superclass tooleval classdefinitionsuperclass exp env if not class superclass error quotUnrecognized superclass MAKECLASS gtgt quot l ssdefinitionsuperclass exp let name classdefinitionname exp allslots collectslots classdefinitionslotnames exp superclass let newclass akeclass name superclass allslots definevariable name newclass env list defined class name The only tricky part here is that we haye to collect all the slots from all the ancestor classes to combine with the slots declared for this particular class This is accomplished by the procedure collectslots see the code The nal special form make clam tsot n m m m 1 rain 3 6 001 Sample assignment Objectroriented programming is handled by the procedure evalmake This constructs an instance for the speci ed class with the designated slot yalues See the attached code for details REST STOP Applying generic functions Here is where the fun start and what all the preceding machinerjxr39 2 generic function to some arguments we rst nd all the methods that are applicable giyen the classes of the arguments This giyes us a list of methods of which we will use the rst one We39ll see why the rst one in a minute W39e extract the procedure for that method and apply that procedure to the arguments Note the subtle recursion here applygenericfunction below calls toolapply with the procedure part of the method for When we apply a define applygenericfunction genericfunction arguments let methods computeapplicablemethodsusingclasses enericfunction map classof arguments if null methods error quotNo method found APPLYGENERlCFUNCTIDNquot toolapply methodprocedure car methods arguments To compute the list of applicable methodsquot we rst nd all methods for that generic function that can e applied giyen the list of classes for the arguments We then sort these according to an ordering called methodmorespecific The idea is that the rst method in the sorted list will be the most speci c one which is the the best method to apply for those arguments define mpu LLquot L m h d u ins la 5 u ri fun ti u classes sort filter lambda method methodappliestoclasses method classes genericfunctionmethods genericfunction methodmorespecific To test if a method is applicable giyen a list of classes of the supplied arguments we examine the method specializers and see whether for each supplied argument the class of the argument is a subclass of the class required by the specializer define methodappliestoclasses method classes define checkclasses supplied require cond and null supplied null required true all chalked or null supplied null required false something left over subclass car supplied car required checkclasses cdr supplied cdr required else false checkclasses classes methodspecializers method To determine subclasses we use the class ancestor list class is a subclass of classQ if classQ is a member of the clas ancestor list of classl 6 001 Sample a gnment Objectroriented progranuning 10 define subclass classl class2 or eq39 classl class2 memq class2 classancestors class1gtgt Finally we need a way to compare two methods to see which one is more speci cquot We do this by looking at the method speci39 1 rs Methodi is considered to be more speci c than method2 if for each clz s in the list of specializers the for methodi is a sul s of the class for method2 See the procedure methodmorespecific in the attached code X Tutorial exercise 4 In the example at the end of section 1 explain how the generic function dispatch chooses the correct say method when we ask the cat fluffy to say a number In particular what are all the applicable methods In what order will they appear after they are sorted according to methodmorespecific39 Classes for Scheme data TOOL is arranged so that ordinary Scheme data o jects numbers symbols and so on appear as TOOL objects For example any number is an instance of a prede ned class called ltnumbergt which is a class with no slots whose superclass is ltobjectgt The TOOL interpreter accomplishes this by haying a special set of classes called schemeobjectclasses If a TOOL object is not an ordinary instance ie an instance data structure as described aboye the interpreter checks whether it belongs to one of the Scheme object classes by applying an appropriate test For example anything that satis es the predicate number is considered to be an instance of ltnumbergt See the code for details Initial environment and driver loop When the interpreter is initialized it builds a global enyironment that has bindings for true false nil the prLde ned classes and the initial set of generic functions listed at the end of section 1 The driyer loop is essentially the same as the driverloop procedure in chapter 4 of the notes One cute difference is that this driyer loop prints yalues using the TOOL generic function print By de ning new methods for print you can change the way the interpreter prints data objects Tutorial exercise 5 De ne a print method so that TOOL will print yectors which you de ned in exercise 2 showing their xcor and ycor 3 To do in lab When you load the code for this problem set the entire TOOL interpreter code attached will be loaded into Scheme Howeyer in order to do the lab exercises you will need to modify only a tiny bit of it This code has been separated out in the le modscm so you can edit it conyeniently 6 001 Sample assignment Objectroriented programming 11 To start the TOOL interpreter type init ializetool This initializes the global enyironrnent and starts the readieyaliprint loop To evaluate a TOOL expression type it after the prompt followed by T39I39erx T39I39ere In order to keep the TOOL interpreter simple we haye not provided any mechanism for handling errors Any error such as an unbound yaria le will bounce you back into Scherne39s error handler To get back to TOOL quit out of the error and restart the driyer loop by typing driverloop If you make an error that requires reinitializing the enyironrnent you can rerun initilializetool but this will make you lose any new classes generic functions or methods you haye de ned Lab exercise 6 Start the TOOL eyaluato and try out your yector de nitions from exercise 2 Also check you answer to exercise 33 where you de ned a new print method for yectors How did TOOL print yectors before you added your own print rnethod39 Turn in your de nitions and a brief interaction showing that they work Lab exercise 7 One annoying thing about TOOL is that if you de ne a method before you39ye de ned a generic function for that method you will get an error For example in the rst example in section 1 we had to explicitly eyaluate definegenericfunction 4legged before we could e r39aluate definemethod 4legged thing lt0bjectgtgtgt Whoknows Otherwise the second expression would giye the error that 4legged is unde ned Modify the TOOL interpreter so that if the user attempts to de ne a method fo a generic function that does not yet exist TOOL will rst autornatically de ne the generic function One thing to consider In which enyironrnent should the name of the generic function be bound the global enyironrnent the enyironrnent of the eyaluation39 some other enyironrnent39 There is no right answerquot to this question you are the language designer But whateyer choice you make write a brief paragraph justifying your choice In particular include an example of a prog arn for which the choice of enyironrnent rnatters ie where the prog arn would haye a different behayior or perhaps giye an error if the choice were different Hint The only procedure you should need to modify for this exercise is evaldefinemethod Turn in along with your design justi cation your rnodi ed code together with a brief interaction showing that the modi ed interpreter works as intended Lab exercise 8 Another inconyenience in TOOL is that we need to use getslot in order to obtain slot yalues It would be more conyenient to haye TOOL autornatically de ne selectors for slots For example it would be nice to be able to get the x and y coordinates of a yector by typing xcor v and ycor v ather than getslot v xcor and getslot v ycor Modify the interpreter to do this Name r wheneye a class is de ned TOOL should automatically de ne a generic function for each of its slot narnes together with a method that returns the corresponding slot yalue for arguments of that class Turn in a listing of your code and an example showing that it works Hint The only part of interpreter you need to modify for this exercise is evaldefineclassj 4 6 001 Sample assignment Objectroriented programming 12 Lab exercise 9 Give some simple example of de ning some objects and methods besides cats and vectors that involve subclasses superclasses and methods and which illust ate the modi car tions vou made in exercises 8 and 9 4 Multiple Superclasses To do AFTER you are done in the lab This nal question asks vou to consider a trickv issue in language design We are not requiring vou to actuallv implement vour design Nevertheless we do expect vou to think carefullj about the issues involved and to give a careful description of the solution vou come up with Don39t think that this is a straightfrward exercise designers of objectioriented languages are still arguing about it The major r in which TOOL is simpler than other objecForiented languages such as Dvlan or the Common Lisp Object Sjvstem CLOS is that each class has onlv mm immediate superclass As illustrated with messagLpassing sr39stems lecture on October 22 there are cases where it is convenient to have a class inherit behavior from more than one kind of class This will involve some changes to TOOL As a start the svntax for defineclass must be modi ed to accept a list of superclasses rather than a single superclass Let39s assume that defineclass now takes a list of superclasses For instance going back to our original example about cats we might have din m rm r a r a w a gtgt This new class should inherit from both lthousecat and showcat In gene al when the new cla is constructed it should inherit methods and slots from all its superclasses and their ancestors However it39s not obvious what inheritance should mean For example suppose we have a generic function eat and we de ne methods as follows definemethod eat c lthousecatgt print yum I m hungry definemethod eat c ltshowcatgt print I eat only caviar What should happen when we ask a fancvihouswcat which is both a show439at and a house439at to eat More gener39 what is the most speci c methodquot that should be used when a generic function is applied to its arguments given that some of the arguments mav have multiple superclasses What are the new kinds of choices that arise How should the language give the user the abilitv to control these choices Or mavbe it shouldn t give the user this level of control Postlab exercise 10 You are now a language designer Your task is to design an extension to TOOL so that it handles classes with multiple superclasses Three of the issues vou have to deal with are a What should be the svntax for de ning classes b What slots does a class get when it is de ned How is a method chosen when a generic function is applied to its arguments Prepare a design writeup that has three parts 6 001 Sample assignment Objectroriented programming 13 1 Write a clear 2 3 page description of vour language extension This description should be geared toward the usurof the language It should include a simple but realistic and nonitrivial example of a prog am that involves multiple superclasses The example should illust ate how vour language handles each of the three issues a b and You should also explain how the language deals with each of these issues in general 2 For each of design choices vou illustrated in part 1 give an alternative choice vou could have made and explain brie v whv vou think vour choice is better If vou can39t think of anv other choice vou might have made then s 3 As carefullv as vou can but without actuallv writing anv code specifv the procedure that the evaluator should follow in choosing which method to select when applving a generic function to a given set of arguments Your description should be clear enough so that someone could implement this procedure based upon vour speci cation Optional extra credit Irnplernent vour design for multiple superclasses in TOOL and lOIIlOIk st ate that it works The TOOL interpreter was designed to make this not too dif cult but it will involve a conside able number of small changes to the code and is likelv to be tirnwconsurning Dynamic Memory Allocation Agenda Process Layout 0 Memory Allocation Algorithms Garbage Collection Algorithms Reference Ch 57 and 85 Process Layout lower addresses executable code text static data e g globals heap stack higher addresses Process Layout lower addresses higher addresses executable code text static data e g globals heap V sossorppe stack sossolppla PHI2A PH12A Process Layout lower addresses executable code V sossorppn text rigid gt static data eg globals rigid gt heap changed With sbrk gt changed by calling and gt returning om functions stack higher addresses sossolppla PHI2A PH12A Sbrk include ltunistdhgt Prototype void sbrkptrdifft increment Increases or decreases the address of the bottom of the heap Returns the previous address sbrk O can be used to obtain the current address Implementation of sbrk is operating system dependent Example Compiled on tux using gcc this program produces the following output OX00020908 OX00022908 include ltstdiohgt include ltstdlibhgt include ltunistdhgt int main printfquotOX08pnquotsbrkO malloc1024 printfquotOX08pnquotsbrkO return 0 What happened Initially the heap ended at 0x00020908 executable code text static data e g globals stack lt OX00020908 What happened Initially the heap ended at 0x00020908 Then I said that I needed an additional lk executable code text static data e g globals stack lt OX00020908 What happened Initially the heap ended at 0x00020908 Then I said that I needed an additional lk So malloc increased the heap size by 8k executable code text static data e g globals stack lt OX00020908 lt OX00022908 Agenda Process Layout Memory Allocation Algorithms Fixed Size Variable Size FirstFit NextFit BestFit The Buddy Algorithm Garbage Collection Algorithms Fixed Size Algorithm Maintain a list of free blocks the freelist To allocate a block pop one off the front of the list To free a block push it back onto the front of the list Fixed Size Algorithm Obtain a large Chunk of memory Fixed Size Algorithm Divide it up into blocks of the appropriate size Fixed Size Algorithm Give each of the blocks a fourbyte header Fixed Size Algorithm front AAA Use these headers as nextpointers and arrange the blocks into a linked list Fixed Size Algorithm front AAA To allocate a block pop one off the front of the list eg pl alloc p2 alloc p3 alloc Fixed Size Algorithm To allocate a block pop one off the front of the list eg p1 alloc p2 alloc p3 alloc Fixed Size Algorithm front HANNA H H H HI p1 p2 To allocate a block pop one off the front of the list eg pl alloc p2 alloc p3 alloc Fixed Size Algorithm To allocate a block pop one off the front of the list eg pl alloc p2 alloc p3 alloc Fixed Size Algorithm T0 free a block push it back onto the front of the list eg free pl free p3 free p2 Fixed Size Algorithm front HANNA HHH p1 p2 p3 T0 free a block push it back onto the front of the list eg free p1 free p3 free p2 Fixed Size Algorithm front WWWWAN I p1 p2 p3 T0 free a block push it back onto the front of the list eg free pl free p3 free p2 Fixed Size Algorithm front 7 p1 p2 p3 T0 free a block push it back onto the front of the list eg free pl free p3 free p2 Fixed Size Algorithm front memmm J V Note that the list is not usually kept sorted by address Agenda Process Layout Memory Allocation Algorithms Fixed Size Variable Size FirstFit NextFit BestFit The Buddy Algorithm Garbage Collection Algorithms Variable Size Algorithmsilt Maintain a list of free blocks the freelist To allocate a block nd a block of suf cient size and remove it from the list To free a block insert it into the list keeping the list sorted by address The Buddy Algorithm does not adhere to this overall scheme Variable Size Algorithms implementation Free Block Variable Size Algorithms Variable Size Algorithms Adjacent free blocks must be coalesced unused unused Finding a block of sufficient size At least three approaches FirstFit Find the first block in the list of suf cient size NextFit BestFit Variable Size FirstFit front 16k Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit 14k p1 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit p1 p2 Example p1 alloc2k freep3 p2 alloc1k freep5 p3 alloc5k p7 alloc3k p4 alloc1k freep6 p5 alloc4k p8 alloc1k p6 alloc1k p9 alloc6k freepl Variable Size FirstFit front 7 7 W0 7 V p1 p2 p3 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit front p1 p2 p3 p4 Example p1 alloc2k freep3 p2 alloc1k freep5 p3 alloc5k p7 alloc3k p4 alloc1k freep6 p5 alloc4k p8 alloc1k p6 alloc1k p9 alloc6k freepl Variable Size FirstFit front p1 p2 p3 p4 p5 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit front p1 p2 p3 p4 p5 p6 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloc1k p6 alloc1k p9 alloc6k freepl Variable Size FirstFit front p1 p2 p3 p4 p5 p6 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freep1 Variable Size FirstFit front 2k 5k p1 p2 p3 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit front 2k SkE 214 p6 p1 p2 p3 p4 p5 Example p1 alloc2k freepB p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit front 2k2k 4k WI p1 p2 p7 p4 p5 p6 p3 Example p1 alloc2k freep3 p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit f t Ion Codca d 2k 7k p1 p4 p5 p6 Example p1 alloc2k freepB p2 alloclk freep5 p3 alloc5k p7 alloc3k p4 alloclk freep6 p5 alloc4k p8 alloclk p6 alloclk p9 alloc6k freepl Variable Size FirstFit front A 2k 7k p8 p2 p7 p4 p5 p6 p1 p3 Example p1 alloc2k freep3 p2 alloc1k freep5 p3 alloc5k p7 alloc3k p4 alloc1k freep6 p5 alloc4k p8 alloc1k p6 alloc1k p9 alloc6k freepl
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'