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

Add Fixpoints in Computational Expressions #773

Open
Heimdell opened this issue Jul 19, 2019 · 1 comment

Comments

@Heimdell
Copy link

commented Jul 19, 2019

Fixpoints in Computational Expressions

In F# the let rec/and-bound expression can refer to itself, which is internally implemented as wrapping it with Lazy behind the scenes.

I propose we add an ability for let!-bound expressions to refer to themselves as well, analogous to how RecursiveDo Haskell extension does it.

Let me show an example:

{-# language RecursiveDo #-}

evalDecls :: Map Name AST -> Eval Frame
evalDecls decls = mdo
  st <- view stack
  frame <- traverse (allocate . Closed (frame : st)) decls
  return frame

As you can see, the monadic definition of frame refers to the frame itself. This is translated at the preprocessor stage to (several) calls of mfix :: (a -> m a) -> m a.

The existing way of approaching this problem in F# is writing a mfix : ('a Lazy -> a' m) -> 'a m function yourself and it's application is not very pretty (notice the Lazy over the argument).

Also, to clean things up, traverse has nothing to do with the problem.

The proposed syntax is

let! rec frame = ... frame ...

We also need to add recognition of MFix, MDo or Fixpoint method in a comp expr to see if the monad in question is able to perform the trick.

Pros and Cons

The advantages of making this adjustment to F# are:

  1. We get monadic fixpoint, which for some tasks (for instance, an evaluator with letrec) can lead to more clean and readable solution.

The disadvantages of making this adjustment to F# are... I don't know if there are any. We don't steal names to become keywords from user or break any code, since let! rec is a syntax error now.

Extra information

Estimated cost (XS, S, M, L, XL, XXL):

  • Parser stage: XS-S, depending on how the monadic syntax is parsed and if rec is a part of name and not the let construct.
  • The concrete algorithm of desugaring: up to M, if its decided to be implement "as in Haskell"
  • Preprocessor stage: S
  • Documentation update: S

Affidavit (please submit!)

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I would be willing to help implement and/or test this

@Heimdell Heimdell changed the title Fixpoints in Computational Expressions Add Fixpoints in Computational Expressions Jul 19, 2019

@dsyme

This comment has been minimized.

Copy link
Collaborator

commented Jul 19, 2019

@Heimdell I'm sympathetic, but we'd need a string of really good motivating examples here, thanks. Preferably comparing what has to be done today to what a let rec! would give you (I think I would prefer this syntax)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.