The Artima Developer Community
Sponsored Link

Weblogs Forum
For Loops

10 replies on 1 page. Most recent reply: Sep 14, 2005 7:02 AM by Michel Parisien

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 10 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

For Loops (View in Weblogs)
Posted: Sep 11, 2005 12:44 PM
Reply to this message Reply
Summary
For loop constructs in programming languages are usually syntactic sugar, but what should they map to?
Advertisement
In C/C++ a for statement maps from:
for (initialization_statement; boolean_invariant_condition; variant_statement) 
  loop_body
to more-or-less the following:
{
  initialization_statement;
  while (boolean_invariant_condition) 
  {
    {
      loop_body;
    }
    variant_statement;
  }
}
I wanted do something new with for loops in Heron which leverages generics. Here is the general form:
for iterator_type iterator_name in iterable_expression {
  loop_body
}
Some examples:
for int i in range(0, 100) { 
  write_int(i); write_char('\n'); 
}

for char c in "hello" {
  write_char(c);
}

for object o in (42, 3.14, 'q') {
  write_object(o);
}

I am happy with this so far, but I want to go further and generalize the notion so that programmers can define new constructs like for-loops. For instance I would like to be able to iterate over the collection in an non-deterministic order. This is important for optimization on concurrent machines.

The best way to generalize this I can think of is to use closures. This way for-loops and programmer defined constructs can map to anonymous functions. The problem right now is trying to figure out an elegant and efficient way to implement closures in HeronFront. In order to implement closures in C++, It seems I have to generate a context data type and pass it to the anonymous function.

Any thoughts?


Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: For Loops Posted: Sep 11, 2005 2:18 PM
Reply to this message Reply
Your for loops look almost identical to Python's.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: For Loops Posted: Sep 11, 2005 5:46 PM
Reply to this message Reply
> For loop constructs in programming languages are usually
> syntactic sugar [...]

> Any thoughts?

This might interest you: http://mlton.org/ForLoops. I also have a considerably more expressive version in my own utility library, but there is a possiblity that MLton does not optimize it as well as the version on the page (I haven't verified it, yet, so I may publish the more expressive version later). The more expressive version includes more stuff inspired by Common Lisp's loop macro.

The point of all this is that you don't necessarily need to put for loops into the core language. For loops don't have to be builtin if your language is expressive enough to build for loops out of combinators (as in SML) or using macros (as in Common Lisp and Scheme).

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: For Loops Posted: Sep 12, 2005 10:14 AM
Reply to this message Reply
> Your for loops look almost identical to
> Python's.

They do, thanks for pointing that out.

I have some questions about Python for loops:

In the examples:

for x in a:
print x, len(x)


The iterable expression is always a variable, is that mandatory?

They also say: "It is not safe to modify the sequence being iterated over in the loop"

Now that concerns me, what does "not safe" mean? Does Python actually have UB (Undefined Behaviour)? That would be pretty funny. How can a programmer safeguard against that kind of problem?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: For Loops Posted: Sep 12, 2005 10:27 AM
Reply to this message Reply
> This might interest you: http://mlton.org/ForLoops.

Thanks for pointing that out. I really appreciate Vesa taht you bring an ML viewpoint to the discussions.

> I also
> have a considerably more expressive version in my own
> utility library, but there is a possiblity that MLton does
> not optimize it as well as the version on the page (I
> haven't verified it, yet, so I may publish the more
> expressive version later). The more expressive version
> includes more stuff inspired by Common Lisp's loop macro.

How efficient is the ML for loop, when compared to an imperative construct? I benchmarked Scala's for comprehensions at one point and was quite dismayed. It was more efficient to write

> The point of all this is that you don't necessarily need
> to put for loops into the core language.

I completely agree.

> For loops don't
> have to be builtin if your language is expressive enough
> to build for loops out of combinators (as in SML) or using
> macros (as in Common Lisp and Scheme).

I am currently considering that possibility that statements can be pass as type parameters to meta-functions. This could allow macro-like behaviour but integrated into the type-system.

