SIGPLAN Blog

> A game written in Haskell or Scheme probably has a main loop implemented via recursion, but it's still called a main loop

If such a 'main loop' is a single function which (a) dispatches to one of a bunch of 'handlers' then (b) calls itself recursively, I would still call it a 'main-loop anti-pattern'.

More formally, it's likely to be in "defunctionalised" form https://blog.sigplan.org/2019/12/30/defunctionalization-everybody-does-it-nobody-talks-about-it

The problem with such 'main loops', whether actual loops or self-recursive functions, is that control flow has to keep doubling-back to this 'central dispatcher'. In the case of actual 'main loops' this is often an unavoidable consequence of lacking tail-call elimination. In languages with tail-call elimination, we're just over-complicating the problem.

> This sounds like a recipe for spaghetti.

The control flow for a 'main loop' program goes like this:

main function fooHandler barHandler
|
+------call-------+
|
+-----return------+
|
+------call---------------------+
|
+-----return--------------------+
|
...

If we have tail-call elimination, the handlers can just call the 'main loop' instead of returning (this is just a CPS transformation), e.g.:

main function fooHandler main function barHandler main function
|
+----call--------+
…

I have heard this said, mainly because some patterns can be made unnecessary with first-class functions and pattern matching. Closures are emulated with explicit objects, and the visitor pattern is equivalent to pattern matching. Something that's pretty interesting, though, is that it's a transform called defunctionalization. There's an article about it [1] that has been shared before on HN.

One form of defunctionalization is the well-known transformation of a recursive function into one that uses an explicit stack.

The thing is, I don't think defunctionalization (from the equivalent functional form) present in object-oriented languages is strictly worse. Defining things with explicit objects may sometimes be more understandable, and more extensible; for example, the command pattern could be implemented as a closure, but then you can't later add an "undo" method to it later.

Here's an example where defunctionalization makes the code more readable, not less.

Haskell has a difference list [0] data structure; the purpose of it is that you can concatenate two difference lists in constant time, and then turn it into one long normal linked list in O(n) time. This gives much better performance than concatenating lists directly all the time. It's a lot like a rope, except for lists, not strings, and it's immutable.

But the code is somewhat cryptic; it makes use of partial application and stores the tree in terms of partially applied functions. The "Demystifying DList" [0]…

> When you're a small startup, what matters is the expressiveness of your language, and the ability do do a lot of things very very quickly. Type safety, performance, readability, those things don't matter. You're just a bunch of engineers who know the whole codebase inside out, you're pretty certain of what you're doing.

I'm not familiar with this use of the term "expressiveness".

My understanding is that expressiveness (as per "On the expressive power of programming languages", Felleisen 1991 [0]) has to do with capabilities that a language has that separate it from another language. C is more expressive than Python in that it gives you direct access to memory management, whereas Python is more expressive than C in that it provides inheritance/OO. (These are just examples.)

Type safety, performance, and readability are all wholly separate from expressiveness, I think. A language's type system and performance benchmarks have nothing to do with the expressive power of a language outright, and "readability" is entirely subjective to begin with.

So: would you mind elaborating on what you mean, exactly, by "expressiveness of [a] language" here?

---

In fact, most of what you (and the linked article) are talking about has to do with the dynamic/static spectrum, not this "wizarding/engineering" spectrum you've coined (though I do kind of like the idea of that for discussing development methodologies).

The article is all about how the dynamically-typed nature of Python…

I've been teaching a compiler class for 5 years. My experience has been that writing and teaching to write compiler is more efficient using horizontal step rather than vertical steps.

What I call vertical steps are lexing, parsing, typing, compiling, emitting output code.

What I call horizontal steps are language features going through all the vertical steps.

For example it is far better to start with a compiler for the "int language" (valid programs consist in a single integer and that's it), and then progressively add horizontal layers (features) to the language, being able to tests these new features each time. For example adding additions, then other binary operation, then multiple instructions, then variables and affectation, etc.

Next fall I will try the backward approach in my course (still using horizontal steps for building the project, but teaching the vertical steps backward). I'm quite convinced it will work better since I read this article: https://blog.sigplan.org/2021/02/23/teaching-compilers-backward/

This made me wonder if RLibm has been extended to doubles yet[0]. Sadly that doesn't seem to be the case. It's a floating point math library that always produces correct rounding results, but it is limited to 32-bit floats (and posits, for that matter). Interestingly, despite being the only library that always rounds correctly, it also claims to be faster than other libraries (at same bit-depth).

I can recommend the papers, they're quite accessible and there is something very satisfying about the math tricks they came up with to build the polynomials.

They do seem to have added more rounding modes though, which presumably makes the library more generally useful.[1]

[0] https://people.cs.rutgers.edu/~sn349/rlibm/

[1] https://blog.sigplan.org/2022/04/28/one-polynomial-approximation-to-produce-correctly-rounded-results-for-multiple-representations-and-rounding-modes/

> So.... this is just a fancy name for the advice "give your functions a name"?

Not quite: "defunctionalization" is a name for replacing functions with not-functions (data structures). (And IMO it's the most unfancy name one can give to that activity, as the name literally just indicates "removing functions"... I can't think of a less fancy name for it: maybe "un-function-ize"? But that's pretty much the same as "defunctionalization".)

BTW I recommend reading the 3 linked articles in this order:

1. https://blog.sigplan.org/2019/12/30/defunctionalization-everybody-does-it-nobody-talks-about-it/

2. http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html (with accompanying video)

3. https://www.gresearch.co.uk/article/defunctionalisation/ (this one actually shows how you can incrementally adopt this)