aristanetworks / aristanetworks/purescript-backend-optimizer

TCO can fail to trigger on Boolean yielding branches

Open
#106 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
PureScript
Stars
216
Forks
24
Avg merge
8m
Merged PRs (30d)
2

Description

Given a TCO function like:
```
go a = if f a then go (a + 1) else false
```

The optimizer will simplify this to the equivalent of

```
go a = f a && go (a + 1)
```

Which TCO doesn't understand. We should either not simplify this case or teach TCO to understand this. If we choose to not simplify this case, we should move this simplification rule to the JS backend after TCO. It's difficult to simplify this conditionally on the recursive call, because bottom-up we don't have the context to know that `go` is recursive unless we thread the environment though to `build`, which is not ideal.

@MonoidMusician @f-f Do you know if erl and scheme will eliminate the boolean and as a tail call? If not, then I'll probably move this rule to JS.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by locating the TCO pass and the simplification that rewrites conditional branches to boolean &&, then reproduce the issue with the example in the report. Check whether the Erlang and Scheme backends preserve the recursive tail call, and compare that with the JavaScript backend. Done means the simplification no longer prevents TCO, either by preserving the conditional or by making TCO understand the boolean form.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.