Morel Xavier

Posts: 73
Nickname: masklinn
Registered: Sep, 2005

Re: For Loops Posted: Sep 12, 2005 2:15 PM
Reply to this message Reply
> The iterable expression is always a variable, is that
> mandatory?

I'm not sure if that was what you were looking for, but Python allows you to use any iterable structure, and has 2 constructs for iterable ranges out of the box (namely "range" and "xrange") with a reversing operator (reversed), allowing you to build any numeric range you may need.

Python's range and xrange take 3 arguments: upper bound, lower bound and step, with step defaulting to 1 and lower bound defaulting to 0, upper bound is required (obviously).

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: For Loops Posted: Sep 12, 2005 5:58 PM
Reply to this message Reply
It's also pretty close to Ada's (for I in Data_Index loop ... end loop;).

Not that I like Ada. Just suggesting that there may be an even older language (perhaps Algol) that did things that way.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: For Loops Posted: Sep 13, 2005 8:23 AM
Reply to this message Reply
> How efficient is the ML for loop, when compared to an imperative construct?

It can be very efficient. The (time) efficiency of MLton generated binaries is comparable to the efficiency of binaries generated by C compilers.

Note that Standard ML specifically does not define a for-loop construct (in fact, it can be said that Standard ML does not define any iteration mechanisms). However, you can implement such a thing (in many ways) in the language. The efficiency of each approach depends on the particular compiler. In terms of efficiency, this isn't really any different from an imperative language. The efficiency of for-loops depends on the implementation of the language. Some C compilers produce faster for-loops than others.

However, there are good reasons to expect good performance from the particular for-loop implementation on the page http://mlton.org/ForLoops. I'll elaborate the reasons briefly. The only fundamental way to implement iteration in SML is through recursion (pseudo code):

   let
      fun loop x =
         if isEndOfLoop x then
            ()
         else
            loop (doSomethingWith x)
   in
      loop initialX
   end


SML compilers striving for efficiency are designed to generate efficient code for recursive functions (such as the above). Good SML compilers can essentially turn the above to something comparable to what compilers for imperative languages do for (pseudo code):

   begin
      x = initialX
      while not (isEndOfLoop x) do
         doSomethingWith x
      done
   end


IOW, good SML compilers can keep the inner loop variables in registers and generate jmp-instructions rather than call+ret-instructions for the loop.

Now, let's take a look at the to-combinator from the http://mlton.org/ForLoops page (reformatted):

   fun op to (a, b) f =
       let
          fun loop a =
             if a < b then
                (f a; loop (a+1))
             else
                ()
       in
          loop a
       end


As you can see, the loop-function inside the to-combinator is essentially just like the previous example of a(n imperative) loop in SML. An invocation of the to-combinator looks essentially like this:

   (lo to hi) (fn x => ...)


All that a SML compiler needs to do to generate efficient code for the above is to instantiate (inline) the to-combinator with the specific anonymous function (fn x => ...). After that, the same optimizations that work for the previous example loop will do.

Similar arguments apply to the other combinators. SML compilers are quite good at dealing with control flow optimizations.

Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: For Loops Posted: Sep 13, 2005 8:59 AM
Reply to this message Reply
Sorry for taking my time on my reply. I've been sick all week.

As mentioned above, Python has a structure called "xrange". xrange is like range, except the values returns are generated on the fly. The rule of thumb is not to use this unless your range might have thousands of values, as it is supposedly a tad slower, but I have never seen xrange be a bottleneck in a program.

Also, python has native iterable support. Instead of the word "return", you can use the word "yield", and so each time you hit a yield, it returns a value, and the next time you call the instance of the function, it will continue where it left off, with all the values intact.

So to summarize: though python is a big fan of passing a static list right from the start to a for loop, you can, with iterables, essentially have it return any value you want to changing circumstances, without needing a big chunk of memory if you want, for example, to loop from 1 to 1 billion.

