Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow reflecting functions with local definitions #2480

Open
facundominguez opened this issue Jan 27, 2025 · 1 comment
Open

Allow reflecting functions with local definitions #2480

facundominguez opened this issue Jan 27, 2025 · 1 comment

Comments

@facundominguez
Copy link
Collaborator

facundominguez commented Jan 27, 2025

Functions with local definitions cannot be reflected at the moment. If the user wants to reflect them, she must rewrite them to not use local definitions.

For instance, the following fails at the moment.

{-@ LIQUID "--reflection" @-}
import Prelude()

{-@ reflect foldr @-}
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z = go
  where
    go [] = z
    go (x:xs) = f x (go xs)

The error is

Test2.hs:6:13: error:
    Cannot lift Haskell function `foldr` to logic
    Cannot make Logical Substitution of Recursive Definitions
  |
6 | {-@ reflect foldr @-}
  |

The following rewritten definition can be reflected instead.

{-@ LIQUID "--reflection" @-}
import Prelude()

{-@ reflect foldr @-}
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

The designs of the solution need to be explored. One approach is to use local rewrites.

@AlecsFerra
Copy link
Contributor

I think that it should work with local rewrites by rewriting go as a lambda: go = \(x:xs) -> f x (go xs) as I guess the termination checker can already check if go is terminating, one down side is that we will lock the user in using --eta-beta but personally I think it is fine

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants