No Ifs, Ands, or Buts

No Ifs, Ands, or Buts: Uncovering the Simplicity of Conditionals. Jonathan Edwards.

Schematic tables are a new representation for conditionals. Roughly a cross between decision tables and data flow graphs, they represent computation and decision-making orthogonally. They unify the full range of conditional constructs, from if statements through pattern matching to polymorphic predicate dispatch. Program logic is maintained in a declarative canonical form that enforces completeness and disjointness among choices. Schematic tables can be used either as a code specification/generation tool, or as a self-contained diagrammatic programming language. They give program logic the clarity of truth tables, and support high-level direct manipulation of that logic, avoiding much of the mental computation demanded by conventional conditionals.

Many of us are skeptical of "visual programming", but also intrigued by the impact that powerful development tools might have on language design. This represents an interesting compromise. It addresses a pervasive problem in a novel way, and this is a paper with many interesting and accessible ideas. I look forward to seeing an implementation.

Jonathan posted this on his blog, where there are already several comments.

[I'm not sure where to put this... Seems like plain-old "Paradigms" is the best fit...]

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Wow!

My goodness, that's really awesome!!! Seriously, I think it has lots of potential. I'm not skeptical of visual programming at all. Sure, it has failed in the past - people haven't approached it properly. Everyone seems to be inspired by the thought "hey, what if the flowchart was the program?". People need to realize, as this guy has, that 2d is extremely freeing. Text is just a really limited 2d. By removing the constraints of ascii, much better syntax and editing may be achieved.

I'm not sure about the subtext part, subtext is very cool, but some of the parts of it seemed a bit rough - like all the sections of the ide and the var ordinal pointers.

I hope i can use this... I might have to integrate it deeply into my 'ideal' programming language.

pdf kinda sucks though... the figures need to be inlined.

Text is limited 2-d?

That seems to me to be a very limited way of looking at things. We can write a formula to describe something in eleven dimensions -- try doing that visually.

uhh...

[Edit2 - old topic "Good Point, sorta"] Nevermind, looks like the wee hours also addled my reading - that's a horrible point. Math, as I will show is a fantastic example of a 2d language. Matrices even look kinda like this guy's conditional stuff. Perhaps there is a misunderstanding about what 'visual language' means. It doesn't mean there's no text - it means that the text is nonlinear, and additional nonascii constructions may be included.

(originally I thought he was trying to say that 11-dimensional diagrams would theoretically be better than 2-dimensional diagrams, by my logic)

Sorry, I figured that what I meant was implicit in the post. Or perhaps it's just because I wrote it at the wee hours of the night when I forget people can't read my mind.

Anyway, a big part of it is that our visual centers of the mind are very powerful pieces of equipment - they do huge amounts of parallel processing behind the scenes. The combination of reading Edward Tufte's books and Steven Pinker's "How The Mind Works" is probably necessary for really grasping this, and other cooler stuff :)

This power is somewhat leveraged with the programming practices of indentation and similar expression alignment.

Sure, you can write math in a 1-dimensional language such as latex, but mathematicians hate it - math is 2d! Ever wonder why subscripts, superscripts, multiplication, and higher order parameters all use 2d juxtaposition and scaling? It's because mathematicians have found a concise, understandable syntax which takes advantage of the freedom rendered by existence on a 2 diminsional surface.

[EDIT] A part i forgot earlier is that 2-dimensional code allows for more than two spatial connections. In 1d you can only go backwards and forwards. Languages that utilize carraige return for 2d-ness would be awkward if they actually used 2d location for relations. 2 dimensions allow for many connections between components without overlaps. A good illustrating example is the function call - each expression is slotted into a parameter. However, each successive parameter is further and further away from what it goes into. 2d layout helps to fix this problem by allowing parameters to be positioned around the function call. One way languages get around this is naming things - local variables, parameter names. These are good, but much of the time they are redundant with the type. Another way, as seen in a few languages, is to go purely compositional, combintators and all.

