Loading ...
Sorry, an error occurred while loading the content.

Where's the "left-hand side" of let rec?

Expand Messages
  • Jeff Massung
    All joking aside, I must find this to be - without a doubt - the most annoying compile error of all time. For fun I ve put together a little parsec-style
    Message 1 of 5 , Jun 2, 2011
    • 0 Attachment
      All joking aside, I must find this to be - without a doubt - the most
      annoying compile error of all time. For fun I've put together a little
      parsec-style parser for myself. Now, using it to create a simple Lisp-syntax
      parser, I can't get past some simple expressions. For example:

      let parse_atom = many1 letter >>= (make_atom |> return)
      let parse_fixnum = many1 digit >>= (collect |> int_of_string |> make_fixnum
      |> return)
      let parse_string = between (char '"') (many (none_of "\"")) (char '"') >>=
      (collect |> make_str |> return)

      So, some pretty basic parsing. Everything works just as expected. But, now
      we move onto parsing lisp objects with lists (i.e. recursive parsing) and
      everything will grind to a quick halt.

      let rec parse_cell = parse_atom <|> parse_fixnum <|> parse_string <|>
      parse_list
      and parse_list = between (char '(') (many parse_cell) (char ')') >>=
      (make_list |> return)

      # Error: This kind of expression is not allowed as right-hand side of `let
      rec'

      Note: I've simplified the above a tad for clarity (removing whitespace
      skipping, etc), but I can also prove that the above will work if I just futz
      around with the REPL a bit and break things up...

      let parse_cell = parse_atom <|> parse_fixnum <|> parse_string
      let parse_list = ...

      (* now redefine parse_cell to be recursive and reference parse_list *)
      let rec parse_cell = parse_atom <|> parse_fixnum <|> parse_string <|>
      parse_list

      And now everything works just fine.

      I guess some questions I have are A) what is it about the original code that
      the compiler can't handle? Is it because it can't prove that the recursion
      isn't infinite and therefore bails? B) is there any way around this where I
      can just tell the compiler to trust me because I know what I'm doing? or C)
      am I just misunderstanding something fundamental here and trying to do
      something "wrong"?

      Thanks!

      Jeff M.


      [Non-text portions of this message have been removed]
    • rixed@happyleptic.org
      ... Not sure it s related, but I hit the same message (while coding a small parser similar to your own, incidentaly), and started a thread on caml-list ML
      Message 2 of 5 , Jun 3, 2011
      • 0 Attachment
        > # Error: This kind of expression is not allowed as right-hand side of `let
        > rec'

        Not sure it's related, but I hit the same message (while coding
        a small parser similar to your own, incidentaly), and started a
        thread on caml-list ML about it:

        http://www.mentby.com/rixed/strange-behavior-of-mutualy-recursive-definitions.html

        (or look for message id 20110427204629.GA8872@...
        if your mail reader is able to)
      • ga_sche
        This is a natural, but sometimes annoying, restriction on recursive definitions. Recursive are clearly well-defined when they immediately begin with a fun x
        Message 3 of 5 , Jun 3, 2011
        • 0 Attachment
          This is a natural, but sometimes annoying, restriction on recursive definitions.

          Recursive are clearly well-defined when they immediately begin with a "fun x -> ..." constructor. "let rec f x = ..." has a clear semantics, which comes from the fact that a function doesn't evaluate its body, so you can define it even if the function itself, which may be used recursively in the body, is not yet well-defined.

          Once you get outside of what statically is a function, some things are actually well-defined, while some others are not. For example:

          let rec li = 1::li (* can be given a meaning as an infinite, cyclic list *)
          let rec x = x + 1 (* should be rejected or not terminate *)
          let rec f = f 1 (* makes no sense *)
          let rec f = foo f (* may makes sense or not, depending on 'foo' *)

          Your example is an instance of the last case : you define 'parse_cell' recursively as the result of an *application* (actually, a bunch of applications of the binary operator <|>).

          The OCaml compilers cannot decide statically which applications are safe and which aren't (it would need to know which functions actually force evaluation of their arguments, and which do not, which is undecidable), so it plays it safe by disallowing them all.

          For a documentation of what non-immediate-functions recursions are allowed, see the relevant manual page :
          http://caml.inria.fr/pub/docs/manual-ocaml/manual021.html#toc70

          You can fix your example easily by making it apparent syntactically that what you're building is indeed a function:


          let rec parse_cell x = (parse_atom <|> parse_fixnum <|> parse_string <|> parse_list) x
          and parse_list x = (between (char '(') (many parse_cell) (char ')') >>= (make_list |> return)) x

          This manual transformation of (f) into (fun x -> f x) is called "eta-expansion", and may also be useful in other cases, in particular to cope with the value typing restriction. See the FAQ:
          http://caml.inria.fr/resources/doc/faq/core.en.html#eta-expansion

          The workaround I propose is syntactically ugly. Also, it may be problematic if you wished to define your parser as an abstract type, hiding his function type.

          There are two other possibilities:

          - instead of having caml-level recursive definitions, you could define a family of "fix" combinators for your parsing combinator library, and write instead
          let parse_cell, parse_list = fix2 (fun parse_cell parse_list -> ..., ...)

          - recursion is always allowed on lazy values, so you could use
          let rec parse_list = lazy (.... Lazy.force parse_list ...)
          or more generally exposing all your parsing combinators in a lazy type.

          --- In ocaml_beginners@yahoogroups.com, Jeff Massung <massung@...> wrote:
          >
          > All joking aside, I must find this to be - without a doubt - the most
          > annoying compile error of all time. For fun I've put together a little
          > parsec-style parser for myself. Now, using it to create a simple Lisp-syntax
          > parser, I can't get past some simple expressions. For example:
          >
          > let parse_atom = many1 letter >>= (make_atom |> return)
          > let parse_fixnum = many1 digit >>= (collect |> int_of_string |> make_fixnum
          > |> return)
          > let parse_string = between (char '"') (many (none_of "\"")) (char '"') >>=
          > (collect |> make_str |> return)
          >
          > So, some pretty basic parsing. Everything works just as expected. But, now
          > we move onto parsing lisp objects with lists (i.e. recursive parsing) and
          > everything will grind to a quick halt.
          >
          > let rec parse_cell = parse_atom <|> parse_fixnum <|> parse_string <|>
          > parse_list
          > and parse_list = between (char '(') (many parse_cell) (char ')') >>=
          > (make_list |> return)
          >
          > # Error: This kind of expression is not allowed as right-hand side of `let
          > rec'
          >
          > Note: I've simplified the above a tad for clarity (removing whitespace
          > skipping, etc), but I can also prove that the above will work if I just futz
          > around with the REPL a bit and break things up...
          >
          > let parse_cell = parse_atom <|> parse_fixnum <|> parse_string
          > let parse_list = ...
          >
          > (* now redefine parse_cell to be recursive and reference parse_list *)
          > let rec parse_cell = parse_atom <|> parse_fixnum <|> parse_string <|>
          > parse_list
          >
          > And now everything works just fine.
          >
          > I guess some questions I have are A) what is it about the original code that
          > the compiler can't handle? Is it because it can't prove that the recursion
          > isn't infinite and therefore bails? B) is there any way around this where I
          > can just tell the compiler to trust me because I know what I'm doing? or C)
          > am I just misunderstanding something fundamental here and trying to do
          > something "wrong"?
          >
          > Thanks!
          >
          > Jeff M.
          >
          >
          > [Non-text portions of this message have been removed]
          >
        • Jeff Massung
          ... Hands-down, this is one of the best explanations I ve read regarding this problem (combined with solutions). I just used the first solution you proposed
          Message 4 of 5 , Jun 3, 2011
          • 0 Attachment
            On Fri, Jun 3, 2011 at 4:43 AM, ga_sche <gabriel.scherer@...> wrote:

            >
            > Once you get outside of what statically is a function, some things are
            > actually well-defined, while some others are not. For example:
            >
            > let rec li = 1::li (* can be given a meaning as an infinite, cyclic list *)
            > let rec x = x + 1 (* should be rejected or not terminate *)
            > let rec f = f 1 (* makes no sense *)
            > let rec f = foo f (* may makes sense or not, depending on 'foo' *)
            >
            > Your example is an instance of the last case : you define 'parse_cell'
            > recursively as the result of an *application* (actually, a bunch of
            > applications of the binary operator <|>).
            >
            > The OCaml compilers cannot decide statically which applications are safe
            > and which aren't (it would need to know which functions actually force
            > evaluation of their arguments, and which do not, which is undecidable), so
            > it plays it safe by disallowing them all.
            >
            > For a documentation of what non-immediate-functions recursions are allowed,
            > see the relevant manual page :
            > http://caml.inria.fr/pub/docs/manual-ocaml/manual021.html#toc70
            >
            > You can fix your example easily by making it apparent syntactically that
            > what you're building is indeed a function:
            >
            > let rec parse_cell x = (parse_atom <|> parse_fixnum <|> parse_string <|>
            > parse_list) x
            > and parse_list x = (between (char '(') (many parse_cell) (char ')') >>=
            > (make_list |> return)) x
            >
            > This manual transformation of (f) into (fun x -> f x) is called
            > "eta-expansion", and may also be useful in other cases, in particular to
            > cope with the value typing restriction. See the FAQ:
            > http://caml.inria.fr/resources/doc/faq/core.en.html#eta-expansion
            >
            > The workaround I propose is syntactically ugly. Also, it may be problematic
            > if you wished to define your parser as an abstract type, hiding his function
            > type.
            >
            > There are two other possibilities:
            >
            > - instead of having caml-level recursive definitions, you could define a
            > family of "fix" combinators for your parsing combinator library, and write
            > instead
            > let parse_cell, parse_list = fix2 (fun parse_cell parse_list -> ..., ...)
            >
            > - recursion is always allowed on lazy values, so you could use
            > let rec parse_list = lazy (.... Lazy.force parse_list ...)
            > or more generally exposing all your parsing combinators in a lazy type.
            >

            Hands-down, this is one of the best explanations I've read regarding this
            problem (combined with solutions). I just used the first solution you
            proposed and everything "just worked". I now understand what the error
            message means and have tools in my box to make it work.

            I'm coming from Haskell where the lazy evaluation greatly helps here. Maybe
            I'll take a look at using the lazy module as I expand my library.

            I'm quite sure there are many OCaml "copies" of Parsec out there that others
            have written. But if anyone would like to see mine (it's dead simple) I'd be
            happy to share.

            Thanks again!

            Jeff M.


            [Non-text portions of this message have been removed]
          • Gabriel Scherer
            ... Jun Furuse has made a similar attempt recently, which you may be interested in: https://sympa-roc.inria.fr/wws/arc/caml-list/2011-05/msg00163.html I don t
            Message 5 of 5 , Jun 3, 2011
            • 0 Attachment
              >
              > I'm quite sure there are many OCaml "copies" of Parsec out there that
              > others
              > have written.
              >

              Jun Furuse has made a similar attempt recently, which you may be interested
              in:
              https://sympa-roc.inria.fr/wws/arc/caml-list/2011-05/msg00163.html

              I don't know how far you went, but his project is quite full-featured:
              correct handling of locations information in particular is no small feat.
              That he was able to lex&parse the OCaml language directly is impressive, but
              this also comes with a performance question.

              I had a suggestion (in the mailing-list thread) at a direction that would
              improve performance, which is not specific to his library (and would
              certainly be easier to put in practice in yours if it is simpler): instead
              of using a "functional" state-like monad, where computations are represented
              as closures, represent the build parsers as a concrete algebraic data type
              -- in a sense, a small "language" for parsers -- which would then be
              interpreted in one go, instead of building a closure at each step as of now.
              Sadly, I have had no time to play with the idea. If you're interested, I'm
              quite sure it makes a nice exercise.

              On Fri, Jun 3, 2011 at 5:44 PM, Jeff Massung <massung@...> wrote:

              >
              >
              > On Fri, Jun 3, 2011 at 4:43 AM, ga_sche <gabriel.scherer@...> wrote:
              >
              > >
              > > Once you get outside of what statically is a function, some things are
              > > actually well-defined, while some others are not. For example:
              > >
              > > let rec li = 1::li (* can be given a meaning as an infinite, cyclic list
              > *)
              > > let rec x = x + 1 (* should be rejected or not terminate *)
              > > let rec f = f 1 (* makes no sense *)
              > > let rec f = foo f (* may makes sense or not, depending on 'foo' *)
              > >
              > > Your example is an instance of the last case : you define 'parse_cell'
              > > recursively as the result of an *application* (actually, a bunch of
              > > applications of the binary operator <|>).
              > >
              > > The OCaml compilers cannot decide statically which applications are safe
              > > and which aren't (it would need to know which functions actually force
              > > evaluation of their arguments, and which do not, which is undecidable),
              > so
              > > it plays it safe by disallowing them all.
              > >
              > > For a documentation of what non-immediate-functions recursions are
              > allowed,
              > > see the relevant manual page :
              > > http://caml.inria.fr/pub/docs/manual-ocaml/manual021.html#toc70
              > >
              > > You can fix your example easily by making it apparent syntactically that
              > > what you're building is indeed a function:
              > >
              > > let rec parse_cell x = (parse_atom <|> parse_fixnum <|> parse_string <|>
              > > parse_list) x
              > > and parse_list x = (between (char '(') (many parse_cell) (char ')') >>=
              > > (make_list |> return)) x
              > >
              > > This manual transformation of (f) into (fun x -> f x) is called
              > > "eta-expansion", and may also be useful in other cases, in particular to
              > > cope with the value typing restriction. See the FAQ:
              > > http://caml.inria.fr/resources/doc/faq/core.en.html#eta-expansion
              > >
              > > The workaround I propose is syntactically ugly. Also, it may be
              > problematic
              > > if you wished to define your parser as an abstract type, hiding his
              > function
              > > type.
              > >
              > > There are two other possibilities:
              > >
              > > - instead of having caml-level recursive definitions, you could define a
              > > family of "fix" combinators for your parsing combinator library, and
              > write
              > > instead
              > > let parse_cell, parse_list = fix2 (fun parse_cell parse_list -> ..., ...)
              > >
              > > - recursion is always allowed on lazy values, so you could use
              > > let rec parse_list = lazy (.... Lazy.force parse_list ...)
              > > or more generally exposing all your parsing combinators in a lazy type.
              > >
              >
              > Hands-down, this is one of the best explanations I've read regarding this
              > problem (combined with solutions). I just used the first solution you
              > proposed and everything "just worked". I now understand what the error
              > message means and have tools in my box to make it work.
              >
              > I'm coming from Haskell where the lazy evaluation greatly helps here. Maybe
              > I'll take a look at using the lazy module as I expand my library.
              >
              > I'm quite sure there are many OCaml "copies" of Parsec out there that
              > others
              > have written. But if anyone would like to see mine (it's dead simple) I'd
              > be
              > happy to share.
              >
              > Thanks again!
              >
              >
              > Jeff M.
              >
              > [Non-text portions of this message have been removed]
              >
              >
              >


              [Non-text portions of this message have been removed]
            Your message has been successfully submitted and would be delivered to recipients shortly.