I know get how logical operators for if logic gates work, but I am trying to understand how while loops fit into that picture. I realize that this question is a bit vague. It all started because I was wondering if one could write a while-loop with a series of if statements. Then I realized there had to be something deeper in our programming languages.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ They are not magical at all once you have "goto" statement. And "goto" itself might be implemented at low-level as simple storing a value to PC register. $\endgroup$– VladislavCommented Mar 20, 2020 at 9:08
-
$\begingroup$ Thank you, Vladislav for your comment. I will change the wording. That is what I was getting at. Do you find my question and description to be unclear? $\endgroup$– Paul D. P. BlumCommented Mar 20, 2020 at 9:24
-
3$\begingroup$ It was clear enough already. The answer remains the same: "goto" statement. You can rewrite while-loop as combination of "if" and "goto". $\endgroup$– VladislavCommented Mar 20, 2020 at 9:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Vladislav is right, but there is more that can be said.
A loop means running some code, and then running it again. An if just conditionally branches to two different bits of code. If one of those bits of code can jump back to the earlier code, or to the if itself, then you can get a loop. So you need something that can jump somewhere else. A goto is one command that does that in some languages. You have to have a way to naming or identifying where the jump is to, though, even if it's just by a line number.
Another way to implement a loop is with recursion. To do that, you need to be able to name procedures or functions or targets, and then embed the call to the named code in one of the branches of the if. (In tail-recursive languages such as Common Lisp and Scheme, this can be as efficient as a loop in some circumstances.)
In both cases, it's crucial that there be a way of referencing earlier code, and jumping into it. If you don't have that, an if won't be enough. (But see below.)
You could do without the named code if you knew that your while "loop" didn't need to perform more than $n$ iterations. Then you just expand the loop explicitly:
run my code
if something is true then stop
else run my code
if something is true then stop
else run my code
if something is ....
However, naming isn't actually required in order to loop without just writing the same code repeatedly. You can do it with recursion, as noted above, but it's possible to define a recursive function using a Y combinator. This is probably not very efficient, and if your language evaluates eagerly, as most do, it's kind of a mind-twister at first (it's simpler in with certain kinds of delayed evaluation), but it works, and it's cool. (My favorite source for the complicated version that most languages need is The Little Schemer by Friedman and Felleisen; you can probably find the simple version in any book on lambda calculus. That's the version described in the Wikepedia page, so maybe that's enough.)
In answer to the title of the question, in hardware there has to be some jump to a location--probably the same location--that causes the same code to be executed repeatedly--or some way of getting the same code to start running in the CPU, such as rewriting the stack. Others will be able to say more about this.
(It would be appropriate if the Y combinator function was named after Paul Graham's Y combinator company, since the company is named after the function. Graham's book on lisp On Lisp discusses recursion without naming, but very briefly, in an endnote on pages 387-388.)
