Is there a way in a message-only language to define a whileTrue message without recursion or compiler tricks?

Question

Smalltalk has the whileTrue:-Message implemented through recursion (in VisualWorks) or through compiler-inlining (in Squeak/Pharo). Is there a way to define such a method without using one of them? If not, is there a proof for that avaiable somewhere?

Answer 1

I propose the following solution:

BlockContext>>myWhileTrue: aBlock 
    | start |
    start := thisContext pc.
    self value ifFalse: [ ^ self ].
    aBlock value.
    thisContext pc: start

Instead of using recursion and compiler tricks, the above code uses reflection on the execution stack. Before the loop starts the method stores the current program counter in a temporary variable and resets it at the end to jump back to the start of the method. In some Smalltalk implementations such an approach might be slow as some Smalltalk dialects reify the stack on demand only, but in Pharo/Squeak this trick is quite practicable.

Note, the above code does not answer the result of the last block activation as the original implementation of #whileTrue: does. It should be easy enough to fix that though.

Answer 2

You could also use an exception handler to make it go back to the beginning, but that might count as cheating if the exception handling code used a whileTrue: or other looping construct somewhere. So, basically, the question boils down to whether you can implement a loop without either goto or recursion, and I think the answer to that is no. So if recursion is forbidden, you're left trying to cobble together a goto out of techniques like setting the method pc or using an exception.

Answer 3

Hi Lukas, whileTrue: & whileFalse: always return nil. e.g. if there is a normal recursive definition:

whileTrue: aBlock
    ^self value ifTrue: [self whileTrue: aBlock]

the ifTrue: will return nil if self value is false and so the value should always be nil. That's reflected in the compiler's optimization. The original blue book Smalltalk-80 V2 definition is

whileTrue: aBlock
    "Evaluate the argument, aBlock, as long as the value
    of the receiver is true. Ordinarily compiled in-line.
    But could also be done in Smalltalk as follows"

    ^self value
        ifTrue:
            [aBlock value.
            self whileTrue: aBlock]

So just change your's to

BlockContext>>myWhileTrue: aBlock 
    | start |
    start := thisContext pc.
    self value ifFalse: [ ^ nil ].
    aBlock value.
    thisContext pc: start

or??

BlockContext>>myWhileTrue: aBlock 
    | start |
    start := thisContext pc.
    ^self value ifTrue:
        [aBlock value.
         thisContext pc: start]

But alas both of these crash the VM sometime after the second iteration because thisContext pc doesn't answer the pc on the next iteration, but instead whatever the top of stack is :)

However the following does work:

ContextPart methods for controlling
label
    ^{ pc. stackp }

goto: aLabel
    "N.B. we *must* answer label so that the
     top of stack is aLabel as it is when we send label"
    pc := aLabel at: 1.
    self stackp: (aLabel at: 2).
    ^aLabel

BlockContext>>myWhileTrue: aBlock 
    | label |
    label := thisContext label.
    self value ifFalse: [^nil].
    aBlock value.
    thisContext goto: label

BlockClosure>>myWhileTrue: aBlock 
    | label |
    label := thisContext label.
    ^self value ifTrue:
        [aBlock value.
         thisContext goto: label]

Answer 4

Just do:

BlockClousure>>whileTrue: aBlock

self value ifTrue: [ aBlock value. thisContext restart. "restart on pharo, reset on VW" ]