Donald Knuth used an Erlang-like notation | Hacker News Reader

Donald Knuth used an Erlang-like notation

videlalvaro.github.io

149 pointsold_sound93 comments

Knuth is simply defining a piecewise function here in ordinary math notation. Functional programming languages borrow heavily from math, Erlang is a functional language. The resemblance would probably be even more striking with Haskell... which only serves to undermine the message.

Erlang's great though. Glad to see some irrational exuberance for it.

I'm waiting for the sequel, Gutenberg used the same characters as in C, making him the first C programmer.

C predates Gutenberg

"One of the main causes of the fall of the Roman Empire was that, lacking zero, they had no way to indicate successful termination of their C programs." - Robert Firth

That's some deep theosophical kung-fu you bring there, grasshopper. But seeing as the words of the Torah existed before the creation of the world, it might just be that you are correct.

Knuth's function would be written in Haskell as thus:

f [n] = [n]

f [m, n] = [m, n, 0, 1]

f [m, n, r, 1] = [m, n, mod m n, 2]

f [m, n, r, 2] = if r == 0 then [n] else [m, n, r, 3]

f [m, n, p, 3] = [n, p, p, 1]

It needs to be implemented with variable-length lists instead of fixed-length tuples, in order to satisfy the type system.

For me what's striking about Erlang syntax is the meaning of the semi-colon and the period, as function clause separator. Most of the rest is just vanilla FP lang syntax.

To be fair that's just vanilla English orthography.

Yup, and still people get confused at Erlang's use of semi-colons and periods.

Do you think it is because other programming languages don't uses the semi-colon that way? Or that periods are usually used to access class members, but not to finish function declarations?

I think it's because most people have no idea how to use semicolons in natural languages too.

I think this is true. Anecdotally, I've looked up the usage of semicolons a few times now, and I think I know how to use them, but every time I'm about to I just rephrase what I'm saying so I don't have to. They are used so rarely in English it's hard to feel confident through exposure.

I use semicolons all the time; they are easy and useful.

The two clauses separated by a semicolon are sentences; thus the semicolon is logically and grammatically equivalent to a full stop. (As long as you normalise the capitalisation). The difference is in nuance, flow, and other soft things.

So when do you use a semicolon instead of a full stop? Whenever you want to!

The really difficult punctuation mark in English is the full colon.

Sure, which is what the rules always say, and is fairly straightforward. The hard part is actually using it because it usually looks so out of place to me. It's a chicken and egg problem, where semicolons are hard to comfortably use because they are so rare they look out of place when I try, and I assume part of the reason for their rarity is other people feel the same way.

What's a full colon? Hard/NSFW to google for that...

Just a plain colon, as an emphatic distinction from a semicolon.

I feel like the semicolon-period thing of Erlang is only really frustrating for the first day you're using it. After that, I actually found it to be a fairly natural syntax, and had little trouble switching between it and JS.

Erlang's usage of commas, semi-colons and periods is based on Prolog's use of these punctuation-marks. (Erlang was developed in Prolog and retains many similarities to it).

Just a small nitpick: your code is not recursive, you are missing 'f' on the right hand side.

Neither is Knuth's definition; it's just mapping an input to an output.

With haskell it will be less similar since Haskell doesn't use the semi-colon to separate function clauses, and the period for delimit the last one. You could argue that Haskell tuples will use the () syntax instead of {} as in Erlang.

I've mostly wrote this joke since many Erlang beginners find the semi-colon/period syntax confusing, but then there you have it on an essential book about programming

Any text that defines piecewise functions is going to use syntax similar to Knuth. It's much older than him or his text. Piecewise functions are not common in the normal math track though, because they're not continuous and differentiable, so they make the path to calculus more complex.

In my experience, it is we programmers who care about syntax the most. Math folks seem to be happy if you can get the gist of something.

Still, you're right, the semicolon/period thing is troubling for Erlang beginners, but that part of the syntax really does come from Prolog.

How are piece wise functions NOT covered in normal math tracks? While not strictly necessary for algebra and geometry, I can't imaging being able to grok behavior at asymptotes in calculus and analysis without being somewhat comfortable with them. They were taught in middle/early high school in Maryland school systems, if I recall.

I'm pretty sure many more people find TAOCP confusing than they do Erlang :p

Can we say: "If you understand the first 20 pages of TAOCP, you understand Erlang"?

