MATHEMATICAL BACKGROUND This supplementary chapter(present on the CD-ROM version of the book only)describes some of the mathematical concepts behind the graphical techniques introduced in chapter 32 of Object-Oriented Software Construction,second edition.It is extracted from the ISE manual on EiffelBuild [M 1995e]. The conventions,and any cross-reference that you may encounter in this chapter, are those of [M 1995e]rather than the rest of Object-Oriented Software Construction. Pages are numbered 1076.1,1076.2 and so on to avoid any confusion with the page numbers of the rest of the book,as they appear in the printed version
MATHEMATICAL BACKGROUND This supplementary chapter (present on the CD-ROM version of the book only) describes some of the mathematical concepts behind the graphical techniques introduced in chapter 32 of Object-Oriented Software Construction, second edition. It is extracted from the ISE manual on EiffelBuild [M 1995e]. The conventions, and any cross-reference that you may encounter in this chapter, are those of [M 1995e] rather than the rest of Object-Oriented Software Construction. Pages are numbered 1076.1, 1076.2 and so on to avoid any confusion with the page numbers of the rest of the book, as they appear in the printed version
32A Mathematical background 32A.1 OVERVIEW EiffelBuild relies on simple properties of functions.This chapter presents a summary of the necessary notions. You can use EiffelBuild without having read this discussion,and in fact if you are eager to get your hands on EiffelBuild you may prefer to skip this chapter on first reading and move immediately to the following chapter and the Guided Tour.But an understanding of the elementary mathematical notions discussed below will help you get the most out of EiffelBuild,especially for advanced uses. "Introduction to the Theory Many of the topics of this chapter are also useful for the formal study of of Programming programming languages,and are covered in more details in the book Introduction to the Languages",Prentice Hall. 1991.ISBN013.4985109 Theory of Programming Languages 0-13498502-8pbk. 32A.2 FINITE SETS,CARTESIAN PRODUCT A finite set may be given by the list of its members in braces,for example PERSONHelene,Kiyoko,Laura,Roberto,Helmut) COUNTRY Japan,France,Italy,UK where A means "is defined as". A note about naming conventions:the example sets used in this chapter,such as PERSON and COUNTRY,follow the Eiffel rules for types(classes):they are written in upper-case letters,and use the singular rather than the plural.So PERSON denotes a set of persons and COUNTRY a set of countries.A mathematical text might call these sets PEOPLE and COUNTR/ES,but for a programmer it is more attractive to think of declarations of the form Helene:PERSON --(Eiffel syntax) meaning"Helene represents an object of type PERSON",hence the singular. If X and Y are sets,then Xx Y,called the cartesian product of these sets,is the set of all pairs of the form where x is a member of X and y is a member of Y.For example the set PERSON x COUNTRY contains all the pairs such as , ,...,,and so on. Cartesian product is also applicable to infinite sets.For example if N is the set of natural (non-negative)integers,then N x N is the set of all possible pairs of natural integers
32A Mathematical background 32A.1 OVERVIEW EiffelBuild relies on simple properties of functions. This chapter presents a summary of the necessary notions. You can use EiffelBuild without having read this discussion, and in fact if you are eager to get your hands on EiffelBuild you may prefer to skip this chapter on first reading and move immediately to the following chapter and the Guided Tour. But an understanding of the elementary mathematical notions discussed below will help you get the most out of EiffelBuild, especially for advanced uses. Many of the topics of this chapter are also useful for the formal study of programming languages, and are covered in more details in the book Introduction to the Theory of Programming Languages. 32A.2 FINITE SETS, CARTESIAN PRODUCT A finite set may be given by the list of its members in braces, for example PERSON {Hélène, Kiyoko, Laura, Roberto, Helmut} COUNTRY {Japan, France, Italy, UK} where means “is defined as”. A note about naming conventions: the example sets used in this chapter, such as PERSON and COUNTRY, follow the Eiffel rules for types (classes): they are written in upper-case letters, and use the singular rather than the plural. So PERSON denotes a set of persons and COUNTRY a set of countries. A mathematical text might call these sets PEOPLE and COUNTRIES, but for a programmer it is more attractive to think of declarations of the form Hélène: PERSON -- (Eiffel syntax) meaning “Hélène represents an object of type PERSON”, hence the singular. If X and Y are sets, then X × Y, called the cartesian product of these sets, is the set of all pairs of the form where x is a member of X and y is a member of Y. For example the set PERSON × COUNTRY contains all the pairs such as , , ..., , and so on. Cartesian product is also applicable to infinite sets. For example if N is the set of natural (non-negative) integers, then N × N is the set of all possible pairs of natural integers. “Introduction to the Theory of Programming Languages”, Prentice Hall, 1991, ISBN 0-13-498510-9 (0-13-498502-8 pbk). = ∆ = ∆ = ∆
1076.5 THE CONCEPTS $32A.3 32A.3 RELATIONS Let X and Y be two sets.A relation with source set Y and target set Y is a set of pairs of the form such that,in every such pair,x is a member of X and y is a member of y. In other words,a relation is one particular subset of the cartesian product Xx Y. For example.the set of pairs citizenship (,,, , is a relation with PERSON as source set and COUNTRY as target set.This relation could represent the intuitive notion"x is acitizen of y".Note that Helene would then be a person with dual citizenship.As indicated,this relation will be called citizenship. This example is a finite relation.We can also have infinite relations;for example with the set of natural integers N serving both as source set and target set,we can define the infinite set of pairs neighbors A {, ,, ,, ,∈N×Nly=x+Iory=x-I} and representing the relation whose pairs all contain elements that differ from each other by either +1 or-1.This relation,as indicated,will be called neighbors. The set of all possible relations between two sets X and Y is written >Y.For example the relation citizenship is a member of the set PERSON>COUNTRY;and the relation neighbors is a member of NN.The precise definition of Y is that it is the set P (x Y),using the notation P(4),for any set A,to mean the powerset of 4,that is to say,the set of all possible subsets of 4. The domain of a relation is the set consisting of all elements x such that the relation contains a pair of the form for some y-that is to say,a pair with x as its first element.The domain is a subset of the source set.In the case of relation citizenship,the source set is {Helene,Kiyoko,Laura,Roberto;it does not contain Helmut,even though this element has been listed as a member of the source set PERSON,because no pair in citizenship has it as its first element.(The relation does not give any information about the citizenship of Helmut. The range of a relation is the inverse notion:the set consisting of all members of the target set that appear as second element of at least one pair in the relation. A relation is total if its domain covers its entire source set-that is to say,if for every member x ofits source set there is at least one pair of the form (for some y) in the relation.It is partial otherwise.If we say "relation"without further qualification
1076.5 THE CONCEPTS §32A.3 32A.3 RELATIONS Let X and Y be two sets. A relation with source set X and target set Y is a set of pairs of the form such that, in every such pair, x is a member of X and y is a member of Y. In other words, a relation is one particular subset of the cartesian product X × Y. For example. the set of pairs citizenship {, , , , } is a relation with PERSON as source set and COUNTRY as target set. This relation could represent the intuitive notion “x is a citizen of y”. Note that Hélène would then be a person with dual citizenship. As indicated, this relation will be called citizenship. This example is a finite relation. We can also have infinite relations; for example with the set of natural integers N serving both as source set and target set, we can define the infinite set of pairs neighbors {, , , , , , , ...} denoted more precisely and concisely (with the bar | used to mean “such that”) as { ∈ N × N | y = x + 1 or y = x – 1} and representing the relation whose pairs all contain elements that differ from each other by either +1 or –1. This relation, as indicated, will be called neighbors. The set of all possible relations between two sets X and Y is written X ↔ Y. For example the relation citizenship is a member of the set PERSON ↔ COUNTRY; and the relation neighbors is a member of N ↔ N. The precise definition of X ↔ Y is that it is the set P (X × Y), using the notation P (A), for any set A, to mean the powerset of A, that is to say, the set of all possible subsets of A. The domain of a relation is the set consisting of all elements x such that the relation contains a pair of the form for some y — that is to say, a pair with x as its first element. The domain is a subset of the source set. In the case of relation citizenship, the source set is {Hélène, Kiyoko, Laura, Roberto}; it does not contain Helmut, even though this element has been listed as a member of the source set PERSON, because no pair in citizenship has it as its first element. (The relation does not give any information about the citizenship of Helmut.) The range of a relation is the inverse notion: the set consisting of all members of the target set that appear as second element of at least one pair in the relation. A relation is total if its domain covers its entire source set — that is to say, if for every member x of its source set there is at least one pair of the form (for some y) in the relation. It is partial otherwise. If we say “relation” without further qualification = ∆ = ∆
$32A.4 FUNCTIONS 1076.6 the relation may be partial or total.Relation neighbors is total,but relation citizenship is not because Helmut,a member of its source set,is not in the relation's domain. Note that the notion of relation used here is limited to binary relations,that is to say relations between two sets(the source and the target).If necessary,we can model a more general notion of relations involving any number of sets by using this notion:for example we can capture relations between three sets X,Y and Z by taking relations in X←(Y←Z).This idea will further be applied below to“currying”. 32A.4 FUNCTIONS A function is a relation as just defined,with the extra property that for any x in the source set X,there is at most one pair of the form for some y-that is to say,at most one pair with x as its first element-in the relation. The relations used above as examples are not functions.In the case of citizenship, there are two pairs with Helene as their first element.In the case of neighbors,for each number n except 0,there are two pairs with n as their first element:the pair and the pair . If we prohibit dual citizenship,that is to say if we remove one of the pairs for Helene,then citizenship becomes a function. The set of pairs for all possible natural integers n,is a function.Let us call it next.(This is a subset of relation neighbors.) Like a relation,a function may be partial or total.As with relations,the word "function"without further qualification means a function that may be total or partial. Putting together the definitions of“function”and“total relation”we see that with a total function there is,for every member x of its source set,exactly one y in the target set such that is in the function. More generally,if f is a function and x is a member of its domain,there is exactly one y such that is in the function.This legitimates the usual notation for expressing the value of that y: f(x) For example,next(6)has the value 7;and,once we have made citizenship a function by removing one of the two pairs for Helene,citizenship(Kiyoko)has the value Japan. Remember,however,that the notation f(x)has a taboo associated with it:unless the function is known to be total,the notation is meaningless without a guarantee that x belongs to the domain off. The set of all possible functions with source set X and target set y is written >Y.Since every function is a relation,>Y is a subset of Y. The bar across the arrow in the symbol reminds us that the functions may be partial.The set of total functions from X to Y,a subset of>Y,is written>y without a bar
§32A.4 FUNCTIONS 1076.6 the relation may be partial or total. Relation neighbors is total, but relation citizenship is not because Helmut, a member of its source set, is not in the relation’s domain. Note that the notion of relation used here is limited to binary relations, that is to say relations between two sets (the source and the target). If necessary, we can model a more general notion of relations involving any number of sets by using this notion: for example we can capture relations between three sets X, Y and Z by taking relations in X ↔ (Y ↔ Z). This idea will further be applied below to “currying”. 32A.4 FUNCTIONS A function is a relation as just defined, with the extra property that for any x in the source set X, there is at most one pair of the form for some y — that is to say, at most one pair with x as its first element — in the relation. The relations used above as examples are not functions. In the case of citizenship, there are two pairs with Hélène as their first element. In the case of neighbors, for each number n except 0, there are two pairs with n as their first element: the pair and the pair . If we prohibit dual citizenship, that is to say if we remove one of the pairs for Hélène, then citizenship becomes a function. The set of pairs , for all possible natural integers n, is a function. Let us call it next. (This is a subset of relation neighbors.) Like a relation, a function may be partial or total. As with relations, the word “function” without further qualification means a function that may be total or partial. Putting together the definitions of “function” and “total relation” we see that with a total function there is, for every member x of its source set, exactly one y in the target set such that is in the function. More generally, if f is a function and x is a member of its domain, there is exactly one y such that is in the function. This legitimates the usual notation for expressing the value of that y: f (x) For example, next (6) has the value 7; and, once we have made citizenship a function by removing one of the two pairs for Hélène, citizenship (Kiyoko) has the value Japan. Remember, however, that the notation f (x) has a taboo associated with it: unless the function is known to be total, the notation is meaningless without a guarantee that x belongs to the domain of f. The set of all possible functions with source set X and target set Y is written X Y. Since every function is a relation, X Y is a subset of X ↔ Y. The bar across the arrow in the symbol reminds us that the functions may be partial. The set of total functions from X to Y, a subset of X Y, is written X → Y without a bar. | | | |
1076.7 THE CONCEPTS $32A.5 32A.5 FINITE FUNCTIONS Like any set,a relation or function may be finite or infinite.Finite functions,that is to say functions made of a finite set of pairs,will be of particular interest for the rest of this discussion. Function citizenship is finite;function next is infinite. If both X and y are finite,as in the case of citizenship,then their cartesian product Xx Y is also finite,so any function in X>Y(and more generally any relation in >)being a subset of Yx Y,will be finite.If X or Y or both are infinite,however,a function with source set X and target set y may be finite or infinite.So in spite of the next example you can have a finite function between infinite sets;for example,with N as both source and target,the function ,)is finite even though N is infinite. A function is finite if and only if both its domain and its range are finite. The set of finite functions with source set X and target set Y,a subset of>Y, is written Y>Y,where the stands for"finite". 32A.6 VISUALIZING A FINITE FUNCTION Finite functions and relations are of particular interest for software applications because they can be easily represented in the memory of a computer.But for a graphical application builder such as EiffelBuild finite functions have an even more specifically useful property:they are easy to construct and manipulate visually,using an obvious graphical representation in the form of a table.For example you can graphically display the three-pair function{Helene,☐>，，}-a function in PERSON>SHAPE where SHAPE is a set of graphical icons-as Helene Helmut Kiyoko This representation has the immediate visual advantage that for a reasonably small function it is easy to check visually that what is displayed is a function,not just a general relation:just look at the first column(the function's domain)and check that it has no duplicate.This will be even easier if the source set has a simple order relation so that elements in the first column can be kept sorted,as has been done above using alphabetic order
1076.7 THE CONCEPTS §32A.5 32A.5 FINITE FUNCTIONS Like any set, a relation or function may be finite or infinite. Finite functions, that is to say functions made of a finite set of pairs, will be of particular interest for the rest of this discussion. Function citizenship is finite; function next is infinite. If both X and Y are finite, as in the case of citizenship, then their cartesian product X × Y is also finite, so any function in X Y (and more generally any relation in X ↔ Y), being a subset of X × Y, will be finite. If X or Y or both are infinite, however, a function with source set X and target set Y may be finite or infinite. So in spite of the next example you can have a finite function between infinite sets; for example, with N as both source and target, the function {, } is finite even though N is infinite. A function is finite if and only if both its domain and its range are finite. The set of finite functions with source set X and target set Y, a subset of X Y, is written X Y, where the f stands for “finite”. 32A.6 VISUALIZING A FINITE FUNCTION Finite functions and relations are of particular interest for software applications because they can be easily represented in the memory of a computer. But for a graphical application builder such as EiffelBuild finite functions have an even more specifically useful property: they are easy to construct and manipulate visually, using an obvious graphical representation in the form of a table. For example you can graphically display the three-pair function {, , } — a function in PERSON SHAPE where SHAPE is a set of graphical icons — as This representation has the immediate visual advantage that for a reasonably small function it is easy to check visually that what is displayed is a function, not just a general relation: just look at the first column (the function’s domain) and check that it has no duplicate. This will be even easier if the source set has a simple order relation so that elements in the first column can be kept sorted, as has been done above using alphabetic order. | | f f Hélène Kiyoko Helmut
$32A.7 DEALING WITH MULTI-ARGUMENT FUNCTIONS 1076.8 Typed pick-and-throw is This convention blends particularly well with the visual principles of ISE Eiffel,as described in section 4.5 described in ISE Eiffel:The Environment.In particular,the environment's typed pick- of'ISE Eiffel:The and-throw mechanism immediately suggests a convenient way for users to build a Environment”. function: Argument Result hole Helene hole Helmut Kiyoko To add a new pair to the function,you will drag-and-drop an element from the source set to the top-left hole.This will only have an effect if that element is not already in the function's domain,that is to say if it is distinct from all the elements in the left column.Dropping the element into the hole will cause the hole to become occupied (according to the conventions of the environment a small dot in the hole should indicate this).When you then drag-and-drop to the top-right hole a member of the target set,the newlywed pair clunks down the table to its proper station in life. The order in which you select the pair's elements is immaterial:you can drag-and- drop the result element into its hole first if you prefer. See“Building a The scheme just described is the basis for building behaviors in EiffelBuild,the behavior pair'”,5.6.6, fundamental mechanism for producing context-event-command associations and hence page63and“THE interactive graphical applications.It also governs the State Tool of EiffelBuild. STATE TOOL".6.11. page 150. 32A.7 DEALING WITH MULTI-ARGUMENT FUNCTIONS The example functions discussed so far in this chapter are unary,that is to say take a single argument (a member of the source set). It is often necessary to use multiary functions -functions with two or more arguments.Mathematically,this does not raise any particular problem:rather than talking about a function with two arguments from sets A and B,we consider that we have a function whose(single)source set is the cartesian product A x B;the function will be a member of the set of functions A x B>C for some C,and similarly for more than two arguments. The practical consequences are awkward,however,if we want to keep the visual representation of functions introduced above.We could generalize that representation to give displays of the form
§32A.7 DEALING WITH MULTI-ARGUMENT FUNCTIONS 1076.8 This convention blends particularly well with the visual principles of ISE Eiffel, as described in ISE Eiffel: The Environment. In particular, the environment’s typed pickand-throw mechanism immediately suggests a convenient way for users to build a function: To add a new pair to the function, you will drag-and-drop an element from the source set to the top-left hole. This will only have an effect if that element is not already in the function’s domain, that is to say if it is distinct from all the elements in the left column. Dropping the element into the hole will cause the hole to become occupied (according to the conventions of the environment a small dot in the hole should indicate this). When you then drag-and-drop to the top-right hole a member of the target set, the newlywed pair clunks down the table to its proper station in life. The order in which you select the pair’s elements is immaterial: you can drag-anddrop the result element into its hole first if you prefer. The scheme just described is the basis for building behaviors in EiffelBuild, the fundamental mechanism for producing context-event-command associations and hence interactive graphical applications. It also governs the State Tool of EiffelBuild. 32A.7 DEALING WITH MULTI-ARGUMENT FUNCTIONS The example functions discussed so far in this chapter are unary, that is to say take a single argument (a member of the source set). It is often necessary to use multiary functions — functions with two or more arguments. Mathematically, this does not raise any particular problem: rather than talking about a function with two arguments from sets A and B, we consider that we have a function whose (single) source set is the cartesian product A × B ; the function will be a member of the set of functions A × B C for some C, and similarly for more than two arguments. The practical consequences are awkward, however, if we want to keep the visual representation of functions introduced above. We could generalize that representation to give displays of the form Typed pick-and-throw is described in section 4.5 of ‘‘ISE Eiffel: The Environment”. Hélène Kiyoko Helmut Argument hole Result hole See “Building a behavior pair”, 5.6.6, page 63 and “THE STATE TOOL”, 6.11, page 150. |
1076.9 THE CONCEPTS $32A.8 Helene UK Kiyoko Japan Helene France Kiyoko Italy Helmut Japan representing here a function in PERSONx COUNTRY>SHAPE,the function {，,O>,,●>， ,O>,,> But this representation is less convenient than for unary functions.In particular,it becomes much more difficult to check visually that the table indeed represents a function; since the number of members of 4 x B is the product of the numbers of members in each, the size of the table will soon become too large. To solve this problem we can resort to a mathematical device known as currying. 32A.8 CURRYING Consider a function f2 corresponding to the usual notion of a function with two arguments.For any applicable pair of values in A and B respectively,f2 yields a result in C.As we have seen,f2 will be for some A,B and C a member of the set FUNC2⊥A×B+→C We can associate with f2,through a one-to-one correspondence,a function f/-the "curried"form off2-having just one argument.Here is how. Function f7 will be a member of the set FUNCIA>(B+>C) What fl represents,like any other member of FUNCI,is a function taking one argument(a member of A),and yielding for any applicable value of that argument(that is to say,any member of the function's domain)another function,itself a member of B>C-that is to say a function that for any applicable value in B yields a result in C. Givenf2,the associated fl has as its domain the set of all members a of A for which there exists a member b of B such that the pair belongs to the domain of f2.Now take such an a.The value of fl(a)is itself a function,from B to C.Let us call that function
1076.9 THE CONCEPTS §32A.8 representing here a function in PERSON × COUNTRY SHAPE, the function {, >,, >, , >, , >, , >} But this representation is less convenient than for unary functions. In particular, it becomes much more difficult to check visually that the table indeed represents a function; since the number of members of A × B is the product of the numbers of members in each, the size of the table will soon become too large. To solve this problem we can resort to a mathematical device known as currying. 32A.8 CURRYING Consider a function f2 corresponding to the usual notion of a function with two arguments. For any applicable pair of values in A and B respectively, f 2 yields a result in C. As we have seen, f2 will be for some A, B and C a member of the set FUNC2 A × B C We can associate with f 2, through a one-to-one correspondence, a function f1 — the “curried” form of f 2 — having just one argument. Here is how. Function f1 will be a member of the set FUNC1 A (B C) What f1 represents, like any other member of FUNC1, is a function taking one argument (a member of A), and yielding for any applicable value of that argument (that is to say, any member of the function’s domain) another function, itself a member of B C — that is to say a function that for any applicable value in B yields a result in C. Given f 2, the associated f1 has as its domain the set of all members a of A for which there exists a member b of B such that the pair belongs to the domain of f 2. Now take such an a. The value of f1 (a) is itself a function, from B to C. Let us call that function UK Japan France Hélène Kiyoko Hélène Kiyoko Italy Helmut Japan f = ∆ | = ∆ | | |
$32A.8 CURRYING 1076.10 fla The domain of fla is the set of all members b of B such that belongs to the domain off2.For any such b,the value of f(b)is simply f2(a,b).(If this paragraph is not immediately luminous,just read on the explanations and examples that follow.) The transformation which for any two-argument function f2 yields the corresponding one-argument function fl is called currying(not because it was designed over dinner in some oriental restaurant but after the name of an English mathematician). Currying is itself a function-a total one,since every function,whether finite,partial or total will always have a curried version.If we call curry the function that curries functions (over some arbitrary basic sets A,B and C as above)we see that it is a member of the set (A×B+>C)→(A→(B+>C) If we are only interested in finite functions-which is the case for visual programming applications studied in this book-we can replace all the >symbols (but not the,of course)by.Function curry is not only total but one-to-one: every two-argument function in A x B>C has a one-argument curried version in 4>(B>C),and every such one-argument function is the curried form of some two-argument function. Using the first argument Were it not for Professor Curry,the function could have been called specialize,since is a matter of this is what it does:taking a function with two arguments and specializing it with respect convention.It is possible to its first argument.Starting with the two-argument function f2,the curried version fl to curry a multi- argument function with takes only one argument,and is such that fl(a)-what was called fl above-is like f2 respect to any argument. but with the first argument set to be a in all cases. Consider for example the addition function on integers,which we may call add2.It takes two arguments and yields their sum.It is a member of N x N->N.(Addition on integers is a total function,so in this example all the arrows can be written as->rather than just >.The function,addl A curry (add2)-the curried version of add2-is a member of N→(N→N) that is to say a function which,for any integer n,yields a function which,for any integer m,yields an integer. What concretely is add/?Well,for any n,addl (n)is the function which,for any m,yields n +m.For example,addl (1)is the "successor"function on integers: addl (1)=next where next,as introduced earlier,is the function in NN defined by the property that next (n)is n+I for every integer n.Similarly,addl (-1)is the function previous that subtracts one from any integer;add/(0)is the identity function on N-the function that, for any n,returns n itself,add/(2)is the function that adds 2 to any integer;and so on. One way to describe currying informally is to say that this mechanism trades argument complexity (cartesian product level)for result complexity (higher-level functions).Define the argument level of a function as the number of x,plus one,in the definition of its source set (that is to say the number of function arguments),and its result level as the number of arrows,plus one,in its target set.For example a function in ((A x B)x C)>(D ->E)has argument complexity 3 and result complexity 2
§32A.8 CURRYING 1076.10 f1a. The domain of f1a is the set of all members b of B such that belongs to the domain of f 2. For any such b, the value of f1a (b) is simply f2 (a, b). (If this paragraph is not immediately luminous, just read on the explanations and examples that follow.) The transformation which for any two-argument function f2 yields the corresponding one-argument function f1 is called currying (not because it was designed over dinner in some oriental restaurant but after the name of an English mathematician). Currying is itself a function — a total one, since every function, whether finite, partial or total will always have a curried version. If we call curry the function that curries functions (over some arbitrary basic sets A, B and C as above) we see that it is a member of the set (A × B C) → (A (B C)) If we are only interested in finite functions — which is the case for visual programming applications studied in this book — we can replace all the symbols (but not the →, of course) by . Function curry is not only total but one-to-one: every two-argument function in A × B C has a one-argument curried version in A (B C), and every such one-argument function is the curried form of some two-argument function. Were it not for Professor Curry, the function could have been called specialize, since this is what it does: taking a function with two arguments and specializing it with respect to its first argument. Starting with the two-argument function f2, the curried version f1 takes only one argument, and is such that f1 (a) — what was called f1a above — is like f2 but with the first argument set to be a in all cases. Consider for example the addition function on integers, which we may call add2. It takes two arguments and yields their sum. It is a member of N × N → N. (Addition on integers is a total function, so in this example all the arrows can be written as → rather than just .) The function, add1 curry (add2) — the curried version of add2 — is a member of N → (N → N) that is to say a function which, for any integer n, yields a function which, for any integer m, yields an integer. What concretely is add1? Well, for any n, add1 (n) is the function which, for any m, yields n + m. For example, add1 (1) is the “successor” function on integers: add1 (1) = next where next, as introduced earlier, is the function in N → N defined by the property that next (n) is n+1 for every integer n. Similarly, add1 (–1) is the function previous that subtracts one from any integer; add1 (0) is the identity function on N — the function that, for any n, returns n itself; add1 (2) is the function that adds 2 to any integer; and so on. One way to describe currying informally is to say that this mechanism trades argument complexity (cartesian product level) for result complexity (higher-level functions). Define the argument level of a function as the number of ×, plus one, in the definition of its source set (that is to say the number of function arguments), and its result level as the number of arrows, plus one, in its target set. For example a function in ((A × B) × C) (D E) has argument complexity 3 and result complexity 2. | | | | f | | | Using the first argument is a matter of convention. It is possible to curry a multiargument function with respect to any argument. | = ∆ | |
1076.11 THE CONCEPTS $32A.9 If we curry it we get a function in(A x B)(C>(D->E)),with argument level 2 and result level 3.If we curry this curried version once more,we get a function in A >(B>(C>(D >E))),with respective levels 1 and 4.Each currying operation reduces the argument level by 1 but increases the function level by 1. The is example illustrates the need for a notational convention to reduce the number of parentheses.As soon as we enter the spice-rich world of currying we start dealing with higher-level function spaces such as 4>(B>(C(D >E)));so to make things lighter it is customary to allow dropping parentheses with the understanding that arrows associate from the right.As a result the notation A B>C>D>E means the same as the last expression.Similarly,a state was defined in the previous chapter as a member of the set CONTEXT ->EVENT >COMMAND,which should be understood as an abbreviation for CONTEXT>(EVENT>COMMAND). For a different grouping or to remove risks of ambiguity,you may of course reinstate the parentheses. 32A.9 A DIGRESSION:CORRECTNESS OF COMPILERS AND INTERPRETERS In a totally different application domain,currying helps understand notions related to software,programming languages and programming tools.In particular,the notions of compiler and interpreter are not always well understood,so it is useful to provide precise definitions.This example is not directly relevant to EiffelBuild,but it should help you improve your appreciation of the concepts.As on the other topics of this chapter,the book Introduction to the Theory of Programming Languages provides more extensive discussions and examples. Consider a programming language,say Eiffel (although any other example would do).It defines the set EIFFEL_SYSTEM of valid systems (programs).Let EXECUTABLE be the set of machine-language programs for a certain architecture,say Intel X86.We may abstractly consider that set as a function: EXECUTABLE INPUT>OUTPUT where INPUT is the set of all possible program inputs,and OUTPUT the set of all possible program outputs.What this definition expresses is that a machine program defines a function that,for any possible input,should produce the corresponding output. Such functions are partial (hence the>and the word "should"in the preceding sentence)because a program may for some inputs enter into an infinite loop or recursion, or crash,and hence fail to yield an output. Now consider a compiler for Eiffel.It is a mechanism to transform Eiffel systems into machine programs;mathematically this means that the compiler is the implementation of a function compiler-a member of the set EIFFEL SYSTEM>EXECUTABLE Next consider an interpreter.Unlike a compiler,it is able to execute a system directly without first translating it to another form.What you feed into such execution is not just the input but also the software itself;to do its job,the interpreter has an equal need for both of these two elements
1076.11 THE CONCEPTS §32A.9 If we curry it we get a function in (A × B) (C (D E)), with argument level 2 and result level 3. If we curry this curried version once more, we get a function in A (B (C (D E))), with respective levels 1 and 4. Each currying operation reduces the argument level by 1 but increases the function level by 1. The is example illustrates the need for a notational convention to reduce the number of parentheses. As soon as we enter the spice-rich world of currying we start dealing with higher-level function spaces such as A (B (C (D E))); so to make things lighter it is customary to allow dropping parentheses with the understanding that arrows associate from the right. As a result the notation A B C D E means the same as the last expression. Similarly, a state was defined in the previous chapter as a member of the set CONTEXT EVENT COMMAND, which should be understood as an abbreviation for CONTEXT (EVENT COMMAND). For a different grouping or to remove risks of ambiguity, you may of course reinstate the parentheses. 32A.9 A DIGRESSION: CORRECTNESS OF COMPILERS AND INTERPRETERS In a totally different application domain, currying helps understand notions related to software, programming languages and programming tools. In particular, the notions of compiler and interpreter are not always well understood, so it is useful to provide precise definitions. This example is not directly relevant to EiffelBuild, but it should help you improve your appreciation of the concepts. As on the other topics of this chapter, the book Introduction to the Theory of Programming Languages provides more extensive discussions and examples. Consider a programming language, say Eiffel (although any other example would do). It defines the set EIFFEL_SYSTEM of valid systems (programs). Let EXECUTABLE be the set of machine-language programs for a certain architecture, say Intel X86. We may abstractly consider that set as a function: EXECUTABLE INPUT OUTPUT where INPUT is the set of all possible program inputs, and OUTPUT the set of all possible program outputs. What this definition expresses is that a machine program defines a function that, for any possible input, should produce the corresponding output. Such functions are partial (hence the and the word “should” in the preceding sentence) because a program may for some inputs enter into an infinite loop or recursion, or crash, and hence fail to yield an output. Now consider a compiler for Eiffel. It is a mechanism to transform Eiffel systems into machine programs; mathematically this means that the compiler is the implementation of a function compiler — a member of the set EIFFEL_SYSTEM EXECUTABLE Next consider an interpreter. Unlike a compiler, it is able to execute a system directly without first translating it to another form. What you feed into such execution is not just the input but also the software itself; to do its job, the interpreter has an equal need for both of these two elements. | | | | | | | | | | | | | | | f f f f = ∆ | | |
$32A.10 CURRYING FOR VISUAL DISPLAY 1076.12 Looking at the interpreter properties from a mathematical perspective,we may understand the interpreter as implementing a two-argument function interpreter,a member of the set EIFFEL SYSTEMX INPUT>OUTPUT Some software development environments provide both a compiler and an interpreter for the same language.The goal is to let environment users use the interpreter when they need fast turnaround,and the compiler when they need the highest possible performance. ISE Eiffel applies a more sophisticated form of this technique:its Melting Ice Technology integrates both compiled and interpretative techniques,but the choice between the two kinds is done automatically by the environment according to the needs of the moment,rather than by users selecting one or the other. The presence of both a compiler and an interpreter raises a tricky issue:how to guarantee that the semantics is the same-in other words,that you will not get some results when you are using the interpreter during development,and different ones when you move to production and start relying on the compiler? In the above framework the semantics compatibility requirement may be expressed simply:what we want is compiler curry (interpreter) 32A.10 CURRYING FOR VISUAL DISPLAY Let us return now to graphical application building.Currying provides us with a simple solution to the problem of displaying multi-argument functions.Displaying such a function directly in a tabular form is,as we saw,neither convenient nor convincing. The tabular format is only satisfactory with two columns,one for the input and one for the output-that is to say for single-argument functions,so that it is easy to check visually for the function property.The solution,then,is to curry multi-argument functions as many times as needed until we only have single-argument equivalents Our earlier example was the display of the following function,with argument level 2: {,▣>，,O>,:,●>， ,O>,,> Currying it means specializing on the first argument;or,to put it differently, considering separately the country-to-shape correspondences induced by each of the persons:the correspondence for Julie,the correspondence for Kiyoko and so on.Here is the curried version,one line per person,source sets alphabetically ordered: (，}>， }> ,Japan,O>> The first element on each line is a person;the second is a finite function from countries to shapes
§32A.10 CURRYING FOR VISUAL DISPLAY 1076.12 Looking at the interpreter properties from a mathematical perspective, we may understand the interpreter as implementing a two-argument function interpreter, a member of the set EIFFEL_SYSTEM × INPUT OUTPUT Some software development environments provide both a compiler and an interpreter for the same language. The goal is to let environment users use the interpreter when they need fast turnaround, and the compiler when they need the highest possible performance. ISE Eiffel applies a more sophisticated form of this technique: its Melting Ice Technology integrates both compiled and interpretative techniques, but the choice between the two kinds is done automatically by the environment according to the needs of the moment, rather than by users selecting one or the other. The presence of both a compiler and an interpreter raises a tricky issue: how to guarantee that the semantics is the same — in other words, that you will not get some results when you are using the interpreter during development, and different ones when you move to production and start relying on the compiler? In the above framework the semantics compatibility requirement may be expressed simply: what we want is 32A.10 CURRYING FOR VISUAL DISPLAY Let us return now to graphical application building. Currying provides us with a simple solution to the problem of displaying multi-argument functions. Displaying such a function directly in a tabular form is, as we saw, neither convenient nor convincing. The tabular format is only satisfactory with two columns, one for the input and one for the output — that is to say for single-argument functions, so that it is easy to check visually for the function property. The solution, then, is to curry multi-argument functions as many times as needed until we only have single-argument equivalents. Our earlier example was the display of the following function, with argument level 2: {, >, , >, , >, , >, , >} Currying it means specializing on the first argument; or, to put it differently, considering separately the country-to-shape correspondences induced by each of the persons: the correspondence for Julie, the correspondence for Kiyoko and so on. Here is the curried version, one line per person, source sets alphabetically ordered: {, }>, }> , }>} The first element on each line is a person; the second is a finite function from countries to shapes. compiler = curry (interpreter) |
