Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: If I was forced to use only one kind of loop for the rest of my days it would be a

by ambrus (Abbot)
on Sep 29, 2005 at 19:12 UTC ( #496210=note: print w/replies, xml ) Need Help??


in reply to If I was forced to use only one kind of loop for the rest of my days it would be a

I certainly wouldn't think it's a drag to use just one kind of loop: it can be kind of elegant. However, the rest of my life is just too long, my opinion on which single loop is elegant varies with time. Also I wouldn't use a single loop just because I'm forced to it: I like TIMTOWTDI languages that don't force me to use a single programmign style.

Scheme basically has one kind of looping construct: tail recursion. However, it has some advanced special forms built upon tail recursion. It has let which is just a short notation for tail recursion. But the most important looping construct is do which is by itself so powerful that one could program using only it. However, using do comes out really good only if you're doing side-effectless programming, which I don't always like. (There's a do form in common lisp too, which is similar in form but very different deep down. That do <disgust>changes the values of loop variables</disgust>, so it's not side-effect-less, and has nothing to do with tail recursion which Common lisp doesn't have anyway.)

What I've said above is not entirely true: there's one more way of looping in scheme apart from calls and tail calls: call-with-current-continuation is by itself a universal looping construct. It's however not something I'd use as a single looping construct in my whole life. (Even worse than that would be to use only setjmp/longjmp in C.)

If my mind is in a low level state, I could live with only conditional gotos.

If I program C, I'd definitely go with for. (That's what I've voted for.) It's just much more general than while. To tell the truth, just about any looping construct is more general than while. It's also nice that you don't have to look at keywords if you only use if and for as they have different number of argumets. So, I definitely don't like while. (Update: I forgot to mention it, but I did mean using only for seriously: Re: Pattern matching)

At one time, I thought that the best looping construct was { ...; ... and last; ...; redo }. This is not only my mania, as the while loop in bash, and the \loop ... \repeat macros in Plain TeX work like this.

At that time, I actually wrote a toy language where the only looping construct was ( COMMANDS; *) which executed COMMANDS repeatedly. You can exit from it with the COND ? RET operator which exited from the innermost pair of parentheses iff COND stands, and make the result of the parenthisized expression be RET.

This is actually a bit more general than the above, because you can use more of these statements in a single loop. This ? operator also served as the single way to do conditional expressions, as you can use it in a non-looping pair of parentheses, so (COND? THEN_PART; ELSE_PART) is a conditional expression. If COND is true then the THEN_PART is evaluated, and than the question mark exists from the parenthesis, so ELSE_PART isn't evaluated. If COND is false, than THEN_PART is not run, so execution proceeds to ELSE_PART. It's easy to do if-elseif constructs the same way. The question mark was chosen for this shallow analogy with (COND ? THEN_PART : ELSE_PART) in C or perl. (The language also has functions, but not tail calls. I haven't implemented that the functions could receive arguments, but that can be worked around using lexical variables and assignments. There's also a syntactic sugar COND ! RET which does the same as ? but negates the COND. To tell the truth, I've added short-circuitting and and or conditional operators in later versions, which sort of breaks the elegance of ? and !.)

I certainly wouldn't choose foreach as the single looping construct, as I've learnt that it wouldn't give me a Turing-complete language. In logician terms, we say that you can build constructive languages from foreach, which is a true subset of the set of recursively enumerable languages.

Update 2010-10-17: see also the other poll Re: My favorite looping mechanism in Perl is:.

  • Comment on Re: If I was forced to use only one kind of loop for the rest of my days it would be a
  • Select or Download Code

Replies are listed 'Best First'.
Re^2: If I was forced to use only one kind of loop for the rest of my days it would be a
by BerntB (Deacon) on Sep 30, 2005 at 03:36 UTC
    However, the rest of my life is just too long
    Someone has better statistics of heart problems among their relatives than I have... :-)
    wouldn't choose foreach as the single looping construct, as I've learnt that it wouldn't give me a Turing-complete language.
    A language with 'if' statements, blocks and foreach should be Turing complete? Write a state engine with if conditions -- put inside an infinitely looping foreach. (-: To get that foreach, lazy eval would be a feature, of course. :-)

    To chose goto and learn source filtering to get everything else is cheating, I guess.

      That's it: an infinitely looping foreach isn't a foreach. It's not a foreach in perl. It's not a for-each in standart scheme either, as r5rs clearly says that the arguments to for-each are lists. (In some interpreters, you can give an infinite list to for-each, but that's clearly an extension. Others, like mzscheme, raise an error on an infinite list.) For in sh and foreach in csh won't allow you to loop infinitely (except for the new arithmetic for loop in bash, but that's not a foreach loop, it's rather a c-style for loop).

        But you said Turing complete.

        A Turing machine is a theoretical construct that needs an infintely long tape, so any implementation has to be a subset, without invoking religion (-: and then you first have to prove that the g.d you use really exists :-).

        So isn't it a bit non-gracious to complain about an infinite list?

        I mean, it wouldn't be impossible to use a tied array. (The semantics for how a list is created makes that impossible, I think?)

        (define a (list 1 2 3)) (set-cdr! a a) (for-each (lambda (x) (display "hello world\n")) a)
Re^2: If I was forced to use only one kind of loop for the rest of my days it would be a
by Anonymous Monk on Sep 30, 2005 at 16:19 UTC
    If I program C, I'd definitely go with for. (That's what I've voted for.) It's just much more general than while. To tell the truth, just about any looping construct is more general than while.
    Now I'm curious. Could you give an example of a loop you could write with "for" that you couldn't write with "while"?
    #include<stdio.h> int main(int argc, char** argv) { int a = 0; while(a++,a<10) { printf("%d\n",a); } }
      While it's true you can do anything you can do with a for loop with a while loop, I picked for.

      I really like the capability that for gives you to keep all the operations controlling the loop - initialisation, incrementing and testing - in one place. In C99 (and Perl) you can declare variables in the for statement, and they will have a scope of precisely the for loop. You'll need an extra block to do that with while. So taking the example above, I assume this is intended to synthesise (updated:) ambrus noted that this is equivalent to:

      // UNTESTED for(int a = 1; a<10; a++) { printf("%d\n",a); }

      In fact, you'll need an extra block to get the correct scope:

      // UNTESTED // UPDATED: de-obfuscated { int a = 1; while(a<10) { printf("%d\n",a); a++; } }

      Which is starting to look rather messy.

      Context switch back to Perl here!

      Synthesising while and foreach from for seems reasonably intuitive to me on the other hand.

      # UNTESTED for (;EXPR;) BLOCK # leave first and third EXPRs blank to be # equivalent to while (EXPR) BLOCK # UNTESTED for (my @list = LIST, VAR = shift @list; # iterate manually through @list; # LIST in "for" to be VAR = shift @list) BLOCK # somewhat like # foreach VAR (LIST) BLOCK # without the usual aliasing

      OK, the foreach is starting to look a bit funny, but a foreach from while will be worse, and spread into the block, rather than be confined to the statement itself.

      One issue is that for doesn't have a continue block, but as I come from C I don't tend to use those. continue blocks also split up code that happens every time round the loop, which puts me off. for's third expression is roughly equivalent I suppose, but stuffing a large continue block there could hardly be called good style.

      Recursion is another story but I don't think I could live with it as the only looping mechanism. I'd rather have the reverse issue of synthesising recursion, say with a list of hashes, on the rare occasions I really needed it.

      updated in response to ambrus's comments.

      Also, note:

      perl -MO=Deparse -e "for (;<>;){print}" while (defined($_ = <ARGV>)) { print $_; } -e syntax OK

      the for deparses as a while!

        In fact, I belive

        for(int a = 0; a<10; a++) { printf("%d\n",a); }
        is equivalent to
        { int a = 0; while(a<10) { printf("%d\n",a); a++; }
        Your other code,
        { int a = 0; while(a++,a<10) { printf("%d\n",a); } }
        doesn't run the printf statement with a = 0.

      In C, there's no such loop. But that's true to goto and most other constructs as well, you know. It's just that I like the foreach version of the loop more.

Re^2: If I was forced to use only one kind of loop for the rest of my days it would be a
by Anonymous Monk on Sep 30, 2005 at 16:25 UTC
    I certainly wouldn't choose foreach as the single looping construct, as I've learnt that it wouldn't give me a Turing-complete language. In logician terms, we say that you can build constructive languages from foreach, which is a true subset of the set of recursively enumerable languages. Who cares about Turing completeness? You're running on a machine with a finite number of states; so a DFA language is all you can really implement in real life. Turing complete languages can't be implemented; just approximated. Godel's theorem implies that any language you design is by definition incomplete; no matter how big you make the field of numbers that it enumerates, you can make an infinite number of infinitely more expressive languages (which is unsurprising, since Cantor proved that there are an infinite number of magnitudes of infinities, making the whole thing hard to talk about...) It's silly to stop with a Turing machine; why not work over a bigger field than the integers, if you're just doing abstract math for the fun of it? And if you're not just doing abstract math for the fun of it, why are you bothering to talk about infinity at all? -- AC
      Who cares about Turing completeness? You're running on a machine with a finite number of states; so a DFA language is all you can really implement in real life. Turing complete languages can't be implemented; just approximated.

      I could attack this statement from the theocretical side. Computer hardware is developping in a very fast pace. Let's imagine you have a system where the state of the program can be saved and reloaded on a machine with more memory, or one that runs on a transparent cluster of machines where new nodes can be added dynamically and old nodes discarded. Such a system could run forever, if you keep updating it with new hardware. While my lifetime or the lifetime of the computer I'm typing on right now is certainly finite, such an advanced system could live forever, if the civilisation doesn't end in some catastrophe. (In fact, Paul Davies argues in his book The Last Three Minutes that a super-entity could do an infinite number of calculations, and discusses this in the two cases of whether the Universe will expand forever and end in a Big Chill, or gravitation will win and the Universe will end in a Big Crunch.)

      However, even if a DFA is all you can implement in the real-world (there are some steps between the DFA and a Turing machine in power of course), I am a mathematician, and I'd like to at least imagine that I have a Turing-complete machine. I use it even if it's only a theocretical construction. I am not an engineer, who uses a ruler to draw straight line, and uses large plastic templates to be able to draw any kind of ellipse. I just draw a bumpy line or a potato by hand, and say it's a straight line (moreover, an infinitely extending straight line that has no width or thickness) or an ellipse. This is a very pleasant, almost god-like state, because I can create objects engineers can't even dream of just by the power of my mind.

      Naturally, this is not the real reason I wouldn't rely on foreach loops. The reason is simply that they're often difficult to use. It's not easy to convert while loops to foreach loops. It's even more difficult to do it if you care about efficency (because I don't just have any DFA, but a DFA with a limited number of states and limited speed of execution). Foreach loops require to use side-effects even if I don't want to, and you could easily avoid it with do loops. Foreach loops come in different versions in each programming language. But the deciding reason is that C doesn't have a foreach loops, so if I decided on foreach, I couldn't use C anymore.

      Update: "it's silly to stop with a Turing-machine" -- you're right with this part. "Why not use a bigger field(?) than the integers" -- indeed, why not: Symbolic calculations with operator overload, Re^3: Illegal Modulus zero.

        I could attack this statement from the theocretical side. Computer hardware is developping in a very fast pace. Let's imagine you have a system where the state of the program can be saved and reloaded on a machine with more memory, or one that runs on a transparent cluster of machines where new nodes can be added dynamically and old nodes discarded. Such a system could run forever, if you keep updating it with new hardware.

        Nope, not even theoretically possible, unless you're much more theoretical than me. You need infinite memory as well as infinite time; where are you going to get infinite matter? It would take infinite energy to assemble it all. It would take infinite space to put it, and we're pretty sure the universe is finite, even if constantly expanding.

        Worse yet, any system we can concieve of has some critical component with non-zero probability of failure. Over infinite time, that non-zero failure probability becomes a certainty. To my mind, anything that requires perfect anything as a theoretical condition of it's existance is just a mathematical excercise, and there are more interesting ones out there.

        Update: "it's silly to stop with a Turing-machine" -- you're right with this part. "Why not use a bigger field(?) than the integers" -- indeed, why not: Symbolic calculations with operator overload, Re^3: Illegal Modulus zero.

        I wasn't trying to argue for computer implementation of various fields (the most basic being simple polynomials), nor was I looking for a first year primer on group theory. Thanks, but I've been to school once already. :-)

        My point was, if you're just in it for the complex mathematical abstraction, you can carry a Turing machine as far as you like. Cantor's theorems (together with some others) imply that you can make fields as arbitrarilly large as you like: for any field you care to name, there's a field extension that will make it infinitely bigger, even if the field already was infinite in size. Godel's theorem states that the field extension can never be large enough; for any field with basic, interesting properties, there is always a proposition which has a truth or falsehood which is expressable in a given field, but the truth or falsehood of that statement is not resolvable within that field, but only (possibly) in some field extension.

        You can build an infinite number of meta-Turing machine models in your head, and use them to do transfinite arithmetic if you so choose. None of it means anything, though; you're stuck with boring old DFAs when it comes down to what you can really ever build, so trotting out Intro To Theoretical Computing is nice and all, but in the real world, we can't even factor million digit numbers, let alone infinitely large ones. It would be nice to solve the optimal Travelling Salesman problem for all the cities on the planet, but we can't even do a single country. It's a long, long way to infinity! -- AC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://496210]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (6)
As of 2019-10-15 01:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?