News for hackers. Stuff that matters.

danielnicholas

Re:Puzzles to convince you you don't understand dependence on Sunday October 02, 2022 @10:55AM (#33056381)
I’m a co-author of the paper that the OP’s post discusses. A few clarifications:

- In safety- or security-critical systems, you may want to define a small trusted base, or to be able to audit the system to be confident that certain failures won’t occur (https://groups.csail.mit.edu/sdg/pubs/2009/dnj-cacm-4-09.pdf). Reasoning about such things requires being able to say when one part depends on another. Existing definitions of dependency are too vague or incomplete to support such reasoning, let alone to build tools.

- The puzzles are our attempt to distill issues that arise in practice to the simplest possible examples, so if they sound obvious, so much the better. The fallback case is important in critical systems. Suppose you build a component X and you’ve reasoned that it meets a spec S required by a client C. But then you’re not completely confident in your reasoning, so you build a simpler fallback version X’ that you switch to if X fails to meet some property at runtime. Presumably when you reason about C you’ll want to account for X’ as well. This is a basic engineering issue and not a linguistic nicety.

- The problem is to account for systems the way they’re actually built, not to propose a new way to build them. Even if your code was built with objects, the Liskov Substitution Principle wouldn’t be enough because it only addresses subtyping. Global variables, for example, can’t be ignored. They were pervasive in the car code that JPL analyzed as part of a study I was involved in (https://nap.nationalacademies.org/catalog/13342/trb-special-...), and they arise implicitly in OO code whenever you have static features. Another example: if you’re designing a Mars rover, you’d want to account for failures in a battery maintenance module even for modules that make no calls to it. Interfaces can’t account for this kind of thing.

- @layer8 offers a nice formulation of dependence in terms of reasoning and properties. This was a starting point for our work, and I’d previously suggested a model like this in a 2002 paper (https://groups.csail.mit.edu/sdg/pubs/2002/monterey.pdf) and Eunsuk Kang and I suggested a diagrammatic notation for it in a later paper (https://eskang.github.io/assets/papers/mj_workshop_09.pdf). One key limitation of this approach is (as @csours notes) that it doesn’t let you account explicitly for all the assumptions you typically make in such reasoning. It’s not clear, for example, how such an approach could account for Log4Shell.

- A historical note: I first learned about making dependences explicit from Barbara Liskov and John Guttag from TAing their class (https://mitpress.mit.edu/9780262121125/abstraction-and-speci...). Even back then, we realized that the dependence model was only an approximation, and that it couldn’t be derived from the code. Long after Barbara developed her substitution principle, when we taught the same class together (in 1997) we continued to use dependence diagrams, because they address a different problem.

Re:Jackson structured programming on Friday August 13, 2021 @07:14PM (#28176011)
For those not familiar with the JSP style alluded to in the comments, and its contrast to the "traditional style," here's an example of a function that splits a string into words. The "traditional" version was shown by a famous computer scientist in a conference talk a few years ago; I translated it to JS to provide some anonymity :-).

JSP's claim to greater clarity is based on the correspondence between the code blocks and the structure being processed: the body of the outer loop processes a group (of gap and word); the body of the inner loops process a gap and a word respectively. The traditional style, in contrast, is like a state machine, and can't be viewed structurally---you need to think about what's happening at each point. This makes it harder to modify the code (eg, by adding something that happens once per word, which is now in two places) and often leads to bugs.

This same structural clarity is why, in my view, code that uses list functionals like map/reduce is usually more comprehensible than traditional imperative code.

    // JSP version of a split function
    split_jsp = function (s) {
      words = [];
      i = 0;
      while (i < s.length) {
        while (is_white (s[i]))
          i++;
        word = "";
        while (is_alpha (s[i]))
          word += s[i++];
        if (word.length > 0) words.push(word);
        }
      return words;
      }
  
    // "traditional" version of a split function
    split_traditional = function (s) {
      words = [];
      word = "";
      for (i = 0; i < s.length; i++) {
        ch = s[i];
        if (is_white (ch)) {
          if (word != "") words.push (word)
          word = "";
          }
        else
          word += ch;
        }
      if (word != "")
        words.push (word);
      return words;
      }

    is_white = ch => (ch == ' ' || ch == '\t' || ch == '\n')
    is_alpha = ch => ch != undefined && (/[a-zA-Z]/).test(ch)
Re:Jackson structured programming on Friday August 13, 2021 @12:17PM (#28170867)
If you want an intro to JSP, you might find helpful an annotated version [0] of Hoare's explanation of JSP that I edited for a Michael Jackson festschrift in 2009.

For those who don't know JSP, I’d point to these ideas as worth knowing:

- There’s a class of programming problem that involves traversing context-free structures can be solved very systematically. HTDP addresses this class, but bases code structure only on input structure; JSP synthesized input and output.

- There are some archetypal problems that, however you code, can't be pushed under the rug—most notably structure clashes—and just recognizing them helps.

- Coroutines (or code transformation) let you structure code more cleanly when you need to read or write more than one structure. It’s why real iterators (with yield), which offer a limited form of this, are (in my view) better than Java-style iterators with a next method.

- The idea of viewing a system as a collection of asynchronous processes (Ch. 11 in the JSP book, which later became JSD) with a long-running process for each real-world entity. This was a notable contrast to OOP, and led to a strategy (seeing a resurgence with event storming for DDD) that began with events rather than objects.

[0] https://groups.csail.mit.edu/sdg/pubs/2009/hoare-jsp-3-29-09...

Re:Jackson structured programming on Friday August 13, 2021 @10:45AM (#28169525)
JSP used the "quit" statement to handle errors and backtracking; it was a primitive form of exception before exceptions were common. There's a lengthy defense of this in the JSP book (on p.282) arguing that eliminating GOTOs dogmatically is a mistake.
Re:Jackson structured programming on Friday August 13, 2021 @10:39AM (#28169455)
That's exactly how JSP was used. In its first application to COBOL, the JSP-COBOL tool turned structured code into coroutining code with suspend/resume, and tools built later for JSD generated code to save state in a database.