Sections3 7

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

By: Aadinitin (95 month(s) ago)

its very easy to understand

Presentation Transcript

Data Abstraction Abstract Data Types (3.7): 

Data Abstraction Abstract Data Types (3.7)

Abstract data types: 

Abstract data types A datatype is a set of values and an associated set of operations Int: div, mod, is, isEven, isOdd, isNat, toFloat, toString Number: +, -, *, ~, abs, is, pow A datatype is abstract if only it is completely described by its set of operations regardless of its implementation This means that it is possible to change the implementation of the datatype without changing its use The datatype is thus described by a set of procedures These operations are the only thing that a user of the abstraction can assume

Example: A Stack: 

Example: A Stack Assume we want to define a new datatype stack T whose elements are of any type T fun {NewStack}: Stack T fun {Push Stack T T }: Stack T fun {Pop Stack T T }: Stack T fun {IsEmpty Stack T }: Bool These operations normally satisfy certain conditions: {IsEmpty {NewStack}} = true for any E and S0, S1={Push S0 E} and S0 ={Pop S1 E} hold {Pop {NewStack} E} raises error

Stack (list-based implementation): 

Stack (list-based implementation) fun {NewStack} nil end fun {Push S E} E|S end fun {Pop S E} case S of X|S1 then E = X S1 end end fun {IsEmpty S} S==nil end

Stack (another implementation): 

Stack (another implementation) fun {NewStack} nil end fun {Push S E} E|S end fun {Pop S E} case S of X|S1 then E = X S1 end end fun {IsEmpty S} S==nil end fun {NewStack} emptyStack end fun {Push S E} stack(E S) end fun {Pop S E} case S of stack(X S1) then E = X S1 end end fun {IsEmpty S} S==emptyStack end

Dictionaries: 

Dictionaries The datatype dictionary is a finite mapping from a set T to andlt;valueandgt;, where T is either atom or integer fun {NewDictionary} returns an empty mapping fun {Put D Key Value} returns a dictionary identical to D except Key is mapped to Value fun {CondGet D Key Default} returns the value corresponding to Key in D, otherwise returns Default fun {Domain D} returns a list of the keys in D

Implementation: 

