Arrow notation?

Question

can someone explain what the following notation is?

For j <- 1 to n
    Legal <- True

I've seen these in various places, including wikipedia articles. It seems to be a specific notation, but I don't know the name and can't find much of anything on it.

Can someone explain what it is, where it's used, if it's in widespread use, and maybe provide a link to a reference or somewhere I can learn the language/symbols and their meaning?

Answer 1

In general, there are no standards for pseudo-code. Everybody can design their own pseudo-code however they want to. Normally, an author should define the conventions they use for their pseudo-code.

Unfortunately, pseudo-code is often used without documenting it, under the assumption that it will be "obvious" to the reader what the code means. As you have discovered, what is and isn't obvious to the reader obviously depends on the reader!

In my case, the snippet you posted is obvious to me, because I am used to programming languages that use the ← operator symbol in the same way: Scala, Haskell, historic Smalltalk.

Arrows generally are used to indicate that "some thing" is "flowing" in the direction of the arrow. A rightwards arrow typically means "goes to" in the sense of a mapping or a function. A leftwards arrow typically means "becomes" or "let" or "draws from". However, arrows can also indicate message sends or receiving messages. You have to be aware of the context.

This code looks like it is simple imperative structured programming code, so the "assignment" meaning is the more likely interpretation, but if this where pseudo-code for some process calculus, an asynchronous, concurrent, parallel, or distributed algorithm or data structure, or something along those lines, it could likely also mean "blocks until it receives a message" or something like that.

In this particular case, the two leftwards arrows have slightly different, but strongly related meaning:

The second one simply means "Legal becomes True", so this is a form of assignment. (This assignment syntax was actually used by historic Smalltalk versions.)

The first one also means assignment, but it is interpreted to mean that j takes all the values on the right-hand side, one after the other. In other words, this is a FOREACH iterator loop. (Scala actually uses the leftwards arrow in precisely this meaning in its for comprehensions.)

Answer 2

Left arrows often mean assignment or modification. This pseudo-code can be interpreted as

"For j from 1 to n, the variable Legal is given the value True"

Check this page: https://en.wikipedia.org/wiki/Pseudocode#Common_mathematical_symbols

Answer 3

This notation, and others such as :=, is a reaction against the use of = for assignment, which some computer scientists find deplorable, due to that symbol's role as a pure relation in mathematics.

There is an anecdote I recall from very long ago about some famous computer scientist, perhaps Dijkstra, having become outraged during some seminar lecture and loudly yelling out "becomes! becomes!" at the point when the presenter had written or projected an "a = b + c" expression which he then began reading out loud as "a equals b plus c".

That <- symbol is "becomes". It's intended to thwart being read as "equals" and any confusion which that might entail.

Here is a true story of my own: he first time I had ever seen a computer program, which was written in line numbered BASIC and contained a few lines of variable assignments, I was really puzzled because I thought that this was a system of equations being declared for the machine to solve! "But how on Earth can X be equal to X + 1??!" I thought.

Answer 4

I think this is often used in pseudo-code to distinguish between equality and assignment because different languages have different rules for how this works. For example, = can be an assignment or copy in c++ and javascript has a table of rules on how equality checks works. The point of pseudocode is not to depend on language conventions and to attempt to be unambiguous in what the code does.