New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Reece Little DVM


Reece Little DVM
GPA 3.57


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 133 page Class Notes was uploaded by Reece Little DVM on Sunday September 27, 2015. The Class Notes belongs to COM S 541 at Iowa State University taught by Staff in Fall. Since its upload, it has received 40 views. For similar materials see /class/214512/com-s-541-iowa-state-university in ComputerScienence at Iowa State University.

Similar to COM S 541 at ISU

Popular in ComputerScienence




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/27/15
Communicating and Mobile Systems Overview Programming Model Interactive Behavior Labeled Transition System Bisimulation The nCalculus Data Structures and kCalculus encoding in the nCalculus References Robin Milner Communication and Concurrencyquot Prentice Hall 1987 Robin Milner Communicating and Mobile Systems the nCalculus Cambridge University Press 1999 Gerald K Ostheimer and Antony J T Davie TECEIICUIUS Characterizations of some Practical kCalculus Reduction Strategiesquot Department of Mathematical and Computing Science University of St Andrews CS93 14 1993 Com S 541 The Programming Model Communication is a fundamental and integral part of computing whether between different computers on a network or between components within a single computer Robin Milner s view Programs are built from communicating parts rather than adding communication as an extra level of activity Q Programs proceed by means of communication Com S 541 Evolving Automata Static System Static System Com S 541 Evolving Automata Deleted Note Deleted Note at 77039 41 a I D quotz 2 I I I I Com S 541 Evolving Automata Divided Node Divided Node Com S 541 Evolving Automata Moved Link Moved Link Com S 541 Automata Starting point The components of a system are interacting automata An automaton is a quintuple A 2 Q no 0 F with a set 2 of actions sometimes called an alphabet a set Q qo q of states a subset F of Qcalled the accepting states a subset o of 2x A x Qcalled the transitions a designated start state qo A transition qaq e o is usually written qu39 The automaton A is said to be finite if Qis finite Com S 541 Behavior of Automata An automaton is deterministic if for each pair qa 6 0x 2 there is exactly one transition qu39 deterministic automata nondeterministic automata Com S 541 Vending Machine A teacoffee vending machine is implemented as black box with a three symbol alphabet 1 coffee Com S 541 Internal Transition Diagrams Deterministic system 31 Nondeterministic system 32 1 Are both systems equivalent Com S 541 1 2 2 qOlql8 qOlqllq28 qltuTaq0 lq2 q125a qO q2 eq0 q2l q3 q3 eq0 ql tea qO l coffee qO q0l Eagm lEerH8 q2lEeq0 q01 Ea sl aqmg q01Eaqo11 eqog qO 1 Ea sl ev q01 Eaqo1Eeqmg qO 1 Ea 1 coffee q0g qO l Ea1oo ee The systems 31 and 52 are languageequivalent but the observable behaII39oris not the same Com S 541 Automata Summary Languageequivalence is not suitable for all purposes If we are interested in interactive behavior then a nondeterministic automaton cannot correctly be equated behaviorally with a deterministic one A different theory is required Com S 541 Labeled Transition Systems A labeled transition system over actions Actis a pair Q T consisting of a set Q 70 q1 of states a ternary relation Tg Qx Actgtlt Q known as a transition relation If q0cq e T we write qu and we call qthe source and q the target of the transition Com S 541 States and Actions Important conceptual changes What matters about a string 5 a sequence of actions is not whether it drives the automaton into an accepting state since we cannot detect this by interaction but whether the automaton is able to perform the sequence of s interactively A labeled transition system can be thought of as an automaton without a start or accepting states Anystate can be considered as the start Actions consist of a set L of labelsand a set I of colabes wit7 Ia ae L We use 0c 3 to range over actions Act Com S 541 Strong Simulation Idea In 1981 D Park proposed a new approach to define the equivalence of automatons bisimulation Given a labeled transition system there exists a standard definition of bisimulation equivalence that can be applied to this labeled transition system The definition of bisimulation is given in a coma ucz I39Ie style that is two systems are bisimular if we cannot show that they are not Informally to say a system 81 simulates system 82 means that 81 s observable behavior is at least as rich as that of 82 Com S 541 Strong Simulation Definition Definition Let Q T be an labeled transition system and let s be a binary relation over Q Then s is called a strong simulation over Q T if whenever qu if pip39 then there exists q e Q such that qiq39and p Sq We say that q strongly simulates p if there exists a strong simulation 8 such that qu Com S 541 Strong Simulation Example 81 1 fee 6 1 ea The statequ and pOaIedjfEeIaqt 82 Therebre he system 581 and S2 are 39 notoonsjdered to be equivalaqt 1 1 I 1 coffee Com S 541 Strong Simulation Example II Define s by s DO 10 p1q1 p3q1 DZ 14 D4 12 p5 13 then Sis a strong simulation hence qO strongly simulates p0 To verify this for every pair q e s we have to consider each transition of p and show that it is properly matched by some transition of q However there exists no strong simulation R that contains the pair ql p1 because one of ql S transition could never be matched by pl Therefore the states qO and p0 are different and the systems 81 and 82 are not considered to be equivalent Com S 541 Strong Bisimulation Definition The converse R1 of any binary relation R is the set of pairs yX such that Xy e R Let Q T be an labeled transition system and let s be a binary relation over Q Then s is called a strong bisimulation over Q T if both s and its converse slare strong simulations We say that p and q are strongly bisimular or strongly equivalent written p q if there exists a strong bisimulation s such that qu Com S 541 Checking Bisimulation 81 SZ 81 To construct 8 start with p0 qO and check whether 52 can match all transitions of 51 5 I30 lt10 I31 ql I33 ql I32 lt12 I34 13 System 52 can simulate system 51 Now check whether 31 is a simulation or not 5391 lt10 D0 ql D1 ql D3 lt12 D2 lt13 D4 Start with qO p0 e s l 1 qO has one transition a that can be matched by two transitions of 51 target p1 and p3 respectively and we have ql pl 6 s 1 and ql p3 e s 1 2 ql has two transitions b and c which however cannot appropriately be matched by the related states p1 and p3 of system 51 p1 has only a b transition whilst p3 has only a c transition We have therefore 51 90 2 Com S 541 Some Facts on Bisimulations is an equivalence relation If S i 12is a family of strong bisimulations then the following relations are also strong bisimulations Idp slos2 PR for someo with cpoe s1 QRE s2 I Si39l Usi el Com S 541 Some Facts on Bisimulations II 81 82 PR for some Q with PQe sl QRe 82 Proof Let CPR 6 81 o 82 Then there exists a Q with PQ 6 s1 and QRe 82 9 If p L p then since PQ e slthere exists Q 39and Q Q and P Q 39 6 Si Furthermore since Q R e 82 there exists a R with R i R and Q R e 82 Due to the definition of sl 0 82 it holds that P R 6 sl 0 82 as required 9 similar to 9 Com S 541 Bisimulation Summary Bisimulation is an equivalence relation defined over a labeled transition system which respects nondeterminism The bisimulation technique can therefore be used to compare the observable behavior of interacting systems Note Strong bisimulation does not cover unobservable behavior which is present in systems that have operators to define reaction ie internal actions Com S 541 The ncalculus The ncalculus is a model of concurrent computation based upon the notion of naming The ncalculus is a calculus in which the topology of communication can evolve dynamically during evaluation In the ncalculus communication links are identi ed by names and computation is represented purely as the communication of names across links The ncalculus is an extension of the process algebra CCS following the work by Engberg and Nielsen who added mobility to CCS while preserving its algebraic properties The most popular versions of the ncalculus are the monadic ncalculus the polyadic ncalculus and the simplified polyadic ncalculus Com S 541 The ncalculus Basic Ideas The most primitive in the ncalculus is a name Names infinitely many are Xy e N they have no structure In the ncalculus we only have one other kind of entity a process We use PQ to range over processes Polyadic prefixes Input prefix x 1 input some names ylquot yn along the link named xquot output prefix 3ltlt gt output the names ylquot yn along the link named xquot Com S 541 The ncalculus i Syntax Note We only consider the simplified polyadic version po p 19 Parallel composition 1 x p Restriction XylynP Input 3ltltyl yngt Output 1P Replication inputonly o Null Com S 541 Reduction Semantics Robin Milner proposed first a reduction semantics technique Using the reduction semantics technique allows us to separate the laws which govern the neighborhood relation among processes from the rules that specify their interaction lPEP P PEP O p IQEQ p PIQREPQ IR vxm IQE vaP lox qo Q PgtRP PgtQ uxpgtuxo Xylyn P 3ltlt21zngt gt Pylynzizn Com S 541 Evolution y xu ltvgt 3K2 can evolve to ltVgt 32 or y 2lt v39gt ruxlt3ltltygt xru ltvgt 3ltlt2gt can evolve to ltvgt lt2gt 3ltltygt lxu ltvgt 3ltltzgt can evolve to Tzltvgt l1xugt ltvgt 3ltzgt or 3ltltygt l1xugt ltvgt Eltvgt and Tzltvgt lixm ltvgt Eltvgt Com S 541 Church s Encoding of Booleans The boolean values True and False are encoded as processes waiting at channel b for a pair t f that represent the corresponding continuations Similarly the function NotiS implemented a process waiting at channel b for a boolean value and sends along channel cthe negated boolean value True lb E b it ft False lo a be fTE Notloc E blc fEft VP lUClNO E lbc True icFalse lb UCbtfEftIctf i btfkf Com S 541 Actions ad 1 5caltl gt Input action a is the name at which it occurs b is the tuple of names which are received Output action a is the name at which it occurs 5 is the tuple of names which are emitted Restricted output action a is the name at which it occurs b is the tuple of names which are emitted it i denotes private names which are carried out from their current scope scope extrusion Silent action this action denotes unobservable internal communication Com S 541 INa ltPL6P ltB OUT5lt6gtLgt0 mam P39 y a yelS i QWW w p OPENP Q 516 Q COMP gt56 P39 p QLgtplQI 05056 Pl Q 516 Q Ppiswmw ping PAR p QLgtEgtIQ ComSS41 Labeled Transition Semantics O z if M Q bM me R u Xena 0XPLgt XP39 awpi gp iaxPLmP lt6iaxP Some Facts The side conditions in the transition rules ensure that names do not become accidentally be bound or captured In the rule RES the side condition prevents transitions like u xa lo P L o XPbx which would violate the static binding assumed for restriction In the given system bound names of an input are instantiated as soon as possible namely in the rule for input it is therefore an earytransition system Late instantiation is done in the rule for communication The given system implements an asynchronous variant of the ncalculus Therefore output action are not directly observable There is no rule for occonversion It is assumed that occonversion is always possible Com S 541 Experiments r1c1Notlbc TruelcFalse1b p u c M fEft let fgtEgtbltq fgtE Experiment 1 Experiment 2 wcbtfEl t cropt btfTE M v c cyxgt lee fob bltxrygt 3 L z c 3 yo 0 yo 0 Note using strong bisimulation the systems are not equivalent We have an internal action in the left system which cannot be matched by the right system Furthermore an asynchronous observer can only indirectly see that an output message has been consumed Com S 541 Bisimulation A Board Game The central idea of bisimulation is that an external observer performs experiments with both processes P and Q observing the results in turn in order to match each others process behavior stepbystep Checking the equivalence of processes this way one can think of this as a game played between two persons the unbeliever who thinks that P and Q are not equivalent and the believer who thinks that p and Q are equivalent The underlying strategy of this game is that the unbeliever is trying to perform a process transition which cannot be matched by the believer Com S 541 Synchronous Interactions There exists two kinds of experiments to check process equivalence mputexperments and outputexperments Both experiments are triggered by their corresponding opposite action In the synchronous case input actions for a process P are only generated if there exists a matching receiver that is enabled within 19 The existence of an input transition such that P evolves to P reflects precisely the fact that a message offered by the observer has actually been consumed Com S 541 Asynchronous Interactions In an synchronous system the sender of an output message does not know when the message is actually consumed In other words at the time of consumption of the message its sender is not participating in the event anymore Therefore an asynchronous observer in contrast to a synchronous one cannot directly detect the input actions of the observed process We need therefore a different notion of inputexperiment Solution Asynchronous inputexperiments are incorporated into the definition of bisimulation such that inputs of processes have to be simulated only indirectly by observing the gutput behavior of the process in context of arbitrary messages eg P ltbgt Com S 541 The Silent Action Strong bisimulation does not respect silent actions ttransitions Silent transitions denote unobservable internal communication From the observer s point of view we can only notice that the system takes more time to respond Silent actions do not denote any interacting behavior Therefore we may consider two systems P and o to be equivalent if they only differ in the number of internal communications We write P gt P if P LML L P In other words a given observable action can have an arbitrary number of preceding or following internal communications Com S 541 Asynchronous Bisimulation A binary relation 8 over processes P and Q is a weak observable bisimulation if it is symmetric and P s Q implies whenever PL where 0c is either I or output with brim lP Q then Q 39 exists such that Q ggt Q 39and P s Q P 55 S Q 55 for all messages 55 Two processes P and Q are weakly bisimular written P zQ if there is a weak bisimulation s with P s Q Com S 541 Some Facts z is an equivalence relation z is a congruence relation Leading ttransitions are significant that is they cannot be omitted Asynchronous bisimulation is the framework that enables us to state P Q if and only if p z Q and vice versa Com S 541 An Simple Object Model Re renoeCeJJ E to vsg Vlt0gt Ismrgtvltgtltvltngt fltgtgt lg 6 V6 x7ltgt lfltagtgt Com S 541 A List A list is either Nlor Consof value and a list V The constant Nil the construction Cons I L and a list of nvalues are defined as follows Ni 2 h inc ConsVL 0 ml lhlr1c 7 m1 vltvgt lLltJgtgt E71Vn ConsVlConsCons7nle Com S 541 Encoding kterms With Callbyvalue Reduction If the kterm is just a variable then we return immediately the value of this variable along channel p If the kterm is a k abstraction we first create a new channel which we can think of as the location of kxe We immediately return falong channel p and start a replicated process that represents the k abstraction If the kterm is an application we evaluate it left toright We evaluate both subexpressions before we evaluate the whole term lbi ltpgt Mer Vf f x e ltpgt lt gt q ee39 lqlre Iqfe39 rXfltXpgt p q Com S 541 Parallel Encoding of a kapplication We can evaluate an application in parallel We start the evaluation of ean e and synchronize the results with a third process eei E I ltpgt V q l Ii eltqgt I eltIgt qf rX X pgt Com S 541 Encoding kterms With Callbyname Reduction The encoding of both a variable and a k abstraction is the same as in the case of callby value reduction If the kterm is an application we start with e which denotes the function In contrast to the callbyvalue encoding we do not start the evaluation of e Instead we start a replicated process waiting on channel x and apply f to the argument x and the result channel p If factually needs the associated value of x it has to communicate with the replicated process located at x iJiltpgt pltXgt if 0 eltpgt Vfll f I Xq eltqgt ee39ltpgt V q 1 X eltqgt Iqffxpgt txce IltCgt Com S 541 A Concurrent Language V X Y Variable F 0 1 Function symbols C V E Assignment C C Sequential Composition J39fE dlen C elseC Conditional Statement wthe E do C While Statement JetD in C end Declaration C parC Parallel Composition jnputV Input outputE Output skip D varV Variable Declaration E V Variable Expression FE1 En Function Call Com S 541 Ambiguous Meaning XO XX1parXX2 What is the value of X at the end of the second statement Com S 541 Basic Elements We assume that each element of the source language is assigned a process expression Variables X dnJ39IE ruvse gtltge gtlt 7jnj1gt eet X r1rv739ltngt f llget39X rvj7lt1gt f3gt I Skip doneo C1C2 t1c Cldonec cC2 ClparC2 rUlrrtMKtme Cldone C2done1 GOtbjfb rler1rSkjpeseiltgt Elte1segt rtcojfba1en15kjpe1seiltgt Elte1segtn Com S 541 Expressions X U ack getX ack lack VESV F031quot En argl iargnxnFxi 1res M F CE En Darglp argnWI LE1resargl I M En1resargn M FD Com S 541 Operation Sequence I 0 X1parXX2 X X What is the value of X at the end of the second statement According to the former definitions the value of X is either 1 2 or 3 The three values are possible since every atomic action can occur in an arbitrary and meshed order To guarantee a specific result eg 1 or 2 we need to employ semaphors Com S 541 What Have We Learned Classical automata theory does not cope correctly with interacting behavior Bisimulation is an equivalence relation defined over a labeled transition system which respects nondeterminism and can therefore be used to compare the observable behavior of interacting systems The ncalculus is a namepassing system in which program progress is expressed by communication With the ncalculus we can model higher level programming abstractions like objects and lists A concurrent programming language can be assigned a semantics based on the ncalculus Com S 541 Introduction to Category Theory and Monads Overview Basic constructions Diagrams Functors Natural Transformations and Monads Modeling state output and nondeterminism Monad transformers References Benjamin C Pierce Basic Category Theory for Computer Scientistsquot MIT Press 1991 Andrea Asperti and Guiseppe Longo Categories Types and Structuresquot MIT Press 1991 Richard Bird Introduction to Functional Programming using Haskellquot Prentice Hall 1998 Com S 541 Categories Category theory studies objects and morphisms between them Category theory was originated in part as a technique for seeing a collection of similar results as instances of a more general theory of mathematical structures and the relationships between structures Category theory provides a very abstract framework to reason about objects and their relationships Any immediate access to the internal structure of objects is prevented all properties of objects must be specified by properties of morphisms existence of morphisms their unicity validity of some equations among them and so on This is quite similar to considering objects as abstract data types ie data specifications that are independent of any particular implementation Category theory is a tool for studying the semantics of programming languages and in many cases the categorical viewpoint matches much better with the basic motivations of computer science than the alternative foundational theories Com S 541 Definition A category C comprises A collection of objects A collection of arrows often called morphisms Two operations dom cod assigning to each arrow f two objects respectively called domain source and codomain target of f We write f A 9B or A gt B to show that dom f A and cod f B The collection of all arrows with domain A and codomain B is written C AB An operation 0quot composition assigning to each pair f g of arrows with dom f oodg an arrow f O gsuch that dom f O g dom g oodf 0 g oodf satisfying the following associative lam for any arrow fA 9 B g B 9 c and h c 9 D with A B c and D not necessarily distinct ho 9013 hogof An operation id assigning to each object b a morphism iib A 9 A the identity of b such that dom 3911 oodiib b satisfying the following identity lam for any arrow sz9 B iibo f fand f 0 11b f Com S 541 Category Set The category Set has sets as objects and total functions between sets as arrows Composition of arrows is the settheoretic function composition Identity arrows are identity functions In order to see that Setis a category we restate its definition in the categorical format and check that the laws hold An object in Setis a set An arrow f A 9 B in Setis a total function from set A into the set B For each total function fWith domain A and codomain B we have dom f A ood f B and 6 SetAB The composition of a total function f A 9 B with another total function g B 9 C is the total function from A to C mapping each element a e A to gfa e C Composition of total functions on set is associative for any functions f A 9 B ng9candhc9Dwehaveh g of hog of For each set A the identity function iiA is a total function with domain and codomain A For any function f A 9 B the identity functions on A and B satisfy the identity law iiB 0 f fand f 0 iiA f Note for a set A we have it f 0 fl Com S 541 Category Poset An object in Posetis a partiallyordered set A SA and an arrow is an order preserving total function f A SA 9 B SB such that if aSA a then fa SB fa Verification of the composition operation The composition of two orderpreserving total functions f A 9 B and g B 9 C is the total function g0 f from A to c Furthermore if aSA a it holds that fpreserves A s ordering fe SB fe39 and since g preserves B s ordering we have gfa SC gfa Therefore 9 O fis order preserving Composition of order preserving functions is associative because each order preserving function on partially ordered sets is just a function on sets and composition of functions on sets is associative Com S 541 Category FPl Types Builtin functions Constants I Int IsZero Int 9 Bool Zero Int Real Not Bool 9 Bool True Bool Bool Suchnt Int 9 Int False Bool I Unit SuccReal Int 9 Int Unit Unit ToReal Int 9 Real The corresponding category FF is built by Taking Int Real Bool and Unit to be objects Taking IsZero Not Suchnt SuccReal and ToReal to be arrows Taking the constants Zero True False and Unit to be arrows from the Unit object to Int Real Bool and Unit respectively which map the single element of Unit to the appropriate elements of these types Adding arrows for the identity functions at each type For every composable pair of arrows adding an arrow for the function formed by composing them Equating certain arrows such as False Not 0 True and IsZero 0 Zero True that represent the same functions according to the semantics of the language Com S 541 FPl Leaving out the identities and the composities the category FPL looks like this Suchnt IsZero ToReaI SuccReaI Bool 0 Zero Real False Not True Unit Com S 541 Diagrams An important tool in the practice of category theory is the use of diagrams a graphical style for representing equations Definition A diagram in a category c is a collection of vertices and directed edges consistently labeled with objects and arrows of c where consistently means that if an edge in the diagram is labeled with an arrow fand fhas domain A and codomain B then the endpoints of this edge must be labeled with A and B Definition A diagram in a category c is said to commute if for every pair of vertices X and Y all paths in the diagram from X to Y are equal in the sense that each path in the diagram determines an arrow and these arrows are equal in c Com S 541 Commuting Diagrams Saying that the diagram commutesquot is exactly the same as saying fo g go f Com S 541 Visual Proofs When a specific property is stated in terms of a commuting diagram then proofs involving that property can be given visually Example Proposition If both inner squares of the following diagram commute then so does the outer rectangle f f A gt B gt C 9 Proof 9 0 9 O a g 0 g 0 a associativity 9 O b O f commutativity of first square g 0 b O f associativity c O f O f commutativity of second square c O f 39 O f associativity End ofPIoof Com S 541 Verification of Program Transformations If a programming language is described as a category we can use commutative diagrams to assert the validity of program transformations in which the order of operations is permuted S ccmt Example FPL mt u mt ToReall l ToReal SuccReal Real gt Real Com S 541 Dual Category Definition The dual category c0p of a category C has the same objects and the same morphisms of c jdo b jdb for all PP dom f oodPP oodf dom PP and fpoopgopz 90 f Duality is a very powerful technique of category theory If P is a generic proposition expressed in the language of category theory the dual of P POP is the statement obtained by replacing the word dom by cod cod dom g 0 fl Pp Cop 90pquot If P is true in a category c then Pop is true in COP if P is true in every category then also Pop is since every category is the dual of its dual Duality may be applied to diagrams as well given a diagram in a category c the dual diagram in cop is obtained by simply inverting the arrows A dual diagram commutes however if and only if the original one does Com S 541 Category PX ancl PXDP I X 1 2 Arrows in PXare inclusions while those in PXOP are the reverse of inclusion PX 1amp3 mamv 12 13 23 1 2 3 1 2 3 12 13 23 L 1l3 The categories are shown without composites and identities Furthermore the categories are isomorphic ie they differ only in the names of the objects and arrows Com 5 541 Operator Representation in Categories Categories provide the basis for explaining a variety of familiar operators in a general way Examples The product Agtlt B of sets A and B is the set of ordered pairs ab where ae A and be B In particular there are projections EBA x B 9 A and sndzA x B 9 B which map a pair ab to the first and second component a and b respectively Moreover a pair is uniqueydetermined by its projections in the sense that for any xe A x B we have x fstX end gt0 The idea of a product of structure is even more general The product of posets A SA and B SB is the set product A x B of the underlying sets A and B with an ordering SAXB given by 1bSAx B a b iff aSA a and b SB b The projections are defined as they are for sets We can use categories as a language for expressing the essential common structures of operators However in a categorytheoretic definition everything must be de ned in terms of the morphisms arrows of the category Com S 541 Product Definition A product of two objects A and B is an object A x B together with two projection arrows in A x B 9 A and n2 A x B 9 B such that for any object c and pair of arrows f c 9 A and g c 9 B there is exactly one mediating arrow fg c 9 Agtlt B making the diagram commute ie nlo fg fand n20 fg g Dashed arrows are used to represent arrows that are asserted to exist when the rest of the diagram is filled in appropriately Com S 541 Product in PX Each pair of objects in the category PX has a product Consider subsets 12 and 123 of x Then their product is 12 f i g iltfggt i 12 lt n 12 m 123 ngt 123 The product of two objects A and B in PX is their intersections the greatest lower bound of the two objects infimum The product in Setis A x B Note Not all categories have a product Com S 541 Product in PXDP Each pair of objects in the category PXOP has a product Consider subsets 12 and 123 of X Then their product is 123 f i g iltfggt i 12 4 7 l2u 123 ngt 123 The product of two objects A and B in PXOP is their union the least upper bound of the two objects supremum Com S 541 Coproduct The dual notion of product coproduct corresponds to the settheoretic disjoint union Definition A coproduct of two objects A and B is an object A B together with two injection arrows 11 A 9 A B and 12 B 9 A B such that for any object c and pair of arrows fA 9 c and g B 9 c there is exactly one arrow ng A B 9 c making the following diagram commute L L A 1gtABlt2 B g 9 C Com S 541 Coproduct in PX Each pair of objects in the category PX has a coproduct sum Consider subsets 12 and 123 of X Then their coproduct is 12 A 12 u 23 lt 2 23 f8 123 The coproduct of two objects A and B in PXis their union the least upper bound of the two objects supremum The coproduct in Setis the disjoint union of A and B Com S 541 Coproduct in PXDP Each pair of objects in the category PX P has a coproduct sum Consider subsets 12 and 123 of X Then their coproduct is 12 4 min 123 123 f8 12 The coproduct of two objects A and B in PXOP is their intersections the greatest lower bound of the two objects infimum Com S 541 Initial and Terminal Objects An object o in category C is called initial object if for every object A in C there is exactly one arrow 0 9 A I Q jsthe jrlitialobjectjn PX 123 jsthe jrlitialobjectjn PXOP An object 1 in category C is called terminal object if for every object A in C there is exactly one arrow A 9 1 Q jsthetem jrlalobjectjn PXOP 123js d1etennjrlalobjectjr1PX Com S 541 Category P1 I id1 9 19 f Q lt3 c Q is the initial object o 1 is the terminal object P1 has a product P1 has a coproduct Com S 541 Higherorder Functions In some categories the collection of arrows from an object A to an object B can be reflected as itself an object BA of the category For example in Setthe functions from a set A to a set B is itself a set BA f sz 9 B The categorical characterization of the product is identified by finding the basic operations for products pairing and projections and their equational properties What are the analogous basic operations for functions One of these is application For example given a function sz 9 B and an element a e A there is a binary operation between fand aWhiCh has as its value the result in B of applying a to compare with domain Store The other is curring Com S 541 Exponen a on Definition Let C be a category with product gtlt An exponent of two objects A and B is an object BA and an arrow appr such that for any object c and arrow f c gtltA 9 B there is a unique arrow curryf C 9 BA making the diagram B appk X A CgtltA gtBAgtltA commute ie unique cumf such that appyo cums1f gtlt jo39iA f Com S 541 Functors Definition Let Cand D be categories A functor F C9 D is a map taking each C object A to a Dobject F A and each C arrow sz 9 B to a Darrow F f F A 9 F B such that for all C objects A and composable C arrows fand g l FJ39dAJ39dFAgt 2Fo FoF B FCB V w gof Fgof A C FA gtFC mammwc mamme Com S 541 Functor fmap class Functor f where fmap a gt b gtfagtfb instance Functor Tree where fmap f Leaf X Leaf f X fmap f Branch r Branch fmap f I fmap f r Com S 541 Natural Transformation Definition Let Cand Dbe categories and F and G be functors from Cto D A natural transformation T from F to G written I F G is a function that assigns to every C object A to a Darrow TA F A 9 G A such that for any C arrow sz 9 B the following commutes in D FCB GB Com S 541 Sliding Between Categories m o gtGCB FC Tc G V 5 G C Com S 541 Natural Transformation reverse reverse a gt a reverse reverse XXs reverse xs X reverse 12345 5I4I3I2I1 Com S 541 Natural Transformation Diagrams A common pictorial representation of a natural transformation is a diagram of the form c Gin which can be read as the two functors F G C 9 D with the natural transformation quotC that provides a translation between the two Com S 541 Composing Natural Transformations Natural transformations can be composed either vertically or horizontally Given two natural transformations 1 and o the diagram below shows a vertical composition Com S 541 Functor Category For every object A in the category A the functors FG H A 9 B and the natural transformations 5 and o the following commuting diagram in the category B can be drawn cock GA TA l A Fe gtGA HA f Fi Go Ho 6 C B FCB B GB B HCB l 50513 T CategoryA CategoryB The commuting diagram on the right can be used as the basis for a new category F that has functors as objects and natural transformations as its morphisms the functor C6139E39g0 MC0m S 541 Horizontal Composition The horizontal composition of two natural transformations 1 and 5 can be expressed by the following diagram F H gt gt Com S 541 From Category A to Category C For an object A in the category A the functors FG A 9 B functors H K B 9 C and the natural transformations 5 and o the following commuting diagram in the category C can be drawn HFALHG A 6FA 5G A KF A gt KG A K CA Com S 541 Monads The Idea The underlying idea of monads in computer science is the distinction between simple datavalued functions and functions that perform computations A datavalued function is one in which the returned value is solely determined by the values of its arguments no sideeffects A function that performs a computation can encompass ideas such as state or nondeterminism Moreover as a consequence of its application a function that performs a computation produce implicitly more results than the explicitly returned value Com S 541 Monads in Category Theory Definition A monad over a category Cis a triple T n u where T is the endofunctor T c 9 c a function with a mapping to and from the same category and n and u are two natural transformations The natural transformations of the monad are defined as n jdc 9 T and u T2 9 T T2 TT T O T the composition of functor T idc T2 c T in C C T l C Com S 541 Monads A Model for Computation The endofunctor T is a mapping between all objects of the category C ObjC which can be viewed as the set of all values of type t to a corresponding set of objects T ObjC which are interpreted as the set of computations of type t The natural transformation 11 can be thought of as an operator that includes values into computations The natural transformation u flattens a computation of computations into a single computation Com S 541 Monad Laws In order the call the triple formed by T n and u a monad the assoaatve law of a monaa and the left and right Identity laws must hold THA LL HM A iiTe A iiTe T A T2A gtTA HA leomoTEMOIoM lvLoIonEdAEMonoI Com S 541 State Transformer Computations with side effects may be described by the functor T A A X S5 where A x S5 f lfzS 9 A x 8 an exponential object that represents all morphisms from s a set of states to a pair A x S the product of an object A and a updated set of states A computation takes a state and returns a value together with the modified state Then a monad is obtained by setting for each type or object A 1 a ksas and Lu f AsapphE For every fe A x SS uA f is the computation that given a state s first computes the pair computationstate given by f gtlt s39 S then evaluates f applied to 9 apply and returns a new pair valuestate 1 a maps a into a computation Com S 541 The Kleiin Category In the application of monads the idea is to go from objects or types to the image by a functor of an object More precisely programs take values in A to computations in T B Definition Given a monad T n p over category C the Kleisli category CT is the category whose objects are those of C the set C7AB of morphisms from A to B in Cris CAT 8 the identity C7AA is n A 9 T A Moreover the composition of fe C7AB and g e CTCBC in Cris g fpC Tg f Ae TCB9 T2c 9 TC The expression LLC Tg fis interpreted as applying fto some value a to produce some computation fa this computation is evaluated to produce some value b and g is applied to b to produce a computation as a result Com S 541 The Kleiin Triple Definition The Kleisli triple TObj n can be constructed from a monad T n u where T0 is the restriction of the b endofunctor T to object and and for any function f A 9 T A we have fk TA 9 TBEuB O Tf Kleisli triples can be thought of as a different syntactic presentation of a monad as there is a onetoone correspondence between Kleisli triple and a monad Egt Saunders Mac Lane Categories for working mathematician SpringerVerlag 1971 page 143 Com S 541 Monads in Functional Programming Philip Wadler adapted the ideas of using monads to structure the semantics of computations into a tool for structuring functional programs Given a monad T n u the functor T and the two natural transformations are modeled in a functional programming language by a type constructor a function map parameterized on the type constructor and two polymorphic functions Example State Monad type S a State gt a State functor T to map objects mapS a gt b gt Sa gt S b unitS a gt S a joinS S S a gt S a functor T to map morphisms 39 ll ll Com S 541 Monad Laws map id id map fog mapf0mapg map f 0 unit unit 0 f map f O join join 0 map map f join 0 unit id join 0 map unit id join 0 map join join 0 join Com S 541 Monad Laws Illustrated TA A map id id map id 3 id 3 map f 0 g map f 0 map 9 map a gt a 1 ord A 66 map a gt a 1 map ord A map a gt a 1 65 66 map f 0 unit unit 0 f map chr unit 65 map chr 65 A unit chr 65 unit A A join 0 unit id join unit 3 join 3 3 id 3 join 0 map unit id join map unit 3 join 3 3 id 3 join 0 mapjoin join ojoin join map join 3 join 3 3 join join 3 join 3 3 Com S 541 How People Really Use Monads In more recent developments the current use of monads bears a closer resemblance to Kleisli triples The triple Tunitbjnd forms a monad when the following laws hold m bind unit m unit a bind f fa m bind f bind g m bind f bind g The elements of the triple have to be read as T is a type constructor that maps a value into a computation unjtiS the inclusion function Le 11 and bind is a composition operator which applied to some fand g denotes the same expression as uc Tg fin the Kleisli category Com S 541 Type Class Monad class Monad m where return a gt m a unit gtgt magt a gtmb gtmb bind gtgt m a gt m b gt m b bind ignore left fail String gt m a Minimal complete definition gtgt return I3gtgtCl 3gtgt39gtCl fail s error 5 Com S 541 Instance Declaration for State Monad data StateMonad a SM State gt aState instance Monad StateMonad where define state propagation SM m1 gtgt fm2 SM sO gt let rsl ml 50 SM m2 fm2 r in m2 51 return a SM sO gt asO extract state from the monad readSM StateMonad State readSM SM s gt ss update the state of the monad updateSM State gt State gt StateMonad updateSM f SM s gt 0 f s run a compuation in the SM monad runSM State gt StateMonad a gt aState runSM 50 SM C c 50 Com S 541 Monads Enhance Modularity Pure functional languages offer the power of lazy evaluation and the simplicity of equational reasoning Impure functional languages offer features like state exception handling or continuations Pure languages ease the change of programs since operations do not have sideeffects But a small change may require a program in a pure language to be extensively restructured when the use of an impure feature may obtain the same effect be merely altering a few lines of code Monads enhance modularity In order to change a program one has to redefine the monad and make a few local changes Com S 541 A Monadic Interpreter Abstract Syntax Statement Name Term Statement Term Statement Term Name Number Term Term function Name Term Term Term Term Com S 541 A Monadic Interpreter Data Structures data Term Variable Name Constant Int Add Term Term Function Name Term Application Term Term Braced Term data Value Wrong Num Int Fun Value gt M Value type Environment Name Value Com S 541 The Identity Monad data M a I a functor T instance Monad M where Ivgtgt fmfmv bindn return v Iv unit 1 showM Show a gt M a gt String showM I v show v Com S 541 Auxiliary Definitions instance Show Value where show Wrong quotltwronggtquot show Num i show i show Fun f quotltfunctiongtquot lookupName Name gt Environment gt M Value lookupName return Wrong lookupName n nxvxxs n nx return vx otherwise lookupName n xs Com S 541 The Term Interpreter interpreter Term gt Environment gt M Value interpreter Variable n e lookupName n e interpreter Constant i e return Num i interpreter Add t1 t2 e interpreter t1 e gtgt v1 gt interpreter t2 e gtgt v2 gt addition v1 v2 where addition Num i1 Num i2 return Num i1i2 addition return Wrong interpreter Function n t e return Fun a gt interpreter t nae interpreter Application t1 t2 e interpreter t1 e gtgt f gt interpreter t2 e gtgt a gt apply fa where apply Fun f a fa apply return Wrong interpreter Braced t e interpreter t e showM interpreter Add Variable quotnquot Constant 3 quotnquotNum 4 7quot Com S 541 The Interpreter Loop data Statements S Statement Statements Nil data Statement Assign Name Term Eval Term interpLoop Statements gt Environment gt M Value gt M Value interpLoop Nil e v v interpLoop S s ss e v let v39e39 evalStatement s e v in interpLoop ss e39 v39 evalStatement Statement gt Environment gt M Value gt M Value Environment evalStatement Assign n t e v let I v interpreter t e in I vnve evalStatement Eval t e v interpreter t e e val S Assign quotdquot Function quotfquot Add Variable quotfquotConstant 3 S Eval Application Variable quotdquot Constant 4 Nil showM interpLoop val return Wrong 7quot Com S 541 Error Messages To add error messages to the interpreter we can define the following monad data M a Success a Error String instance Monad M where Success v gtgt fm fm v Error 5 gtgt fm Error 5 return v Success v returnError String gt M a returnError s Error 5 showM Show a gt M a gt String showM Success v quotSuccess quot show v showM Error 5 quotError quot 5 Com S 541 Towards the Error Monad Necessary chances lookupName n returnError quotundefined name quot n addition a b returnError quotshould be numbers quot show a quot quot show b apply f returnError quotshould be a function quot show f evaIStatement Assign n t e v evaITerm interpreter t e n e where evaITerm Success v n e Success v nve evaITerm Error 5 e Error 5 e Com S 541 The State Monad type State Int data M a SM State gt aState instance Monad M where SM sm gtgt fm SM sO gt let v1sl sm 50 SM sm2 fm v1 in sm2 sl return v SM sO gt vsO tickS M tickS SM s gt s 1 showM Show a gt M a gt String showM SM m let v s m 0 in quotValue quot show v quot quot quotCount quot show 5 Com S 541 Towards Application Count To add a function application count we have to chance 2 additional lines in the original interpreter code addition Num i1 Num i2 tickS gtgt return Num i1i2 apply Fun f a tickS gtgt fa val S Assign quotdquot Function quotfquot Add Variable quotfquotConstant 3 S Eval Application Variable quotdquot Constant 4 Nil showM interpLoop val return Wrong Value 7 Count 1 Com S 541 The DO Syntax The do syntax provides a simple shorthand for chains of monadic operations do e1 e2 e1 gtgt e2 doplt e1 e2 e1 gtgt pgt e2 The second form of do is refutable pattern matching can fail In this case the fail operation is called complete translation doplt e stmts letokp d0stmts ok fail in e gtgt ok The new application count definitions addition Num i1 Num i2 do tickS return Num i1i2 apply Fun f a do tickS fa Com S 541 Type Systems Overview What is a Type Static vs Dynamic Typing Kinds of Typing Polymorphic types Overloading User Data Types References Richard Bird Introduction to Functional Programming using Haskellquot Prentice Hall 1998 David Watt Programming Language Concepts and Paradigms Prentice Hall 1990 Luca Cardelli and Peter Wegner On Understanding Types Data Abstractions and Polymorphismquot ACM Computing Survey 174 Dec 1985 pp 471522 Com S 541 What Is a Type Type errors 5 ERROR Illegal Haskell 98 class constraint in inferred type Expression 5 Type Num a gt a A type is a set of values Int 2 10 1 2 Bool True False Point X0 y0 x1 y0 x0 y1 A type is a partial specification of behavior nm mt nm is valid but notCn is an error n mt n 1 is valid but n heilowor39ld is an error Com S 541 Static and Dynamic Typing Values have static types defined by the programming language Variables and expressions have dynamic types determined by the values they assume at run time A language is statically typea if it is always possible to determine the static type of an expression based on the program text alone A language is strongly typed if it is possible to ensure that every expression is type consistent based on the program text alone A language is dynamically typed if only values have fixed type Variables and parameters may take on different types at runtime and must be checked immediately before they are used Type consistency may be assured by i compiletime typechecking ii type inference or iii dynamic typechecking Com S 541 Kinds of Types All programming languages provide some set of builtin types Most strongly typed modern languages provide for additional userdefined types Primitive types booleans integers oats chars Composite types functions lists tuples Userdefined types enumerations recursive types generic types The Type Completeness Principle Watt No operation should be arbitrarily restricted in the types of values involved Firstclass values can be evaluated passed as arguments and used as components of composite values Functional languages attempt to make no class distinctions whereas imperative languages typically treat functions at best as secondclass values Com S 541 Types in Haskell Luca Cardelli Haskell is a typefu language All Haskell values are firstclass They may be passed as arguments to functions returned as results placed in data structures etc Haskell typeson the other hand are notfirst class Types describe values and the association of a value with its type is called typing Haskell s type system is different and somewhat richer than the most An adjustment to the power and complexity of Haskell s type system may be very difficult for those having only experience with relatively untypeful languages like Perl Tcl or Scheme It will be easier for those which are familiar with Java C Modula or ML Com S 541 Function Types Functions types allow one to deduce the types of expressions without the need to evaluate them fac Int gt Int 42 Int fac 42 Int Curried types a gt a gt gt a a1gt a2 gt gt an 1 2 n and fX1 X2 Xn E f X1 X2 Xn SO Int gt Int gt Int 5 Int gt Int This example also demonstrates the first class nature of functions partical application of a curried function which when used in this way are usually called hI39gIerora erfunctions See also Higherorder Functions Com S 541 List and Tuple Types List types A list of values of type a has the type a 1 Int Note All elements in a list must have the same type a 2 False this is illegal It cannot be typed Tuple types If the expressions x1 x2 xn have types a1 a2 an respectively then the tuple x1 x2 xn has type a1 a2 an 1 2 3 Int Int Int a False Char 800 12 34 IntInt Int Int The unit type is written and has a single element which is also written as 0 Com S 541 Polymorphism Languages like Pascal have monomorphic type systems every constant variable parameter and function result has a unique type Such languages hinders however the definition of generic abstraction if possible at all Haskell incorporates p0ym0rp7ctypes In fact these types are universally quantified Polymorphic type expressions describe families of types For example V a a is the family of types consisting of for every type a the type of lists of a Haskell has only universally quantified types Therefore one does not need to write out the symbol for universal quantification All type variables are implicitly universally quantified See also Polymorphic Typesquot Com S 541 Composing Polymorphic Types We can deduce the types of expressions using polymorphic functions by simply binding type variables to concrete types Consider length a gt Int map a gt b gt a gt b Then map length a gt Int Hello World Char String Char map length Hello World Int Com S 541 Polymorphic Type Inference map map map map The polymorphic type inference yields the function s principle type which is the least general type that intuitively contains all instances of the expressionquot The existence of unique principle types is a feature of all HhdeyMlner type systems The Hindley Milner type inference provides an effective algorithm for automatically determining the types of polymorphic functions The corresponding type system is used in many modern functional languages including ML and Haskell Com S 541 Userdefined Types New data types can be introduced by specifying i optionally a context ii a datatype name iii a set of parameter types and iv a set of constructors for elements of the type data Context gt DatatypeName a1 an Constructorl Constructorm An important predefined type in Haskell is that of truth values data Bool False True The type Bool has exactly two values True and False Type Bool is an example of a nullary type constructor and True and False are also nullary data constructors Com S 541 Examples of Userdefined Data Types Enumeration types data Day Sun Mon Tue Wed Thu Fri Sat whatShallIDo Sun relax whatShallIDo Sat go shoppingquot whatShallIDo looks like I ll have to go to workquot Union types data Temp Centigrade Float Fahrenheit Float freezing Temp gt Bool freezing Centigrade temp temp lt 00 freezing Fahrenheit temp temp lt 320 Com S 541 Polymorphic Userdefined Data Types An example of a polymorphic userdefined data type is Point data Point a Pt a a Because of the single constructor the type Point is also called a tuple type since it is essentially just a cartesian product of other types tuples are like records in other languages In contrast multiconstructor types such as Bool and Day are called disjoint union or sum type More importantly Point is a polymorphic type for any type 1 it defines the type of the cartesian points that use tas the coordinate type Furthermore the type of the binary data constructor Pt is a gt a gt Point a and thus the following typings are valid Pt 20 30 Point Float Pt a b Point Char Pt True False Point Bool Com S 541 Recursive Data Types Types can also be recursive as in the type of binary trees data Tree a Leaf a Branch Tree a Tree a Here we have defined a polymorphic binary tree whose elements are either leaf nodes containing a value of type a or internal branches containing recursively two subtrees When reading data declarations such as this remember again that Tree is a type constructor whereas Leaf and Branch are data constructors which have the following types Leaf a gt Tree a Branch Tree a gt Tree a gt Tree a Examples countLeaves Tree a gt Int leaves Tree a gt a countleaves Leaf 1 leaves Leaf x x countLeaves Branch r leaves Branch l r countLeaves l countLeaves r leaves I leaves r Com S 541 Kinds of Polymophism POJym onph39sm Universal Param eUCbpoJym onphi m ap mctbn J391 Haskell n poi39ltertype in Pascal mchsbn subtypi39lg graphi objects Ad H 00 O vefoadi39lg app39es 113 both htegeIs and fbat39ng poi39ltnum beIs Coercbn htegervalles can be used where fbat39ng poi39ltnum beIs are expected and vie veIsa l C oercbn orove badilg how does one d39Bthgu39Bh 4 wwww 39o39o ugt rbbpb Com S 541 Overloading The overloaded behavior of operators is different for each type In fact sometimes the behavior is undefined or error On the other hand parametric polymorphism the type truly does not matter For example the function countLeaves really does not care what kind of elements are found in the leaves of the tree In Haskell type Classes and mstance declara on provide a structured way to to control ad hoc polymorphism or overloading Com S 541 Type Class Eq Overloaded operators are introduced by means of type classes class Eq a where a gt a gt Bool xy notX y The class Eq defines two operations one for equality the other for inequality It also demonstrates the use of a default method in this case for the operation inequality If a method for a particular operation is omitted in an instance declaration then the default method of the class if it exists is used instead Com S 541 Instances of Eq For each overloaded instance a separate definition must be given instance Eq Int where x y x primEqInt y instance Eq Bool where True True True False False True False instance Eq a gt Eq Tree a where Leaf a Leaf b a Branch l1 r1 Branch l2 r2 II False II E v 20 S20 A 1 H N v Com S 541 Class Extension We may wish to define a class Ord which inherits all of the operations of Eq but in addition has a set of comparison operations and minimum and maximum functions class Eq a gt Ord a where lt lt gt gt a gt a gt Bool min max a gt a gt a This class declaration uses a context Eq a which states that Eq is a superclass of 0rd conversely Ord is a subclass of Eqand any type which is an instance of 0rd must also be an instance of Eq As an example of the use of 0rd consider the principle type of the function quicksort quicksort Ord a gt a gt a In other words quicksort only operates on lists of values of ordered types Com S 541 Higherorder Types The type constructor Tree has always been paired with an argument as in Tree mtthe tree containing integer values or Treea representing the family of trees containing a values But Tree by itself is a type constructor and as such takes a type as an argument and returns a type as a result There are no values in Haskell that have this type but such higherorder types can be used in class declarations class Functor f where fmap a gt bgtfagtfb Com S 541 The Function fmap The function fmap is a generalization of map and the type variable fis applied to other types in f a and f b An instance of Functor for type Tree would be instance Functor Tree where fmap f Leaf X Leaf f X fmap f Branch r Branch fmap fl fmap f r This instance declaration declares that Tree rather than Tree a is an instance of Functor The function nap can work uniformly over arbitrary data types Category theory A functor is a structurepreserving map between categories both objects and arrows are mapped Com S 541 Kinds The type system detects typing errors in expressions But what about errors due to malformed type expressions The expression 1 2 3 results in a type error since takes only two arguments Similarly the type Tree Int Int should produce the same kind of error The solution is a second type system which ensures the correctness of types Each type has an associated kind which ensures that the type is used correctly The expressions are classified into different lands which can take two possible forms The symbol represents the kind of type associated with concrete data objects That is if the value vhas type 1 the kind of vmust be If kl and k2 are kinds then kl 9 k2 is the kind of types that take a type of kind kl and return a type of kind k2 Com S 541 A Different Perspective OOP A general statement about OOP simply substituting type Class for Class and type for object yields a valid summary of Haskell s type class mechanism Classes capture common sets of operations A particular object may be an instance of a Class and will have a method corresponding to each operation Classes may be arranged hierarchically forming notions of superCasses and subclasses and permitting inheritance of operationsmethods A default method may also be associated with an operationquot In contrast to GOP types are not objects and in particular there is no notion of an object s or type s internal state Methods in Haskell are completely type safe Furthermore methods are not looked up at runtime but are simply passed as higherorder functions Com S 541 Comparison to Other Languages The classes used by Haskell are similar to those used in other object oriented languages like C and Java There are however some significant differences Haskell separates the definition of a type from the definition of the methods associated with that type The class methods defined by a Haskell class correspond to virtual functions in a C class Each instance of a class provides its own definition for each method class defaults correspond to default definitions for a virtual function in the base class Haskell classes are roughly similar to Java interfaces Like an interface declaration a Haskell class declaration defines a protocol for using an object rather than de ning an object itself Haskell does not support the C overloading style in which functions with different types share a common name The type of a Haskell object cannot be implicitly coerced there is no universal base class such as Object which values can be projected into or out of There is no access control eg public or private Instead the module system must be used to hide or reveal components of a class Com S 541


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.