in reply to Functional Perl 6/PUGS

Maybe this is just my procedural background showing, but is it a good idea to use these recursive functions? In Perl 5 this blows the stack when too many arguments are passed. Does this work better in PUGS and the planned Perl 6? I assume this works fine in ML because it is tail-recursive.

Replies are listed 'Best First'.
Re^2: Functional Perl 6/PUGS
by stvn (Monsignor) on Feb 28, 2005 at 15:39 UTC
    Maybe this is just my procedural background showing, but is it a good idea to use these recursive functions?

    Well, they are examples, and no you probably wouldn't want to actually do a recursive length function (especially since you can just do +@array in perl 6 to get the same thing). But recusion is not the bad thing it used to be back in the days of low CPU/low memory, and even then it was mostly an implementation issue.

    In Perl 5 this blows the stack when too many arguments are passed.

    Perl 5 actually does not have a stack (at least not in the same way that C has a stack). Perl 5 can recurse forever (or until your memory runs out). See this thead for more details.

    I assume this works fine in ML because it is tail-recursive

    Actually neither of those ML functions are tail recursive as both of them force all calculation to be done at the last moment. They could both be optimized to be tail recusive though. And ML's efficiency actually does not come from tail recursion, but from a stackless compilation model (IIRC based on heaps) which is specifically made with recursion in mind (sort of the opposite of C's compilation model).

    Does this work better in PUGS and the planned Perl 6?

    Well PUGS is written in Haskell, which is also a functional language like ML, which handles recursion just fine as well. However, i cannot say if that will actually matter since it matter more how autrijus is writing the interpreter than the language he is using to write it in. However, I assume that recursion will be reasonably efficient in perl 6 (however it is not all that un-efficient in perl 5 though).

    -stvn
Re^2: Functional Perl 6/PUGS
by BrowserUk (Pope) on Feb 28, 2005 at 16:08 UTC

    I gotta agree.

    Why count bytes when perl already knows the length of a string?

    Why wait for four billion, two hundred and ninty four million, nine hundred and sixty seven thousand, two hundred and ninty six mutual recursions to find out that 4294967296 is even when this can be determined with a single opcode (usually with an optional branch!) on every processor known to man?

    And how come -1 tests true as both even and odd?

    It kinda like 50 years of programming has been forgotten. Next, they'll be producing a uniq list from a non-unique list by comparing every element in a list against the first element of another list constructed by removing the first element from the first list and then against the next by comparing that element against the first element of a new list constructed from the second list by removing it's first element, and then comparing it against the third element by comparing it against the first element of a new list constructed by removing the first element from the third list and then comparing it with the fourth element by comparing it with the first element of a new list constructed by removing the first element from the fourth list--(Geez! I do hope this list isn't to long!)--and then comparing it against the fifth element of the list by comparing it against the first element of a new list constructed by removing the first element from the fifth list...

    Oh wait! They are!


    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.

      FWIW, the code is not meant to be efficient, or real-world useful. It is meant to be an example of the argument pattern matching style of ML with perl6.

      As for "why the hell would anyone program like this" question, the answer is that (virtually) no one really would.

      However, it does illustrate the style of programming which is free of both assignment statements and side effects. This style is an area of interest in the study of concurrent programming (both non-assignment and single assignment variables actually). By not introducing side effects and limiting assignment you can remove an entire class of concurrent programming issues.

      It is also useful to not think of this style of programming the way you view procedural execution. If you were to write these functions in prolog (or something similar like Erlang) the code would be quite similar, but since the execution model is much different, they are not as in-efficient as you might think.

      And if you were stranded on a deserted isle with only functions and simple logical and comparison operators, and all your assignment statements, for & while loops, if statements etc, were lost at sea. You would have to program like this too.

      -stvn
        FWIW, the code is not meant to be efficient, or real-world useful. It is meant to be an example of the argument pattern matching style of ML with perl6.

        I understand that. The problem is, whenever I look for any examples of FP-style programming, these are the same examples that are always given--like they exemplified the virtues of FP?

        However, it does illustrate the style of programming which is free of both assignment statements and side effects. This style is an area of interest in the study of concurrent programming (both non-assignment and single assignment variables actually). By not introducing side effects and limiting assignment you can remove an entire class of concurrent programming issues

        Thankyou for that last sentance!

        That is the first time in nearly 4 months of looking that I have seen, what appears to be--on the surface at least--a good reason for wanting to use "the style of programming which is free of both assignment statements and side effects".

        Most every other text I've read that attempts to justify this style of code--where they bother at all--attempts to do so on the basis of provability. An argument that simply doesn't hold water--but I think I debunked that claim enough elsewhere.

        I'm not entirely convinced that the concurrency argument works, but it certainly gives me another angle to research. Thanks.

        It is also useful to not think of this style of programming the way you view procedural execution.

        I hope you'll excuse me for saying this, but that sounds a bit like saying not to compare getting from Beachley, Wales to Aust, England by:

      • following the left and right banks of the River Severn via the source.

        with:

      • Crossing the Severn Bridge.

        Both would work, but even with the bridge toll, you probably won't get many takers for the former.

        If you were to write these functions in prolog (or something similar like Erlang) the code would be quite similar, but since the execution model is much different, they are not as in-efficient as you might think.

        This I would like to understand? Any pointers on how the mutually recursive is_odd()/is_even() method of determining a numbers oddness can be made efficient?

        Unless of course the interpreter/compiler recognises the pattern and optimises it to x & 1, in which case it is similar to perl5 sort in as much as

        sort{ $a<=>$b }@array

        never actually sets $a or $b or transfers control to the block. In reality, the entire construct is simply recognised to mean

        sortNumericallyAscending( @array )
        .

        Whilst that makes sense for Perl in terms of backwards compatibility, I don't follow the logic of creating entire languages that purport to hold to some ideal of academic purity, only to then need to create hugely complex optimising compilers with hardcoded recognition of the common, elegantly inefficient, idealised idioms and convert them wholesale to standard code. That just makes the idealism a source level sham.

        And if you were stranded on a deserted isle with only functions and simple logical and comparison operators, and all your assignment statements, for & while loops, if statements etc, were lost at sea. You would have to program like this too.

        Given those rather unlikely circumstances arose, I would spend my first week programming a string type that only needed to calculate it's length when assigned to--I guess I'd have to re-invent assignment first--bitwise and, for & while loops and if statements. And the next week writing a C compiler that could compile itself...


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.