HigherOrderCO/Bend

Potential bug with float combinators pass

Open

#721 opened on Sep 27, 2024

View on GitHub
 (0 comments) (0 reactions) (0 assignees)Rust (19,158 stars) (466 forks)batch import
bughelp wanted

Description

Reproducing the behavior

In the float combinators pass, we move combinators to the top-level when they are considered "unsafe" (as in, they could cause an infinite loop) or when their bodies are too large.

References at the end of a lambda sequence are considered always safe. At the same time, these terms can be in active position, like as the head of an application.

This means that with enough arguments, the references could become "exposed", active and trigger an infinite expansion.

Because applications are considered as safe if all of their children are safe, it looks to be possible to have a situation where an application is not properly moved to top-level due to these conditions.

I was thinking of something like (@* ref-to-recursive safe1 safe2), but don't currently have any concrete examples.

We need to investigate this a bit and see if this is a bug or not. If it's not, write down some comments in the code explaining why this is ok.

System Settings

Bend commit 124c43d

Additional context

No response

Contributor guide

Tech stack
rust
Domain
backendperformance
Issue type
bug
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
3-5 days
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
needs investigation
Prerequisites
Rustcompiler designcombinator optimizationBend codebase
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
20
Research direction
Investigate the float combinators pass implementation in the Bend compiler (likely in Rust files under src/). Focus on the logic that determines when combinators are moved to top level based on safety conditions. Check the condition for applications where children are safe, and see if exposed references can cause infinite expansion. If no concrete example found, add comments explaining why it's safe. See commit 124c43d for context.