1

I'm trying to understand what this pseudocode does and I can't seem to understand what the comma is suppose to do here.

I know that j <- 1 is j = 1 but what about the i? And what does j <- j do in this case?

 fib iter(n) 
    i,j ← 1 
      for k ← 1 to n−1 
      i,j ← j,i + j 
    return j 
  • 6
    It means whatever the author of that pseudocode has defined it to mean. The author of that pseudocode is the only person who can tell you that. – Jörg W Mittag Feb 24 at 7:43
  • 1
    I'm not 100% certain, but I think this is actually actual code. I'm blanking on the programming language, but I'm pretty sure I've worked with this syntax before... though having said that, I'm now reminded of a professor I had in college who wrote his psuedocode in SmallTalk, but when I tried to talk with him about SmallTalk, he claimed ignorance. A week later he thanked me for introducing him to a language that worked so much like how he thought. So I suppose it could be both valid code and pseudocode. – Ed Grimm Feb 24 at 8:18
  • 2
    @JörgWMittag While that's technically true, we can make a pretty good guess from circumstantial evidence here: the inclusion of the word "fib", and the fact that reading it a certain way would result in a generator of Fibonacci sequences could just be coincidence, I suppose. – IMSoP Feb 24 at 9:06
  • @IMSoP: We can assume, for example, that i,j ← 1 means parallel assignment. But, there are essentially two ways to interpret this: either i is assigned 1 and j is assigned null (or whatever the equivalent in this pseudocode is), or i is assigned null and j is assigned 1. The former is how the equivalent expression i, j = 1 would be interpreted in Ruby (i == 1; j == nil), for example, the latter is how let i, j = 1; would be interpreted in ECMAScript (i === undefined; j === 1;). Which one of the two is the intended meaning, only the author can say. – Jörg W Mittag Feb 24 at 10:26
  • 3
    @JörgWMittag You're still ignoring the context. If this is in fact an algorithm for generating Fibonacci numbers, we know exactly what i and j need to be initialised to. Even without that, we can rule out a deliberate assignment of null, because it would make the use of i+j a few lines later meaningless. I mean, it could mean "set i to the string ','" but Occam's razor suggests this is a commonly illustrated algorithm, using a straightforward integer addition, and that i and j both need to be initialised to 1. – IMSoP Feb 24 at 10:40
10

Assuming this is the algorithm for a Fibonacci number generator, it represents simultaneous/parallel assignment; the comma is not separating two statements, but two operands to the <- operator.

In i, j <- 1, both i and j are set to 1; it's just shorthand for i <- 1 and j <- 1, which could happen in any order.

In i,j ← j,i + j, it means i <- j and simultaneously j <- i+j. It's necessary for both to happen at once, because you need to use the original values of both variables.

In a language without that facility, you'd have to introduce a temporary variable:

i2 <- i
i <- j
j <- i2 + j

or

j2 <- j
j <- i + j
i <- j2 

This may be based on a real language with this syntax, or it may just be a convenience for the algorithms being discussed. For instance, sort algorithms will often be written in a pseudocode with a "swap" operator of some sort, rather than the full set of instructions needed in a particular language, in order to focus on the most relevant details.

3

It most likely is a tuple assignment, i.e. assigning multiple values on the right to multiple variables on the left, with a shortcut to have only one value on the right which will be assigned to all variables. so

i,j ← 1 

is the same as

i ← 1
j ← 1  

And

i,j ← j,i + j 

is a bit more complicated because it changes a variable it also uses, but the same as

tmp ← i + j
i ← j 
j ← tmp 

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.