You can understand Erlang even if you're not that good at math, but you won't be able to make much of TAOCP if you aren't good at math.

One thing is for sure: just trying to read TAOCP will eventually make you better at math.

There's no such thing as "being good at math". You either put effort and practice to learn it, or you don't. Fixed va Growth Mindset, etc…

> There's no such thing as "being good at math". You either put effort and practice to learn it, or you don't.

I agree with your second sentence, and, as a mathematician and a teacher, I think that I agree with the spirit of the first, but I think that it's probably not worded as you mean. Think of the same sentence with, say, 'baseball' in place of 'math': I think that most people would agree with the second sentence, but not the first. By the same token, there's no such thing as "being inherently good" (or, for that matter, inherently bad) "at math"; but I think that it would be silly to pretend that the effort and practice don't make you good (or at least better) at it.

The thing about the beginning of Vol 1 of TAOCP is that it begins with the "mathematical preliminaries" which is among the most difficult things in the book (aside from some of the more hard-core analysis). Like, his description of heap-sort in Vol 3. is easy enough to follow, but fuck man, generating functions are hard!

Which is why my professor and classmate and I switched to Concrete Mathematics about halfway through working through chapter 1. More thorough examination of many of the topics in chapter 1, plus more material.

My advisor would always make a joke to his classes, when that book came up, that it had a dual purpose name - - that it was foundational, but also because it's hard as concrete. I used it as reference in some of my math classes but haven't given it a thorough read.

We worked through about 1/3 of the material starting one summer term (where we started on TAOCP) and finishing sometime in the fall. Definitely hard, but it also helped me finally understand a lot of math that I "knew" but hadn't yet grokked.

Hence the 'platonic language ideal' that the author speaks about in the last paragraph?

Certainly, though (1) Knuth is mostly irrelevant here and (2) the causality is obfuscated.

A more precise title would be "Erlang uses math-like notation (and kudos)"

To the eye of a developer used to more modern languages that also shows some bad choices in the design of the Erlang syntax. Basically everything that makes the source code less readable than the original: uppercased variables, the minuses that prefix the module and export statements, the wierd =:= operator. I add the also wierd <> binary and string concatenation operator, not used in this example.

The semicolon-period statement separators/terminators are in the original and in natural languages, but newer languages proved them to be useless. Probably compilers in the 80s needed some help by the programmer to be fast.

Elixir fixed some of the worst offenders, kept others and added something. Examples: the <> is still there but at least we can interpolate strings Ruby like, the useless do at the end of almost every defsomething declarations (the compiler should get it by itself.)

But every languages has its wierdnesses, the contest is to have the least of them.

It's worth noting that Erlang gets a lot of that weirdness from its progenitor language, Prolog, where arguably some of that stuff makes more sense. For instance, the =:= operator is an equality operator that forces arithmetic evaluation, unlike = which is just used for unification. In Prolog, this is a fairly crucial difference ("1 + 1 = 2" is false in prolog, while "1 + 1 =:= 2" is true) and there needs to be language constructs that make the distinction clear. Given that, having different operators is a sensible solution to the problem.

On the other hand, it's arguably true that Prolog has an over-reliance on a massive swath of operators. All of these operators represent some variation of the concept of equality: =, ==, =:=, =@=, #=, and "is". The differences make sense if you're deep into Prolog, and it's rich capacity for designing new operators is arguably a strength of the language, but it's clearly an obstacle to beginners.

I absolutely adore Prolog, but it's a real shame that development of logical programming basically stopped with it. It would be as if functional programming never properly progressed beyond early Lisps. Its a shame that Erlang borrowed so much of its syntax, when the syntax is clearly not its strongest suit (though it fits Prolog better than Erlang).

> The differences make sense if you're deep into Prolog

They make sense academically, but they only slow down language adoption.

> Basically everything that makes the source code less readable than the original: uppercased variables, the minuses that prefix the module and export statements,

Capitalized variables stand out from lower cased functions. I find that makes it easier to read than having everything lowercase. It's enforced so all the code has to follow that convention.

Semicolon at the end of a function clause indicates there is another function clause following it, that is a useful affordance when navigating code.

> The minuses that prefix the module and export statements

Well in natural language you use dashes to create an itemized list. Would # be better like in include statements in C/C++? Maybe the alternative is to introduce some "defun / fun / def / function" keyword to define functions and another keyword "directives"? But that is less ergonomic, I really like how function definitions don't have to start with an extra keyword and they are just function names starting on the left side of the page.

