Talk:Y combinator: Difference between revisions
m
→Problem with the first non function recursive Haskell version of Y-combinator
GordonBGood (talk | contribs) m (→Comment on the overall task: minor correction) |
GordonBGood (talk | contribs) |
||
| (7 intermediate revisions by 2 users not shown) | |||
Line 294:
:: My purpose in the above sample code is not to specify implementation details, but merely to show that features required in order to accomplish my suggested result objective is possible for languages that don't have those features either built-in or available in a standard library. --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 03:32, 11 July 2016 (UTC)
==Temporary reversion of a recent Haskell edit==
For the moment I have reverted a couple of edits made to Haskell last night – mainly because the second piece of code no longer compiled. Reversion of the first piece may not have been necessary – reading the editors note, I initially took the phrase 'correcting grammar' as a reference to Haskell grammar, and interpreted the introduction of () as a slight misunderstanding :-) Perhaps it refers, though, to the English preamble. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 13:15, 10 October 2018 (UTC)
:I had converted the bindings to the head of the infinite facs` lists to functions to remind users of memory leaks as per [https://wiki.haskell.org/Memory_leak the Haskell wiki]: a binding to the head of an evaluated list means that none of the list can be released; it doesn't matter much here where only 20 elements are evaluated and printed before the program closes, but imagine if the last of a million elements were printed where millions of Megabytes would be tied up - the use of a function means that the head of the list can be released as the list is consumed, meaning that in this case only two elements (the first and second) need be in memory at any given time.
:As to the second part you've temporarily removed, there was a mistake that crept into the type signature for <code>simplefac</code> which should be <code>simplefac :: Integer -> Integer</code>; this prevented it from compiling.
:The reason for the second part, and its included actually third part is that this task is ambiguous as to the type of recursion that is disallowed: Although because Haskell is non-strict and doesn't have a problem with either recursive bindings (as used in the the <code>fix f = x where x = f x</code> definition) or recursive functions (as used in the <code>fix f = f (fix f)</code> definition with regard to <code>fix</code>), many non-strict languages disallow the first unless there is a function injected (<code>fix f = x() where x = \() -> f x</code>) in the interested of avoiding cyclic data, and a few don't allow recursive functions which call themselves from their own definition. In these cases, the Y-combinator may be actually useful in allowing recursion where otherwise it would be forbidden.
:I think @WillNess, who posted the second part originally, intended to show that one can avoid binding recursion but still use the "non-sharing point form" of the Y-combinator, and his Y-combinator example of <code>fibs</code> then is essentially the same version as currently used which uses the double <code>fix</code> and completely avoids even function recursion (just in a simpler, easier to understand form in not using the applicative).
:My point in modifying his <code>fibs</code> example, adding an equivalent <code>facs</code> example, and adding the "simple" non-fix/non-Y-combinator versions is that, if function recursion is to be allowed as in the definition of the non-sharing version of <code>fix</code> (with the function <code>fix</code> self referenced in its definition), then there is no need for <code>fix</code>/Y-combinator at all in these cases as they can be defined just using function recursion.--[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 22:13, 10 October 2018 (UTC)
:: Understood – many thanks for the explanations – will you fix the non-compiling part and revert the rest in the way seems best to you ? [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 22:31, 10 October 2018 (UTC)
::: Good edits and explanations. Many thanks. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 11:53, 11 October 2018 (UTC)
::::Done and dusted...
::::While I was making sure everything compiled, I did some performance tests, with some interesting results...
::::I didn't change the first and second parts much other than to make the code producing lazy lists functions so the lists can be consumed as evaluated as discussed above, and forced evaluations so they wouldn't be deferred until the end of the calculation, which need showed up in performance testing.
::::However, performance and capability as far as range of usefulness stunk, so I added back the working simple function recursive versions, which are at least ten times faster, don't take so much memory, don't crash for large ranges, and which compile easily without showing up compiler bugs. I'm a little harsh in evaluating the usefulness of the Y-combinator unless someone can show the error in my analysis...
::::As always, I monitor this Talk page and the main page if anyone would like to discuss it...--[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 12:05, 11 October 2018 (UTC)
:::::I've been asked to remove the non-Y-combinator versions as off the topic of this task and am in process of doing so. I believe the task should be modified in two ways: 1) to clarify if function recursion is allowed although binding recursion clearly isn't: if function recursion isn't allowed then the second Haskell example wouldn't be allowed either, and 2) it should be noted that, other than as an interesting intellectual exercise, the Y-combinator/Z-combinator is rarely of practical use other than for implementing recursion for languages that don't support it, as for languages that do support recursion (the majority of modern languages at least support function recursion) its use comes at a sometimes major performance cost.--[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 01:47, 13 October 2018 (UTC)
==Problem with the first non function recursive Haskell version of Y-combinator==
The first non function recursive implementation of the Y-combinator <code>fix</code> doesn't compile using either GHC version 8.4.3 or 8.6.1 on 64-bit Windows other than in non-optimized interpretive mode (-O0), with an error message about exceeding the "tick count", but increasing this "tick count" immensely doesn't help. Error message as follows:
<pre>Simplifier ticks exhausted
When trying UnfoldingDone x_s3FU
To increase the limit, use -fsimpl-tick-factor=N (default 100).
If you need to increase the limit substantially, please file a
bug report and indicate the factor you needed.
If GHC was unable to complete compilation even with a very large factor
(a thousand or more), please consult the "Known bugs or infelicities"
section in the Users Guide before filing a report. There are a
few situations unlikely to occur in practical programs for which
simplifier non-termination has been judged acceptable.
To see detailed counts use -ddump-simpl-stats
Total ticks: 11445</pre>
Someone more knowledgeable than I should investigate whether it is possible to modify this to fully compile with optimizations. With optimization, the only versions of the Y-combinator usable on current GHC versions are the built-in one using binding recursion or the second version using function recursion posted here--[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 01:47, 13 October 2018 (UTC)
| |||