As for that page saying changing the iteration is dangerous: keep in mind that my link was to the tutorial, which is more or less "Python for dummies". All they're warning against is that generally, if you're going to change the value of your iteration range on the fly, you're probably not doing things right. But this is something that applies to any language.

Morel Xavier

Posts: 73
Nickname: masklinn
Registered: Sep, 2005

Re: For Loops Posted: Sep 13, 2005 11:35 AM
Reply to this message Reply
> Sorry for taking my time on my reply. I've been sick all
> week.
>
> As mentioned above, Python has a structure called
> "xrange". xrange is like range, except the values returns
> are generated on the fly. The rule of thumb is not to use
> this unless your range might have thousands of values, as
> it is supposedly a tad slower, but I have never seen
> xrange be a bottleneck in a program.
>
That's not true, it's actually always better (or so the Python documentation states) to use xrange over range for iterations: marginally better for regular iterations (xrange is minimally faster) but xrange is much more memory-efficient, and also faster when the loop does not end (when you get out through a "break").

Basically, range creates every value out of the box while xrange creates them on the fly. CPU consumption therefore roughly the same whichever you use but spanned across the whole iteration for xrange (while range is a "huge" [relatively] overhead and then [roughly] null consumption), but range has to store every single value while xrange never stores more than one at a given moment.
> Also, python has native iterable support. Instead of the
> word "return", you can use the word "yield", and so each
> time you hit a yield, it returns a value, and the next
> time you call the instance of the function, it will
> continue where it left off, with all the values intact.
>
What you describe here is not the "iterable" protocol, it's (the main) part of the "generator" protocol. A generator's specificity is that it is a function (the iterable protocol applies to an object), and that yield throws an expression before returning to the function in the exact state it was left in when yield was called.

A regular iterable object merely needs to implement the "iterable" protocol, which means that it needs a "__iter__()" and a "next()" method with "__iter__()" returning the iterator object and "next()" returning the next item of the iterable container.

Michel Parisien

Posts: 25
Nickname: kriggs
Registered: Jul, 2005

Re: For Loops Posted: Sep 14, 2005 7:02 AM
Reply to this message Reply
> That's not true, it's actually always better (or so the Python documentation states) to use xrange over range for iterations: marginally better for regular iterations (xrange is minimally faster) but xrange is much more memory-efficient, and also faster when the loop does not end (when you get out through a "break").

Funny. I remember reading a while back that Guido prefered "range" for speed. After looking for it myself in the documentation, I found this:

http://docs.python.org/lib/typesseq-xrange.html

"The advantage of the xrange type is that an xrange object will always take the same amount of memory, no matter the size of the range it represents. There are no consistent performance advantages."

So, for the hell of it, I just ran my own test, and found my results to support the above:

for i in xrange(someBigNumber):
for j in range(100):
x=1+1


versus

for i in xrange(someBigNumber):
for j in xrange(100):
x=1+1


I tried 100 here, but I also tried 1 and 10. I found that, on my Pentium running Windows, the difference in time was negligeable (sometimes, range would win, others xrange would win). This combined that it might change from one implementation to the next, my results show that it isn't really worth a debate (ie. I was at fault for mentioning speed in the first place). I would be interested in the results from someone who has tested on 5+ different implementations, if you would happen to know where I could find that. Also, could you point me to where in the documentation you saw that xrange was faster? I was looking, but I couldn't find it.

> What you describe here is not the "iterable" protocol, it's (the main) part of the "generator" protocol.

For some dumb reason, I made the decision to use "iterable" instead of "generator" since I thought, from a C/C++ programmer's perspective, that iterable would be more readily understood. I wasn't being too technical in my reply. This was a lapse of judgement on my part, since I usually will use the vocabulary of the particular language of which I am speaking. I would like to thank you however for pointing this out to me.

Thank you for being thorough. No more will I make a assumptions that I can get away with anything when posting on these Heron forums ;)

Flat View: This topic has 10 replies on 1 page
Topic: East of West and West of East: Engaging Other Academic Cultures Previous Topic   Next Topic Topic: Myths of Memory Management


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us