5 ms·

Wait, does F# not support mutual recursion? Can one not write eg a recursive descent parser?

Iwan-Zotow 2y ago
No, this is about single pass compiler, which makes it fast but all references to use in current file to be defined earlier
- kerkeslager 2y ago
  Single pass compilation can support backreferences, i.e. referencing a symbol and then defining it later, efficiently with a technique called "backpatching". All single-pass compilers I know of use backpatching for computing jumps--I'm not even aware of any other way to compute jumps. For symbols, the implementation of backpatching is a bit more complex, but it's a pretty well-known solution and I don't think it would be a significant barrier for any competent compiler developer. That is to say, if they've chosen to not support backreferences, it's not because it's hard to do in a single-pass compiler. EDIT: The wonderful book Crafting Interpreters has an implementation of backpatching jumps to implement loops. Before anyone says "this is an interpreter, not a compiler", be aware that most modern interpreters contain a compiler. https://craftinginterpreters.com/jumping-back-and-forth.html https://craftinginterpreters.com/jumping-back-and-forth.html
  - Iwan-Zotow 2y ago
    Sure, we could do some craft to work around single pass limitations, but that was Don Syme decision from long time ago, and F# folks are faithful to it. Actually liked language a lot, thought it could replace Python as top level AI/ML tool
- bunderbunder 2y ago
  That was why it was done that way in languages developed in the 1970s. But, as kerkeslager points out, that logic doesn't work for an enterprise programming language from the 2000s. We don't actually need to speculate on this. Don Syme has explicitly said that this was a deliberate language design decision meant to discourage the big ball of mud antipattern. And the language maintainers continue to cite this as the reason why they don't change this behavior even though they easily could.
kerkeslager 2y ago
They do support mutual recursion, but you have to make it explicit. https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/functions/recursive-functions-the-rec-keyword#mutually-recursive-functions https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref...
- mananaysiempre 2y ago
  Same as the rest of the ML family then.
  - bunderbunder 2y ago
    Same as the rest of the functional languages, even.
    - mananaysiempre 2y ago
      My first functional language was Haskell, which essentially only has a letrec, so afterwards I’ve always viewed everybody else’s approach as a bit peculiar :) Fair point that it’s the Lisp way too.
  - mjaniczek 2y ago
    Nah, Elm doesn't need the rec keyword and could be argued to be a ML descendant

No, this is about single pass compiler, which makes it fast but all references to use in current file to be defined earlier

kerkeslager 2y ago
Single pass compilation can support backreferences, i.e. referencing a symbol and then defining it later, efficiently with a technique called "backpatching". All single-pass compilers I know of use backpatching for computing jumps--I'm not even aware of any other way to compute jumps. For symbols, the implementation of backpatching is a bit more complex, but it's a pretty well-known solution and I don't think it would be a significant barrier for any competent compiler developer. That is to say, if they've chosen to not support backreferences, it's not because it's hard to do in a single-pass compiler. EDIT: The wonderful book Crafting Interpreters has an implementation of backpatching jumps to implement loops. Before anyone says "this is an interpreter, not a compiler", be aware that most modern interpreters contain a compiler. https://craftinginterpreters.com/jumping-back-and-forth.html https://craftinginterpreters.com/jumping-back-and-forth.html
- Iwan-Zotow 2y ago
  Sure, we could do some craft to work around single pass limitations, but that was Don Syme decision from long time ago, and F# folks are faithful to it. Actually liked language a lot, thought it could replace Python as top level AI/ML tool
bunderbunder 2y ago
That was why it was done that way in languages developed in the 1970s. But, as kerkeslager points out, that logic doesn't work for an enterprise programming language from the 2000s. We don't actually need to speculate on this. Don Syme has explicitly said that this was a deliberate language design decision meant to discourage the big ball of mud antipattern. And the language maintainers continue to cite this as the reason why they don't change this behavior even though they easily could.

kerkeslager 2y ago

They do support mutual recursion, but you have to make it explicit. https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/functions/recursive-functions-the-rec-keyword#mutually-recursive-functions https://learn.microsoft.com/en-us/dotnet/fsharp/language-ref...

mananaysiempre 2y ago
Same as the rest of the ML family then.
- bunderbunder 2y ago
  Same as the rest of the functional languages, even.
  - mananaysiempre 2y ago
    My first functional language was Haskell, which essentially only has a letrec, so afterwards I’ve always viewed everybody else’s approach as a bit peculiar :) Fair point that it’s the Lisp way too.
- mjaniczek 2y ago
  Nah, Elm doesn't need the rec keyword and could be argued to be a ML descendant