Hi all,
I was looking at the implementation of some of the flow control methods and I have a question with the method *whileTrue*.
First of all, I can see two identical implementation in the classes * BlockClosure* and *BlockContext* the implementation is this
*whileTrue*: aBlock "Ordinarily compiled in-line, and therefore not overridable. This is in case the message is sent to other than a literal block. Evaluate the argument, aBlock, as long as the value of the receiver is true."
^ [self value] whileTrue: [aBlock value]
I'm assuming here that there's another class *Block* I'm missing (something like the literal block mentioned in the comment) which is the one that contains the logic I was looking for. But I'm not able to find any other whileTrue method in my image. What's the difference between BlockClosure and BlockContext?
Thanks, Erlis
On 04.10.2011, at 17:58, Erlis Vidal wrote:
Hi all,
I was looking at the implementation of some of the flow control methods and I have a question with the method whileTrue.
First of all, I can see two identical implementation in the classes BlockClosure and BlockContext the implementation is this
whileTrue: aBlock "Ordinarily compiled in-line, and therefore not overridable. This is in case the message is sent to other than a literal block. Evaluate the argument, aBlock, as long as the value of the receiver is true."
^ [self value] whileTrue: [aBlock value]I'm assuming here that there's another class Block I'm missing (something like the literal block mentioned in the comment) which is the one that contains the logic I was looking for. But I'm not able to find any other whileTrue method in my image.
"Block" is just short for either BlockClosure or BlockContext. "Literal" blocks are those written directly with square brackets. If you store a block in a variable and pass that variable, the block would not be literal.
What's the difference between BlockClosure and BlockContext?
BlockClosures are BlockContexts Done Right.
If you wrote square brackets in older Squeak versions (3.x) you would get a BlockContext. In a current Squeak you get a BlockClosure.
So since now we only have closures, the difference is only of historic interest. You can do some things with closures that you couldn't do with block contexts, e.g. recursive blocks:
| fac | fac := nil. fac := [:n | n > 1 ifTrue: [n * (fac value: n - 1)] ifFalse: [1]]. fac value: 10
This would not have worked with contexts.
- Bert -
Hi Bert,
Thanks for your answer, it clarifies some issues but I'm still confused about the logic I've found in the whileTrue method.
For example, I don't know the answers to the following questions:
Can I add methods to literal blocks? Where do I implement those methods? In case your answer is in BlockClosures, why I don't see any ifTrue: in the while implementation?
Thanks once again Erlis
On Tue, Oct 4, 2011 at 12:22 PM, Bert Freudenberg bert@freudenbergs.dewrote:
On 04.10.2011, at 17:58, Erlis Vidal wrote:
Hi all,
I was looking at the implementation of some of the flow control methods and I have a question with the method *whileTrue*.
First of all, I can see two identical implementation in the classes * BlockClosure* and *BlockContext* the implementation is this
*whileTrue*: aBlock "Ordinarily compiled in-line, and therefore not overridable. This is in case the message is sent to other than a literal block. Evaluate the argument, aBlock, as long as the value of the receiver is true."
^ [self value] whileTrue: [aBlock value]I'm assuming here that there's another class *Block* I'm missing (something like the literal block mentioned in the comment) which is the one that contains the logic I was looking for. But I'm not able to find any other whileTrue method in my image.
"Block" is just short for either BlockClosure or BlockContext. "Literal" blocks are those written directly with square brackets. If you store a block in a variable and pass that variable, the block would not be literal.
What's the difference between BlockClosure and BlockContext?
BlockClosures are BlockContexts Done Right.
If you wrote square brackets in older Squeak versions (3.x) you would get a BlockContext. In a current Squeak you get a BlockClosure.
So since now we only have closures, the difference is only of historic interest. You can do some things with closures that you couldn't do with block contexts, e.g. recursive blocks:
| fac | fac := nil. fac := [:n | n > 1 ifTrue: [n * (fac value: n - 1)] ifFalse: [1]]. fac value: 10
This would not have worked with contexts.
- Bert -
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
On 04.10.2011, at 18:41, Erlis Vidal wrote:
Can I add methods to literal blocks?
Yes.
Where do I implement those methods?
In class BlockClosure.
In case your answer is in BlockClosures, why I don't see any ifTrue: in the while implementation?
Because the compiler generates a jump byte code for whileTrue: directly. In a browser on the whileTrue: method, click the "source" button to switch to showing byte codes.
- Bert -
Thanks Bert!
The byte code has the answer, I thought that the byte code will map the source code but I see that's not the case, probably to ensure some optimizations.. or to do that "jump" I don't know how to do that in smalltalk
Thanks a lot for taking the time to answer such a newbie question.
Erlis
On Tue, Oct 4, 2011 at 12:57 PM, Bert Freudenberg bert@freudenbergs.dewrote:
On 04.10.2011, at 18:41, Erlis Vidal wrote:
Can I add methods to literal blocks?
Yes.
Where do I implement those methods?
In class BlockClosure.
In case your answer is in BlockClosures, why I don't see any ifTrue: in the while implementation?
Because the compiler generates a jump byte code for whileTrue: directly. In a browser on the whileTrue: method, click the "source" button to switch to showing byte codes.
- Bert -
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
On 04.10.2011, at 19:16, Erlis Vidal wrote:
Thanks Bert!
The byte code has the answer, I thought that the byte code will map the source code but I see that's not the case, probably to ensure some optimizations.. or to do that "jump" I don't know how to do that in smalltalk
For ifTrue: it is purely an optimization, yes. It would work fine by actually sending that message. It would just be slower.
In the case of whileTrue:, however, it's not just an optimization. The only way to do loops otherwise would be by recursion. But the Squeak VM does not do tail-call elimination, so it would run out of space pretty soon. Generating the loop as a byte code back jump is essential for the system to work.
- Bert -
Bert Freudenberg <bert <at> freudenbergs.de> writes:
On 04.10.2011, at 19:16, Erlis Vidal wrote:
Thanks Bert!
The byte code has the answer, I thought that the byte code will map the
source code but I see that's not the
case, probably to ensure some optimizations.. or to do that "jump" I don't
know how to do that in smalltalk
For ifTrue: it is purely an optimization, yes. It would work fine by actually
sending that message. It would
just be slower.
In the case of whileTrue:, however, it's not just an optimization. The only
way to do loops otherwise would
be by recursion. But the Squeak VM does not do tail-call elimination, so it
would run out of space pretty
soon. Generating the loop as a byte code back jump is essential for the system
to work.
- Bert -
Oh no, we could as well reduce stack depth to (numberOfIteration log: 2) with silly recursive code like this:
Block>>tryTwiceThen: aBlock self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. ^ [self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. true] tryTwiceThen: [^aBlock value]
Block>>log2WhileTrue ^self tryTwiceThen: [^nil]
| i maxDepth sender | i := maxDepth := 0. [i := i+1. depth := 0. sender := thisContext. [(sender := sender sender) isNil] whileFalse: [depth := depth+1]. maxDepth := maxDepth max: depth. i<10000] log2WhileTrue. ^maxDepth
Nicolas
On 05.10.2011, at 00:24, nicolas cellier wrote:
Bert Freudenberg <bert <at> freudenbergs.de> writes: On 04.10.2011, at 19:16, Erlis Vidal wrote:
Thanks Bert!
The byte code has the answer, I thought that the byte code will map the
source code but I see that's not the
case, probably to ensure some optimizations.. or to do that "jump" I don't
know how to do that in smalltalk
For ifTrue: it is purely an optimization, yes. It would work fine by actually
sending that message. It would
just be slower.
In the case of whileTrue:, however, it's not just an optimization. The only
way to do loops otherwise would
be by recursion. But the Squeak VM does not do tail-call elimination, so it
would run out of space pretty
soon. Generating the loop as a byte code back jump is essential for the system
to work.
- Bert -
Oh no, we could as well reduce stack depth to (numberOfIteration log: 2) with silly recursive code like this:
Block>>tryTwiceThen: aBlock self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. ^ [self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. true] tryTwiceThen: [^aBlock value]
Block>>log2WhileTrue ^self tryTwiceThen: [^nil]
| i maxDepth sender | i := maxDepth := 0. [i := i+1. depth := 0. sender := thisContext. [(sender := sender sender) isNil] whileFalse: [depth := depth+1]. maxDepth := maxDepth max: depth. i<10000] log2WhileTrue. ^maxDepth
Yes, but log(n) is still not good enough for loops that run forever. Like the Morphic main loop. Or the idle process.
I don't think it's possible to emulate whileTrue without reaching for the meta hammer. Interesting discussion though. Maybe a bit over the head of the average newbie ;)
- Bert -
Bert Freudenberg <bert <at> freudenbergs.de> writes:
On 05.10.2011, at 00:24, nicolas cellier wrote:
snip... gmane is a tyrant
Yes, but log(n) is still not good enough for loops that run forever. Like the
Morphic main loop. Or the idle process.
I don't think it's possible to emulate whileTrue without reaching for the meta
hammer. Interesting
discussion though. Maybe a bit over the head of the average newbie ;)
- Bert -
Ah yes of course, this is the essential case... And we cannot even know if the loop is going to halt. For the two specific cases you submitted, we could cheat by using another VM magic and let the UI and idle process regenerate by forking themselves and completely ignore any synchronisation requirement. Or emulate tail call elimination by playing with thisContext>>sender: But the sport is becoming a bit crooked. And we're getting far from initial question. It's already something to know that a jump bytecode solves these problems efficiently.
Nicolas
is there any reason why smalltalk doesn't implement tail recursion optimization? Is by "language design"? It tries to avoid any issue?
Thanks Erlis
On Wed, Oct 5, 2011 at 1:50 PM, nicolas cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
Bert Freudenberg <bert <at> freudenbergs.de> writes:
On 05.10.2011, at 00:24, nicolas cellier wrote:
snip... gmane is a tyrant
Yes, but log(n) is still not good enough for loops that run forever. Like
the Morphic main loop. Or the idle process.
I don't think it's possible to emulate whileTrue without reaching for the
meta hammer. Interesting
discussion though. Maybe a bit over the head of the average newbie ;)
- Bert -
Ah yes of course, this is the essential case... And we cannot even know if the loop is going to halt. For the two specific cases you submitted, we could cheat by using another VM magic and let the UI and idle process regenerate by forking themselves and completely ignore any synchronisation requirement. Or emulate tail call elimination by playing with thisContext>>sender: But the sport is becoming a bit crooked. And we're getting far from initial question. It's already something to know that a jump bytecode solves these problems efficiently.
Nicolas
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Great explanation here: http://gbracha.blogspot.com/2009/12/chased-by-ones-own-tail.html
Read the comments as well.
On Wed, Oct 5, 2011 at 12:56 PM, Erlis Vidal erlis@erlisvidal.com wrote:
is there any reason why smalltalk doesn't implement tail recursion optimization? Is by "language design"? It tries to avoid any issue?
Thanks Erlis
On Wed, Oct 5, 2011 at 1:50 PM, nicolas cellier nicolas.cellier.aka.nice@gmail.com wrote:
Bert Freudenberg <bert <at> freudenbergs.de> writes:
On 05.10.2011, at 00:24, nicolas cellier wrote:
snip... gmane is a tyrant
Yes, but log(n) is still not good enough for loops that run forever. Like the
Morphic main loop. Or the idle process.
I don't think it's possible to emulate whileTrue without reaching for the meta
hammer. Interesting
discussion though. Maybe a bit over the head of the average newbie ;)
- Bert -
Ah yes of course, this is the essential case... And we cannot even know if the loop is going to halt. For the two specific cases you submitted, we could cheat by using another VM magic and let the UI and idle process regenerate by forking themselves and completely ignore any synchronisation requirement. Or emulate tail call elimination by playing with thisContext>>sender: But the sport is becoming a bit crooked. And we're getting far from initial question. It's already something to know that a jump bytecode solves these problems efficiently.
Nicolas
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
On Wed, Oct 5, 2011 at 4:05 PM, Bert Freudenberg bert@freudenbergs.de wrote:
On 05.10.2011, at 00:24, nicolas cellier wrote:
Bert Freudenberg <bert <at> freudenbergs.de> writes: On 04.10.2011, at 19:16, Erlis Vidal wrote:
Thanks Bert!
The byte code has the answer, I thought that the byte code will map the
source code but I see that's not the
case, probably to ensure some optimizations.. or to do that "jump" I don't
know how to do that in smalltalk
For ifTrue: it is purely an optimization, yes. It would work fine by actually
sending that message. It would
just be slower.
In the case of whileTrue:, however, it's not just an optimization. The only
way to do loops otherwise would
be by recursion. But the Squeak VM does not do tail-call elimination, so it
would run out of space pretty
soon. Generating the loop as a byte code back jump is essential for the system
to work.
- Bert -
Oh no, we could as well reduce stack depth to (numberOfIteration log: 2) with silly recursive code like this:
Block>>tryTwiceThen: aBlock self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. ^ [self value ifFalse: [^aBlock value]. self value ifFalse: [^aBlock value]. true] tryTwiceThen: [^aBlock value]
Block>>log2WhileTrue ^self tryTwiceThen: [^nil]
| i maxDepth sender | i := maxDepth := 0. [i := i+1. depth := 0. sender := thisContext. [(sender := sender sender) isNil] whileFalse: [depth := depth+1]. maxDepth := maxDepth max: depth. i<10000] log2WhileTrue. ^maxDepth
Yes, but log(n) is still not good enough for loops that run forever. Like the Morphic main loop. Or the idle process.
I don't think it's possible to emulate whileTrue without reaching for the meta hammer. Interesting discussion though. Maybe a bit over the head of the average newbie ;)
- Bert -
But this kind of thread is also one of the reasons I like the Squeak community. Newbies get right to the core with their questions and there is little hierarchy.
Karl
beginners@lists.squeakfoundation.org
-
Bert Freudenberg -
David Mitchell -
Erlis Vidal -
karl ramberg -
nicolas cellier