> the wierd =:= operator.

Yap that is a weird one. = is used for pattern matching so reusing it for equality / equivalence testing might be ambiguous.

> Basically everything that makes the source code less readable than the original:

The original has "remainder of _ divided by _". That looks ok in a small example but repeating that phrase throughout the program many times is probably not the best idea.

Overall, after reading large code bases of Erlang, Python, C++, C#, and Java. I would put Erlang right behind Python and readability and how ergonomic it is. The most important thing about it is it is small and self-consistent. Contrast that with a "modern" language like Javascript which looks "familiar" but is not very consistent and full of gotchas (see the famous wat video on that).

One must not compare dynamic type language ergonomics with a static one - different niches ;-)

There is an interesting overlap in Haskell, Standard ML and OCaml as they do type inference. Hence they read like a dynamically typed language, but forces a strict typing discipline by deriving the types from the written code by inference.

Modern?

1990 Erlang is presented at ISS'90, which results in several new users, e.g Bellcore

Python was conceived in the late 1980s[1] and its implementation was started in December 1989

Both (and pretty much all languages other than the first ones) borrow heavily from languages that came before them.

You deem that syntax "weird" only because you're experience is with other families of languages. If we all grew up writing Prolog, we'd think the algol C-like languages looked weird.

History of Computing should be a required course for CS majors.

One thing I don't like about Elixir is the Ruby-style "optional" sytax e.g. `IO.puts "hello"` vs `IO.puts("hello")` and the whole keyword list arguments syntax sugar thing. I mean, I get it now, but it's sorta hard to read as non-Ruby beginner.

Hmm you can just use `IO.puts("hello")`

The point is some people don't, making it harder to read that code.

I am afraid the ability of people to write hard to read code is infinite. If you are using Elixir in a production project your team can set a guideline to always use () I have not looked into it but it also likely can be enforced by a linter.

>To the eye of a developer used to more modern languages

Perhaps its the eye of the developer "used to more modern languages" that has the problem?

I started in the 80s with BASIC, Pascal, C and Perl :-)

The point is that languages generally got better syntaxes along the years. Restricting ourselves to a niche, it's not that Ruby, Python and JavaScript are young (20+) but Ruby got it almost right from the beginning, Python maybe (it has more oddities but it could be a matter of tastes) and JavaScript is evolving a better syntax. Even PHP is getting more readable.

>The point is that languages generally got better syntaxes along the years.

Some of the popular languages got more sugar, but compared e.g. to Lisp are they really an improvement?

Heck, even Go is not that different than Algol-68.

Sugar somewhat matters. We could debate if it really makes us better and faster developers or if it's only an addiction. For sure I don't want to go back to Perl even if it shares the same basic programming model of Ruby. Heck, I don't even want to go back to Python, because it looks like Ruby with a bad skin disease (I'm working on two Python projects right now.) C and Java instead are substantially different beasts because of the garbage collection. I don't want to go back to manually manage memory and that's not sugar. Obviously I'd be back to malloc on those platforms where there are no alternatives. Luckily I don't work on them.

The semicolons usually help me when I'm reading code. I'm not sure if it's because of me being used to them or how my brain is wired. Probably both.

If I were designing a programming language though (no worries, not going to happen), I'd probably still omit the semicolons because I feel (got nothing concrete) that most people don't like them.

On the other hand, I'm not sure how one would objectively eliminate the redundancy without hurting readability by humans and/or machines. Curious if there's some research about this.

Even in natural language the semicolon is a weird construct: one can write perfectly well without it. The same cannot be said of the period for instance, or even the comma. And semicolon's cousin, the colon, serves a very specific purpose, which also makes it indispensable.

I personally find Erlang readable while C not so much. Maybe it has more to do what you are used to than the actual syntax.

> the useless do at the end of almost every defsomething declarations (the compiler should get it by itself.)

That's actually one of the things I personally love about Elixir relative to other Ruby-like-syntax languages (including Ruby itself). Sure, it might technically be extraneous and unnecessary, but it's a nice bit of consistency. Why shouldn't def and defmodule and what have you not be ordinary statements that take a block as an argument?

This is, in fact, consistent with the 'def foo, do: bar' shorthand format in Elixir (and related shorthands like 'if foo, do: bar, else: baz'). No need to have a bunch of different statements that can start a new scope when it's just three more characters to throw a ' do' at the beginning of each of them. Consistent and clear.

