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

Make count and enumerate work for user-defined recursive types #175

Open
byorgey opened this issue Oct 2, 2019 · 4 comments
Open

Make count and enumerate work for user-defined recursive types #175

byorgey opened this issue Oct 2, 2019 · 4 comments
Labels
C-Moderate Effort Should take a moderate amount of time to address. S-Critical Critical importance U-Interpreter Z-Bug Z-Feature Request

Comments

@byorgey
Copy link
Member

byorgey commented Oct 2, 2019

Original comment: Have to extend count and enumerate to take the context of type definitions. Count has to do some kind of least fixed point computation, or a Jacobian matrix or something like that...

Using the enumeration library, and the fact that we should no longer support enumeration of infinite types (because lists are strict and hence finite), this should not be too bad. See also #309 and #347.

@byorgey byorgey added C-Moderate Effort Should take a moderate amount of time to address. Z-Feature Request labels Oct 2, 2019
@byorgey byorgey added C-Project A larger project that may take multiple days. S-Nice to have Minor importance Z-Research Project U-Interpreter and removed C-Moderate Effort Should take a moderate amount of time to address. labels Jun 24, 2020
@byorgey byorgey added C-Low Hanging Fruit Shouldn't take too much time; ideal issues for new contributors. and removed C-Project A larger project that may take multiple days. labels Jun 29, 2021
@byorgey
Copy link
Member Author

byorgey commented Jun 29, 2021

Actually, should be easy now with the enumeration library!

@byorgey byorgey added S-Moderate Moderate importance and removed S-Nice to have Minor importance labels Mar 19, 2022
@byorgey
Copy link
Member Author

byorgey commented Mar 19, 2022

This seems important to be able to do things like define recursive trees and enumerate or count them.

@byorgey byorgey added S-Critical Critical importance and removed S-Moderate Moderate importance labels Mar 28, 2022
@byorgey
Copy link
Member Author

byorgey commented Mar 28, 2022

Note that at the moment we can actually make Disco crash:

Disco> type X = Unit + Unit + Unit
Disco> count(X)
left(■)
Disco> enumerate(X)
disco: enumType: can't enumerate TyCon (CUser "X") []
CallStack (from HasCallStack):
  error, called at src/Disco/Enumerate.hs:174:23 in disco-0.1.5-58eEULBwaXh4U3Jv7xOL2y:Disco.Enumerate

@byorgey
Copy link
Member Author

byorgey commented Feb 28, 2024

See https://github.com/disco-lang/disco/blob/474384f5682dcd2b94f0aae1a58c578f1639c6df/src/Disco/Enumerate.hs . The obvious thing we need to do is extend the enumType function to handle TyUser. However, in order to do that we would need to add an extra argument to enumType, enumTypes, enumerateType, and enumerateTypes, namely, a map from user-defined type names to their definitions; however, that map is not available at runtime. Some solutions that come to mind:

  1. Perhaps VType values should also contain the mapping from user type names to definitions. I don't know how easy/possible it would be to capture that map at the time VType values are created.
  2. We could transform type values into a closed form using fixpoint bindings.

In any case, the idea would be build a lazy map from type names to enumerations; when we see a name that is already in the map we can stick an infinite combinator on top of the looked-up enumeration to prevent unproductive recursion. (Possible problem: do we need to do some analysis in order to only insert infinite when the type is, in fact, infinite?)

@byorgey byorgey added C-Moderate Effort Should take a moderate amount of time to address. and removed C-Low Hanging Fruit Shouldn't take too much time; ideal issues for new contributors. labels Feb 28, 2024
@byorgey byorgey added the Z-Bug label Sep 25, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-Moderate Effort Should take a moderate amount of time to address. S-Critical Critical importance U-Interpreter Z-Bug Z-Feature Request
Projects
None yet
Development

No branches or pull requests

1 participant