Implementation fun {NewDictionary} nil end fun {Put Ds Key Value} case Ds of nil then [Key#Value] [] (K#V)|Dr andthen Key==K then (Key#Value) | Dr [] (K#V)|Dr andthen Kandgt;Key then (Key#Value)|(K#V)|Dr [] (K#V)|Dr andthen Kandlt;Key then (K#V)|{Put Dr Key Value} end end

Implementation: 

Implementation fun {CondGet Ds Key Default} case Ds of nil then Default [] (K#V)|Dr andthen Key==K then V [] (K#V)|Dr andthen Kandgt;Key then Default [] (K#V)|Dr andthen Kandlt;Key then {CondGet Dr Key Default} end end fun {Domain Ds} {Map Ds fun {$ K#_} K end} end

Abstract Data Types: 

Abstract Data Types A set of values together with operations Implementation can be changed without affecting clients Improves modularity, maintainability Secure ADTs Names Chunks Futures

Further implementations: 

Further implementations Because of abstraction, we can replace one ADT implementation with another, and change nothing except possibly efficiency. Data abstraction makes clients of the ADT unaware (other than through perceived efficiency) of the internal implementation of the data type. It is important that clients do not use anything about the internal representation of the data type (e.g., using {Length Stack} to get the size of the stack). Using only the interface (defined ADT operations) ensures that different implementations can be used in the future.

Secure abstract data types:Stack is not secure: 

Secure abstract data types: Stack is not secure fun {NewStack} nil end fun {Push S E} E|S end fun {Pop S E} case S of X|S1 then E=X S1 end end fun {IsEmpty S} S==nil end

Secure abstract data types II: 

Secure abstract data types II The representation of the stack is visible: [a b c d] Anyone can fiddle with the contents (ie., be tempted by the syntactic convenience of lists to manipulate the stack directly, rather than through the ADT Anyone can use an incorrect representation, i.e., by passing other language entities to the stack operation, causing it to malfunction (like a|b|X or Y=a|b|Y) Anyone can write new operations on stacks, thus breaking the abstraction-representation barrier How can we guarantee that the representation is invisible?

Secure abstract data types III: 

Secure abstract data types III It is not possible to build secure abstract data types in the declarative model we have seen so far (think about it!) The model has to be extended. Here are two ways: By adding a new basic type, an unforgeable constant called a name By adding encapsulated state. A name is like an atom except that it cannot be typed in on a keyboard or printed! The only way to have a preexisting name is if one is given it explicitly There are just two operations on names: N={NewName} : returns a fresh name N1==N2 : returns true or false

Secure abstract datatypes IV: 

Secure abstract datatypes IV proc {NewWrapper ?Wrap ?Unwrap} Key={NewName} in fun {Wrap X} fun {$ K} if K==Key then X end end end fun {Unwrap C} try {C Key} catch _ then raise error(unwrap( C)) end end end end We want to « wrap » and « unwrap » values Let us use names to define a wrapper andamp; unwrapper

Secure abstract data types:A secure stack: 

Secure abstract data types: A secure stack With the wrapper andamp; unwrapper we can build a secure stack local Wrap Unwrap in {NewWrapper Wrap Unwrap} fun {NewStack} {Wrap nil} end fun {Push S E} {Wrap E|{Unwrap S}} end fun {Pop S E} case {Unwrap S} of X|S1 then E=X {Wrap S1} end end fun {IsEmpty S} {Unwrap S}==nil end end

Capabilities and security: 

Capabilities and security We say a computation is secure if it has well-defined and controllable properties, independent of the existence of other (possibly malicious) entities (either computations or humans) in the system What properties must a language have to be secure? One way to make a language secure is to base it on capabilities Capabilities originated in operating systems research A capability can give a process the right to create a file in some directory

Capabilities: 

Capabilities A capability is an unforgeable language entity (« ticket ») that gives its owner the right to perform a particular action and only that action In our model, all values are capabilities (records, numbers, procedures, names) since they give the right to perform operations on the values Having a procedure gives the right to call that procedure. Procedures are very general capabilities, since what they do depends on their argument Using names as procedure arguments allows very precise control of rights; for example, it allows us to build secure abstract data types

Secure abstract datatypes V: 

Secure abstract datatypes V We add two new concepts to the computation model {NewChunk Record} returns a value similar to record but its arity or label cannot be inspected, nor can it be unified. recall {Arity foo(a:1 b:2)} is [a b] Operator ’.’ is the only legal operation {NewName} a function that returns a new symbolic, unforgeable (i.e. cannot be guessed or manually constructed), name declare MyName={NewName} in foo(a:1 b:2 MyName:3) makes impossible to access the third component, if you do not know the arity {NewChunk foo(a:1 b:2 {NewName}:3) } Returns what ?

Secure abstract datatypes VI: 

Secure abstract datatypes VI proc {NewWrapper ?Wrap ?Unwrap} Key={NewName} in fun {Wrap X} {NewChunk foo(Key:X)} end fun {Unwrap C} try C.Key catch _ then raise error(unwrap(C)) end end end end

Secure abstract data types:Another secure stack: 

Secure abstract data types: Another secure stack With the new wrapper andamp; unwrapper we can build another secure stack (since we only use the interface to wrap and unwrap, the code is identical to the one using higher-order programming) local Wrap Unwrap in {NewWrapper Wrap Unwrap} fun {NewStack} {Wrap nil} end fun {Push S E} {Wrap E|{Unwrap S}} end fun {Pop S E} case {Unwrap S} of X|S1 then E=X {Wrap S1} end end fun {IsEmpty S} {Unwrap S}==nil end end

Protecting Unbound Variables: 

Protecting Unbound Variables Problem example: Stream: a list with an unbound tail S=a |b |c | X Anyone who reads X or S can close it by binding X, whether you want them to or not Solution: a read-only view of a variable Called a future Operation: Y= !!X ;Y is a read-only view of X Any binding of X will be transferred to Y Y can be handed to any entities that need the value of X, but that are not authorized to set the value of X A bind on Y when Y is undetermined will suspend until Y is determined

authorStream Live Help