Why is this function not tail-recursive?

Request Feedback
1

Can someone spot why the compiler cannot make this function tail-recursive?

Its a port of A Prettier Printer (by Philip Wadler) in Elm starting from a Haskell implementation. It needs to be tail recursive or else it is not going be able to process large syntax trees.

Pretty.elm#379

    be : Int -> Int -> List ( Int, Doc ) -> Normal
    be w k docs =
        case docs of
            [] ->
                NNil

            ( i, Empty ) :: ds ->
                be w k ds

            ( i, Concatenate doc doc2 ) :: ds ->
                be w k <| ( i, doc ) :: ( i, doc2 ) :: ds

            ( i, Nest j doc ) :: ds ->
                be w k <| ( i + j, doc ) :: ds

            ( i, Text text ) :: ds ->
                NText text <| be w (k + String.length text) ds

            ( i, Line ) :: ds ->
                NLine i <| be w i ds

            ( i, Union doc doc2 ) :: ds ->
                better w
                    k
                    (be w k <| ( i, doc ) :: ds)
                    (\() -> be w k <| ( i, doc2 ) :: ds)

            ( i, Nesting fn ) :: ds ->
                be w k <| ( i, fn i ) :: ds

            ( i, Column fn ) :: ds ->
                be w k <| ( i, fn k ) :: ds
2

https://github.com/elm/compiler/issues/1770?

Try removing the pipe operators.

3

Pipe operators are one thing, but you are also using the result of the recursive calls as arguments to NText, NLine and better.

2 Likes
4

Interesting about the pipe operators, they are more than just syntactic sugar it seems.

The cases where I am using the recursive calls as arguments to other functions or constructors, I will have to put those calls behind thunks, \() -> .... The original Haskell algorithms rely on laziness to avoid evaluating undesirable layouts - the algorithm is actually a backtracking search but looks like a function. Obviously the thunks will not be tail recursive, but may avoid exploring the search space unnecessarily deeply, if parts of it can be avoided altogether.

Aiming to be able to pretty print code files with 10,000 or more lines. With the pipe operators removed and few more thunks inserted, I am up to around 400 lines from 20, so still some way to go.

5

I changed this algorithm by introducing an explicit accumulator to build up the results in, rather than using the stack to implicitly do it. From this:

    layoutInner : Normal -> List String
    layoutInner normal2 =
        case normal2 of
            NNil ->
                []

            NText text innerNormal ->
                text :: layoutInner (innerNormal ())

            NLine i innerNormal ->
                "\n" :: (copy i " " :: layoutInner (innerNormal ()))

To this:

    layoutInner : Normal -> List String -> List String
    layoutInner normal2 acc =
        case normal2 of
            NNil ->
                acc

            NText text innerNormal ->
                layoutInner (innerNormal ()) (text :: acc)

            NLine i innerNormal ->
                layoutInner (innerNormal ()) (("\n" ++ copy i " ") :: acc)

This also requires the list to be reversed at the end.

Up to around 3000 lines now…

2 Likes
6

Ok, I’m up to 32K lines now. This trick of introducing an explicit accumulator seems very useful.

What I am trying to do is to create a dummy AST for some imaginary (and not terribly useful) programming language, randomly generate 10K+ lines of code and then pretty print them. Just to make sure this kind of thing can be done in Elm without being excessively slow, and not blowing the stack.

1 Like
7

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.