Thursday, February 17, 2011

Observations on the Feeling of the Ugly and Insignificant

vsm001 said...
I neglected to add my biggest objection to Louis's project, the lack of a strictly (or lazily) functional subset.

Louis told me he is planning on writing a book about interpreter implementation. I have offered to write prolegomena for any future meta-circularity, but Louis doesn't seem too keen on the idea.

vsm001 went directly to the meta-point of many of my posts: This is no way to go about designing a language.

BUT, I wanted to explore a particular issue in the design space of languages, not whether we should be in the space in the first place. In particular, let us assume some plausible rationale for inventing a language and then ask the questions that vsm001 raised.

vsm001 asked,
What are the characteristics of problems that Reason is well-suited to solve?

I'll rephrase this. What are the characteristics of problems that would be better solved by a language that has two complementary ‘modes’ of operation as opposed to a language in which a single mode suffices? In other words, neither of the two modes of Reason taken separately is quite powerful enough to be Turing complete, you really need both of them; under what situations would this provide an advantage over using a single, Turing complete mode?


  1. Why don't define return a value in scheme so that it can be used as an expression?

  2. Louis might defend the two modes on readability or analyzability grounds — "in Lisp mode, you know there's no tricky flow-control going on" — but such arguments-from-inexpressiveness have a terrible track record.

    Separating pure functional code from state is a better justification. If you take away all the egregious mistakes (and everything that doesn't look like an elephant), Reason's two modes could become a pure/stateful split, like Haskell's, but with a more conventional imperative side.

  3. Reason's two modes could become a pure/stateful split, like Haskell's, but with a more conventional imperative side.

    Or like C's, but with a more conventional pure functional side.

  4. Functional vs. imperative is a red herring here. While it is true that any code doesn't return a value must use side effects in order to be observable, that doesn't constrain the code that does return a value. (For instance, a function call can perform arbitrary side effects and still return a value.)

    Arcane Sentiment suggests that Louis may have a plausible defense. I'll grant you that that may be the case, but it is at least as likely that Louis is confused. What I'm looking for is an existence proof that there is a class of problems that are more difficult to solve when there is no distinction between forms that return a value and forms that do not. I suggest that no such problems exist simply because it is trivial to ignore a return value that you do not want.

  5. Curiously, the Steelman requirements require a language that meets them to have both procedures and functions, and has this to say about side effects:

    7C Side Effects. The language shall attempt to minimize side effects in expressions, but shall not prohibit all side effects. A side effect shall not be allowed if it would alter the value of a variable that can be accessed at the point of the expression. Side effects shall be limited to own variables of encapsulations. The language shall permit side effects that are necessary to instrument functions and to do storage management within functions. The order of side effects within an expression shall not be guaranteed. [Note that the latter implies that any program that depends on the order of side effects is erroneous.]

    I interpret the last remark in brackets to mean "order of side effects within an expression" rather than "order of side effects tout court". Ada, the language built to meet these restrictions, actually allows unlimited side effects within functions, but it would be interesting to design a modern language that satisfied Steelman. It could, for example, allow functions only the side effect of modifying specified global variables, where access to the values of such variables is permitted only within the side-effecting statement, not within the rest of the function. That would keep functions pure and functional as far as their return values are concerned, but still allow instrumentation of them. I'm not sure what to do about the requirement to allow allocation: it would take some further thinking.