35 3535 352010-05-13 00:43:32 / rev b667c9e4c1f1+2Abstraction2.1 Diagrams as abstractions 312.2 Recursion 342.3 Low-pass filters 392.4 Summary and further problems 44Divide-and-conquer reasoning breaks enigmas into manageable prob-lems. When the reasoning is represented as a tree, the manageable prob-lems become the leaf nodes of the tree, and they are conceptually simplerthan the original problem or its intermediate subproblems. For example,the length of a classical symphony is a simple concept compared to thedata capacity of a CDROM.Being simpler, it is more likely than the parent nodes to be used in anothercalculation. Imagine that you are an architect designing a classical concerthall. One task is to ensure sufficient airflow to handle the heat producedby 1500 audience members during a concert. But how long is a concert?Reuse the symphony leaf node from the CDROM-capacity estimate. Con-certs often include a symphony before or after a break (the intermission),with a comparably long other half, so a rough concert duration 2.5 hours.Creating and using such reusable parts is the purpose of our second toolfor organizing complexity: abstraction. Abstraction is, according to theOxford English Dictionary [29]:The act or process of separating in thought, of considering a thing independentlyof its associations; or a substance independently of its attributes; or an attributeor quality independently of the substance to which it belongs. [my italics]The most important characteristic of abstraction is reusability. As Abelsonand Sussman [1, s. 1.1.8] describe:36 3636 36282010-05-13 00:43:32 / rev b667c9e4c1f1+The importance of this decomposition strategy is not simply that one is di-viding the program into parts. After all, we could take any large programand divide it into parts – the first ten lines, the next ten lines, the next tenlines, and so on. Rather, it is crucial that each procedure accomplishes anidentifiable task that can be used as a module in defining other procedures.What they write about programs applies equally well to understandingother systems. As an example, consider the idea of a fluid. At the bottomof the abstraction tower are the actors of fundamental physics: quarksand electrons. Quarks combine to build protons and neutrons. Protons,neutrons, and electrons combine to build atoms. Atoms combine to buildmolecules. And large collections of molecules act – under some conditions– like a fluid. The idea of a fluid is a new unit of thought that helpsunderstand diverse phenomena, without our having to calculate or evento know how quarks and electrons interact to produce fluid behavior.capacity, areacapacity areaAs a local example, here is how I draw the divide-and-conquer trees found throughout this book. The tree inthe margin, repeated from Section 1.3, could have beendrawn using one of many standard figure-drawing pro-grams with a graphical user interface (GUI). Making thedrawing would then require using the GUI to place all the leaves at theright height and horizontal position, connect each leaf to its parent with aline of the correct width, select the correct font, and so on. The next treedrawing would be another, seemingly separate problem of using the GUI.The graphical and captive user interface makes it impossible to organizeand tame the complexity of making tree diagrams.An alternative that avoids the captive user interface is to draw the figuresin a text-based graphics language, for then any editor can be used to writethe program, and common motifs can be copied and pasted to make newprograms that make new trees. The most successful such language isAdobe’s PostScript. PostScript statements are mostly of the form, “Draw acurve connecting these points.” because PostScript is a full programminglanguage, by clustering repeated drawing operations into reusable units,one can create procedures that help automate tree drawing.Instead of using PostScript directly, I took a lazier approach by usingthe high-level graphics language MetaPost mainly because this languagehas been used to write an even higher-level language for making andconnecting boxes. In the boxes language, the tree program is as follows:37 3737 37292010-05-13 00:43:32 / rev b667c9e4c1f1+% specify the textsboxit.root(btex capacity, area etex);boxit.capacity(btex capacity etex);boxit.area(btex area etex);% specify their relative positionsypart(capacity.n-area.n) = 0;xpart(area.w-capacity.e) = 10pt;root.s - 0.5[capacity.ne,area.nw] = (0,20pt);% place (draw) the texts without bordersdrawunboxed(root, capacity, area);% connect root with its two childrendraw root.s shifted (-5pt,0) -- capacity.n;draw root.s -- area.n;The boxes program translates this program into the MetaPost language.The MetaPost program translates this program into PostScript (or intoanother page-description language such as PDF). A PostScript interpreterin the printer or in the on-screen viewer translates the PostScript intoblack and white dots on a piece of paper or into pixels on a computerscreen.Even with MetaPost, a long program is required to make such a simplediagram. A clue to simplifying the process is to notice that it repeats manyoperations. For example, the direct children of the root have the samevertical position; if there were grandchildren, all of them would have thesame vertical position, different from the position of the children. Suchrepeating motifs suggest that the program is written at the wrong levelof abstraction.After using the boxes package to create several complicated tree diagrams,I took my own medicine and created a language for drawing tree dia-grams. In this language, the preceding tree is specified by only threelines:capacity, areacapacityareaThe tree-language interpreter, which I wrote for the occasion, translatesthose three lines into the boxes language. The abstraction tower is there-fore as follows; (1) the tree language , (2) the boxes language, (3) the38 3838 38302010-05-13 00:43:32 / rev b667c9e4c1f1+MetaPost language, (4) the PostScript language, and (5) pixels on a screenor specks of toner on a page.The tree minilanguage made constructing tree diagrams so easy that I cre-ated many diagrams to explain divide-and-conquer reasoning in Chap-ter 1 and to explain the subsequent ideas in this book. Here is a figurefrom Section 4.3.1:jump height henergy requiredh m genergy availablemuscle massanimal’s mass m muscle fractionenergy densityin muscleIts program in the tree minilanguage is short:jump