'&$%CSE 341:Programming LanguagesHal PerkinsSpring 2011Lecture 21— Defining and Implementing Dynamic-DispatchHal Perkins CSE341 Spring 2011, Lecture 21 1'&$%Where are We?In 7 weeks, we’ve picked up enough ML, Scheme, and Ruby to talkintelligently about modern, general-purpose PLs.• Congratulations to us!Now we need to:• Consider OO semantics as carefully as we did FP semantics• Consider various OO extensions and design decisions• Consider OO type systems as carefully as we did FP type systems• Compare OO and FP, specifically extensibility and polymorphism• Discuss memory management and garbage collectionToday: Ruby look-up rules, a lower-level view of dynamic dispatchHal Perkins CSE341 Spring 2011, Lecture 21 2'&$%Look-up rulesHow we resolve various “symbols” is a key part of language definition.• In many ways, FP boils down to first-class functions, lexical scope,and immutability.In Ruby, we syntactically distinguish instance fields (@x) and classfields (@@x) from method/block variables (x) and method names (x).• Unlike Java, no shadowing of fields.– Makes lookup rules for fields easy.• Unlike Java, can shadow method names (does m+2 read a variableor call a method)– Rather clumsy since variables aren’t declared.– Will ignore confusion today; see book for the rules.Hal Perkins CSE341 Spring 2011, Lecture 21 3'&$%“First-class”If something can be computed, stored in fields, passed as arguments,returned as results, etc., we say it is “first-class”.All objects in Ruby are first-class (and most things are objects).These things are not:• Message names: Must write if b then x.m else x.n end, notx.(if b then m else n end)• Blocks (hence conversion to Proc instances)• Argument listsHal Perkins CSE341 Spring 2011, Lecture 21 4'&$%Variable lookupTo resolve a variable (e.g., x):• Inside a code block that defines x ({|x| e}), x resolves to thelocal variable of the block (i.e., the argument).• Else inside a code block, x resolves to an x that is defined in theenclosing method.– Lexical scope, just like in ML and Scheme– Ruby implementation must build closures (those pairs of codeand environment you built for homework 5)Nothing really new hereHal Perkins CSE341 Spring 2011, Lecture 21 5'&$%Message lookupTo resolve a message (e.g., m):• A message is sent to an object (e.g., e.m), so first evalauteexpression e to an object obj.• Get the class of obj (e.g., A) (every object has a class).• If m is defined in A (check instance methods first, then classmethods), invoke that method, else recur with superclass of A.– Will slightly complicate this story next time with mixinsHal Perkins CSE341 Spring 2011, Lecture 21 6'&$%What about self?As always, evaluation takes place in an environment.In every environment, self is always bound to some object. (Thisdetermines message resolution for self and super.)Key principles of OOP:• Inheritance and override (last slide)• Private fields (just abstraction)• The semantics of message sendTo send m to obj means evaluate the body of the method that mresolves to for obj in an environment with argument names mapped toactual arguments and self bound to obj.That last phrase is exactly what “late-binding”, “dynamic dispatch”,and “virtual function call” mean. It is why code defined insuperclasses can invoke code defined in subclasses.Hal Perkins CSE341 Spring 2011, Lecture 21 7'&$%A Simple Example, part 1fun even x = if x=0 then true else odd (x-1)and odd x = if x=0 then false else even (x-1)(* does not change behavior of odd *)fun even x = (x mod 2) = 0(* neither does this *)fun even x = falseHal Perkins CSE341 Spring 2011, Lecture 21 8'&$%A Simple Example, part 2class Adef even xif x=0 then true else odd(x-1) endenddef odd xif x=0 then false else even(x-1) endendendclass B < Adef even x # changes B’s odd too!x % 2 = 0endendHal Perkins CSE341 Spring 2011, Lecture 21 9'&$%Some Perspective on Late-BindingSome opinions:• Late-binding makes a more complicated semantics– Ruby without self is easier to define and reason about– It takes months in CSE 142 to get to where we can explain it– It makes it harder to reason about programs• But late-binding is often an elegant pattern for reuse– OO without self is not OO– Late-binding fits well with the “object analogy”– Late-binding can make it easier to localize specialized codeeven when other code wasn’t expecting specialization∗ More reuse/abuse.Hal Perkins CSE341 Spring 2011, Lecture 21 10'&$%A Lower-Level ViewRuby clearly encourages late-binding with its message-send semantics.But a definition in one language is often a pattern in another...We can simulate late-binding in Scheme easily enoughAnd sketch how compilers/interpreters implement objects• A naive but accurate view of implementation can give an alternateway to reason about programsHal Perkins CSE341 Spring 2011, Lecture 21 11'&$%The Key IdeaThe key to implementing late-binding is extending all the methods totake an extra argument (for self).So an object is implemented as a record holding methods and fields,where methods are passed self explicitly.And message-resolution always uses self.Hal Perkins CSE341 Spring 2011, Lecture 21 12'&$%What about classes and performance?This approach, while a fine pattern, has some problems:• It doesn’t model Ruby, where methods can be added/removedfrom classes dynamically and an object’s class determinesbehavior.• It is space-inefficient: all objects of a class have the same methods.• It is time-inefficient: message-send should be constant-time, notlist traversals.We fix the first two by adding a level of indirection: all instances madefrom same “constructor” share list of methods, and we can mutate thelist.We fix the third with better data structures (array or hash) and varioustricks (so subclassing works).Hal Perkins CSE341 Spring 2011, Lecture 21 13'&$%Static typing gets in the way• We have seen late-binding as a Scheme pattern• In reality, we have learned roughly how OO implementations do it,without appealing to assembly code (where it really happens)• Using ML instead of Scheme would have been a pain:– The ML type system is “unfriendly” for self.– We would have roughly taken the “embed Scheme in ML”approach, giving every object the same ML type.– But to be fair, basic OO typing (coming soon) is “unfriendly”to ML datatypes, first-class functions, and parametricpolymorphism.Hal Perkins CSE341
View Full Document
Unlocking...