7
$\begingroup$

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?

$\endgroup$
4
  • 5
    $\begingroup$ Some authors prefer to use the $\gets$ notation when writing pseudocode because it clearly distinguishes between equality and assignment. And yes, it is in widespread use. $\endgroup$ – Steven Feb 21 at 20:31
  • 2
    $\begingroup$ It was also used in Smalltalk, back when Smalltalk still had its own keyboard and character set. Nowadays, Smalltalk uses :=. (In between, it used _ which is the ASCII character with the same encoding as had in the original encoding.) Haskell also uses it in monad comprehensions and list comprehensions, Scala uses it in for comprehensions. $\endgroup$ – Jörg W Mittag Feb 22 at 6:35
  • 2
    $\begingroup$ R uses it for assignment. In recent versions of R = is also possible, but using <- is still more common. $\endgroup$ – John Coleman Feb 22 at 15:13
  • 1
    $\begingroup$ I see this used most when written by people with math background or by people who want to write maths in their pseudocode. As @Steven points out, it clearly distinguises between asigment and math, so if you do i=i+1 this does not get confused by a math equation. $\endgroup$ – Ander Biguri Feb 23 at 11:09
11
$\begingroup$

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.)

$\endgroup$
5
  • 1
    $\begingroup$ I don't think you can find a single person who knows programming but cannot figure out what the first line means, and therefore also what the second line should mean. Of course, I'm not against documented conventions, but at some point it's really not necessary because it is clear to the intended audience. $\endgroup$ – user21820 Feb 22 at 13:21
  • $\begingroup$ It's easy to figure out what it probably means, obviously (there aren't a lot of things it can mean in the given context: an arrw is bound up with the idea of direction, which in turn would suggest either input or output). But that's not very certain. My question was more interested in understanding if it's a well-established system with clear-cut rules. I've finally found this as well en.m.wikipedia.org/wiki/Arrow_(computer_science) , which seems to be related but where notation gets more complex. $\endgroup$ – Daniel Feb 22 at 14:26
  • 1
    $\begingroup$ @Daniel: Actually, that's kind of the other way around. The name of the Arrow type class was chosen because this type class is an abstraction that can be used to encode many things we would generally write with arrows. $\endgroup$ – Jörg W Mittag Feb 22 at 16:23
  • $\begingroup$ @user21820 I'm not confident I can say for sure what the second line means. Sure, the obvious interpretation is assignment, but why would you assign a constant to the same variable n times? Edit: or possibly Python is poisoning my brain, and there is more that has been omitted $\endgroup$ – Mike Caron Feb 22 at 21:36
  • 1
    $\begingroup$ @MikeCaron: Silly people do stupid things in programming. That doesn't change the most likely interpretation of the syntax here. Sure, we may have suspicions about whether the example is complete or there is some trick, but the most likely explanation is that it was a silly programmer. Anyway, the very slight uncertainty is why I said "what the second line should mean". $\endgroup$ – user21820 Feb 23 at 6:50
8
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ If someone knows the reference for this story, I would be much obliged. $\endgroup$ – Kaz Feb 23 at 0:48
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.