Hacker News Reader

Comment by glifchits | Hacker News Reader

Looking at a random file in the Flow source [0]

      (* The entry point *)
      let rec go content =
        let env = { file = None; modified = []; line = 0; result = [] } in
        let lines = split_lines content in
        start env lines;
        match List.rev env.result with
        | [] -> []
        | _ :: results -> results

      (* Skip the text before the first +++ (to make things work with git show) *)
      and start env = function
        | [] -> ()
        | line :: lines
          when String.length line > 4 && String.sub line 0 3 = "+++" ->
            header env line;
            modified env 0 lines
        | _ :: lines -> start env lines

Its beautiful to me because its very concise looking, while still using a fair bit of real English, meaningful symbols, and idioms like [] makes an empty array or whatever. I have to admit, much of this is lost on me, but it does feel more accessible than other FP languages. It almost has a Python feel.

[0] https://github.com/facebook/flow/blob/master/hack/parsing/fo...

View on HN

To be clear, here's the Haskell translation

    go content =
      let env   = Env { file = Nothing, modified = [], line = 0, result = 0 }
          lines = split_lines content
          env'  = start env lines
      in case reverse (result env') of
           []          -> []
           _ : results -> results

    start env x = case x of
      [] -> return ()
      line : lines
        | length line > 4 && take 3 line == "+++" ->
          do header env line
             modified env 0 lines
        | otherwise ->
          start env lines

Or, slightly differently, start probably should have been

    start env x = case x of
      [] -> env
      line : lines 
        | length line > 4 && take 3 line == "+++" ->
          modified (header env line) 0 lines
        | otherwise ->
          start env lines

This reflects the pure functional style over the state monad mechanism I half implemented above. OCaml is just using normal mutability.

Is there any reason for using a case instead of

    start env [] = env
    start env (line:lines)
        | length line > 4 && take 3 line == "+++" =
            modified (header env line) 0 lines
        | otherwise =
            start env lines

or even

    start env [] = env
    start env (line@('+':'+':'+':_:_):lines) =
        modified (header env line) 0 lines
    start env (_:lines) =
        start env lines

?

The first one is basically identical. The second one I probably wouldn't do. In both cases it just comes down to style though.

Another thing maybe difficult to mentally parse is the `and`. One might assume it's a logical operator, and get confused. But actually in OCaml

    let rec f (farg1) =
      ...
    and g (garg1) =
      ...

is used to define mutually recursive functions f and g.

Then again, in the given code the function `start`, while calling itself, doesn't call the other function `go`, so they are not really mutually recursive. `go` just calls `start` but actually `go` is not recursive at all.

So they could have written:

    let rec start (env) =
      ...

and then

    let go (content) =
      ...

In this case, `start` needs to be defined first in the source code, so `go` can call it. Maybe the author wanted to write `start` below the definition of `go` (kind of Haskell style) and kind of abused the mutual recursion form for stylistic reasons?

Out of interest: why is it this way? In a lot of other languages (e.g. Java or Python), you don't need to do this. Can't the compiler just figure out that a function refers to another function that's defined later in the same scope? Clojure also requires you to declare a function manually, so I guess it's not completely unheard of, but I'm curious if there's a technical reason or if it's just a more or less arbitrary choice.

I guess for historical and stylistic reasons the OCaml people wanted to allow redefining variables while using the old values in the definition.

So you can say

    let process data =
      let data = sanitize data in
      f(data)

instead of

    let process data0 =
      let data1 = sanitize data0 in
      f(data1)

And because OCaml uses the same let syntax for variables and functions, this also lets you to

    let f x = x * x
    let f x = f (f x)
    
    # now f(3) will be 81

So we can define new f using the definition of old f.

In some cases I can see the point of overwriting variables, instead of using new names like data0, data1, data2, but in the case of functions, redefining functions while utilizing the previous definition in the body of new definition will probably not catch on.

But anyway, because this is possible, OCaml needs another way to signify the that f used in the definition of f is not meant to refer to a previous definition, but the current one.

Hence, let rec.

Also, while marking a single function recursive maybe does not make much difference when reading source code, it's kind of nice to read code when a group of mutually recursive functions is explicitly marked as such.

It's actually quite nice to have to explicitly declare when binding scopes are recursive. It's an easy bug to make on accident otherwise.

Additionally, a recursive binding (behind the scenes) is semantically much more complex as it's the effect of having a fixed-point operator called on a higher-order function. It's nice to have to make a specific syntactic call out to have this happen.

I weakly agree, having been frustrated by both sides of the issue.

I really wish Haskell used `let rec`. It's really easy to accidentally write an infinite loop when all lets are rec, but if you forget the rec you almost certainly will get a name or type error.

Maybe I'd hate it after a day, but I think I wouldn't.

In my experience, both errors happen rarely, but both happen, and unintended-rec is much harder to track down.

You need it due to type inference, otherwise the engine cannot infer all the types properly.

I don't think this is true. Because: Standard ML does not have let rec, but can do type inference just fine.

https://realworldocaml.org/v1/en/html/variables-and-function...

"OCaml distinguishes between nonrecursive definitions (using let) and recursive definitions (using let rec) largely for technical reasons: the type-inference algorithm needs to know when a set of function definitions are mutually recursive, and for reasons that don't apply to a pure language like Haskell, these have to be marked explicitly by the programmer."

Hmm, yes.

Depends on whether /u/hencq asked about why rec is needed, or why and is needed.

I answered above, why rec. And you answered why an explicit grouping of mutually recursive functions using and is needed. And true, this is needed for type inference. And even though Standard ML does not need rec, it does need and.

Ah very interesting. I guess my question was mainly about and, though I hadn't thought about the reasons for rec. It makes sense that that removes a class of errors.

So as a follow-up question: why is type inference impossible without and or what is it about and that makes it possible? For instance, what would happen if I (out of laziness or something) would just insert and everywhere, even for functions that aren't mutually recursive. So, e.g.

  let rec f x = x + 1
  and g y = y * 2

Would type inference somehow fail on that? If not, what's stopping me from writing a version of OCaml where all top level lets are automatically converted to let ... and ... and? (Other than a complete lack of necessary compiler writing skills obviously)

Here is a Stackoverflow answer: http://stackoverflow.com/a/904715/1115446

I don't think anything stops you from defining all functions in a program in one giant let rec ... and ..., but doing that might set some other limitations on how you can structure your code.

I agree that OCaml syntax is relatively nice, and very readable. But the first line

    let rec go content =

may be problematic for an outsider who doesn't know that let and rec are keywords.

It means let recursive function go(content) = ...

Looks better with syntax highlighting: https://paste.debian.net/133342/

I'm not sure it is that concise. Just look at the code that you've given. What is it actually doing? How much of it is the juicy part and how much is the language clutter? To me, it feels like in terms of the actual functionality this code does not do that much. Skips the text before first "+++". In more concise languages that whole piece would look like a single line:

    env.lines = [line for line in env.lines if not line.startswith("+++")]

And just look at this:

    when String.length line > 4 && String.sub line 0 3 = "+++"

Really? Specifying numbers like that in the code? And are we really going to alloc an object here? Wow. Wouldn't anyone prefer to use something like:

    line.startswith("+++") ?

edit: my code doesn't implement the exact same functionality. I've only attempted to give a feel/look of the code, not rewrite it. it looks like the original code returns the lines after the '+++' lines, but I can not tell for sure, as the header/modified function implementations are not given.

> In more concise languages that whole piece would look like a single line:

---

  env.lines = [line for line in env.lines if not line.startswith("+++")]

---

I don't think that's what its actually doing. I think its actually return all the lines after the first line that starts with "+++". Or maybe all those lines but the first.

(I don't think its a good example of clear FP code, either.)

To this Haskeller it appears to be keeping state as well.

Certainly some information is moving behind the scenes, given the "header ... ; modified ..."

Yeah, in Haskell I'd probably have done something like

    dropWhile (not . T.isPrefixOf "+++") >>> \case
        [] -> return ()
        (line:lines) -> do
            header env line
            modified env 0 lines

edited to add: code above assumes LambdaCase and OverloadedStrings extensions, and that you've imported Data.Text qualified as T

lambdacase is one of my favorite extensions :D

I really like ScopedTypeVariables

I'm pretty sure the Ocaml code is doing more than the Python code you posted. Hopefully someone who knows Ocaml can explain it to us and then we can write the actual python equivalent.

Err. Ok. Just look at this. Is that concise?

    when String.length line > 4 && String.sub line 0 3 = "+++"

Specifying numbers like that in the code? Allocating an object? Wow. I don't understand why anyone wouldn't prefer to use something like:

    line.startswith("+++")

The ocaml standard library is minimal to a fault. It's just enough to implement the compiler itself. For higher level operations like starts_with, you use libraries. The Batteries library for example provides what you want:

    String.starts_with line "+++"

Note, that the original code reads:

    when String.length line > 4 && String.sub line 0 3 = "+++"

And the Batteries library is not being used in the original code. If that doesn't tell you anything, I'm sorry. And good luck.

It's a problem. Until people have standardized on which 'better standard library' to use, programs will keep building from these too low level building blocks.

It is a style, not a problem. OCaml had been there a long long time. I've brushed with it a couple of times over the years, and every time the same thing.

You look at some random OCaml code, and it looks like this:

    when String.length line > 4 && String.sub line 0 3 = "+++"

I'm looking at it, and I'm not even sure - is it a bug there? Should it be '>=3' or they've really wanted to say '> 4'. Numbers all other the place? Ten different variants of equal signs?

You can call it a style if that makes a difference. I think there are reasons behind that style, and I think the too minimal standard library is the main reason. The lack of a good package manager until recently may be another contributing reason.

I hesitate to answer your hyperbole about ten variants of equal signs. It's not uncommon for languages to have two notions of equality like ocaml has (or even more): Here's Python for example: http://stackoverflow.com/questions/132988/is-there-a-differe...

To answer your original question of why anyone would prefer to not use startswith: I don't think anyone does.

Well, for starters,

    start env = function
      | [] -> ()
      | line :: lines
        when String.length line > 4 && String.sub line 0 3 = "+++" ->
          header env line;
          modified env 0 lines
      | _ :: lines -> start env lines

is a bit elitist way to write a 2 argument function as a combination of 1 argument function and a lambda function. So let me rewrite:

    start (env) (list) = match list with
      | [] -> ()
      | line :: lines
          when String.length line > 4 && String.sub line 0 3 = "+++" ->
          header env line;
          modified env 0 lines
      | _ :: lines -> start env lines

So the function `start` takes some kind of state `env` as a first argument, and then it takes a list as a second argument, here named `list`.

If the list is empty, [], it does nothing.

If the first list element, which is a string, starts with "+++", it calls two other functions: first header(env,line) where `line` is now the first list element, and then modified(env,0,lines) where `lines` is the rest of the list, not containing the first element.

If the first list element does not start with +++, it recurses to the rest of the list.

So this is not a filter: After first encounter of "+++" it calls those two other functions and stops.

Sounds a bit silly to write something like that by hand, when you could use BatList.drop_while (from batteries) like so:

    let line_is_not_header line =
        String.length line < 4 || String.sub line 0 3 != "+++"
    match (BatList.drop_while line_is_not_header lines) with
    | header_line :: following_lines ->
        header env header_line;
        modified env 0 following_lines
    | _ -> ()

In practice, I find that it's rarely useful to write recursive functions by hand, unless you're willing to limit yourself to the default stdlib.

In python3 something like:

    def start(env, lines):
        while lines:
            line, *lines = lines
            if len(line) > 4 and line.startswith("+++"):
                header(env, line)
                modified(env, 0, lines)

Notes:

    while lines:

is pythonic for

    while not lines == []:

Correction (I forgot the break):

    def start(env, lines):
        while lines:
            line, *lines = lines
            if len(line) > 4 and line.startswith("+++"):
                header(env, line)
                modified(env, 0, lines)
                break

> looks like the original code returns the lines after the '+++' lines, but I can not tell for sure, as the header/modified function implementations are not given

Actually from the line

    | [] -> ()

we know that the function `start`returns nothing (well, returns a special value 'unit' which is OCaml's way to say nothing), so also the functions `header` and `modified` inside must return nothing, so they are called for their side effects only.

> we know that the function `start`returns nothing

Which is cool, but start is a (recursive) helper function for the go function (and if you look at the source file, there are a number more that are defined along with it, this is kind of a weird excerpt to just show the main go function and the first of several helpers), which is be the main public interface being defined in the code presented. I wasn't trying to describe what it looked like start did when called, but what it seemed like go was trying to do.

(And, I was doing so looking just at the excerpt and going a bit off the cuff; its clearly, looking at the source file, doing a lot more.)

Your code is not doing the same thing. A few minor bits; env has no 'lines' in its definition and String.sub does not allocate objects: it's better to think of String.sub, String.length, etc. as functions packaged in a module of helpful combinators.

OCaml is a language with currying and higher order functions, all that power is wasted if instead of composition you `.Objected` into everything. The advantages of piping, currying and composition on first class functions simply cannot be overstated.

Okay, so the next thing, from String.sub line 0 3 it's clear that you need to know the string length, hence the > 4 can't be avoided. You could pack it away into a function but why waste time if you're not going to write this 3 or more times?

The function `start` takes an env, a string list and returns unit. It's a procedure. The function looks for a string that starts with "+++" and either fails to find and returning () else passes to `modified` (also a procedure, tail recursive) which goes through the list (line :: lines returns the head and the tail of the list) applying modifications to env by tracking which lines were modified. `Lines` is an integer list and `result` is an integer pair list, so hopefully it's clearer now why your code is doing something completely different.

When I saw OCaml the first time I saw a much different syntax than this: lots of double semicolons (and lots more single semicolons than were present here). This looks much like Standard ML instead. What's up with that?

Double semicolons are used in the OCaml REPL to evaluate the current input (instead of newlines as in e.g. Python REPL). They don't need to be used in .ml files.

If you write in imperative style (using expressions for their side effect and discarding their return values) then you separate statements with a ;. But for code written in functional style, there will be no ;'s.

Then ;; is used to separate statements at the top level. But in most of the cases when a new top level statement begins, OCaml can understand this anyway and you can omit the ;;. Or use the ;; if you prefer that style.

So, imperative code is as full of ;'s as C code, and toplevel use of ;; is a stylistic issue.

https://ocaml.org/learn/tutorials/structure_of_ocaml_program...

Nitpick: [] is an empty list, an empty array would be [||]

I included the "or whatever" to cover this case :)

Reply on news.ycombinator.com