I think your view is the limited way of looking at things. You have used ascii all your life, and can't see the possibilities beyond it.

As you can see, I've thought about this a lot. At least a year or two, and normal language design for quite a few years before that. (though recently I've beeen thinking about the possibilities of agent-based parsing...)

Text is 1d

All those lines you see are just one big line with newlines thrown in.

Really?

I am probably missing a smiley here, but

  (/ (* (- 2 3)
        (+ 4 1))
     (+ 11 3))

seems quite two-dimensional to me.

(Example by Guy Steele)

Other examples include indentation-based languages like Haskell and python.

Sort-of

The thing is, that's just how it's stored - the common display of text is 2d. A png is just a 1d stream of bytes. Every file on your computer is.

I agree with you, though, in essence text is 1d in regards to the connections that you can reasonably make between elements. You could have semantics which depend on the locations of symbols up/down with eachother, but it'd be a horrible language - you'd always be aligning and adjusting stuff. (no this isn't a slight against pythonic indentation - I'm talking about where you actually need 2d alignment between multiple elements per line)

The key observation is that text is a subset of the syntax a visual language might have. I think good visual languages will mostly be text, with no non-semantic visual elements (gradients, thick borders, etc).

Ok...we put functions into a table...so?

I downloaded the PDF but it did not contain any images...I also visited the blog, but still no images. Anyway...

I really liked the part that said conditionals/pattern matching/polymorphism is one and the same thing, i.e. application of a function over a set of values which transforms the values into another set.

But I do not get how putting all of it in a schematic table will make my programs more readable or better in any way. Some care to analyse it further?

At the end

>I downloaded the PDF but it did not contain any images.

The images are all at the end of the pdf, a poor layout, unfortunately not so rare when the paper is made in LaTeX..

[OT] Probably not LaTeX

Images at the end of a file isn't really a LaTeX issue: it's easy to place images inline in LaTeX, or on pages of their own interleaved with the text. More likely, it has something to do with whatever journal the author is submitting to. Some journals require submissions to include all figures at the end of the text. [Edit: I have no idea what OOPSLA's requirements are like. I suppose another possibility is that since this is a draft, he hasn't quite figured out where to stick the figures yet]

Rethinkers rethink things

From the paper:

The diagrams ... have been placed at the end of the
paper so that they can be torn off and followed separately.

Latex-challenged

To be honest, this was my first foray with latex, taken under duress. The advice I got was that cross-column figure placement would be torturous, and I would probably not be able to get it perfect. My reviewers preferred them at the end. It seems that not everyone agrees. The PC will have the last say.

Check out the images at the bottom

The images are actually the most exciting part. The later examples are particularly awesome. I probably wouldn't have gotten so much out of the text alone.

What does that make the rest of us programmers?

Sinners in the hands of an angry Decision Table?

Slow, so very slow, but progress happens

When I first saw this post, I was prepared for the worst. These kinds of tables are really old, and having this submitted to OOPSLA did not nothing to decrease this sense of dread.

And then I was very pleasantly surprised. The papers with which I am quite familiar with on this issue are properly cited (like [15,17,23]). Many ancient papers are cited (not a common thing in CS!). Of course, when you see these papers, my subject line becomes clear: it has taken a long long time for these ideas to drift from their community of origin ``sideways'' to related disciplines.

And then I continued to read the paper, and I went from pleasantly surprised to impressed. The paper shows the author really understands the power of proper notation as well as the underlying semantics of tables. The crucial semantic properties of disjointness and coverage (ie partitioning) are front-and-center. Better yet, a carefully thought-through UI design based on these ideas is presented. And then Section 5 is about noticing that dynamic-dispatch based subtyping polymorphism is actually "the same" as a poset partition of the type space -- and tables are all about walking partitions of *any* space.

Perhaps the only substantial negative point would be that Dijkstra's guarded commands are not mentioned at all.