Its interesting how you squeezed 'Erlang language' into some syntax choices. Erlang is about actor model, not about pattern matching. Joe had his inspiration from Prolog - it is a well-known fact from publicly available sources.

Anyway, thanks for the article, it sparked some emotions in my brains :-)

I know all that. Long time Erlang dev, former RabbitMQ core dev, so yeah, I've heard already about the Prolog story. Interesting you talk about the Actor Model, since even Robert Virding has said that when they created Erlang they had no idea there was a thing called "Actor Model".

Wow! Ok. Well yes, as far as I know both Joe and Rob agree on that it is accident that Erlang have implemented 'actor model' thing. Also its interesting to note that functional nature of Erlang is very different to ML-family languages. Authors used all these functional stuff because of pragmatics in the first place and not because of solid theory underpinnings.

Yup. See this convo https://twitter.com/old_sound/status/788349221946662912

Joe Armstrong's comment on this post is gold just for this:

    But as Abraham Lincoln said - "don't believe everything you read on the Internet"

It's called pattern matching, and is present in most functional languages - Haskell is a good example of something which uses this style extensively.

In a sense it's derived from the way that some mathematical functions are expressed, e.g. i've seen the fibonacci sequence expressed in this manner a few times.

The only thing this excerpt from the book has to do with Erlang is that they both used the same (existing) idea.

As mentioned already:

>For me what's striking about Erlang syntax is the meaning of the semi-colon and the period, as function clause separator. Most of the rest is just vanilla FP lang syntax.

It's strikes me that everybody notices the pattern matching part, but not the way the clauses are separated, which AFAIK, it's something used by Erlang Syntax only.

And yeah, after working in Erlang and other FP langs for the past 6 years I kinda know this is called pattern matching ;-)

> it's something used by Erlang Syntax only.

Well... and English syntax. In English, you can specify a list of things by separating each thing with a semicolon and then a sentence is terminated by a period. Example:

> Today I would like you to buy coffee; talk to Sarah about the party if you can, otherwise send her a text; drop off the kids; meet me at soccer practise.

You see how the sentence is terminated with a period, each individual item in the list is separated by a semicolon, and the comma is free to use inside each item to indicate related clauses. I've changed nothing about the structure of that list, except replaced the items with function definitions.

> Today I would like you to define f(m, n, r, 1) as f(m, n, remainder of m divided by n, 2); f(m, n, r, 2) as n if r is 0, otherwise as f (m, n, r, 3); f(m, n, p, 3) as f(n, p, p, 1).

It's the same thing, only we've replaced the mundane everyday tasks with function definitions. Now reformat the thing and we get

    Today I would like you to define

      f(m, n, r, 1) = f(m, n, remainder of m divided by n, 2);
      f(m, n, r, 2) = n              if r is 0, 
                      f (m, n, r, 3) otherwise;
      f(m, n, p, 3) = f(n, p, p, 1).

Sure, Erlang syntax happens to coincide with the syntax of English, and I'm not sure whether this was intentional or not, but it certainly has nothing to do with Knuth.

Really you can use semi-colons on a sentence and then end the sentence with a period? And I thought I had learned something during all my years studying linguistics and grammar.

BTW, newsflash: many languages use semi-colons inside sentences. Spanish for example, which could be argued to be older than English. So did Erlang copy Knuth, or Erlang actually copied El Cid Campeador? I think Erlang comes from El Cantar del Cid.

I just find it more likely that Knuth continued to use English for those definitions, and not that he switched to Spanish, or for that matter Erlang.

For me it's pretty clear he was trying to write the algorithms in Spanish, therefore the semicolons.

Semicolon has two uses in English. First, to separate two related sentences in a way weaker than a period. Second, in place of commas separating items in a list where at least one list item contains commas.

It's a poor mind that can only conceive of two uses for a punctuation mark. Sure, those are the two conventional uses for semicolons, but it's far from all the ways a semicolon can be used. Try combining it with reported speech; consider deploying it in lists which don't contain commas (like this one); use it to jam together sentence fragments in poetry; use it to notate interruption in a screenplay; use it to make your smileys wink ;)...

Conventional uses was all I was speaking to. Clarification of that fact omitted for brevity.

F# does the same thing I believe.

