From squeak-dev-admin@lists.squeakfoundation.org Tue Jan 29 22:06:18 2002 Delivered-To: mailman-squeak-dev@lists.squeakfoundation.org To: squeak-dev@lists.squeakfoundation.org Path: not-for-mail From: cg@home.cdegroot.com (Cees de Groot) Newsgroups: lists.squeak Subject: Re: Squeak practical use?We run the equity markets through it! Organization: cdegroot.com Lines: 27 References: KIEPINLHGIEALPPHHADCEEOHGEAE.mark@vibrant3d.com Sender: squeak-dev-admin@lists.squeakfoundation.org Errors-To: squeak-dev-admin@lists.squeakfoundation.org X-BeenThere: squeak-dev@lists.squeakfoundation.org X-Mailman-Version: 2.0.8 Precedence: bulk Reply-To: squeak-dev@lists.squeakfoundation.org X-Reply-To: cg@cdegroot.com List-Help: mailto:squeak-dev-request@lists.squeakfoundation.org?subject=help List-Post: mailto:squeak-dev@lists.squeakfoundation.org List-Subscribe: http://lists.squeakfoundation.org/listinfo/squeak-dev, mailto:squeak-dev-request@lists.squeakfoundation.org?subject=subscribe List-Id: The general-purpose Squeak developers list <squeak-dev.lists.squeakfoundation.org> List-Unsubscribe: http://lists.squeakfoundation.org/listinfo/squeak-dev, mailto:squeak-dev-request@lists.squeakfoundation.org?subject=unsubscribe List-Archive: http://lists.squeakfoundation.org/pipermail/squeak-dev/ Date: 29 Jan 2002 09:56:42 +0100 Someone wrote: >No one language does all things well, and it is >true Smalltalk does iteration particularly badly. >But so does Java when you get right down to it. I wonder if this is a case of someone not realising that the C++ STL "input iterators" and "output iterators" have good analogues in Smalltalk: ReadStreams and WriteStreams respectively.
It really boils down to "Smalltalk DOESN'T do iteration, WE do." It's an open system. If there's a better way to iterate than the usual collection methods and/or streams, let's find out what it is and add it.
"Richard A. O'Keefe" comments:
Someone wrote:
No one language does all things well, and it is true Smalltalk does iteration particularly badly. But so does Java when you get right down to it.
I wonder if this is a case of someone not realising that the C++ STL "input iterators" and "output iterators" have good analogues in Smalltalk: ReadStreams and WriteStreams respectively.
It really boils down to "Smalltalk DOESN'T do iteration, WE do." It's an open system. If there's a better way to iterate than the usual collection methods and/or streams, let's find out what it is and add it.
I must say that I don't understand this "badness of iteration" in Smalltalk. What is 'the' iteration?
We've passed through all kind of mapping iterators, folders/reducers (catamorphisms) etc. in purely functional languages, in APL, in logic languages, etc., and each set of programming paradigms has its own "iterator patterns" and style. Whether you call something foldl or inject:... is not so relevant.
There are imperative constructs, there are also purely functional ones. It is hard (for me) to believe that a *generic* better way to iterate exists at all. Backtracking is also a kind of iteration. Difficult to do in a "classical" language, yet Prolog machines have been constructed in Smalltalk, as we know.
Of course, Smalltalk has its deficiencies. You can't (apparently) define and use an optimized tail-recursive method; if
anObject doesSomethingWith: params
... "folk dance and whatever. At the end, conditionally:"
^ self doesSomethingWith: newParams
each call instance will stack the receiver, and finally we get a squeak: "low memory" or something alike, if the depth is too large. In Scheme (say)
(funct obj params) ... ;; which calls at the end (funct obj newparams)
will turn in constant space. And that is how the *strict* iteration is defined in functional languages. The arguments are not stacked, they smash the previous ones. In principle a good optimizing Smalltalk compiler might do that as well, although I cannot be categorical. Any opinion of The Gurus?
--
There are also lazy iterators, similar to streams, but permitting to use the co-recursion to construct and iterate over *infinite* collections of data.
That's why I am waiting for genuine closures in Smalltalk, to check whether co-recursive algorithms may work... Here no STL pompous patterns can help.
[BTW. VisualWorks docs say that their blocks *are* closures. Anybody tested that they might be exported out of their method context?]
Jerzy Karczmarczuk Caen, France
Jerzy Karczmarczuk wrote:
Of course, Smalltalk has its deficiencies. You can't (apparently) define and use an optimized tail-recursive method; if
anObject doesSomethingWith: params
... "folk dance and whatever. At the end, conditionally:"
^ self doesSomethingWith: newParams
each call instance will stack the receiver, and finally we get a squeak: "low memory" or something alike, if the depth is too large. In Scheme (say)
(funct obj params) ... ;; which calls at the end (funct obj newparams)
will turn in constant space. And that is how the *strict* iteration is defined in functional languages. The arguments are not stacked, they smash the previous ones. In principle a good optimizing Smalltalk compiler might do that as well, although I cannot be categorical. Any opinion of The Gurus?
I remember this being discussed here on the list some time back. It sounded like it would not be difficult to change the system to enable tail recursion optimization, though I don't recall whether a compiler change would be sufficient, or a VM change would be necessary in the general case. (I think a compiler change is sufficient, at least, for self-recursive methods, but possibly not for mutual recusion.) As to whether it would be a good idea, the consensus seemed to be that it would interfere too much with the debugger's strengths. (Tail recursion optimization effectively erases all record of intermediate calls, making it much harder (or impossible) to back-trace the execution of a running program.)
-Jesse
Would it be reasonable to implement it in such a way that tail recursion could be explicitly requested by the programmer? The default would remain as it is and tail recursion could be an optimizing option.
Just a thought.
Jimmie Houchin
Jesse Welton wrote:
[snip recursion discussion]
I remember this being discussed here on the list some time back. It sounded like it would not be difficult to change the system to enable tail recursion optimization, though I don't recall whether a compiler change would be sufficient, or a VM change would be necessary in the general case. (I think a compiler change is sufficient, at least, for self-recursive methods, but possibly not for mutual recusion.) As to whether it would be a good idea, the consensus seemed to be that it would interfere too much with the debugger's strengths. (Tail recursion optimization effectively erases all record of intermediate calls, making it much harder (or impossible) to back-trace the execution of a running program.)
-Jesse
On Wed, 30 Jan 2002, Jimmie Houchin wrote:
Would it be reasonable to implement it in such a way that tail recursion could be explicitly requested by the programmer?
Yes, but it raises a whole host of issues :) I.e., there are a lot of "optimization specifications" (e.g., type declaration) one might one to, er, be able to specify.
Common Lisp is a handy place to look.
The default would remain as it is and tail recursion could be an optimizing option.
Or you could set the default as you please :)
Cheers, Bijan Parsia.
This effect can be trivially accomplished by other means:
method: aParm
self doSomeCode. . . ^self method: anExpression
-- coded as --
method: aParm | value | value := aParm. [self doSomeCode. . . value := anExpression] repeat
The general translation, of course, always looks more gross than a more ordinarily coded iteration. Appears to do what you want. (I don't recall whether repeat is inlined. If not, add ". true" to the block and replace repeat with "whileTrue"). The bottom line is that tail recursion is semantically indistinguishable from a corresponding and straightforward iteration.
This reduces the problem to the question whether the proposed semantic/syntactic sugar outweighs the costs of introducing the unfortunate notion of "pragma" to Smalltalk, or whether the cost of automatic optimization would outweigh the benefit of losing the current, presently expected, debugger behavior.
On Wednesday, January 30, 2002, at 02:33 PM, Jimmie Houchin wrote:
Would it be reasonable to implement it in such a way that tail recursion could be explicitly requested by the programmer? The default would remain as it is and tail recursion could be an optimizing option.
Just a thought.
Jimmie Houchin
Jesse Welton wrote:
[snip recursion discussion]
I remember this being discussed here on the list some time back. It sounded like it would not be difficult to change the system to enable tail recursion optimization, though I don't recall whether a compiler change would be sufficient, or a VM change would be necessary in the general case. (I think a compiler change is sufficient, at least, for self-recursive methods, but possibly not for mutual recusion.) As to whether it would be a good idea, the consensus seemed to be that it would interfere too much with the debugger's strengths. (Tail recursion optimization effectively erases all record of intermediate calls, making it much harder (or impossible) to back-trace the execution of a running program.) -Jesse
On Wed, 30 Jan 2002, Andrew C. Greenberg wrote:
This effect can be trivially accomplished by other means:
method: aParm
self doSomeCode. . . ^self method: anExpression
-- coded as --
method: aParm | value | value := aParm. [self doSomeCode. . . value := anExpression] repeat
Simple tail recursion can look this way, but more complicated tail recursion doesn't map as pleasantly:
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ ^succBlock value ] blah2 ifTrue: [ ^failBlock value ] succBlock := [ blah . [^sucBlock value]]
Which is code done in the explicit continuation style. This is especially good for, for example, parsers.
Also, you can suspend and restart these continuations at any time easily. Without tail recursion, this isn't possible.
The general translation, of course, always looks more gross than a more ordinarily coded iteration. Appears to do what you want. (I don't recall whether repeat is inlined. If not, add ". true" to the block and replace repeat with "whileTrue"). The bottom line is that tail recursion is semantically indistinguishable from a corresponding and straightforward iteration.
In the case of mutual tail recursion, not unless your language has 'goto'.. You'd need something like:
[ state == #foo ifTrue: [ .... state _ #baz ] state == #bar ifTrue: [ .... state _ #foo ] true] whileTrue.
Which is especially nasty if the different clauses should be different methods, or even in different classes.
This reduces the problem to the question whether the proposed semantic/syntactic sugar outweighs the costs of introducing the unfortunate notion of "pragma" to Smalltalk, or whether the cost of automatic optimization would outweigh the benefit of losing the current, presently expected, debugger behavior.
Automatic tail-call optimization. If you activate tail-call for a class, all methods in that class automatically do all applicable methods through a tailcall. Or, make it system-wide, and recompile code.
Tailcall's are importantant from a theoretical perspective. Once you have them and closures, you can implement the real elegant and useful algorithms. You also have the option of using new styles of coding, especially proof strategies and parsing strategies.
Scott
Scott A Crosby crosby@qwes.math.cmu.edu is claimed by the authorities to have written:
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ ^succBlock value ] blah2 ifTrue: [ ^failBlock value ] succBlock := [ blah . [^sucBlock value]]
Improper code I'm afraid. Can't assign to a parameter.
tim
Not only that -- how, exactly, is this continuation example an example of a tail recursion? Certainly, its been decades since my A-exams, but as I recall, a tail recursion is generally defined as a recursive call in a tail context. This is neither. And while I understand the notion of "mutual tail recursions," I'm not sure what optimizations are proposed here (or even possible.
foo1: aParm
self doSome ^self foo2: anExpression
foo2: aParm self SomeMore ^self foo1: anExpression
How, exactly, can I safely and in straightforward manner optimize this for any Class, when the definitions of foo1 and foo2 may well depend upon definitions in subclasses, which in turn may change? Moreover, since these kinds of expressions can be horribly complex, I would HATE if the debugger lost contexts when showing me the problem.
In short, while I appreciate the virtue of recursion -- my observation is that TAIL recursion semantically equates to a straightforward iteration, I think, by definition. These other traits, at least with the definition I was using, are not precisely tail recursions.
On Wednesday, January 30, 2002, at 11:19 PM, Tim Rowledge wrote:
Scott A Crosby crosby@qwes.math.cmu.edu is claimed by the authorities to have written:
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ ^succBlock value ] blah2 ifTrue: [ ^failBlock value ] succBlock := [ blah . [^sucBlock value]]
Improper code I'm afraid. Can't assign to a parameter.
tim
-- Tim Rowledge, tim@sumeru.stanford.edu, http://sumeru.stanford.edu/tim Strange OpCodes: HALT: No-Op
On Wed, 30 Jan 2002, Andrew C. Greenberg wrote:
Not only that -- how, exactly, is this continuation example an example of a tail recursion? Certainly, its been decades since my A-exams, but as I recall, a tail recursion is generally defined as a recursive call in a tail context. This is neither. And while I understand the notion of "mutual tail recursions," I'm not sure what optimizations are proposed here (or even possible.
An explicit continutation passing style is a non-trivial use of tail recursion. It can be used when implementing proof or other types of nondeterministic search, and other types of optimization problems.
I'm trying to give examples in my other response.
How, exactly, can I safely and in straightforward manner optimize this for any Class, when the definitions of foo1 and foo2 may well depend upon definitions in subclasses, which in turn may change? Moreover, since these kinds of expressions can be horribly complex, I would HATE if the debugger lost contexts when showing me the problem.
Actually, its not all that bad to implement. Tail recursion can be done by replacing your own context with a new one..
IE:
foo blah blah ^self bar: 12
On Wed, 30 Jan 2002, Tim Rowledge wrote:
Scott A Crosby crosby@qwes.math.cmu.edu is claimed by the authorities to have written:
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ ^succBlock value ] blah2 ifTrue: [ ^failBlock value ] succBlock := [ blah . [^sucBlock value]]
Improper code I'm afraid. Can't assign to a parameter.
Ok. Unintended error.
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ succBlock value ] blah2 ifTrue: [ failBlock value ] newSuccBlock := [ blah . [sucBlock value]] ^self bar: y ifSuccess: newSuccBlock ifFail: failBlock.
Ok, but what exactly are you criticizing here? The functional semantics or the block closure semantics? Clearly, the standard optimization discussed earlier in these threads is no different from the mechanical one I suggested, more or less (except that the generated code WOULD probably change the parameters)? Are you observing that present Squeak block semantics make that optimization semantically unstable, or something else?
Indeed, perhaps all we are doing here is observing that the apparent tail recursion in this example doesn't actually occur in a tail context (and, by at least some definitions, isn't a tail recursion)? Does the new block closure semantics harmonize these issues?
foo: x ifSucces: succBlock ifFail: failBlock | newSuccBlock theX theSuccBlock theFailBlock | "you would need a definition in your example of newSuccBlock ,b.t.w" theX := x. theSuccBlock := succBlock. theFailBlock := failBlock. [blah1 ifTrue: [ theSuccBlock value ] blah2 ifTrue: [ theFailBlock value ] newSuccBlock := [ blah . [newSuccBlock value]]. " iterative substitute for: ^self bar: y ifSuccess: newSuccBlock ifFail: failBlock." theX := y. theSuccBlock := newSuccBlock. theFailBlock := failBlock] repeat
(Of course, extra expressions and variable can be simplified in the obvious ways -- I did the substitution mechanically to show how I was doing this). The real culprit in this not doing what YOU intended is the lack of genuine blockcontexts
On Thursday, January 31, 2002, at 12:47 AM, Scott A Crosby wrote:
On Wed, 30 Jan 2002, Tim Rowledge wrote:
Scott A Crosby crosby@qwes.math.cmu.edu is claimed by the authorities to have written:
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ ^succBlock value ] blah2 ifTrue: [ ^failBlock value ] succBlock := [ blah . [^sucBlock value]]
Improper code I'm afraid. Can't assign to a parameter.
Ok. Unintended error.
foo: x ifSucces: succBlock ifFail: failBlock blah1 ifTrue: [ succBlock value ] blah2 ifTrue: [ failBlock value ] newSuccBlock := [ blah . [sucBlock value]] ^self bar: y ifSuccess: newSuccBlock ifFail: failBlock.
On Thu, 31 Jan 2002, Andrew C. Greenberg wrote:
Ok, but what exactly are you criticizing here? The functional semantics or the block closure semantics? Clearly, the standard optimization discussed earlier in these threads is no different from the mechanical one I suggested, more or less (except that the generated code WOULD probably change the parameters)? Are you observing that present Squeak block semantics make that optimization semantically unstable, or something else?
I'm expressing a feature request for proper tail recursion. :)
Indeed, perhaps all we are doing here is observing that the apparent tail recursion in this example doesn't actually occur in a tail context (and, by at least some definitions, isn't a tail recursion)? Does the new block closure semantics harmonize these issues?
I don't know.
doing this). The real culprit in this not doing what YOU intended is the lack of genuine blockcontexts
What do you mean about this?
Agreed, tail call can frequently turned into iteration. But, the code above is fragile in some ways, in that any change to the function necessitates undoing the mechanical transformation you have made, making the change, and redoing it.
Its hard to come up with a good, yet simple example.
Ah, how about quickfind?
quickfind: foo :in orderedCollectoin from: start to: end start = end ifTrue: [^start] ... do some stuff to partitian the array ... foo < key ifTrue: [^self quickfind: foo in: orderedCollection from: start to: keyloc-1] foo < key ifFalse: [^self quickfind: foo in: orderedCollection from: keyloc to: end]
Which, can be done in the form of tail recursion, but it would opaquify the core essence. Another example is quicksort. The worst-case performance of the naieve quicksort is O(n) stackslots. With tail recursion, the worst-case performance becomes O(log n). (Recurse on the smaller side, tail-recurse on the bigger side.)
Other simlar examples are types of combinatorial search problem, where you break a problem into subproblems, you solve the smaller subproblems recursively, but tail-recurse on the big subproblem. This can avoid using excessive stack space.
ALthough instances of tail recursion can be mechanically transformed in the way you illustrate, instances of mutual tail recursion are not so straightforwad. For example, mutual tail recursion, especially when the methods being tail-recursed sit in different, possibly subclassible classes. (I cannot come up with an immediate non-contrived example which cannot be rewritten such that it does not require mutual tail recursion.)
Perhaps the best thing that can be said is that having tail recursion does allow coding in a different paradigm. And being able to code things in more than one fashion is always an advantage.
Scott
Hi All,
I note that this thread is discussion performance of iterators in Smalltalk. The SmallScript (Smalltalk iteration) based code is pretty darn performance competitive with C++ code. SmallScript provides hi-performance blocks and related jit services are available for eliminating range checks on array bounds that are known, etc.
Benchmarks a few months back, comparing SmallScript collections like <Dictionary>, showed that SmallScript was the fastest available Smalltalk implementation (for this iterator/collection example) in the JIT category [VW, VAST, MT]. And was a lot faster than any of the interpreter implementations like Squeak and Dolphin. To get a sense of what we are talking about, SmallScript was anywhere from 2X-4X faster than the best of the other jitted Smalltalks, and 100's of times faster than the interpreted Smalltalks.
The point here is not that SmallScript is any worse or better than some other Smalltalk [better is entirely subjective based on numerous factors]. The importance of my comments here are that it illustrates that the performance issues are not inherent to the type of language that Smalltalk represents. I.e., if SmallScript can execute pure-classic Smalltalk code at speeds that are competitive with C++ then it is not a Smalltalk language issue, but an implementation question. A big factor of which can be fundamental algorithm issues resulting from core language implementation decisions. --- Here is more discussion of what is possible within the collective set of available Smalltalk dialects. The point here is to encourage Squeak developers to see what is done in SmallScript, and what it achieves. It might yield good patterns for evolving and growing Smalltalk in the Squeak dialect...
So, on a related note, to the topics in this thread, SmallScript directly supports tail-recursion in the JIT opcode set. You can specify that a message always tail-called, never tail-called, or left up to the JIT to decide which it should be. The virtual machine also has specific support for control/exceptions relating to stack overflow (recursion) management and debugging.
On the less obvious side, I use tail-calls fairly often to hide intermediate router methods from a stack frame walker as well. Like with exception routing code.
SmallScript also provides zero cost exception handling which is supported via its zero-cost downward continuations (as they are called in scheme).
You just annotate return operations with the keywords "tail:" or "notail:" for explicit control.
Here is some information from a post I made a while back on the MIT Dynamic Languages Discussion Group:
==== BEGIN ==== In SmallScript/Smalltalk everything is an object, and every operation is a message. Which means every operation results in an object. So, as this discussion is attempting to define things, Smalltalk has no concept of a "statement".
The "default" rule in Smalltalk is that the last expression executed provides the value of an expression. For some expressions, they are explicitly defined to return/evaluate-as <nil> (the singleton of <UndefinedObject>).
So we can write expressions like:
[:i| expr1] whileTrue: [:j| expr2].
Where the <i> value is the result of the last <expr2>, and the <j> value is the result of the last <expr1>. And the initial seed value if <i> is <nil>.
We can write:
|r| := if(expr) [:i| ... ] else [:i| ... ].
Where <i>, for either case, will be the object returned by <expr>. The value of <r> will be the last expression evaluated in either the eqv-true or eqv-false block (context/closure).
If we write:
|r| := if(expr) [...].
Then if <expr> is eqv-true, then <r> is set to the last expression evaluated in the eqv-true block. But, if <expr> is eqv-false then <r> is set to the <expr> value itself.
Same rules apply for other sugar forms:
unless(...) assert(...) while(...) do [...] while(...) until(...) do [...] until(...) switch(...) [...] try [...] ...catches...fault...finally. etc.
And you can design/write your own control structures to do anything you want including tail-call looping, etc.
Method behavior: Object [ myLoop(expr) ^if (self()) [:v|tail:^myLoop(expr(v))] ]
The notion that everything is an object, and that expression results get injected into "apparent" control forms is often exploited for lazy initializers. Commonly, this is done using the binary-message #? that tests to see if a value is <nil>. I say apparent, because all (looping) control forms are really built from messaging that utilizes tail calls, and or (optionally-labeled) branches.
^var ? [var := initExpr]
expr !? [v:...].
==== END ====
-- Dave S. [SmallScript LLC]
SmallScript for the AOS & .NET Platforms David.Simmons@SmallScript.com | http://www.smallscript.org
-----Original Message----- From: squeak-dev-admin@lists.squeakfoundation.org [mailto:squeak-dev- admin@lists.squeakfoundation.org] On Behalf Of Jimmie Houchin Sent: Wednesday, January 30, 2002 11:34 AM To: squeak-dev@lists.squeakfoundation.org Subject: Re: Iterators? (Was: Squeak practical use? ...)
Would it be reasonable to implement it in such a way that tail
recursion
could be explicitly requested by the programmer? The default would remain as it is and tail recursion could be an optimizing option.
Just a thought.
Jimmie Houchin
Jesse Welton wrote:
[snip recursion discussion]
I remember this being discussed here on the list some time back. It sounded like it would not be difficult to change the system to
enable
tail recursion optimization, though I don't recall whether a
compiler
change would be sufficient, or a VM change would be necessary in the general case. (I think a compiler change is sufficient, at least,
for
self-recursive methods, but possibly not for mutual recusion.) As
to
whether it would be a good idea, the consensus seemed to be that it would interfere too much with the debugger's strengths. (Tail recursion optimization effectively erases all record of intermediate calls, making it much harder (or impossible) to back-trace the execution of a running program.)
-Jesse
squeak-dev@lists.squeakfoundation.org
-
Andrew C. Greenberg -
Bijan Parsia -
David Simmons -
Jerzy Karczmarczuk -
Jesse Welton -
Jimmie Houchin -
Richard A. O'Keefe -
Scott A Crosby -
Tim Rowledge