tag:blogger.com,1999:blog-64540062018-03-07T14:48:20.952+00:00Arcane Sentimentabout programming languages and other user interfaces.Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.comBlogger240125tag:blogger.com,1999:blog-6454006.post-68968926507041266142017-06-17T22:57:00.000+00:002017-06-17T23:01:55.656+00:00Purely algebraic abstractions<p>Any abstraction expresses something all its instances share. Usually this is semantic: all instances have some common meaning. They represent the same values, or perform the same computation, or support the same operations. When you know a construct is an instance of a certain abstraction, you know something about what it <em>means</em>. <p>Some abstractions are different. Their instances have no meaning in common, only algebraic properties. These are <dfn>purely algebraic abstractions</dfn>. Such an abstraction tells what transformations are valid on its instances' expressions, but says nothing about what they mean. <p>The classic algebraic abstractions are (of course) those of abstract algebra: groups and rings and fields and such. They abstract the properties necessary for algebraic transformations, and nothing else. If you know that your objects and their operators form a ring, you can manipulate formulae and even prove theorems about them, without knowing anything about what they mean. <p>In contrast, most abstractions in computing focus on meaning, and express algebraic properties only incidentally. If you have a <code><a href='https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html'>java.util.Collection</a></code> or a <code><a href='https://docs.oracle.com/javase/8/docs/api/java/util/Map.html'>java.util.Map</a></code>, you know you can add and remove items, test whether they're there, and iterate over them — but do you know any algebraic properties? Even the most basic properties are broken by unusual collections like caches or Bloom filters. They're semantically legitimate collections, and their algebraic properties are unreliable because they're irrelevant. <p>(Algebraic abstractions are not entirely reliable either, because most of their computational incarnations don't quite satisfy their axioms. Reflection and other debugging features can often detect differences between supposedly equivalent objects. Limitations of memory and time create edge cases where expressions equivalent in denotation are different in operation. Floating-point arithmetic makes a sport of breaking nearly every algebraic property that could be expected of it. But similar problems afflict nearly all attempts to reason about abstractions; they're not specific to algebraic abstractions, and they don't make them useless. The equivalences generally hold for the properties we care to preserve, so they're correct in practice though not in theory.) <h3>Haskell typeclasses</h3> <p>Most Haskell typeclasses have semantic content: <code>Show</code> and <code>Num</code> are about operations with the same meaning for all their instances; <code>Eq</code> expects algebraic properties (reflexivity and transitivity) but still defines the meaning of <code>==</code>. There are a small but increasing number of purely algebraic typeclasses: the Prelude has <code>Monoid</code>, <code>Functor</code>, <code>Applicative</code> and <code>Monad</code>, whose instances have nothing in common but algebraic equivalences. <p>This is why monads are so hard to learn. Each student of Haskell asks what monads <em>mean</em>, and invents a variety of wrong answers (typically semantic generalizations of <code>IO</code> actions), because they're sure that such an important abstraction must be meaningful, and have never heard of algebraic abstraction. Eventually they learn to use monads without asking what they mean, because monads don't mean anything. <p>This is a sore point among Haskellers. It will get more sore, because Haskell is gaining more algebraic abstractions. <code>Applicative</code> is in the Prelude now! <h3>Haskell Prime numbers</h3> <p><a href="https://prime.haskell.org/">Haskell Prime</a> is a collection of ideas for future versions of Haskell, including <a href='https://prime.haskell.org/wiki/NumericClasses'>a proposal to generalize the numeric typeclasses</a> by removing their semantic content, replacing <code>Num</code> and most of its subclasses with purely algebraic classes: <pre><code>(+) :: AbelianGroup a ⇒ a → a → a (*) :: Ring a ⇒ a → a → a (/) :: DivisionRing a ⇒ a → a → a mod :: EuclideanDomain a ⇒ a → a → a</code></pre> <p>(A division ring is like a field except that multiplication is not necessarily commutative.) <p>This makes the numeric operations maximally general, at the cost of making them meaningless. It also gives mundane code types (and type errors) that make sense to mathematicians and no one else: <pre><code>factorial :: (Ring a, Ord a) ⇒ a → a sum :: AbelianGroup a ⇒ [a] → a</code></pre> <p>(I'm not sure why <code>+</code> is on <code>AbelianGroup</code> instead of something more general like <code>Magma</code>. Maybe it's to comply with users' expectation that <code>+</code> be associative and commutative.) <p>This proposal brings the straightforward clarity of <code>Monad</code> to arithmetic, an area where Haskell has long suffered from comprehensibility bordering on practicality. <p>I'm not sure algebraic abstractions are always a bad idea for programming languages, but the difficulty of <code>Monad</code> suggests they're hazardous. <p>A semantic abstraction tells you what its instances mean. An algebraic abstraction only tells you what transformations preserve that meaning. That's enough for optimization, but not for understanding. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/I5sWvDlPeuY" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com2http://arcanesentiment.blogspot.com/2017/06/purely-algebraic-abstractions.htmltag:blogger.com,1999:blog-6454006.post-60208069938990510662017-06-11T14:29:00.000+00:002017-06-11T14:29:29.265+00:00Antedating “datatype” all the way to Plankalkül<p><a href='http://arcanesentiment.blogspot.com/2015/01/a-brief-history-of-type.html'>Previously</a> I speculated that the word “datatype” might have been used in computing before 1958. In response, <a href=/https://news.ycombinator.com/item?id=14406853'>dvt</a> found a precedent from <strong>1945</strong>! It's Konrad Zuse's very early language Plankalkül (Plan Calculus). <a href='http://zuse.zib.de/file/zuse_archive-0233.pdf?id=http%3A//zuse.zib.de/file/1rUAfKDkirW8o3gT/21/1c/70/9e-d718-4b4e-be7b-ed9b620f5683/0/original/092be0ebdd0784fee570ef37eee273c7.pdf' title='Der Plankalkül (In der Fassung von 1945)'>Zuse's notes</a> pervasively use the words <dfn>Angabentyp</dfn> and <dfn>Angabenart</dfn>, without bothering to define them. Modern German uses “Daten” instead of “Angaben”, but the terms are otherwise unchanged: “Datentyp” and “Datenart”. <p>Plankalkül was the world's first programming language, and it begins from first principles: the only primitive type is the bit, charmingly called a “Ja-Nein-Wert” (yes-no-value). It builds everything else out of arrays and tuples. The section on datatypes begins: <blockquote><h2>Angaben und ihre Darstellung [Data and its representation]</h2> <p>Die auftretenden Angaben können mannigfacher Art sein. Z.B. J.-N.-Werte, Zahlen, Listen usw. [The data given can be of various types, e.g. Y-N-values, numbers, lists etc.] <p>[...] <p>Die Unterscheidung der einzelnen Angabenarten soll nun wie folgt formalisiert werden [The distinction between the various datatypes will now be be formalized as follows]: <h3>Angaben-Strukturen [Data structures]</h3> <p>Unter Struktur einer Angabe wird der komponentenmäßige Aufbau einer Angabe ohne Hinblick auf die Bedeutung der einzelnen Fälle und Komponenten verstanden. [The structure of a datum is the component composition of a datum without regard to the meaning of the individual instances and components.] <p>Wir haben Angaben von starrer und von variabler Struktur. Wir führen nun Angabenstrukturzeichen ein, welche jeder Angabe zugeordnet sind. Diese werden mit <code>S</code> und einer Kennzahl bezeichnet. Die Entwicklung der zusammengesetzten Strukturen erfolgt dann durch „Strukturgleichungen“ aus einfachen (bereits definierten) Strukturen. [We have data of fixed and of variable structure. We now introduce data structure symbols, which are assigned to each datum. These are denoted by <code>S</code> and an ID number. The development of composite structures then follows by “structure equations” from simple (already defined) structures.] <p>So wird dem einfachen Ja-Nein-Wert das Strukturzeichen <code>S0</code> zugeordnet. Eine Folge von <var>n</var> J-N-Werten hat dann die Struktur <code>S1.<var>n</var></code>. Es gilt die Strukturgleichung: [Thus the structure symbol <code>S0</code> is assigned to the simple yes-no value. Then a sequence of <var>n</var> yes-no values has the structure <code>S1.<var>n</var></code>. The structural equation applies:] <pre><code>S1.n = n × S0</code></pre> <p>Durch Verfolgung der Strukturgleichungen ist es jederzeit möglich, den Aufbau einer Angabe zu ermitteln, auch wenn dieser sehr kompliziert ist. [By following the structure equations, it is possible at any time to determine the composition of a datum, even when it is very complex.]</blockquote> <p>Plankalkül was never implemented (well, not until 1975), but Zuse wrote enough code in it to discover the need for generics, and duly invented them: <blockquote><p>Wir brauchen noch „unbestimmte“ Strukturzeichen. Wollen wir z.B. andeuten, daß eine Angabe aus einer Liste von n Gliedern besteht, ohne die Struktur des Gliedes im einzelnen festzulegen, so schreiben wir: <code>n × σ</code>. [We still need “undefined” structure symbols. Let us suppose, for example, that a datum consists of a list of <var>n</var> elements, without specifying the structure of the individual elements, so we write: <code>n × σ</code>.] <p>Für <var>σ</var> kann dann ein beliebiges Strukturzeichen eingesetzt werden. [For <var>σ</var> any structure symbol can be used.] <table><tr><td><code>¤ × σ</code><td>Ist das allgemeinste Strukturzeichen einer Liste. (Struktur der Glieder und Zahl der Glieder offen gelassen).<td>Is the common structure symbol of a list. (Structure of elements and number of elements left open.) <tr><td><code>¤ × 2σ</code><td>Ist die Struktur einer Paarliste, bei der die Glieder der einzelnen Paare von gleicher Struktur <var>σ</var> sind.<td>Is the structure of a pair-list where the elements of each pair are of the same structure <var>σ</var>. <tr><td><code>¤ × (σ, τ)</code><td>Ist die Struktur einer Paarliste bei der die Vorderglieder die Struktur <var>σ</var>, und die Hinterglieder die Struktur <var>τ</var> haben.<td>Is the structure of a pair-list where the front elements have the structure <var>σ</var> and the back elements have the structure <var>τ</var>. <tr><td><code>2 × n × σ</code><td>Ist keine Paarliste, sondern ein Paar von Listen.<td>Is not a pair-list, but a pair of lists.</table></blockquote> <p>Array indexes, incidentally, are zero-based: <blockquote>Es sei noch darauf aufmerksam gemacht, daß bei einer aus <var>n</var> Gliedern bestehenden Angabe der höchste Index der Komponenten gleich <var>n − 1</var> ist, da die Komponentennumerierung mit 0 beginnt. [It should be pointed out that for a datum consisting of <var>n</var> elements, the highest index of the components is equal to <var>n − 1</var>, as the component numbering begins with 0.]</blockquote> <p>Separately from data structures, Plankalkül supports constraints on which values can actually be used: <blockquote><p>Eine Angaben-Beschränkung liegt vor, wenn die volle Variabilität der zu einer Angabenart gehörenden Struktur nicht voll ausgenutzt ist. Z.B. können Dezimalziffern durch 4 J.N.-Werte dargestellt werden. Es werden jedoch nur 10 von den 16 möglichen Variationen ausgenutzt. [A data-restriction is available when the full variability of the structure belonging to a datatype is not fully used. E.g. decimal digits can be represented by 4 bits. However, only 10 of the 16 possible variations are used.] <p>In solchen Fällen wird durch eine Beschränkungsformel angegeben, welche Fälle der Struktur in den Definitionsbereich der Angabenart fallen. Eine solche Formel wird mit <code>B</code> und einer Kennzahl bezeichnet. [In such cases, a restriction formula specifies which cases of the structure fall within the defined range of the datatype. Such a formula is denoted by <code>B</code> and an ID number.]</blockquote> <p>“Typ” and “Art” are synonyms, so they're ripe for distinction by anyone who wants words for two concepts. Zuse does: <dfn>Angabentypen</dfn> are optional annotations distinct from both structures and restrictions, while <dfn>Angabenarten</dfn> bundle all three together: <blockquote><h3>Angabentypen [Datatypes]</h3> <p>Den gleichen Strukturen und Beschränkungsformeln können Angaben verschiedener Bedeutung zugeordnet sein. (Z.B. <code>x =</code> und <code>y =</code> Koordinaten). Im allgemeinen ist es nicht nötig, diese zu unterscheiden. Ist dies jedoch vorteilhaft, so werden Typenbezeichnungen eingeführt. Z.B. <code>T<sub>1</sub></code>, <code>T<sub>7</sub></code> usw. [The same structures and restriction-formulas can be assigned to data of different meaning. (E.g. <code>x =</code> and <code>y =</code> coordinates). In general it is not necessary to distinguish them. If it is advantageous, however, type-designations will be introduced. E.g. <code>T<sub>1</sub></code>, <code>T<sub>7</sub></code> etc.] <h3>Angabenart [Datatype]</h3> <p>Jeder Angabenart ist eine Struktur und evtl. eine Beschränkung bzw. eine Typenbezeichnung zugeordnet. Darüber hinaus kann eine Angabenart noch durch spezielle Bedeutungen der Komponenten gekennzeichnet sein. (Z.B. Zahlen in halblogarithmischer Form, vergl. Zahlenrechnungen S. 119 ff). [Each datatype is assigned a structure and possibly a restriction or type-designation. In addition, a datatype can be further characterized by specific meanings of the components. (E.g. numbers in semi-logarithmic [=floating-point] form, see Numerical Calculations, p.119 ff.)] <p>Alle diese Kennzeichnungen können dann unter einem Angabenzeichen <code>A</code> zusammengefaßt werden. Ist eine Angabe durch ein <code>A</code>-Zeichen z.B. <code>A10</code> gekennzeichnet, so ist die besondere Kennzeichnung der Struktur usw. nicht erforderlich, da diese in <code>A10</code> mit enthalten ist. [All these identifiers can be combined under one data symbol <code>A</code>. If a datum is marked with an <code>A</code>-symbol, e.g. <code>A10</code>, the specific identifier of the structure etc. is not required, as it is included in <code>A10</code>.] <p>Angabenart-Zeichen können jedoch auch einer Gruppe analoger Angabenarten verschiedener Struktur zugeordnet sein. Z.B. können Zahlen durch verschiedene Strukturen (z.B. Dual-Zahlen, Dez.-Zahlen) dargestellt werden. Jedoch kann ein allgemeines Zeichen (z.B. <code>A8</code> vergl. Zahlenrechnen S. 121) eingeführt werden, welches lediglich besagt, daß es sich um eine Zahl handelt, ohne ihre Struktur im einzelnen festzulegen. [Datatype symbols can, however, also be assigned to a group of analogous datatypes of different structures. E.g. numbers can be represented by various structures (e.g. binary numbers, decimal numbers). However, a generic symbol (e.g. see <code>A8</code>, Numerical Calculations, p.121) can be introduced which only says that it is a number, without specifying its structure in detail.] <p>Wir führen entsprechend <var>σ</var> ein unbestimmtes Angabenartzeichen <var>α</var> ein. [We introduce an undefined datatype symbol <var>α</var> corresponding to <var>σ</var>.] </blockquote> <p>With abstract types in 1945, Plankalkül's type system is ahead of its time. So is its support for predicate calculus, which is worth a post of its own. Less exotically, it has the basic features of languages a decade later: (one-armed) conditionals, loops, function calls, and the assignment statement (written left-to-right). <p>One feature of Plankalkül is conspicuously primitive. All of the symbols for data structures, restrictions, constants, variables, and so on are not named but numbered. It's like Intercal but 27 years earlier! <p>Zuse noticed that it was confusing to so many numbers with so many different meanings, and tried to distinguish them with a unique two-dimensional syntax: <blockquote><h3>Die Zeilendarstellung [The line format]</h3> <p>Um die zu einer Angabe gehörenden verschiedenen Kennzeichnungen, wie Variablen-Index, Komponentenangabe, Angabenart bzw. Struktur usw. übersichtlich darstellen zu können, werden diese einzelnen Kennzeichnungen je verschiedenen Zeilen einer Formel zugeordnet. [To be able to show the various identifiers belonging to a datum, such as variable index, component data, datatype or structure etc., these individual identifiers are assigned to different lines of a formula.] <p>Wir haben zunächst die Hauptzeile, in welcher die Formel in der bisher üblichen Art dargestellt wird. [First we have the main line in which the formula is shown in the usual way.] <p>Die nächste Zeile dient der Unterscheidung der verscheidenen Variablen, welche durch den „Variablen-Index“ erfolgt. (V ). Eine weitere Zeile dient der Kennzeichnung der Komponenten der durch die Zeile 1 und 2 gekennzeichneten Variablen. (Komponentenindex K.) [The next line serves to distinguish the different variables, which is done by the “variable index” (<code>V</code>). Another line serves to identify the components of the variables indicated by lines 1 and 2. (Component index <code>K</code>.)] <p>Es wird also z.B. der Ausdruck [Thus e.g. the expression] <pre><code>K1(V<sub>3</sub>)</code> <small>Komponente 1 von <code>V<sub>3</sub></code> [Component 1 of <code>V<sub>3</sub></code>]</small></pre> <p>wie folgt geschrieben [is written as follows]: <pre><code>V 3 1</code></pre> <p>bzw. [or] <code>K2.3(Z<sub>4</sub>)</code> = <pre><code>Z 4 2.3</code></pre></blockquote> <p>In modern notation, those are <code>V<sub>3</sub>[1]</code> and <code>Z<sub>4</sub>[2, 3]</code>. <blockquote><p>Weitere Zeilen können der Kennzeichnung der Struktur und Angabenart bzw. der Beschränkung und dem Typ dienen. [Further lines may be used to indicate the structure and type of data, or the restriction and the type.] <p>Im allgemeinen wird entweder die Angabe der Struktur oder der Angabenart genügen. (<code>S</code> = Index bzw. <code>A</code> = Index) [In general either the specification of the structure or of the datatype suffice. (<code>S</code>-index or <code>A</code>-index.)] <p>z.B. [e.g.]</p> <pre><code>Z 4 2.3 0</code></pre> <p>bedeutet: „Z4, Komponente 2.3”. Der Wert ist von der Struktur <code>S0</code>. [means: “Z4, component 2.3”. The value is of the structure <code>S0</code>.] <p>Die Strukturangabe bzw. Angabenart – Angabe bezieht sich dabei auf die Komponente. [The structure specification or datatype specification refers to the component.] <p>Die einzelnen Zeilen werden durch Vorsetzen der Buchstaben <code>V</code>, <code>K</code>, <code>S</code> bzw. <code>A</code> vor die Zeilen der Formel gekennzeichnet: [The individual lines are identified by prefixing the letters <code>V</code>, <code>K</code>, <code>S</code> or <code>A</code> before the lines of the formula:] <pre><code> | Z ^ Z V | 4 2 K | 2.3 S | 0 0</code></pre> <p>Wird von einer Angabe keine Komponente gebildet, so bleibt der Komponenten-index frei. [If no component is established for a datum, the component index remains empty.] <p>Das Zeichen <code>A</code> kann stets an Stelle des Zeichens <code>S</code> gesetzt werden; aber im allgemeinen nicht umgekehrt. Die für Strukturen bereits definierten Kennzahlen dürfen dann nicht mehr für Angabenarten benutzt werden: (Z.B. gibt es nur eine Struktur <code>S0</code>, <code>S1.<var>n</var></code> und die Zeichen <code>A0</code>, <code>A1.<var>n</var></code> sind mit diesen Strukturzeichen identisch.) [The symbol <code>A</code> can always be used in place of <code>S</code>, but in general not vice versa. The ID numbers already defined for structures can thus no longer be used for datatypes: (E.g. there is only one structure <code>S0</code>, <code>S1.<var>n</var></code> and the symbols <code>A0</code>, <code>A1.<var>n</var></code> are identical to these structure symbols.]</blockquote> <p>If only Zuse had thought of giving them names! But he was trying to solve a different problem, of typography: <blockquote><p>Mit Hilfe dieser Darstellung ist es leicht möglich, die einzelnen Angabenarten zu unterscheiden. Es ist nicht mehr wie bisher in der Mathematik nötig, verschiedene Zeichenarten für verschiedene Angabenarten heranzuziehen. (Z.B. deutsche Buchstaben für Vektoren.) Ein solches Verfahren wäre im allgemeinen Plankalkül nicht anwendbar, da die Zahl der verschiedenen Angabenarten innerhalb der gleichen Rechenpläne bzw. Plangruppen derartig mannigfaltig sein kann, daß die zur Verfügung stehenden Zeichenarten nicht ausreichen. [With the help of this representation it is easily possible to distinguish the individual datatypes. It is no longer necessary, as hitherto in mathematics, to draw up different types of symbols for different datatypes. (E.g. German letters for vectors.) Such a method would not be practical for general plan calculus, as the number of different datatypes in one program or program-group can be so many that the available types of symbols are not enough.] <h3>Constanten [Constants]</h3> <p>Den einzelnen Angabenarten, Typen bzw. Strukturen können Constanten zugeordnet werden, denen spezielle Bedeutung zukommt. Eine Constante ist ein bestimmter Fall aus der Menge der möglichen Variationen einer Angabenart bzw. Struktur. Sie werden mit <code>C</code> und einer Kennzahl bezeichnet. [To the individual datatypes, types or structures constants can be assigned which have special significance. A constant is a particular case from the set of possible variations of a datatype or structure. They are denoted by <code>C</code> and an ID number.]</blockquote> <p>In addition to constants, Plankalkül distinguishes three kinds of variables (input, intermediate, and output). Since all four can be used in the same context, the symbols <code>C</code>, <code>V</code>, <code>Z</code> and <code>R</code> must appear on every variable reference to distinguish them, so the two-dimensional syntax is not helping much. It's also difficult to transcribe, so I'll stop here rather that trying to translate all 180 pages. <p>I don't know if Plankalkül was known to the designers of later programming languages, or if it had any influence. But its casual usage of the words “Angabentyp” and “Angabenart” suggests they were already established in 1945. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/AOr3ZKyKLcY" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2017/06/antedating-datatype-all-way-to.htmltag:blogger.com,1999:blog-6454006.post-28759456575926996622016-02-29T13:15:00.000+00:002016-02-29T13:15:26.982+00:00Don't abbreviate rare names<p>Some languages are <em>too</em> consistent about keeping their names short. Arc and <a href="https://github.com/akkartik/wart#readme">Wart</a> call their macro-defining operators <code>mac</code> instead of <code>defmacro</code> or <code>define-macro</code>. <p>I understand how a designer could see <code>mac</code> as an important operator. If you think of macros as a central, distinctive feature of your language, and if you use quite a few of them to bootstrap your standard library, they <em>feel</em> important enough to deserve a short name. <p><code>mac</code> does almost nothing for the length of programs, though. Macro definitions, however fundamental, aren't common enough for it to matter. <code>define-macro</code> is short enough. I prefer <code>defmacro</code>, but only because it follows a naming convention that makes other, more common names shorter; it's not common enough itself to justify an irregularly short name. <p>Save the aggressive abbreviation for common operations like <code>make-hash-table</code>. Giving that a one-word name (or even <code>{}</code>) makes more difference.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/uJhljUUSaoM" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2016/02/dont-abbreviate-rare-names.htmltag:blogger.com,1999:blog-6454006.post-51800382808802068532016-02-07T00:00:00.000+00:002016-02-07T00:11:16.095+00:00It's a normative theory.<p>When a theory fails to usefully describe reality, one bad response is to demand that reality stop disobeying it. Cosma Shalizi <a href='http://bactra.org/weblog/569.html'>illustrates</a>: <blockquote><strong>A</strong>: Hey, you over there, the one walking! You're doing it wrong. <br><strong>B</strong>: Excuse me? <br><strong>A</strong>: You're only using two feet! You should keep at least three of your six in contact with the ground at all times. <br><strong>B</strong>: ... <br><strong>A</strong>: Look, it's easily proved that's the optimal way to walk. <a href="http://en.wikipedia.org/wiki/Hexapod_(robotics)">Otherwise you'd be unstable</a>, and <a href="http://www.cs.toronto.edu/~fbacchus/Papers/BKTSYN90.pdf">if you were walking past a Dutchman he could kick one of your legs with his clogs and knock you over</a> and then lecture you on how to make pancakes. <br><strong>B</strong>: What? Why a Dutchman? <br><strong>A</strong>: You can't trust the Dutch, they're everywhere! Besides, every time you walk it's really just like running the gauntlet at <a href="http://www.schiphol.nl/">Schiphol</a>. <br><strong>B</strong>: It is? <br><strong>A</strong>: Don't change the subject! Walking like that you're actually sessile! <br><strong>B</strong>: I don't seem to be rooted in place... <br><strong>A</strong>: It's a technical term. Look, it's very simple, these are all implications of the axioms of the theory of optimal walking and you're breaking them all. I can't get over how immobile you are, walking like that. <br><strong>B</strong>: "Immobile"? <br><strong>A</strong>: Well, you're not walking properly, are you? <br><strong>B</strong>: Your theory seems to assume I have six legs. <br><strong>A</strong>: Yes, exactly! <br><strong>B</strong>: I only have two legs. It doesn't describe what I do at all. <br><strong>A</strong>: It's a <em>normative</em> theory. <br><strong>B</strong>: For something with six legs. <br><strong>A</strong>: Yes. <br><strong>B</strong>: I have two legs. Does your theory have any advice about how to walk on two legs? <br><strong>A</strong>: Could you try crawling on your hands and knees?</blockquote> <p>Cosma is thinking of Bayesian statistics, but I sometimes feel the same way about type theory. <p>In both cases the problem is not with the theory, but with the movement that insists that the theory should be used for everything, whether it works or not.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/s82CLoosp9w" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2016/02/its-normative-theory.htmltag:blogger.com,1999:blog-6454006.post-49626445267090641822016-01-01T23:59:00.002+00:002016-01-02T00:26:16.950+00:00Many happy returns <p>Some languages can return multiple values from a function, just as they can pass multiple arguments to a function. I used to think this was an important language feature. Functions that return more than one result are common, after all, so every language has a way to express them — by returning structures, or side-effecting reference parameters, or <acronym title='continuation-passing style'>CPS</acronym> — or, instead of these workarounds, by supporting multiple return values directly. It complicates the language kernel a little, but it makes code cleaner, right? <p>No, it doesn't. There are several reasons for a function to return multiple values. None of them require direct language support, and for most of them, it's not even helpful. <h3>Secondary values</h3> <p>Some functions return one useful value, plus some <dfn>secondary values</dfn> that aren't interesting to most callers. For instance, Common Lisp's two-argument <code>floor</code> returns a quotient and a remainder, but usually you just want the quotient. This is where built-in multiple values shine: they can automatically ignore the extra value, so the common case Just Works, with no effort from either the caller or the multivalued function. <pre>CL-USER&gt; <code>(format nil "π is about ~S" (floor 355 113))</code> "π is about 3" CL-USER&gt; <code>(floor 355 113)</code> 3 16 </pre> <p>Returning and destructuring a tuple doesn't handle secondary values well. When the caller wants all the values, it's fine (and equivalent to built-in multiple values), but in the more common case where the caller wants only the primary value, it forces them to explicitly extract one component. This can often be done with a convenience function like <code>left (l, r) = l</code>, but it still adds noise. <p>If your language supports overloading on return type, you can make the function return either the primary value or the structure — whichever the caller wants. This is a rare and difficult feature, though. <p>Returning secondary values by side effect works surprisingly well. If the caller doesn't want the secondary values, it's no trouble, since the arguments to which to write them can be optional. When the caller does want them, it requires binding a variable, which typically forces the expression into a block, which is occasionally a problem for functional code. It's not very verbose, though: <pre><code>int floor(int a, int b, int *remainder = NULL); int remainder; int quotient = floor(a, b, &remainder);</code></pre> <p>Now for my favorite: continuation-passing style. It has a bad reputation because it's associated with total CPS transformation, in which <em>every</em> continuation becomes an explicit lambda, which is onerous and unreadable. That is indeed bad. If you pass explicit continuations only where needed, however, it's no worse than other uses of <code>λ</code>. <p>CPS provides a way to handle secondary values at least as well as built-in multiple values do, but without language support. With no explicit continuation, the function returns the primary value, but if a continuation is provided, it receives all the values: <pre>imaginary-lisp&gt; <code>(floor 355 113)</code> 3 imaginary-lisp&gt; <code>(floor 355 113 (λ (quot rem) rem))</code> 16</pre> <h3>Success and failure</h3> <p>Often a secondary value encodes success or failure, as in Common Lisp's <code>gethash</code>, <code>read</code>, or <code>macroexpand-1</code>, or any of the many Go functions that return an error as their second value. This allows callers who don't care about errors can simply ignore the extra value, while those who do can still get it. <pre><code>(multiple-value-bind (val present?) (gethash vars varname) (if present? val (error "Unbound variable: ~S" varname))) file, err := os.Open("/some/path") if err != nil { panic(err) }</code></pre> <p>Returning a structure + pattern matching handles this cleanly and safely: you simply return a different structure for each continuation. Usually this is something like Haskell's <code>Maybe</code> or <code>Either</code>: <pre><code>case (Data.Map.Strict.lookup vars varname) of Nothing → error "Unbound variable: ~S" varname Just val → val case foo of Left err → error err Right x → x</code></pre> <p>This can be a little verbose, but the verbosity can sometimes be eliminated by operators that automatically propagate the failure case, such as Haskell's various monad operators. <p>CPS has an even cleaner way to handle this: success and failure are two different continuations, so the function can simply take an optional continuation for handling errors, or two explicit continuations (of which the success continuation is often the identity function): <pre><code>(slurp filename (fn (err) (error "Unable to open ~S: ~S" filename err))) (gethash vars varname <abbr title='identity'>i</abbr> (fn () (error "Unbound variable")))</code></pre> <p>This multiple-continuation style is often used in Smalltalk, where it's particularly convenient because of Smalltalk's terse lambdas. <a href='http://www.cs.indiana.edu/pub/techreports/TR346.pdf'>Toward Leakage Containment</a> (Julia Lawall and Dan Friedman, 1992) recommended it for Scheme, but got little attention, perhaps because it used the nonsensical name “continuation-constructing style” (and didn't mention it in the title). I call it multi-CPS and find it very convenient — often more so than catching exceptions. <h3>Complex returns</h3> <p>Some functions really do have multiple values to return — sometimes lots of them, like Common Lisp's <code>get-setf-expansion</code>, with five values, or <code>get-decoded-time</code>, with nine. These functions tend to be awkward to use regardless of how you receive the return values, but the least awkward way is to return a structure, because then at least you're not forced to name each result individually. That's why most languages do this for times: <pre><code>time_t now = time(NULL); tm *decoded = localtime(&amp;now); printf("The year is %d.\n", tm.tm_year + 1900);</code></pre> <p>This is less painful than Common Lisp's multiple-return-value approach, which often forces you to bind more values than you care about: <pre><code>(multiple-value-bind (sec min hour day month year) (get-decoded-time) (format t "The year is ~S.~%" year))</code></pre> <p><code>setf</code> expanders are a similarly complex result that ought to be a structure. <code><pre>(multiple-value-bind (temps forms svars writeform readform) (get-setf-expansion x e) ...)</code></pre> <p>Simpler cases, like partitioning a collection, are adequately handled by tuples (if you have destructuring) or CPS (if you don't). <h3>Why so much trouble?</h3> <p>Expression languages get much of their elegance by encoding dataflow in program structure. Each expression has one parent, and can therefore easily specify what to do with one return value. When there is more than one, there's not enough room in the structure to express what to do with each value, so we have to specify it in some more other way. <p>I still think multiple return values are important, but I no longer think they require special language support. There are plenty of good alternatives, and improving a language's support for those alternatives (by e.g. optimizing destructuring or <code>λ</code>) is easier than complicating the core semantics, and more likely to be useful for other purposes.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/uEgMmvrgGVQ" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com4http://arcanesentiment.blogspot.com/2016/01/many-happy-returns.htmltag:blogger.com,1999:blog-6454006.post-30027349813968054872015-01-31T23:59:00.001+00:002017-07-28T12:17:51.665+00:00A brief history of “type”<p>The word “type” has a variety of meanings in programming languages, which are often a focus of confusion and contention. Here's a history of its use, focusing on particularly influential languages and papers. <h3>1956: Fortran “modes”</h3> <p>The term “type” was apparently not yet established in 1956, because the Fortran manual speaks of integer and floating-point “modes” instead. It has something called “statement types”, but those are what are now called syntactic forms: assignment, conditional, <code>do</code>-loop, etc. <p>The 1963 <a href="http://archive.computerhistory.org/resources/text/Fortran/102663119.05.01.acc.pdf">Fortran II manual</a> speaks of "two types of constants" (integer and floating-point), but this seems to be just the English word. When it talks about these types in more detail, it calls them “modes”, e.g. “arguments presented by the CALL statement must agree in number, order, mode, and array size with the corresponding arguments in the SUBROUTINE statement”. (Evidently the terms “formal” and “actual” parameters weren't established yet either.) <h3>1958-63: Algol</h3> <p>Algol is one of the most influential languages in history. It introduced <code>if ... then ... else</code>, the <code>int n</code> declaration syntax, and semicolons. It also popularized the term “type”. The <a href='http://www.softwarepreservation.org/projects/ALGOL/report/Algol58_preliminary_report_CACM.pdf'>Algol 58 report</a> defines <dfn>type declarations</dfn> on variables in terms of the “type” and “class” of values: <blockquote><dfn>Type</dfn> declarations serve to declare certain variables, or functions, to represent quantities of a given class, such as the class of integers or class of Boolean values. [...] Throughout the program, the variables, or functions named by the identifiers I, are constrained to refer only to quantities of the type indicated by the declarator.</blockquote> <p>The <a href='http://www.masswerk.at/algol60/report.htm'>Algol 60 report</a> is more consistent: <blockquote>The various “types” (<code>integer</code>, <code>real</code>, <code>Boolean</code>) basically denote properties of values. The types associated with syntactic units refer to the values of these units.</blockquote> <p>Note that types are explicitly a property of values, not variables or expressions. But does “basically” mean someone thought otherwise, or just that this isn't a formal definition? <h3>1967: Strachey's Fundamental Concepts</h3> <p>Chris Strachey's <a href='http://www.itu.dk/courses/BPRD/E2009/fundamental-1967.pdf‎'>Fundamental Concepts in Programming Languages</a> was an influential set of lecture notes that established a bunch of common terms. It defines types thus: <blockquote>Most programming languages deal with more than one sort of object—for example with integers and floating point numbers and labels and procedures. We shall call each of these a different <dfn>type</dfn> and spend a little time examining the concept of type and trying to clarify it.</blockquote> <p>Strachey takes it for granted that types can be static or dynamic, and prefers static typing only for reasons of efficiency (which was, after all, of overwhelming importance in 1967): <blockquote>It is natural to ask whether type is an attribute of an L-value or of an R-value—of a location or of its content. The answer to this question turns out to be a matter of language design, and the choice affects the amount of work, which can be done when a program is compiled as opposed to that which must be postponed until it is run.</blockquote> <p>Strachey does not mention type theory, because no one had yet realized that it could be applied to programs. That changed in the next year. <h3>1968: type theory</h3> <p>James Morris was the first to apply type theory to programming languages, in his 1968 <a href='http://dspace.mit.edu/bitstream/handle/1721.1/64850/23882173.pdf?sequence=1'>Lambda-calculus models of programming languages</a>. “A system of types and type declarations is developed for the lambda-calculus and its semantic assumptions are identified. The system is shown to be adequate in the sense that it permits a preprocessor to check formulae prior to evaluation to prevent type errors.” <p>He begins by explaining what types are and why they matter, using the term in the usual programming-languages sense: <blockquote><p>In general, the <dfn>type system</dfn> of a programming language calls for a partitioning of the universe of values presumed for the language. Each subset of this partition is called a type. <p>From a purely formal viewpoint, types constitute something of a complication. One would feel freer with a system in which there was only one type of object. Certain subclasses of the universe may have distinctive properties, but that does not necessiate an <i>a priori</i> classification into types. If types have no official status in a programming language, the user need not bother with declarations or type checking. To be sure, he must know what sorts of objects he is talking about, but it is unlikely that their critical properties can be summarized by a simple type system (e.g., prime numbers, ordered lists of numbers, ages, dates, etc.). <p>Nevertheless, there are good, pragmatic reasons for including a type system in the specifications of a language. The basic fact is that people <em>believe</em> in types. A number is a different kind of thing from a pair of numbers; notwithstanding the fact that pairs can be represented by numbers. It is unlikely that we would be interested in the second component of 3 or the square root of < 2,5 >. Given such predispositions of human language users, it behooves the language designer to incorporate distinctions between types into his language. Doing so permits an implementer of the language to choose different representations for different types of objects, taking advantage of the limited contexts in which they will be used. <p>Even though a type system is presumably derived from the natural prejudices of a general user community, there is no guarantee that the tenets of the type system will be natural to individual programmers. Therefore it is important that the type restrictions be simple to explain and learn. Furthermore, it is helpful if the processors of the language detect and report on violations of the type restrictions in programs submitted to them. This activity is called <dfn>type-checking</dfn>.</blockquote> <p>Then he switches without explanation to taking about static checkers, e.g: <blockquote>We shall now introduce a type system which, in effect, singles out a decidable subset of those <acronym title='well-formed expressions'>wfes</acronym> that are safe; i.e., cannot given rise to ERRORs. This will disqualify certain wfes which do not, in fact, cause ERRORS and thus reduce the expressive power of the language.</blockquote> <p>So the confusion between programming-language and type-theory senses of the word began with the very first paper to use the latter. <h3>1968: APL</h3> <p>APL-360 was the most popular dialect of APL. Its manual doesn't use the word “type”; it speaks of “representations” of numbers. But it considers these an implementation detail, not an important part of its semantics. <p>APL has a lot of unique terminology — <dfn>monad</dfn> and <dfn>dyad</dfn> for unary and binary operators, <dfn>adverb</dfn> and <dfn>conjunction</dfn> for high-order operators, and so on — so it's not surprising that it has its own word for types too. <h3>1970: Pascal</h3> <p>Wirth's 1970 definition of Pascal is, as usual, plain-spoken: “The type of a variable essentially defines the set of values that may be assumed by that variable.” (But there's that “essentially”, like Algol's “basically”.) <h3>1970-73: Lisp belatedly adopts the term</h3> <p>Like Fortran, early Lisps used the word “type”, but only in its ordinary English sense, never as a technical term. AIM-19, from 1960 or 1961, speaks of “each type of LISP quantity”, but doesn't use “type” unqualified. Similarly, the 1962 <a href="http://bitsavers.org/pdf/mit/rle_lisp/LISP_I_Programmers_Manual_Mar60.pdf">Lisp 1.5 Manual</a> uses the word for various purposes, but not as an unqualified term for datatypes. The most common use is for function types (<code>subr</code> vs. <code>fsubr</code>); there are “types of variables” (normal, <code>special</code>, <code>common</code>), but datatypes were not, apparently, considered important enough to talk about. They might not have even been seen as a single concept — there are awkward phrases like “bits in the tag which specify that it is a number and what type it is”, which would be simpler with a concept of datatypes. <p>This changed in the early 1970s. The 1967 <a href='ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-116a.pdf'>AIM-116a</a> and 1970 <a href='ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-190.pdf'>AIM-190</a> still don't use “type”, but the 1973 <a href='http://www.saildart.org/MACLSP.DBA%5BUP,DOC%5D1'>Maclisp manual</a> and 1974 <a href='http://www.softwarepreservation.org/projects/LISP/MIT/Moon-MACLISP_Reference_Manual-Apr_08_1974.pdf'>Moonual</a> do, and it consistently means “data type”. Most tellingly, they have <code>typep</code>, so the term was solidly ensconced in the name of a fundamental operator. <h3>1973: Types are not (just) sets</h3> <p>By 1973, the definition of types as sets of values was standard enough that James Morris wrote a paper arguing against it: “Types are not sets”. Well, not <em>just</em> sets. He was talking about static typechecking, and argued that checking for abstraction-safety is an important use of static typechecking. The abstract explains: <blockquote>The title is not a statement of fact, of course, but an opinion about how language designers should think about types. There has been a natural tendency to look to mathematics for a consistent, precise notion of what types are. The point of view there is extensional: a type is a subset of the universe of values. While this approach may have served its purpose quite adequately in mathematics, defining programming language types in this way ignores some vital ideas. Some interesting developments following the extensional approach are the ALGOL-68 type system, Scott's theory, and Reynolds' system. While each of these lend valuable insight to programming languages, I feel they miss an important aspect of types. Rather than worry about what types are I shall focus on the role of type checking. Type checking seems to serve two distinct purposes: authentication and secrecy. Both are useful when a programmer undertakes to implement a class of abstract objects to be used by many other programmers. He usually proceeds by choosing a representation for the objects in terms of other objects and then writes the required operations to manipulate them.</blockquote> <h3>1977: ML and modern static typing</h3> <p>ML <a href='http://arcanesentiment.blogspot.com/2012/05/when-was-ml-invented.html'>acquired its type system in about 1975</a> and was published in 1977. Until this point, the application of type theory to programming languages had been theoretical, and therefore had little influence. ML made it practical, which has probably contributed a lot to the terminological confusion. <p>ML's theoretical support (along with the misleading slogan “well-typed expressions do not go wrong”) came out in the 1978 paper <a href='http://geofft.mit.edu/p/milner-type-poly.pdf'>A Theory of Type Polymorphism in Programming</a>, which despite being about type theory, speaks of types containing values: <blockquote>Some values have many types, and some have no type at all. In fact “wrong” has no type. But if a functional value has a type, then as long as it is applied to the right kind (type) of argument it will produce the right kind (type) of result—which cannot be “wrong”! <p>Now we wish to be able to show that—roughly speaking—an Exp expression evaluates (in an appropriate environment) to a value which has a type, and so cannot be wrong. In fact, we can give a sufficient syntactic condition that an expression has this robust quality; the condition is just that the expression has a “well-typing” with respect to the environment, which means that we can assign types to it and all its subexpressions in a way which satisfies certain laws.</blockquote> <h3>The short version</h3> <p>So here's the very brief history of “type” <span class=edit>in programming languages</span>: <ol><li>It wasn't used at all until 1958. <li>Types as sets of values: Algol-58. <li>The type-theory sense: Morris 1968. </ol> <p>These may not be the earliest uses. I got most of the old manuals from <a href='http://www.softwarepreservation.org/projects/lang'>Paul McJones' collection</a>, which is a good place to look for more. I welcome antedatings. <p>I'm also curious about the term “datatype”, which might plausibly be ancestral to “type”. I could find no uses of it older than “type”, but I may be looking in the wrong field. Statistical data processing is much older than computing, and has dealt with datatypes for a long time. Might the terms “datatype” and “type” have originated there? <p class=edit>Update August 2015: Jamie Andrews said much the same <a href='http://lists.seas.upenn.edu/pipermail/types-list/2014/001781.html'>seven months earlier</a>. <p class=edit>Update June 2017: In <a href='https://news.ycombinator.com/item?id=14402778'>HN comments</a>, dvt found <a href=' http://arcanesentiment.blogspot.com/2017/06/antedating-datatype-all-way-to.html'>“datatype” in 1945, in Plankalkül</a>. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/fUdBorTivNs" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com5http://arcanesentiment.blogspot.com/2015/01/a-brief-history-of-type.htmltag:blogger.com,1999:blog-6454006.post-11178457846676280422015-01-18T18:00:00.001+00:002015-01-22T02:05:36.554+00:00Incorrect optimization in 1963<p>Floating-point users today are accustomed (or resigned, sometimes) to compilers that make invalid optimizations by assuming all arithmetic is mathematically correct instead of rounding. The situation used to be worse. A 1963 IBM <a href='http://archive.computerhistory.org/resources/text/Fortran/102663119.05.01.acc.pdf'>Fortran II manual</a> warns that it did this for integers too: <blockquote><p>FORTRAN assumes that <em>mathematically</em> equivalent expressions are computationally equivalent. Hence, a sequence of consecutive multiplications, consecutive divisions, consecutive additions, or consecutive subtractions, not grouped by parentheses will be reordered, if necessary, to minimize the number of storage accesses in the object program. <p>Although the assumption concerning mathematical and computational equivalence is virtually true for floating point expressions, special care must be taken to indicate the order of fixed point multiplication and division, since fixed point arithmetic in FORTRAN is “greatest integer” arithmetic (i.e., truncated or remainderless). Thus, the expression <pre><code>5*4/2</code></pre> <p>which by convention is taken to mean [<code>(5 × 4)/2</code>], is computed in a FORTRAN object program as <pre><code>((5/2)*4</code></pre> <p>i.e., it is computed from left to right after permutation of the operands to minimize storage accesses. <p>The result of a FORTRAN computation in this case would be 8. On the other hand, the result of the expression <code>(5 × 4)/2</code> is 10. Therefore, to insure accuracy of fixed point multiplication and division, it is suggested that parentheses be inserted into the expression involved.</blockquote> <p>(Reordering “to minimize the number of storage accesses” is pointless in a constant expression, but apparently the optimizer did it anyway.) <p>If this reordering can be prevented by redundant parentheses, then parentheses don't only affect parsing; they change semantics by introducing a barrier against algebraic transformations! <p>Giving parentheses this additional meaning has an unfortunate effect: other optimizations can no longer ignore them. The manual continues by describing one such problem: <blockquote><p>One important type of optimization, involving common subexpressions, takes place only if the expression is suitably written. For example, the arithmetic statement <pre><code>Y = A*B*C + SINF (A*B)</code></pre> <p>will cause the object program to compute the product <code>A*B</code> twice. An efficient object program would compute the product <code>A*B</code> only once. The statement is correctly written <pre><code>Y = (A*B) * C + SINF (A*B)</code></pre> <p>By parenthesizing the common subexpression, <code>A*B</code> will be computed only once in the object program. <p>In general, when common subexpressions occur within a expression, they should be parenthesized. <p>There is one case in which it is not necessary to write the parentheses, because FORTRAN will assume them to be present. These are the type discussed in “Hierarchy of operations,” and need not be given. Thus <pre><code>Y = A*B+C+SINF (A*B)</code></pre> <p>is, for optimization purposes, as suitable as <pre><code>Y = (A*B)+C+SINF (A*B)</code></pre></blockquote> <p>I'm not sure whether the problem is simply that <code>A*B*C</code> does not contain the subexpression <code>A*B</code>, or that the <acronym title='common sub-expression'>CSE</acronym> lifter sees it but can't merge it with <code>(A*B)</code> because they're not equivalent in all contexts. <p>Optimizers today still have limitations, and still make invalid transformations, but they've become much more subtle!<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/70jdRgfQ1uY" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2015/01/incorrect-optimization-in-1963.htmltag:blogger.com,1999:blog-6454006.post-5992293729888452512015-01-03T21:29:00.001+00:002015-01-03T21:29:13.086+00:00Errors are not the same as incorrectness<p>Program checkers, if they are to check objective properties rather than the prejudices of their authors, must ground their judgements in some aspect of programs' behavior. (Or in their maintainers' behavior, but that's much harder to prove anything about.) Usually the property they check is whether the program will have errors at runtime. If it will fail dynamically, then the checker judges it a bad program statically. <p>This is an obvious premise, and it's the standard justification for all sorts of program checking, but it's not necessarily true, as Andreas Rossberg <a href='http://lambda-the-ultimate.org/node/5086'>points out</a>: <blockquote><p>Take the following degenerate program for computing travel routes: <pre><code>ComputeAndDisplayTravelRoute(inputs); "boo" - 1;</code></pre> <p>This will throw a type error on the second line, and a tool like Dialyzer would (correctly) diagnose that (it's obviously trivial in this case). However, before this error is raised, the program actually successfully completes its designated job, namely computing a travel route and displaying it to the user. Yet such a program is defined as "invalid". I'm asking why.</blockquote> <p>Crashing on exit is a fairly common problem. (Games seem particularly prone to this, perhaps because graphics has so much hardware-dependent setup and teardown.) It doesn't usually cause any problem for the user, so it's not a high priority to fix. But the usual standard of program checking considers it unforgiveable. <p>Programs that produce errors (of any kind, not just type errors) are <em>usually</em> much worse than programs without. But not always. The properties we check are only an approximation to the ones we care about. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/rz2Vk7IUjvo" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com2http://arcanesentiment.blogspot.com/2015/01/errors-are-not-same-as-incorrectness.htmltag:blogger.com,1999:blog-6454006.post-22140976499682743582015-01-03T00:00:00.004+00:002015-01-18T18:30:37.446+00:00If Scheme were like Scheme<p>Scheme's numbers are not like the rest of its library. They're older, and they're mostly borrowed from other languages (Maclisp and Common Lisp), so they follow those languages' style rather than Scheme's. They're designed more for the convenience of users than of theorists; they have a usefully complete feature set; they have a printed representation; their operations are predefined and polymorphic and have very short names. <p>What would Scheme be like if numbers followed the same style as the rest of the language? <p>It would be necessary to import a library before using any numbers. <pre><code>(import (scheme numbers))</code></pre> <p>Numeric constants would be provided as functions returning the constant, apparently because the section of R<sup>N</sup>RS they appear in is called “Standard Procedures”. Only the most basic constants would be provided; <code>pi</code> would not be among them. <pre><code>(define (exact-rational-zero) (make-exact-rational (exact-integer-zero) (exact-integer-one)))</code></pre> <p>Numbers would have no printed representation. Creating them would require explicit constructor calls. <p>There would be no polymorphism. Most operations would include a type in their name. <pre><code>(define (factorial n) (if (exact-integer&lt;=? n (exact-integer-one)) (exact-integer-one) (exact-integer-multiply! (factorial (exact-integer-subtract n (exact-integer-one))) n)))</pre></code> <p>The distinction between exact and inexact numbers would <em>still</em> be supposedly “orthogonal to the dimension of type”. But the lack of polymorphism would make it even more obvious that in practice exactness was simply one of the type distinctions: that between floats and everything else. <p>Floating-point numbers would be called “inexact rationals”. Their constructor would take a numerator and denominator, just like exact rationals; their floating-point representation would be considered an implementation detail. Various details of the specification would be inconsistent with IEEE floating point. <p><code>NaN</code> would not be a number, of course. <code>inf.0</code> and <code>-inf.0</code> would be exact transfinite numbers, not inexact rationals. There would be no negative zero. <p>Names would be <em>descriptive</em>, like <code>inexact-rational-square-root</code> and <code>exact-integer-greatest-common-divisor</code>. <p>There would be <code>exact-integer-&gt;list</code> and <code>list-&gt;exact-integer</code> operations to convert to and from lists of digits (in arbitrary bases). Converting the lists into strings would be up to you. Converting anything other than exact integers to strings would also be up to you. <p>Numbers would be portably mutable. Some operations would have destructive versions. (If we did this exercise on Python, some would have <em>only</em> destructive versions.) Racket would omit these, supposedly to make optimization easier, but would have separate mutable numbers for programs that need them. <p>Operations more obscure than <code>exponent</code> would be left to SRFIs. Users would be able to choose between the widely supported SRFI and the complete SRFI. <p><code>exact-integer-divide</code> would not be provided, on the grounds that it's not defined for all integers, and can't be implemented efficiently without special hardware. <p>There would be a portable way to use exact integers as indexes into lists, but not into vectors or strings. This would be remedied in R<sup>7</sup>RS. <p>Some implementations would support surprisingly obscure and practical floating-point operations, while omitting basic operations their authors never needed. <pre><code>(define (numerically-stable? thunk tolerance) "Run a floating-point computation with various rounding modes to see if this significantly changes the result. This is not a reliable test of numeric stability, but it's an easy way to find bugs." (let ((down (call-with-rounding-mode round-down thunk)) (up (call-with-rounding-mode round-up thunk)) (nearest (call-with-rounding-mode round-to-nearest thunk)) (zero (call-with-rounding-mode round-to-zero thunk)) (roughly-equal? (lambda (a b) (inexact-rational&lt;=? (inexact-rational-absolute-value (inexact-rational-subtract a b)) tolerance))))) (and (roughly-equal? down up) (roughly-equal? down nearest) (roughly-equal? down zero) (roughly-equal? up nearest) (roughly-equal? up zero) (roughly-equal? nearest zero)))</pre></code> <p>There would be debates about whether <code>eq?</code> should “work” on numbers. This would really be about whether numeric operations should always return fresh numbers, and whether the compiler would be allowed to copy them, but no one would mention these merely implementational issues. <p><code>eqv?</code> and <code>equal?</code> would compare numbers, even immutable ones, by identity. Hashtables would — OK, standard Scheme doesn't have hashtables. But if it did, the default hash function would hash numbers by identity, not by value. <p>Arithmetic overflow would still be “a violation of an implementation restriction”. There would still be no way to find out how large a number could safely be. <p>There would still be no bitwise operations on integers. Schemers who understood the purpose would advise using an implementation that supports bitvectors instead of abusing numbers. Those who did not would say they're easy to implement. <pre><code>(define two (exact-integer-add (exact-integer-one) (exact-integer-one))) (define (exact-integer-bitwise-and a b) (list-&gt;exact-integer (map exact-integer-minimum (exact-integer-&gt;list a two) (exact-integer-&gt;list b two))))</code></pre> <p>Complex numbers would, mercifully, be left to a SRFI. The SRFI number would be real, but in most implementations complex-number support would be purely imaginary. <p>All the comparison predicates would end in <code>?</code>. <p class=edit>Edit: Replaced some stray uses of <code>&lt;=</code> and <code>+</code> and <code>min</code> with their counterfactual-Scheme equivalents. <p class=edit>In the <a href='https://news.ycombinator.com/item?id=8869574'>HN comments</a>, cousin_it says: <blockquote class=edit>We can see similar examples in other languages, e.g. C++ strings are "like C++" and a pain to use, while Java strings are "not like Java" and a pleasure to use. Maybe language design really isn't about general-purpose elegance, but about finding good special-purpose solutions.</blockquote> <p class=edit>Or about using the good general-purpose solutions you already have.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/zVPDFY97LqQ" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com1http://arcanesentiment.blogspot.com/2015/01/if-scheme-were-like-scheme.htmltag:blogger.com,1999:blog-6454006.post-39035363595213012582015-01-01T23:59:00.003+00:002015-01-02T00:04:53.479+00:00Parentheses are more annoying in infix<p>There's a lot of code in functional languages written with a C or Java accent. The reverse is much rarer, but I have seen some: C++ written with a Lisp accent. <p>I didn't like it. <p>I didn't like the <code>fooP</code> convention for predicates. I didn't like the large multi-line expressions. And I especially didn't like the redundant parentheses. <p>What? A lisper doesn't like parentheses? <p>Parens are not high on the list of things that bother me in Lisp. They're only a little verbose, only a little distracting, only a little trouble to match. Large expressions don't bother me either; they're clearer than the alternative. And I <em>like</em> <code>foo-p</code>, because it's short and pronounceable. <p>Was I just objecting to C++ that didn't look like C++? Was I offended by contact between pretty Lisp and icky C++? <p>For <code>fooP</code>, that's probably the whole of it. It's camelCase instead of hyphenated, so it looks wrong as Lisp, and it's not standard C++ style, so it looks wrong as C++. And I'd rather not have to explain to other C++ programmers why I'm using a convention from some weird academic language. But I don't have a substantive objection. <p>For the other two features, I do. <p>Large expressions in prefix notation are easy to parse. The root operator is plainly visible at the beginning, and indentation goes a long way toward making the structure clear. Large expressions in infix are not so easy. The root operator is buried somewhere in the middle, and one must parse much of the expression to find it. There's no easy way to indent infix expressions, so breaking an expression across multiple lines doesn't alleviate much of the parsing load. This is why programmers in infix languages usually prefer to break such expressions into multiple statements. <p>Parentheses in Lisp are consistent: they all delimit lists, and almost all delimit forms. The semantics of the forms may be arbitrarily variable, but those of the parens are always the same. In C++, however, parentheses have several different meanings. They sometimes override precedence, sometimes call (or declare) functions, sometimes do typecasts, and sometimes delimit conditions in control structures. So a nest of parentheses in C++ is much more ambiguous than in Lisp, and it takes more parsing effort to determine which ones are which. <p>This goes some way toward explaining why so many programmers are suspicious of Lisp's syntax. Large expressions and nests of parentheses are suspicious in infix languages, and this suspicion does not instantly vanish in a new language. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/nOEnd9eRAeg" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com3http://arcanesentiment.blogspot.com/2015/01/parentheses-are-more-annoying-in-infix.htmltag:blogger.com,1999:blog-6454006.post-43438384840209505862014-12-31T23:59:00.001+00:002015-01-01T01:42:26.384+00:00Effects vs. side effects<p>Commonly used terms get abbreviated. Thus functional programmers often say “effect” instead of “side effect”. I approve of this usage – not only because it's shorter, but because it frees up “side effect” for another concept. This is something assembly language programmers know, and have known for decades, that other programmers seldom speak of. <p>Most machines have no notion of a return value; the only way for parts of a program to communicate is by mutating registers. So assembly language programs must do all their communication by effect. This means they distinguish between different kinds of effect. In particular, they distinguish effects that are part of a routine's contract from those that, however consistent, are not intentional: <dfn>side effects</dfn>. <p>Consider this implementation of <code>factorial</code> on a typical register machine: <pre><code>;The factorial function, iteratively ;args: r1 = n ;results: r2 = n! ;All other registers are preserved. <b>factorial</b>: <abbr title='load immediate'>li</abbr> r2, 1 loop: <abbr title='compare to immediate'>cmpi</abbr> r1, 1 <abbr title='branch if less than or equal'>ble</abbr> done mul r2, r2, r1 sub r1, r1, 1 <abbr title='branch'>b</abbr> loop done: ret</code></pre> <p>This function leaves its result in r2, but also happens to set r1 to 1. This is a <dfn>side effect</dfn>: an effect not in the routine's contract. It is, of course, a bad idea to rely on these, but by accident or desperation, assembly programmers occasionally do, which is why they have a name for them. <p>(Recursive factorial is more complex than iterative on most machines – often absurdly so, if you strictly follow an ABI that wants you to save registers and construct stack frames. This is one of the reasons programmers accustomed to low-level languages don't take readily to recursion. To them, it looks unnecessarily complex, because it <em>is</em> complex in implementation. High-level languages hide this complexity, but low-level programmers know it's still there.) <p>It's not normal for programs in higher-level languages to have side effects in this sense, because they have fewer ways to accidentally have effects. Supposedly unobservable effects like preloading caches are common (and are occasionally relied on), but typically any observable effect that isn't part of the interface is a bug. So this concept is less useful in higher-level languages. The more general concept of relying on unspecified behaviour remains useful, though, and it's quite familiar from discussions of language specs. <p>Functional programming advocacy suffers from a focus on purity, where state is considered a sin to be avoided absolutely. One way the movement might make progress is to distinguish between different kinds of effects, so they could say which ones are deadly and which are venial, rather than treating all effects as indistinguishable evil. Vocabulary analogous to the assembly language programmers' “side effect” might help with this.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/AfhCzEtpaeI" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com1http://arcanesentiment.blogspot.com/2014/12/effects-vs-side-effects.htmltag:blogger.com,1999:blog-6454006.post-51967743403478239532014-12-31T23:35:00.003+00:002014-12-31T23:35:48.988+00:00Customary semantics<p>What is the <em>real</em>, definitive semantics of a language? There are three standard answers: <ol><li>The natural-language specification, because it's the one the designers understand. <li>The reference implementation, because it's unambiguous and well-tested. <li>The formal semantics (of whichever flavor), because it avoids implementation concerns, so it's simpler than a real implementation. (Or because it's difficult and therefore “rigorous”.) </ol> <p>There's a controversial fourth option: <em>the definitive semantics of a language is the behavior that is consistent across all conventional implementations.</em> <p>This approach has some virtues: <ul> <li>It identifies the behavior you can rely on. Implementations have bugs and deliberate deviations from the spec, where you can't rely on the specified behaviour. They also have widely supported extensions which you <em>can</em> rely on, even though they're not in the spec. <li>Unlike any other means of defining semantics, implementations are heavily tested. Formal semantics can be tested by <a href='http://webcache.googleusercontent.com/search?q=cache:S0Z7mbbWu4EJ:www.appsolutions.com/SchemeDS/semantic-functions.scm'>turning them into implementations</a>, but seldom are; natural-language specifications aren't mechanically tested at all. <li>It's reconstructable. Users can always find out what their implementations do, even when the spec is not publicly available, or is difficult to read. (Most specs are.) Sometimes this shows them implementation-dependendent behavior, but by comparing implementations they can discover the customary semantics. </ul> <p>Deferring to custom is unpopular among language designers and theorists. We see it as an ill-defined, unstable foundation about which nothing can be known with confidence, and on which nothing can be built reliably. We remember the chaos that engulfed HTML and CSS and Javascript when their users treated buggy implementations as specs, and we don't want it to happen again. We want our semantic questions to have authoritative answers, and mere custom does not provide that. <p>But it's the de facto standard among <em>users</em> of languages. Most programmers are not language lawyers, and can't readily figure out whether the spec says their code will work. But they can easily try it and see what happens. <p>We can tell users not to do this. We can tell them to avoid empiricism, to seek authority rather than evidence, to shut their lying eyes and trust in doctrine. This is not good advice in most areas, not even in other areas of programming, nor for semantics of other languages natural or artificial. Is it really good advice for programming languages? <p>Whether it's good advice or bad, users don't listen. Their models are based on the behaviour they observe. As a result, many popular “myths” about languages — that is, widely held beliefs that are officially supposed to be false — are true in the customary semantics. For example, here are some parts of C's customary semantics that are <strong>not</strong> part of the formal specification. Some of them are violated on unusual architectures, but most C users have never written for such an architecture, so custom doesn't care. <ul> <li>Signed integers are represented in two's complement. (<a href='http://blog.regehr.org/archives/1149#comment-15698'>Rumor has it</a> this is not quite always true.) <li>Signed integer overflow is modulo word size, like unsigned. <li>All pointer types have the same representation: an integer. <li><code>NULL</code> is represented as 0. <li>Memory is flat: it's all accessible by pointer arithmetic from any pointer. <li>Pointer arithmetic is always defined, even outside array bounds. Overflow is modulo word size, just like integers. <li>Dereferencing an invalid pointer, such as <code>NULL</code> or an out-of-bounds pointer, blindly tries to use the address. <li>Compilers generate native code. The built-in operators compile to machine instructions. <li><code>char</code> is exactly eight bits wide. <li>Characters are represented in a superset of ASCII. </ul> <p>(I thought <code>sizeof(char) == 1</code> was only in the customary semantics, but it's actually in the spec.) <p>Much of the furor over <a href='http://blog.regehr.org/archives/213'>optimizations that exploit undefined behaviour</a> is because they're invalid in the customary semantics. Some C compiler maintainers have come to believe that the spec is the whole of the contract between compilers and users, and thus that users don't care about semantics not defined therein. It's a convenient belief, since it permits optimizations that would otherwise be impossible, but it's wildly at odds with what their users want. This isn't the only problem with these optimizations — they make for perverse error behaviour under any semantics — but this is why users tend to see them as not merely bad but <em>incorrect</em>. <p>Language lawyers, especially those who write specs, should take customary semantics more seriously, so they don't contradict the semantics in actual use. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/Nbyfin8Rkwk" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com2http://arcanesentiment.blogspot.com/2014/12/customary-semantics.htmltag:blogger.com,1999:blog-6454006.post-67484530137240657182014-12-29T00:00:00.000+00:002014-12-29T00:00:56.855+00:00Why is breadth-first numbering hard?<p>John Launchbury gave Chris Okasaki <a href='http://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/breadth-first.pdf'>an annoying puzzle</a>: <blockquote>Given a tree <var>T</var>, create a new tree of the same shape, but with the values at the nodes replaced by the numbers 1 .. |<var>T</var>| in breadth-first order.</blockquote> <p>Go ahead and solve it. I'll wait. <p>If you want to solve it <em>functionally</em>, I'll wait longer. <p>Chris posed this puzzle to many functional programmers, and found that they had a surprisingly hard time with it. They took a long time to solve it, and their solutions were seldom elegant. He came up with various hypotheses as to why: did the programmers not know breadth-first traversal or queues? Did they prematurely commit to lists or pattern matching? He didn't seem to find any of them convincing. Neither do I. <p>One hypothesis he didn't mention is that most functional programmers see a recursive data structure and immediately try to process it by straighforward structural recursion, with a call tree isomorphic to the data structure. When you have many tools, and you encounter a nail, you reach for your hammer, right? But in this case structural recursion is the wrong tool, and it takes a while for programmers to backtrack far enough to notice. <p>It may take even longer for them to identify the right tool. Queues, like hashtables, are a little awkward for functional programmers, because their most natural implementations are stateful, as are many of their applications. They're almost always used linearly (i.e. there's only one version of the queue at a time), so eschewing state buys no useful flexibility, and incurs the extra hassle of explicitly passing the updated queue around. It also prevents using the efficient circular-buffer representation, just as it usually prevents using hashtables. <p>They're also a little awkward to use in functional languages, because none of the most familiar and widely implemented functional data structures (lists, tree dictionaries, tree sets, tries) is easily used as a queue, so would-be queue users must look up a queue library, or build one, or use pairs of lists (if they know this trick), or use some inappropriate data structure, or give up and use some other algorithm. Which is what most of Chris's subjects did. <p>Meanwhile, Java users use its ordinary <a href='http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html'><code>LinkedList</code> class</a> (which is a doubly-linked list, and thus a reasonably efficient deque) to <a href='http://xathis.com/posts/ai-challenge-2011-ants.html'>win contests</a> without having to worry about any of this. Can your functional language do as well? <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/IxumWa6YODo" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com3http://arcanesentiment.blogspot.com/2014/12/why-is-breadth-first-numbering-hard.htmltag:blogger.com,1999:blog-6454006.post-62515480577725959442014-04-29T23:52:00.000+00:002014-04-29T23:52:43.122+00:00“Persistent” is older than I thought<p>“Persistent” usually refers to data that persists across multiple executions of a program. But in the last few years I've occasionally heard it used, especially in the Clojure community, for data structures that are updated nondestructively. (The old version <em>persists</em> after the update — get it?) <p>I saw this as a newfangled sloppy usage, but it ain't so. Like many seemingly new usages, it's surprisingly old. It dates back at least to 1985, when it appears prominently in Sarnak &amp; Tarjan's <a href='http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf'>Planar Point Location Using Persistent Search Trees</a>. It was popularized a few years later by the same authors plus two others in <a href='http://divespot.ca/~morin/teaching/5408/refs/persistence.pdf'>Making Data Structures Persistent</a>, and Tarjan has used it many times since then. <p>The more common sense — data that persists across program executions — is not much older. The earliest uses I've found are from several papers in 1976. Earlier ones are about either persistence of phosphors (an important issue for <acronym title='cathode ray tube'>CRT</acronym>s) or fault-tolerance by <dfn>persistently</dfn> retrying. It apparently caught on quickly, at least in the database community, because Jim Gray's 1977 <a href='http://web.cs.wpi.edu/~cs502/cisco11/Papers/Gray_Database_OS.pdf'>Notes on Data Base Operating Systems</a> takes it as standard enough to use without bothering to define it. <p>So it's reasonable to object to “persistent”=“nondestructive” because it conflicts with a more important concept, but not because it's new. <p>Maybe now someone will tell me it's in some very standard source like Knuth and I never noticed... <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/2gmixe04LYo" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2014/04/persistent-is-older-than-i-thought.htmltag:blogger.com,1999:blog-6454006.post-74812536524786951472014-04-28T00:16:00.003+00:002014-04-28T01:57:21.889+00:00A sound bug finder is an unsound correctness prover<p><a href='http://cacm.acm.org/magazines/2010/2/69354-a-few-billion-lines-of-code-later/fulltext'>This account</a> of Coverity, a commercial bug-finding tool for C and C++, illustrates a peculiar attitude common in the program-checking field: <blockquote>we were also unsound. Our product did not verify the absence of errors but rather tried to find as many of them as possible. Unsoundness let us focus on handling the easiest cases first, scaling up as it proved useful. We could ignore code constructs that led to high rates of false-error messages (false positives) or analysis complexity, in the extreme skipping problematic code entirely (such as assembly statements, functions, or even entire files). Circa 2000, unsoundness was controversial in the research community, though it has since become almost a de facto tool bias for commercial products and many research projects.</blockquote> <p>Most program checkers prove theorems about programs. In particular, most aim to prove programs correct in some respect (e.g. type safety). A theorem prover is sound iff all the theorems it proves are true. So a correctness-prover that claims a buggy program is correct is unsound, but one that rejects a correct program is not. People in the program-checking field are accustomed to this, so they habitually think soundness = proving the absence of bugs. <p>But a bug-finder doesn't aim to prove correctness. Instead, it aims to prove <em>incorrectness</em>: to prove the presence of bugs. It's sound iff all the bugs it reports are real bugs — that is, if it has no false positives. False negatives (overlooking bugs) are OK, because they don't make its claims incorrect. <p>Unfortunately, most interesting properties are undecidable, so a checker can't be sound at both bug-finding and correctness-proving, unless its claims are very weak. <p>So Coverity did the right thing, in theory as well as practice, when they focused on suppressing false positives. Their bug finder was unsound, but it was unsound because it reported spurious errors, not because it missed some real bugs. <h3>Addendum: bug finders in languages</h3> <p>The most visible bug finders (especially in academia) are those, like the ML typechecker, that try to prove something about the program, and report a bug if they fail. These are unsound as bug finders, since they sometimes report nonexistent bugs. Unfortunately, bug finding is their main use, so their standard of soundness does not fit. <p>This is particularly problematic for checkers that are built in to a compiler, and don't just complain but prevent programs from running. (This is part of why they're so visible — if the checker makes mistakes you can't ignore, you have to be aware of it.) It's hard (especially in theory) to justify a compiler that rejects correct programs. Sound bugfinders don't have this problem. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/tB0Dr60lLKA" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2014/04/a-sound-bug-finder-is-unsound.htmltag:blogger.com,1999:blog-6454006.post-79502081025981885982014-04-17T04:48:00.000+00:002014-04-17T04:49:34.831+00:00Why Lambda the Ultimate doesn't make me feel stupid<p>This search term appeared in my referer logs a few years ago: “lambda the ultimate makes me feel stupid”. <p>I used to feel that way — at least, I felt ignorant and despised. The denizens of LtU know an intimidating amount of theory, and some are quick to scorn anyone who doesn't, and demand that they read heaps of literature (often of dubious quality or relevance) before being permitted to talk. Not having read most of that literature, I accepted their evaluation, and felt ignorant. <p>But then battles of the War of Types erupted there, and λ the Ultimate became λ<sub>T</sub> the Ultimate, or even System F the Ultimate. Anyone who dared suggest that dynamic typing was a reasonable basis for a language, or even a meaningful concept, faced voluminous condescension and condemnation. The seemingly knowledgeable scholars appeared to neither know nor care about the fundamental concepts of their field, and treated its greatest successes with learnèd disdain. <p><a href='http://itre.cis.upenn.edu/~myl/languagelog/archives/000124.html'>I do respect very much the elephant</a>, and if your work dismisses him as an ill-formed dinosaur, it is not zoology. <p>(I don't think the dynamic typists gave a good account of themselves either; there was lots of handwaving about flexibility and little mention of the importance of simple semantics. But I found them less offensive, not only because I agree with them, but because they didn't demand the anathematization of the other side, nor of the object of study.) <p>The War of Types subsided, and LtU became once more a place of academic quiet, disturbed only by announcements of new PL papers. It still makes me feel ignorant at times, but it no longer makes me feel stupid. Sometimes it even makes me feel <em>wise</em>. Which is a much more dangerous emotion. When I feel stupid or ignorant, I study to become less so, but when I feel wise, I do nothing.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/j1YKe_eDnKY" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com2http://arcanesentiment.blogspot.com/2014/04/why-lambda-ultimate-doesnt-make-me-feel.htmltag:blogger.com,1999:blog-6454006.post-74649572365710987162014-04-16T16:31:00.000+00:002014-04-16T16:31:17.347+00:00Exceptions are (mostly) for humans<p>Most languages have a way to signal a generic error with a string as the error message. This makes it easy to include relevant information in the description of the error: something as simple as <code>(error "serve-ice-cream: quantity=~S must be positive" q)</code> provides a human-readable description with whatever information you think is relevant. It's not machine-readable, but most errors don't need to be handled mechanically, so this is not usually a problem. <p>Languages with exception systems also allow signalling errors in a machine-recognizable way, typically by defining a new exception class. This is often considered the “proper” way to signal errors, but it's more work than a generic error, so it's typically done only for polished public interfaces. Errors that aren't exposed in such an interface (or aren't <em>intended</em> to be exposed — errors are a kind of implementation detail that's hard to hide) generally make do with strings. <p>When you do create an exception class, it's also more work to include relevant information in the exception. Typically you have to define slots, arrange for them to get the appropriate values, and then embed them in the error message. This requires changing several parts of the definition as well as the call site, so it's enough trouble that you often won't do it. Error reporting code is seldom high on the priority list until the error happens. <p>I ran into this problem a while ago, in a utility function which reported a rare error by throwing a C++ exception class like this: <pre><code>class negative_error : public domain_error { public: not_integer_exn() : domain_error("value must not be negative") {} };</code></pre> <p>This was fine until the error finally happened. A high-level catch-almost-anything handler caught the exception and displayed the error message, which told me almost nothing about the problem. Since this was C++ and not running under a debugger, there was no automatic stack trace, and no hint of <em>what</em> value was negative, or who cared, or why. If I had been lazy and signaled the error with <code>throw domain_error("serve_ice_cream: quantity=" + to_string(q) + " must not be negative")</code>, the relevant information would have been in the string, but because I had done it the “right” way, it was not. <p>(The designers of C++ are aware of this problem. That's why all the standard exceptions take strings. <code>negative_error</code> should have too.) <p>In an ideal exception system, convenience and machine-readability would not conflict. It should be easy to signal an an-hoc error with a human-readable message <em>and</em> machine-recognizable fields. It might help to allow throwing exceptions without declaring them first, e.g. <code>(throw '(negative-error domain-error) :quantity q "value must not be negative")</code>. (Wasn't this allowed in some early exception systems?) But if it's only easy to have one of the two, choose the convenient human-readable form. That's the one you'll use.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/7IPRNg77-2k" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com1http://arcanesentiment.blogspot.com/2014/04/exceptions-are-mostly-for-humans.htmltag:blogger.com,1999:blog-6454006.post-16201544680012999952014-04-15T05:19:00.001+00:002014-04-15T05:28:00.672+00:00What happened to “manifest” and “latent”?<p>Chris Strachey has remarkably influential lecture notes. His 1967 <a href='http://www.itu.dk/courses/BPRD/E2009/fundamental-1967.pdf'>Fundamental Concepts in Programming Languages</a> introduced or popularized a lot of now-standard terminology: <dfn>r-value</dfn> and <dfn>l-value</dfn>, <dfn>first-class</dfn>, <dfn>polymorphism</dfn> (<dfn>ad-hoc</dfn> and <dfn>parametric</dfn>), and maybe <dfn>parametric type</dfn>. <p>It also introduced some terms which didn't catch on, among them <dfn>manifest</dfn> and <dfn>latent</dfn>: <blockquote>We call attributes which can be determined at compile time in this way <dfn>manifest</dfn>; attributes that can only be determined by running the program are known as <dfn>latent</dfn>.</blockquote> <p>These are the concepts now called “static” and “dynamic”. I'm not sure why Strachey bothered to introduce his own words for them, since the standard ones already existed, and he was evidently more comfortable with them — when he discusses types on the same page, he consistently uses “dynamic”, not “latent”. (Was “dynamic typing” already a standard term by 1967?) Maybe he reserved “static” and “dynamic” for behaviour, and wanted different words for the time when a property could be determined. <p>He acknowledges that the boundary between static and dynamic is fuzzy, and explains why it's useful anyway: <blockquote>The distinction between manifest and latent properties is not very clear cut and depends to a certain extent on questions of taste. Do we, for example, take the value of <code>2 + 3</code> to be manifest or latent? There may well be a useful and precise definition—on the other hand there may not. In either case at present we are less interested in the demarkation problem than in properties which are clearly on one side or other of the boundary.</blockquote> <p>I wish more academics dared to do that. <p>Neither “manifest” nor “latent” caught on, and they might have been forgotten like most new coinages — but decades later, both have been resurrected with new meanings in connection with type. “Manifest typing” now refers to languages that require type declarations — an important concept that lacked a short name. “Manifest” is readily reinterpretable as “appearing in source”, and while it might confuse people who remember the old sense, we are few. Less usefully, “latent typing” serves as a euphemism for “dynamic typing” among type-theory partisans (bizarrely, as the word they object to is “type”, not “dynamic”, but at least it avoids using the terminology of the savages). In neither case does Strachey's original meaning survive; if you speak of some property other than type as “manifest” or “latent”, most proglang researchers will not understand. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/q5A6JZcQzcA" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2014/04/what-happened-to-manifest-and-latent.htmltag:blogger.com,1999:blog-6454006.post-49346831081588368462013-12-30T00:35:00.001+00:002013-12-30T17:22:09.240+00:00Where do closures come from?<p>Common Lisp's <code>function</code> form is usually described as a device for switching between namespaces: it evaluates its argument in the “function” namespace instead of the normal “variable” namespace. <p>Older sources have a completely different idea: they say <code>function</code> makes closures. The <a href='http://www.lispworks.com/documentation/HyperSpec/Body/s_fn.htm'>Hyperspec</a> says: <blockquote>If <var>name</var> is a lambda expression, then a lexical closure is returned.</blockquote> <p>and <blockquote><code>function</code> creates a closure of the <code>lambda</code> expression</blockquote> <p>Both of these lines were inherited from <acronym title='Common Lisp: the Language'>CLtL</acronym>, so this is not a new interpretation, nor one incompatible with the best of knowledge. What's going on? <p>To begin with, these two interpretations of <code>function</code> aren't observably different in portable Common Lisp. The only portable way to get a closure is by <code>(function (lambda ...))</code> or by macros like <code>defun</code> that might expand to it. (<code>(lambda ...)</code> expands to <code>(function (lambda ...))</code>, because unlike all other special forms, <code>lambda</code> is in the function namespace, but that's just a historical quirk.) The only way to use <code>lambda</code> without <code>function</code> is <code>((lambda ...) ...)</code>, which has the same semantics regardless of whether it makes a closure. So portable code can't tell the difference. <p>Implementation-specific extensions can. If <code>compile</code> is extended to non-null lexical environments, it will make closures out of <code>lambda</code>-expressions without any help from <code>function</code>. Or if there's a <code>named-lambda</code> form that makes closures, it's unnecessarily complex to attribute the closure in <code>(function (lambda ...))</code> to <code>function</code>. <p>So Common Lisp culture favors the simpler interpretation: <code>lambda</code> makes closures, and <code>function</code> is a mere namespacing operator. <p>Like so many oddities of CL, the old interpretation comes from Lisp Machine Lisp. The <a href='http://bknr.net/static/lmman/fd-eva.xml#function-fun'>1984 Lisp Machine Manual</a> introduces <code>function</code> by saying it “has two distinct, though related, meanings.” The first is to get a symbol's function definition, and the second is to make a closure: <blockquote><pre><code>(let (a) (mapcar (function (lambda (x) (push x a))) l))</code></pre> passes <code>mapcar</code> a specially designed closure made from the function represented by <code>(lambda (x) (push x a))</code>. When <code>mapcar</code> calls this closure, the lexical environment of the <code>function</code> form is put again into effect, and the <code>a</code> in <code>(push x a)</code> refers properly to the binding made by this <code>let</code>.</blockquote> <p>These two meanings were reflected in implementations. Guy Steele's reference interpreter (in the <a href='http://saildart.org/COMMON.2%5BCOM,LSP%5D'>CL mailing list archive</a>) doesn't bother to make a closure for <code>((lambda ...) ...)</code>, only for <code>(function (lambda ...))</code>. But when optimizing compilers became the norm, it no longer seemed silly (or inefficient) for <code>lambda</code> to always make a closure, so reinterpreting <code>function</code> as a namespacing operator made sense. <p>Surprisingly, this is not the first time <code>function</code> has been reinterpreted. <a href='http://www.maclisp.info/pitmanual/eval.html#3.6.1'>The Pitmanual says</a> Maclisp's <code>function</code> didn't make closures — it took a different form, <code>*function</code>, to even partially do that. <code>function</code> was equivalent to <code>quote</code>, except that in compiled code it would make a compiled function instead of just a lambda-expression — it permitted compilation but didn't change scoping. When Lisp Machine Lisp changed it to make closures, that was largely backward compatible, since most lambdas were intended to use lexical scope anyway. (I'm not sure when compilers started to use lexical scope — was that in Maclisp?) <p>I don't think any other language construct has had so many unrelated meanings over the years, let alone done so while preserving the meaning of existing code. <code>function</code> was originally a hint to the compiler, then a way to make closures, and then a namespacing operator. Its history probably ends there, since most new lisps eschew multiple namespaces and omit <code>function</code> rather than repurpose it, but three unrelated meanings is impressive. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/3a69fJkX97o" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com4http://arcanesentiment.blogspot.com/2013/12/where-do-closures-come-from.htmltag:blogger.com,1999:blog-6454006.post-52129645187141217352013-12-07T21:02:00.001+00:002013-12-07T21:02:32.386+00:00Trivial program checkers<p>Typecheckers get (and deserve) a lot of attention for their ability to find bugs, but their success leads people to think <em>type</em>checking is the only way to check programs. It's not. There are useful program checkers much simpler than any typechecker. Here's an example: <pre><code>grep scanf</code></pre> <p>This finds real bugs in real programs — and not just ordinary bugs, but security holes due to <code>%s</code> overflowing buffers. <p>Here's another checker: <pre><code>grep 'printf[^&quot;]*$'</code></pre> <p>This finds <code>printf</code>s that don't have a literal string on the same line, which usually means someone forgot the format string and did this: <pre><code>fprintf(file, somestr);</code></pre> <p>...instead of this: <pre><code>fprintf(file, "%s", somestr);</code></pre> <p>It's a stupid bug, yes, but not a rare one. I once ran this checker on a large application and found dozens of instances of this bug. I also found dozens of false positives, from things like these: <pre><code>snprintf(somewhere->buffer, MAX_BUFFER, "format string", args); fprintf(file, message_format_strings[status], description);</code></pre> <p>But they were obvious false positives, so it was easy to ignore them. <p>Here's an even less selective checker: <pre><code>grep '(\w\+ \?\*)'</code> <small>#beware different versions of grep</small></pre> <p>This finds pointer typecasts, which (in C++, more than in C) are often misguided — they might indicate unsafe downcasts, or non-type-safe containers, or casting away <code>const</code>ness, or simple unnecessary casting. It also finds a great many false positives, of course — mostly function prototypes and innocent casts. <p>These checkers don't <em>prove</em> the absence of the errors they look for. A program that doesn't contain the string <code>scanf</code> might still call it via a library or by <code>dlsym</code>. The <code>printf</code> checker can be defeated by something as simple as a <code>printf</code>-like function whose name doesn't contain <code>printf</code> — hardly a rare occurrence! The cast checker misses mundane things like <code>(char**)</code> and <code>(IntPtr)</code>. They only find bugs; they don't guarantee their absence. <p>They're also not very powerful. They find only certain specific errors, not a wide variety. A real lint program can do much better. <p>But when you don't have a real lint handy, or when your lint doesn't find the problem you're worried about, simple textual checkers can be valuable. <p><em>“They only find bugs”. “Only certain specific errors”.</em> Faint criticism. <p>In addition to being useful, these checkers are a reminder that there are many ways to check programs. None of them are typecheckers in either sense — not in the common sense, because they don't check datatypes, and not in the type-theory sense, because they don't classify expressions. They aren't even aware of the existence of expressions — they see code only as text. This is not a very powerful approach, but it's enough to find a lot of bugs. <p>Not all checkers are typecheckers. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/xCAG5WeC32E" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2013/12/trivial-program-checkers.htmltag:blogger.com,1999:blog-6454006.post-70115971879531538472013-12-06T23:15:00.002+00:002017-05-28T15:23:43.884+00:00Atomic file replacement and unpredictable primitives<p>Many programs need to update files atomically, so they don't corrupt them if they crash while writing. The usual primitive for this is an atomic replacement operation like <a href='http://pubs.opengroup.org/onlinepubs/009695399/functions/rename.html'>POSIX <code>rename</code></a>, which allows programs to implement atomic updates by writing to a temporary file and then replacing the real file with it. Typical use is as in this C macro: <pre><code>#define <b>ATOMIC_WRITE</b>(filevar, path, mode, body) \ do { \ const char *realpath = path; \ char temppath[PATH_MAX]; \ if (snprintf(temppath, PATH_MAX, "%s.temp", realpath) >= PATH_MAX) \ die("path too long: %s", realpath); \ FILE *filevar = fopen(temppath, mode); \ if (!filevar) \ die("unable to write file: %s", temppath); \ body \ fclose(filevar); \ if (rename(temppath, realpath)) { \ remove(temppath); \ die("unable to replace file: %s", realpath); \ } \ } while (0)</code></pre> <p>...but it's not usually written as a macro, because of a common problem of C: there's no good way for the macro to communicate errors to its caller, or to clean up when the caller has an error. It can be written as three functions — one to generate the temporary name and open the file, and two for successful and unsuccessful close, but this is complex enough that we seldom think of it. Instead we just write the same code over and over with different error handling, and different bugs, each time. <p>This makes it a good candidate for standard libraries, at least in languages that don't suffer C's error-handling deficiencies. It could be conveniently provided as an <code>open</code> mode (or a separate operation, if your language don't have modes) that writes to a temporary and atomically replaces the file when it's closed. <p>Common Lisp's <code>:if-exists :supersede</code> option to <code>open</code> <a href='http://www.lispworks.com/documentation/lw60/CLHS/Body/f_open.htm'>sounds like it does this</a>... <blockquote>The existing file is superseded; that is, a new file with the same name as the old one is created. If possible, the implementation should not destroy the old file until the new stream is closed.</blockquote> <p>...but the replace-on-close behavior is optional, and not necessarily atomic. <code>:supersede</code> is also the only portable way to request that the file be truncated when opened, so AFAIK no implementation actually gives it a meaning beyond that. <h3>Why is this so hard in Common Lisp?</h3> <p>I initially gave the example in Common Lisp instead of C, so it could handle errors properly. That part is easy, but it's much more complicated for other reasons: <pre><code>(defun make-temp-pathname (path) "Append .temp to the name of a file, before the extension (if any). Unlike /temp, this keeps it on the same filesystem, so renames will be cheap." <small>;;Simply appending .temp to the namestring doesn't work, because</small> <small>;;operations like rename-file “helpfully” misinterpret it as a file</small> <small>;;type and use it for defaulting, so e.g. (rename-file "a.temp" "b")</small> <small>;;renames a.temp to b.temp.</small> (make-pathname :name (format nil "~A.temp" (pathname-name path)) :defaults path)) (defmacro <b>with-atomic-output-file</b> ((streamvar pathname) &amp;body body) "Execute BODY with STREAMVAR bound to an output stream, like WITH-OPEN-FILE, but update the file atomically, and only if BODY returns normally." (<a href='http://common-lisp.net/project/alexandria/draft/alexandria.html#index-with_002dgensyms-173'>alexandria:with-gensyms</a> (ok? tempfile realfile) `(let* ((,ok? nil) (,realfile ,pathname) (,tempfile (make-temp-pathname ,realfile))) (unwind-protect (with-open-file (,streamvar ,tempfile :direction :output :if-exists :supersede) ,@body (setf ,ok? t)) (if ,ok? (rename-file ,tempfile ,realfile <a href='http://clisp.cons.org/impnotes/file-func.html#rename-file'>#+clisp :if-exists #+clisp :overwrite</a>) #-sbcl (delete-file ,tempfile)))))) <small>;SBCL deletes it automatically and complains that it doesn't exist</small></code></pre> <p>It also isn't portable, because Common Lisp doesn't specify that <code>rename-file</code> will replace an existing file. SBCL does, but Clisp doesn't (even on Unix, surprisingly — it <a href='https://sourceforge.net/p/clisp/clisp/ci/527b7fdc5332962c897227a557391a89b05df225/tree/src/pathname.d#l6043'>goes out of its way to break this</a>) unless it's reassured with <code>:if-exists :overwrite</code>. Also, <code>with-open-file</code> might automatically delete the temporary on abnormal exit, and <code>delete-file</code> might complain if it doesn't exist. These unreliable semantics, together with the perverse conveniences of pathnames, make it harder to write atomic replace portably in CL than in C. <p>So when you provide access to system primitives like <code>rename</code>, don't change their semantics. Users will not be surprised by the system's native behaviour, and sometimes they need it.<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/YHuxGxuLumM" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com0http://arcanesentiment.blogspot.com/2013/12/atomic-file-replacement-and.htmltag:blogger.com,1999:blog-6454006.post-87788432397139220692013-09-20T00:08:00.002+00:002013-09-20T00:25:12.621+00:00Why concatenative programming matters<p>Jon Purdy's account of <a href='http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html'>why concatenative programming matters</a> focuses on static types, which is an odd choice; it seems to me irrelevant to why these languages are interesting. (I suspect it's just mistitled; it could more accurately be called “Some interesting things about concatenative languages”.) If stack-based (“concatenative”) languages are interesting, it's not because they're especially amenable to static analysis or because their data flow incarnates a certain type system, but because of the expressive possibilities they demonstrate. In particular: <ol><li><b>Points-free style matters</b>, because it makes code shorter. Many variables have uninformative names like <code>x</code>, and it loses nothing to leave them out. Even those with informative names are usually repeated more often than justified by their value as comments. <li>...but <b>writing <em>only</em> in points-free style is a pain</b> (<a href='http://prog21.dadgum.com/33.html'>even for Chuck Moore</a>). So binding variables shouldn't be considered shameful, as it often is in Forth culture. <li>...but <b>having lots of combinators available makes it much easier</b>. <a href='http://www.factorcode.org/'>Factor</a> is less puzzle-like than Forth, partly because it has lambda (in the form of <a href='http://docs.factorcode.org/content/article-quotations.html'>quotations</a>) and <a href='http://docs.factorcode.org/content/vocab-combinators.html'>plenty of combinators</a>. <li><b>Stackwise concatenation is not the only reasonable default composition operator</b>. It has a wonderfully simple implementation and operational semantics, but it's hard to use in large expressions or with nonlinear dataflow. Lambda-calculus-based composition combinators like <code>o*</code> and <code>h</code> may be easier to use. <li><b>Code need not have tree structure</b>. The great success of expression languages has accustomed us to thinking that programs must be trees, but those in stack languages are (mostly) sequences. There is another way! (So what about dag and digraph structures?) <li><b>Macros and dynamism work well in low-level languages</b>. These two features are most common in high-level languages, but this is largely a historical accident. Forth happily allows redefining anything at runtime, and uses macros (in the form of compile-time words) for its control structures. Its users find both hugely convenient, and neither is a common source of problems. (Many assemblers also get a lot of power from macros, which is one of the reasons their users were loath to abandon them, but this lesson has been forgotten with their decline.) (This has nothing to do with concatenative languages — just Forth — but it's important enough to mention anyway.) </ol> <p>I suspect stack-based languages per se don't matter that much any more, but they illuminate dimensions of the language design space we wouldn't otherwise notice. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/mDRBtXCs4ls" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com2http://arcanesentiment.blogspot.com/2013/09/why-concatenative-programming-matters.htmltag:blogger.com,1999:blog-6454006.post-13171819081456661902013-09-15T19:41:00.000+00:002013-09-15T19:41:38.345+00:00These are a few of my favourite macros<p><i>Much of this post seems familiar to me, as if I've seen it somewhere else, perhaps on LL1-discuss or comp.lang.*. But I can't find the post I remember, so maybe I'm imagining someone else saying what I'm thinking.</i> <p>Macros are flexible, and unfamiliar to most programmers, so they inspire a lot of confusion (more, in my opinion, than they deserve, but that's a topic for another day). Sometimes people try to make sense of this confusion by classifying them into a few categories. These classifications typically include: <ol> <li>Macros that evaluate some arguments lazily, like <code>if</code> and <code>and</code>, or repeatedly, like <code>while</code>. <li>Macros that pass some arguments by reference rather than by value, like the <code>setf</code> family. <li>Binding macros that simply save a lambda: <code>with-open-file</code>. In languages with very terse lambda (like Smalltalk) these are not very useful, but in languages that require something like <code>(lambda (x) ...)</code>, they're useful and common. <li>Macros that quote some arguments (i.e. treat them as data, not expressions). <li>Defining macros like <code>defstruct</code>. <li>Unhygienic binding macros: <code>op</code>, <code>aif</code>. </ol> <p>The reasons for the classifications vary. Sometimes the point is that all of the categories are either trivial or controversial. (The people making this argument usually say the trivial ones should be expressed functionally, and the controversial ones should not be expressed at all.) Sometimes, as in <a href='http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg01539.html'>this case</a>, the point is that some of the categories are hard to express in any other way. Sometimes the point is that some categories are common enough that they should be built in to the language (e.g. laziness) or supported in some other way (e.g. terse lambda) rather than requiring macros. <p>These classifications aren't wrong, but they are misleading, because the most valuable macros don't fit any of these categories. Instead they do what any good abstraction does: they hide irrelevant details. Here are some of my favourites. <h3>Lazy cons</h3> <p>If you want to use lazy streams in an eager language, you can build them out of <code>delay</code> and eager lists. But this is easy to get wrong. Do you cons an item onto a stream with <code>(delay (cons a b))</code>? <code>(cons (delay a) (delay b))</code>? <code>(delay (cons (delay a) b)</code>? Something else? <p>This is hard enough that there's <a href='http://homepages.inf.ed.ac.uk/wadler/papers/lazyinstrict/lazyinstrict.ps.gz' title='Wadler/Taha/MacQueen: How to add laziness to a strict language without even being odd'>a paper about which one is best and why</a>. Even if you know (and regardless of whether you <a href='http://calculist.blogspot.com/2006/08/even-can-be-odd.html'>disagree</a> with that paper), it's easy to make mistakes when writing the <code>delay</code>s by hand. But the exact place where laziness is introduced is an implementation detail; code producing streams doesn't usually care about it. A <code>lazy-cons</code> macro can hide that detail, so you can use lazy streams without worrying about how they work. That's what any good abstraction should do. <h3>Sequencing actions</h3> <p>Haskell's <code>do</code> is not, officially, a macro, but this is only because standard Haskell doesn't have macros; in any case <code>do</code> is <a href='http://www.haskell.org/onlinereport/exps.html#sect3.14'>defined</a> and implemented by macroexpansion. Its purpose is to allow stateful code to be written sequentially, in imperative style. Its expansion is a hideous chain of nested <code>&gt;&gt;=</code> and lambdas, which no one wants to write by hand (or read). Without this macro, IO actions would be much more awkward to use. Some of this awkwardness could be recovered through functions like <code>sequence</code>, but the use of actions to write in imperative style would be impractical. <code>do</code> hides the irrelevant functional plumbing and relieves the pain of something necessary but very un-Haskell-like. Really, would you want to use Haskell without it? <h3>List comprehensions</h3> <p>Haskell's <a href='http://www.haskell.org/haskellwiki/List_comprehension'>list comprehensions</a>, like its <code>do</code>, express something that could be done with functions, but less readably. List comprehensions combine the functionality of <code>map</code>, <code>mapcat</code>, and <code>filter</code> in a binding construct that looks a lot like set comprehensions. They save having to mention those list functions or write any lambdas. <p>I sometimes wish there was a way to get a <code>fold</code> in there too, but it's a good macro as it is. <p>Haskell list comprehensions wear a pretty syntactic skin over their macro structure, but this is not essential. Clojure's <code><a href='http://clojuredocs.org/clojure_core/clojure.core/for'>for</a></code> demonstrates that a bare macro works as well. <h3>Partial application</h3> <p>Goo's <code>op</code> (and its descendants like Arc's <code>[... _ ...]</code> and Clojure's <code>#(... % ...)</code>) is an unhygienic binding macro that abbreviates partial application and other simple lambdas by making the argument list implicit. It hides the irrelevant detail of naming arguments, which makes it much terser than <code>lambda</code>, and makes high-order functions easier to use. <h3>Language embedding</h3> <p>There is a class of macros that embed other languages, with semantics different from the host. The <code>composition</code> macro from my <a href='/2005/01/composition-without-combinators.html'>earlier posts</a> is one such. A <code>lazily</code> macro that embeds a language with implicit laziness is another. The embedded languages can be very different from the host: macros for defining parsers, for example, often look nothing like the host language. Instead of function call, their important forms are concatenation, alternatives, and repetition. Macros for embedding Prolog look like the host language, but have very different semantics, which would be awkward to express otherwise. <p>Like <code>do</code>, these macros replace ugly, repetitive code (typically with a lot of explicit lambdas) with something simpler and much closer to pseudocode. <h3>The usual tricks</h3> <p>Most macros do fall into the simple categories: binding, laziness and other calling conventions, quotation, defining, etc. It's easy to think, of each of these uses, that it ought to be built into the language so you don't have to “fake” it using macros. <p>Fake? There's nothing wrong with using a language's expressive power to supply features it doesn't have! That's what abstraction is <em>for</em>! <p>The C preprocessor is a very useful thing, but of course it has given macros a bad name. I suspect this colors the thinking even of people who do know real (i.e. tree) macros, leading them to prefer a “proper” built-in feature to its macro implementation. <p>From my point of view, a macro is much <em>better</em> than a built-in feature. A language feature complicates the language's <a href='http://arcanesentiment.blogspot.com/2012/07/kernel-library-and-primitives.html'>kernel</a>, making it harder to implement, and in particular harder to analyze. Macros cover all of them, plus others the designers haven't thought of, in a single feature — and they don't even complicate analysis, because they disappear when expanded, so the analysis phase never sees them. <p>(To be fair, macros do require the language's runtime to be present at compile-time, and create the possibility of phasing bugs. But either interactive compilation or self-hosting requires the former anyway, and the latter only interferes with macros, so at worst it's equivalent to not having them. Neither is remotely as bad as being unable to express things the language designer didn't think of.) <p>So I see macros not as a weird, overpowered feature but as an abstractive tool nearly as important as functions and classes. Every language that aims for expressive power should have them. <img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/vfh1qRTpj0Y" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com4http://arcanesentiment.blogspot.com/2013/09/these-are-few-of-my-favourite-macros.htmltag:blogger.com,1999:blog-6454006.post-37990661493521937402013-09-14T23:55:00.000+00:002013-12-16T01:59:11.566+00:00Taming unspecified behavior<p>When a language spec leaves the behavior of some operation unspecified, there are several things an implementation can do: <ul> <li><b>Signal an error</b> in the usual way (whatever that is). <li><b>Extend</b> the language by defining a useful meaning. <li><b>Crash</b>, i.e. report an unrecoverable error. <li>Return an <b>arbitrary value</b>. <li><b>Break safety</b> by e.g. corrupting memory. <li><b>Choose behavior unpredictably</b>. Some C compilers now do this, to the horror of their users. </ul> <p>Traditionally, when a spec leaves some behavior unspecified, it's completely unspecified, with no constraints at all on what implementations can do. This maximizes implementor freedom, but minimizes the amount of behaviour users can rely on. This sometimes forces them into contortions to stay within the specified language, or leads them to write nonportable code without realizing it. Even worse, implementors sometimes take lack of specification as a license for arbitrarily perverse behaviour. <p>A spec can reduce these problems by leaving behavior only partially unspecified. Here are some options, in roughly increasing order of unspecifiedness: <dl> <dt>Signals an error<dd>The meaning of this operation is undefined — so undefined that implementations must detect it and report it. This provides maximum safety for users, but no freedom for implementors. (This isn't actually unspecified behaviour, but it's pragmatically similar.) <dt>Signals an error unless extended<dd>Implementations must detect the undefined behavior, but they have the option of giving it some useful definition instead of signaling an error. For example, in a language without complex numbers, <code>(sqrt -2)</code> might be specified to signal an error, but an implementation that does have complex numbers could make it return one. In Scheme, <code>(map - (vector 1 2 3))</code> might be specified to signal an error (because the vector is not a list) unless <code>map</code> is extended to work on other sequence types. This lets implementors extend where they want to while preserving safety everywhere else, so it's a good default for languages that aim to be safe. <dt>Unspecified value<dd>The operation will return normally and safely, but the result is unspecified, often with constraints such as a type. For example, C's <code>INT_MAX</code> is an unspecified integer at least 32767. In Scheme, the result of <code>(exact? (/ 1 2))</code> is unspecified but must be a boolean. <dt>Unspecified but safe<dd>The language's basic safety guarantees continue to apply, but behavior is otherwise unspecified. For example, the result of arithmetic overflow in many languages is unspecified — it might signal an error, it might overflow into bignums or flonums or <code>+Inf</code>, it might be modulo some constant, or it might return <code>nil</code> or nonsense — but it won't corrupt memory or crash. <dt>Unspecified but implementationally unsurprising<dd>The behaviour is not specified, but it should make sense in terms of some underlying model. For example, many languages do not specify what sort of pathnames their file operations accept, except that they should be those of the host system. C does <em>not</em> specify that the result of falling off the end of an array or dereferencing <code>NULL</code> is to blindly attempt to access that address, but that's what users expect. <dt>Unspecified and unsafe<dd>The language's usual safety guarantees no longer apply. Anything might happen, including crashes or corruption. In particular: <dt>Unspecified but consistent<dd>The implementation may choose whatever semantics it likes, but it must preserve those semantics when optimizing. It may not assume the operation won't happen, or choose semantics unpredictably. <dt>Unspecified and unpredictable<dd>Behavior is completely unspecified, and the compiler may do whatever it likes, even if it's inconsistent and doesn't make sense in terms of the underlying implementation. Avoid this! As John Regehr <a href='http://blog.regehr.org/archives/213'>puts it</a>, “A compiler that is very smart at recognizing and silently destroying [code with unspecified behavior] becomes effectively evil, from the developer’s point of view.” </dl> <p>These options are combinations of simpler constraints on behavior: safety; normal return vs. signaling an error; predictability; consistency with the underlying implementation. What other constraints, or combinations thereof, are useful? <p class=edit>Update 15 December: See also John Regehr's <a href='http://blog.regehr.org/archives/748'>When is Undefined Behavior OK?</a><img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/aITLQ18KmhY" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com7http://arcanesentiment.blogspot.com/2013/09/taming-unspecified-behavior.htmltag:blogger.com,1999:blog-6454006.post-84292589869032300772013-09-13T23:58:00.002+00:002013-09-14T00:02:31.492+00:00Unboxed arrays break identity<p><a href='http://www.lispworks.com/documentation/HyperSpec/Body/f_eq.htm'>Common Lisp</a> explicitly allows its implementations to copy numbers whenever they feel like it, so object identity is not reliable. <a href='http://arcanesentiment.blogspot.com/2009/08/identity-of-numbers-in-common-lisp-and.html'>Previously</a> I said this was a relic of Maclisp, but I overlooked a simple, obvious stronger reason: unboxed arrays. Long ago on RRRS-authors, Pavel Curtis gave <a href='http://groups.csail.mit.edu/mac/ftpdir/scheme-mail/HTML/rrrs-1993/msg00003.html'>another example where numbers might be copied</a>: <pre><code>(let ((v (make-vector 1 3.0))) (eq? (vector-ref v 0) (vector-ref v 0)))</code></pre> <p>This returns true in any ordinary Scheme, because storing a number into a vector does not copy it. However, if <code>v</code> is an unboxed vector of floats, this will probably return false, because the number naturally gets boxed twice. It does in Racket: <pre>&gt; <code>(require racket/flonum)</code> &gt; <code>(let ((v (make-flvector 1 3.0))) (eq? (flvector-ref v 0) (flvector-ref v 0)))</code> #f</pre> <p>And SBCL: <pre>CL-USER&gt; <code>(make-array '() :element-type 'single-float :initial-element 3.0)</code> #0A3.0 CL-USER&gt; <code>(eq (aref *) (aref *))</code> NIL</pre> <p>(That's a zero-dimensional array, with one element.) <p>Clojure doesn't explicitly allow copying of numbers, but does it anyway, of course: <pre>user&gt; <code>(let [x 1.0 v [x]] (identical? (v 0) (v 0)))</code> true user&gt; <code>(let [x 1.0 a (double-array [x])] (identical? (get a 0) (get a 0)))</code> false user&gt; <code>(let [x 1.0 a (object-array [x])] (identical? (get a 0) (get a 0)))</code> true</pre> <p>It doesn't even require an array, since it sometimes unboxes ordinary variables without preventing multiple reboxing: <pre>user&gt; <code>(let [x 1.0] (identical? x x))</code> false user&gt; <code>(let [x (if true 1.0 1)] (identical? x x))</code> true</pre> <p>Scala hides the issue by making <code>eq</code> unavailable on <a href='http://www.scala-lang.org/api/current/index.html#scala.AnyVal'>potentially unboxed types</a> like <code>Float</code> (and therefore on <code>Any</code>, which might be annoying): <pre>scala&gt; <code>1.0 eq 1.0</code> &lt;console&gt;:7: error: value eq is not a member of Double 1.0 eq 1.0 ^</pre> <p>Any language that boxes floats but wants efficient numerics practically has to support unboxed numeric vectors, and therefore allow implicit copying of numbers, since preventing it requires (undecidable) nonlocal analysis. So its spec must provide some permission to copy numbers — or any boxed type with an unboxed container; it's not specific to numbers. This permission need not be a blanket license to copy, though; it could be restricted to specialized arrays. Or, in order to permit unboxing variables without forcing the compiler to be paranoid about multiple reboxing, it could be permitted for a conservative approximation of "potentially unboxed numbers", e.g. those in local variables statically known to be numbers of a specific type, whose values come from unboxable operations (those that compute new numbers: <code>sin</code>, not <code>car</code>). <p>Does this make NaNboxing sound more attractive?<img src="http://feeds.feedburner.com/~r/ArcaneSentiment/~4/w-8WQmUwsqw" height="1" width="1" alt=""/>Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.com5http://arcanesentiment.blogspot.com/2013/09/unboxed-arrays-break-identity.html