With "verbose syntax" F# (just like OCaml) uses ";" as a generic separator and ";;" for ending top-level definitions. It uses "." for attribute (of modules, objects...) selection.

Doesn't most of this syntax come from Prolog?

Likely that was its direct source (Erlang was originally developed in Prolog, IIRC). However, the first volume of TAOCP came out in 1968, while Prolog dates from 1972. It's possible that the Prolog team got the notation from Knuth, and then Armstrong, et al carried it forward into Erlang.

Knuth didn't invent any notation here, it's just standard math.

There are a million languages out there that resemble math notation (mostly functional languages), many of them resemble it much better than erlang does.

This article reminds me of the "JavaScript is Scheme" meme from a while ago. In that people wanted to increase the prestige of their favourite(?) language by shoehorning it into a comparison with something high-status; which comparison, when you think about it, doesn't make much sense.

> Interesting curiosity, which proves that the Erlang Syntax is some sort of Platonic Language Ideal that predates all programming languages.

Because it supports definition by cases and an if-then-else construct? And because it uses the same punctuation marks that ordinary natural language sentences do? Give me a break.

Go get your break, while you are at it, get a laugh or two, because that's what this article is supposed to be about. nobody is so silly to pretend Knuth was describing Erlang on his book.

> Because it supports definition by cases and an if-then-else construct? And because it uses the same punctuation marks that ordinary natural language sentences do? Give me a break.

Yes, the author, a known Erlang developer and a long time programmer really thought Knuth was using Erlang in this book, and, is now trying to convince you to rewrite every single program you wrote in Erlang as well. Geez...

Are we sure it ain't just Prolog?

In particular, Erlang's syntax is heavily derived from Prolog's, so it's natural to conclude that Prolog would be the closer relative to Knuth's syntax.

In reality, though, it's probably the other way around; Prolog's syntax is in turn more-or-less derived from the conventions in traditional math formulas (especially with the uppercase variables and such).

Author confuses standard math notation with erlang, missing the fact that other, more pure, functional programming languages even more closely resemble math notation.

Nothing to see here.

> Author confuses standard math notation with erlang, missing the fact that other,

The article is silly whimsy, you know that? Knowing the author from online presence, I can assure you the author doesn't really think Knuth was writing Erlang at that time.

> that other, more pure, functional programming languages

Maybe the author doesn't care about other more pure functional programming languages. They care about Erlang so they wrote about it.

Commenter confuses satire with serious article. Assumes author doesn't know about functional languages. Nothing to see here.

Uhh, TAOCP predates Erlang by quite a bit. Shouldn't the headline be, "Erlang uses a Donald Knuth-like notation"?

> TAOCP predates Erlang by quite a bit.

Are you sure Knuth wasn't secretly programming in Erlang since the early 50's. He is considered one of the original inventors, it was just too controversial so it was covered up all this time.

I guess we need special whimsy and/or sarcasm tags so people don't take them too seriously...

Knuth also created in TeX the notation used by Microsoft's Rich Text Format (RTF): {\b bold} etc.

omg, wrong way round. It's more math or logic notation.

More like satire logic notation, but who am I to tell at this point.

Honestly I can't tell sometimes if HN is all just satirical internet comments. I read the article, chuckled at the exchange with Joe Armstrong, then opened the HN comments to look at all the grumbling.

Turns out there's plenty.

What is 'satire logic'? Has it got a different notation from the predicate calculus?

This is a good case of where the HN guidelines call for changing a title of an article: "Please use the original title, unless it is misleading or linkbait." https://news.ycombinator.com/newsguidelines.html

A good HN title is accurate, neutral, and close to the language of the original article. If anyone suggests a better title, we're always happy to change it again.

It's not misleading or linkbait. It's just humor. Don't you have humor guidelines at HN?

Jokes certainly have their place but they're context-dependent, i.e. the same title can work fine in one place but not another.

Is the website title HackerNews not linkbait or misleading? I ask since I usually don't see many "hacker News" around here…

It's a category error to conflate article titles and website names, but I'll play along.

Misleading? Arguably, but I don't think it's much of a stretch from "Hacker News" to "news for hackers" to "anything that good hackers would find interesting", which is the mandate of the site (https://news.ycombinator.com/newsguidelines.html).

Linkbait? I doubt it, but I'm biased.

You want to rename it to HackerJokes?

Clickbait title is clickbait.

minimal-syntax languages tend to look similar.

Reply on news.ycombinator.com