Stream: roctoberfest

Topic: 2023 day 7

Elias Mulhall (Oct 08 2023 at 22:40):

Day 7, found a blocking compiler bug https://github.com/mulias/roctoberfest/blob/main/advent_2022/day_07/main.roc
I think my solution is probably complete, save for some potential tweaks to whitespace consumption in the parser. I'm unable to run the code though, and am getting this error

An internal compiler expectation was broken.
This is definitely a compiler bug.
Please file an issue here: https://github.com/roc-lang/roc/issues/new/choose
thread '<unnamed>' panicked at 'I thought a non-nullable-unwrapped variant for a lambda set was impossible: how could such a lambda set be created without a base case?', crates/compiler/mono/src/layout.rs:1713:61
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The code causing the error is

dirParser : Parser RawStr Dir
dirParser =
    lazy \{} ->
        const
            (\files -> \subDirs ->
                    if List.isEmpty subDirs then
                        Leaf { files }
                    else
                        Node { files, subDirs }
            )
        |> skip dirNameParser
        |> keep filesParser
        |> keep (
            # const []
            # many dirParser
            manyUntil dirParser (string "$ cd ..")
        )
        |> skip optionalWhitespace

The problem in question involves a directory tree with recursive sub-directories. lazy is provided by roc-parser for recursive data structures. If you comment out the manyUntil line and uncomment const [] then it compiles and runs fine, but the parser is of course incorrect. I also tried the many dirParser line to see if a simpler recursive parser would work, but no luck.

The obvious (and reasonable) solution would be to not use recursive parsers, but at this point I'm not particularly concerned with completing the puzzle :laughing:

I know that " lambda sets" get thrown around here a lot and it sounds like there are known issues with the implementation that @Ayaz Hafiz is working on. Would it be useful to try to make a minimal version of this bug?

Elias Mulhall (Oct 08 2023 at 22:45):

Oh, maybe worth specifying: roc check is clean, run/dev/test all return the same error

Richard Feldman (Oct 09 2023 at 01:17):

maybe try removing some type annotations? There is in particular a known issue around those and recursive lambda sets right now

Elias Mulhall (Oct 09 2023 at 04:08):

I tried removing all type annotations, no luck, same error!

Ayaz Hafiz (Oct 09 2023 at 12:11):

Yeah, this is a well-known issue Elias.. unfortunately we have no idea how to solve it :sweat_smile:

Ayaz Hafiz (Oct 09 2023 at 12:12):

The problem is likely

        |> keep (
            # const []
            # many dirParser
            manyUntil dirParser (string "$ cd ..")
        )

if you have a way to refactor this to avoid that recursive call, it will likely work

Agus Zubiaga (Oct 09 2023 at 12:46):

I ran into this issue a few months ago while also trying to build a recursive parser. I found that while this compiler bug prevents us from using lazy, you can rewrap the parser as a workaround.

Agus Zubiaga (Oct 09 2023 at 12:47):

At least it works with mutually-recursive parsers

Elias Mulhall (Oct 09 2023 at 15:18):

@Agus Zubiaga that did it, thanks!
day 7 done https://github.com/mulias/roctoberfest/blob/main/advent_2022/day_07/main.roc

• It's mostly parsers, but because the parsers do the heavy lifting of interpreting the data the last bit of iterating over the data structure is not too bad.
• I realize that not everyone doing AoC in a new language is going to jump directly to "write 80+ lines of parser for each question" so I'll probably not go quite so hard on parsers for the next few puzzles.

Brendan Hansknecht (Oct 09 2023 at 15:54):

Ah, the parser library, both great for AOC parsering, but also probably the biggest source of compiler bugs due to adding in fun lambdaset and typing issues

Brendan Hansknecht (Oct 09 2023 at 15:55):

I woulder if it would be more advised to tell users to write simple data pipelines with string splitting rather than share that library

Brendan Hansknecht (Oct 09 2023 at 15:56):

Most AOC problems can be parsed by first splitting by new line, then splitting by spaces, then converting to the datatype you want

Ayaz Hafiz (Oct 09 2023 at 15:57):

I don't know - I think it a sign that we should try to fix those bugs as soon as possible :D

Elias Mulhall (Oct 09 2023 at 16:08):

I'm kind of with Brendan on this one. I specifically wanted to put roc-parser through its paces, but in general I think parsing is a distraction if you're trying to complete AoC. That said someone picking up a language like Roc for the first time is probably more interested in learning the language than blitzing through puzzles, so I could see this bug being a frustration.

Elias Mulhall (Oct 09 2023 at 16:14):

I gave this a try, just in case there was a way to fix this in roc-parser

subDirsParser : Parser RawStr (List Dir)
subDirsParser =
    lazy \{} -> (manyUntil dirParser dirBackParser)

lazy = \thunk ->
    buildPrimitiveParser \input ->
        parsePartial (thunk {}) input

but no luck, back to the lambda set error. That's what I expected would happen, but you never know.

Brendan Hansknecht (Oct 09 2023 at 16:15):

Ayaz Hafiz said:

I don't know - I think it a sign that we should try to fix those bugs as soon as possible :D

I mean sure 100%. These bugs have just been around for a really long time, so not sure how quick/easily they would get fixed.

Richard Feldman (Oct 09 2023 at 16:18):

Ayaz Hafiz said:

I don't know - I think it a sign that we should try to fix those bugs as soon as possible :D

totally agree - should we set up a chat this week to brainstorm potential fixes?

Richard Feldman (Oct 09 2023 at 16:19):

(that is, for problems that don't have a planned fix yet)

Elias Mulhall (Oct 09 2023 at 16:31):

We could also update the parser library, potentially remove lazy, and add docs on how to implement recursive parsers with a wrapper. This is def an edge case as far as parsing is concerned, and recursive parser combinators are always awkward so a user that already understands how to use the parser library will likely know to watch for the sharp edge.

Last updated: Jul 06 2025 at 12:14 UTC