On another front, I happen to not really like the chosen layout. It is not as visually obvious as I think things could be. Some of the work on "tabular representations" for specifications has produced clearer layouts. On the other hand, some of the facilities provided for cross-column computations are vastly superior to what these allow. And the interaction features (type errors, splittings, etc) are wonderful. Overall, the balance is still quite positive.

Disclaimer: I have done research in the area of piecewise-defined functions (for computer algebra -- see A canonical form for some piecewise-defined functions; one point of my paper is the same key idea #1 in this one: represent computation and logic orthogonally, which allows for the huge efficiency gains). Mathematicians have been displaying these as schematic tables for over a 100 years. So my bias would be to find that this has "all been done before", and yet I like this paper a lot.

non-deterministic choice?

From my very cursory skimming over the text it seems like the tables are so designed as to avoid overlapping of logical conditions. Thus non-deterministic constructs such as Dijkstra's guarded conditionals are not expressible in the proposed notation. If that is so, then the claim that the tables “unify the full range of conditional constructs” is inaccurate.

Another note, for those interested in alternative representations of program control. I'd like to mention a proposal for a control notation, paired with a graphical notation, that made some impression on me in the past: see here or here. It unifies conditional and repetitive constructs.

Go further into the paper

Somewhere in the middle, things get generalized so that some overlap is allowed (but it must ultimately be resolved). So Dijkstra's guarded conditionals indeed cannot be implemented. But that is an explicit design choice of the author, which needs to be justified. What better justification method than to contrast with a famous but opposite decision? [That was my point, which I did not make so well, apparently].

Point taken

I should be explicit that I am focusing only on deterministic conditionals. I like your perspective that Dijkstra uses overlapping to express non-determinism, while I am interpreting it as erroneous ambiguity. Interesting contrast. Thanks.

Dijkstra

This is not my insight, I learned it from various colleagues (probably a combination of Tom Maibaum, Alan Wassyng and Ryszard Janicki, with always a little of David Parnas thrown in for good measure).

And it is important to understand that Dijkstra uses it for non-determinism, and never for under-specification. Those two concepts are easy for people raised on deterministic programming to confuse, but are in fact quite distinct.

there is more to Dijkstra's constructs

... Dijkstra uses overlapping to express non-determinism

I'd rather say that Dijkstra's use of non-determinacy makes overlapping meaningful. But there is more to his non-deterministic conditional construct (and loop) than just this. In Dijkstra's
   if b1 -> a1 [] b2 -> a2 ... fi
or
   do b1 -> a1 [] b2 -> a2 ... od
the order of evaluating the guards bi is irrelevant to the meaning of the construct, so the construct effectively specifies no-order, not excluding concurrent evaluation. This kind of non-determinacy is valuable in itself, and it is independent of the one present in the choice of an action when there are more than one overlapping true conditions.

As for your schematic table approach, I find it interesting and wish you success in developing it.

speaking of guarded commands...

While we are mentioning guarded commands (sorry Jonathan), I was struck by the passage in EWD418 where Dijkstra points out that gcd may be thought of as synchronizing two processes (x:=x-y, y:=y-x) subject to the constraint that x and y remain positive.

This was undoubtedly meant to be reminiscent of synchronizing two processes, a producer and a consumer, subject to the constraint that the queue between them is always somewhere between empty and full — at which point the usual mod operation becomes a context-switch minimization optimization.

I would not be too surprised if had it also been supposed to be reminiscent of computing by synchronizing two processes: an applicator to produce expressions, and an evaluator to consume them, subject to the constraint that the graph between the two is always somewhere between empty and full — where the value of full influences the eagerness or laziness of the resulting calculation.

Has anyone investigated the concurrent variant of guarded commands in which an if ... fi with no valid guards, instead of being equivalent to abort, was considered to have no currently valid guards and hence would be a rough dual to do? (instead of looping until no guards matched, it would yield until at least one guard matched)

Concurrent Constraint Handling Rules

I believe concurrent constraint handling rules do exactly what you want. A Concurrent Constraint Handling Rules Semantics and its Implementation with Software Transactional Memory uses exactly GCD as an example.