{"action":"created","issue":{"url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/12","labels_url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/12/labels{/name}","comments_url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/12/comments","events_url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/12/events","html_url":"https://github.com/freebroccolo/yggdrasil/issues/12","id":92974337,"number":12,"title":"Incremental parsing","user":{"login":"freebroccolo","id":151197,"avatar_url":"https://avatars.githubusercontent.com/u/151197?v=3","gravatar_id":"","url":"https://api.github.com/users/freebroccolo","html_url":"https://github.com/freebroccolo","followers_url":"https://api.github.com/users/freebroccolo/followers","following_url":"https://api.github.com/users/freebroccolo/following{/other_user}","gists_url":"https://api.github.com/users/freebroccolo/gists{/gist_id}","starred_url":"https://api.github.com/users/freebroccolo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/freebroccolo/subscriptions","organizations_url":"https://api.github.com/users/freebroccolo/orgs","repos_url":"https://api.github.com/users/freebroccolo/repos","events_url":"https://api.github.com/users/freebroccolo/events{/privacy}","received_events_url":"https://api.github.com/users/freebroccolo/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-07-04T05:42:58Z","updated_at":"2015-07-04T22:55:25Z","closed_at":null,"body":"I'd like to get incremental parsing working but the issue is complicated somewhat by the fact that `lwt` uses a monadic style but the lexing and parsing libraries do not. Perhaps the `menhir` incremental API makes it less of an issue on the parsing side but I haven't tried it yet so I'm not sure. In general, the problem can be solved by using delimited continuations to mediate between direct-style and monadic-style code (e.g., `lwt` \"fibers\"). However, the `delimcc` implementation seems a bit dodgy (there are problems with the native-code version for some compilers) so relying on it here isn't super appealing.\r\n\r\nOne option would be to re-implement `delimcc` locally and just fix the problems with it. A more appealing alternative would be to experiment with multicore OCaml since it already supports algebraic effects and coroutines. In the long run, it would probably be a natural fit for the project anyway. There are probably some bugs but at least it is under active development."},"comment":{"url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/comments/118561316","html_url":"https://github.com/freebroccolo/yggdrasil/issues/12#issuecomment-118561316","issue_url":"https://api.github.com/repos/freebroccolo/yggdrasil/issues/12","id":118561316,"user":{"login":"freebroccolo","id":151197,"avatar_url":"https://avatars.githubusercontent.com/u/151197?v=3","gravatar_id":"","url":"https://api.github.com/users/freebroccolo","html_url":"https://github.com/freebroccolo","followers_url":"https://api.github.com/users/freebroccolo/followers","following_url":"https://api.github.com/users/freebroccolo/following{/other_user}","gists_url":"https://api.github.com/users/freebroccolo/gists{/gist_id}","starred_url":"https://api.github.com/users/freebroccolo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/freebroccolo/subscriptions","organizations_url":"https://api.github.com/users/freebroccolo/orgs","repos_url":"https://api.github.com/users/freebroccolo/repos","events_url":"https://api.github.com/users/freebroccolo/events{/privacy}","received_events_url":"https://api.github.com/users/freebroccolo/received_events","type":"User","site_admin":false},"created_at":"2015-07-04T22:55:25Z","updated_at":"2015-07-04T22:55:25Z","body":"So it turns out `4.02` introduced a change to the lexing API that allows control over how the buffer gets refilled, which is precisely what is needed to make it work with `lwt`. Unfortunately `sedlex` doesn't seem to have similar functionality yet (as far as I can tell). It probably wouldn't be too hard to add, but I think I'll just use `ocamllex` for now.\r\n\r\nHere's a proof of concept for the lexing part:\r\n\r\n```ocaml\r\n(* lexer.mll *)\r\n{\r\ntype token =\r\n  | EOF\r\n  | INT of int\r\n  | LEFT_PARENTHESIS\r\n  | PLUS\r\n  | RIGHT_PARENTHESIS\r\n  | TIMES\r\n\r\nmodule type SOURCE = sig\r\n  val on_refill : Lexing.lexbuf -> unit Lwt.t\r\nend\r\n\r\nmodule type LEXER = sig\r\n  val token : Lexing.lexbuf -> token Lwt.t\r\nend\r\n\r\nmodule Make (R : SOURCE) : LEXER = struct\r\n  let refill_handler k lexbuf = R.on_refill lexbuf >> k lexbuf\r\n}\r\n\r\nlet int = ['0'-'9'] ['0'-'9']*\r\nlet white = [' ' '\\t']+\r\nlet newline = '\\r' | '\\n' | \"\\r\\n\"\r\n\r\nrefill {refill_handler}\r\n\r\nrule token = parse\r\n  | white\r\n{ token lexbuf }\r\n  | newline\r\n{ Lexing.new_line lexbuf; token lexbuf }\r\n  | int\r\n{ Lwt.return (INT (int_of_string (Lexing.lexeme lexbuf))) }\r\n  | \"(\"\r\n{ Lwt.return LEFT_PARENTHESIS }\r\n  | \")\"\r\n{ Lwt.return RIGHT_PARENTHESIS }\r\n  | \"*\"\r\n{ Lwt.return TIMES }\r\n  | \"+\"\r\n{ Lwt.return PLUS }\r\n  | _\r\n{ Lwt.fail_with (\"Unexpected char: \" ^ Lexing.lexeme lexbuf) }\r\n  | eof\r\n{ Lwt.return EOF }\r\n\r\n{\r\nend\r\n\r\nmodule type STATE = sig\r\n  val ix: Lwt_io.input_channel\r\n  val sz: int\r\nend\r\n\r\nmodule LwtSource (S : STATE): SOURCE = struct\r\n  let resize b n =\r\n    let open Lexing in\r\n    if (b.lex_buffer_len + n) > (Bytes.length b.lex_buffer) then begin\r\n      let tmp_buf = ref b.lex_buffer in\r\n      if (b.lex_buffer_len - b.lex_start_pos + n) > Bytes.length b.lex_buffer then begin\r\n        let new_len = min (2 * Bytes.length b.lex_buffer) Sys.max_string_length in\r\n        if b.lex_buffer_len - b.lex_start_pos + n > new_len then\r\n          failwith \"cannot resize buffer\"\r\n        else\r\n          tmp_buf := Bytes.create new_len\r\n      end;\r\n      Bytes.blit b.lex_buffer b.lex_start_pos !tmp_buf 0 (b.lex_buffer_len - b.lex_start_pos);\r\n      b.lex_buffer <- !tmp_buf;\r\n      for i = 0 to Array.length b.lex_mem - 1 do\r\n        if b.lex_mem.(i) >= 0 then\r\n          b.lex_mem.(i) <- b.lex_mem.(i) - b.lex_start_pos\r\n      done;\r\n      b.lex_abs_pos    <- b.lex_abs_pos    + b.lex_start_pos;\r\n      b.lex_curr_pos   <- b.lex_curr_pos   - b.lex_start_pos;\r\n      b.lex_last_pos   <- b.lex_last_pos   - b.lex_start_pos;\r\n      b.lex_buffer_len <- b.lex_buffer_len - b.lex_start_pos;\r\n      b.lex_start_pos  <- 0;\r\n    end\r\n\r\n  let on_refill b =\r\n    let open Lexing in\r\n    let aux_buffer = Bytes.create S.sz in\r\n    let%lwt n = Lwt_io.read_into S.ix aux_buffer 0 S.sz in\r\n    if n = 0 then\r\n      Lwt.return (b.lex_eof_reached <- true)\r\n    else begin\r\n      resize b n;\r\n      Bytes.blit aux_buffer 0 b.lex_buffer b.lex_buffer_len n;\r\n      Lwt.return (b.lex_buffer_len <- b.lex_buffer_len + n)\r\n    end\r\nend\r\n\r\nlet create (ix : Lwt_io.input_channel) (sz : int) : (module LEXER) * Lexing.lexbuf =\r\n  let open Lexing in\r\n  let m : (module LEXER) = (module Make (LwtSource (struct\r\n    let ix = ix\r\n    let sz = sz\r\n  end))) in\r\n  let zero_pos = {\r\n    pos_fname = \"\";\r\n    pos_lnum  = 1;\r\n    pos_bol   = 0;\r\n    pos_cnum  = 0;\r\n  } in\r\n  let b = {\r\n    refill_buff     = (fun _ -> ());\r\n    lex_buffer      = Bytes.create sz;\r\n    lex_buffer_len  = 0;\r\n    lex_abs_pos     = 0;\r\n    lex_start_pos   = 0;\r\n    lex_curr_pos    = 0;\r\n    lex_last_pos    = 0;\r\n    lex_last_action = 0;\r\n    lex_mem         = [| |];\r\n    lex_eof_reached = false;\r\n    lex_start_p     = zero_pos;\r\n    lex_curr_p      = zero_pos;\r\n  } in (m, b)\r\n\r\nlet driver () : unit Lwt.t =\r\n  let fd = Unix.stdin in\r\n  let ix, sz = Lwt_io.of_unix_fd (Lwt_io.Input) fd, 1 in\r\n  let m, b = create ix sz in\r\n  let module L = (val m : LEXER) in\r\n  let open Lexing in\r\n  let more = ref true in\r\n  while%lwt !more do match%lwt L.token b with\r\n    | EOF ->\r\n        Lwt.return (more := false)\r\n    | INT i ->\r\n        Lwt_io.print (string_of_int i)\r\n    | LEFT_PARENTHESIS ->\r\n        Lwt_io.print \"(\"\r\n    | PLUS ->\r\n        Lwt_io.print \"+\"\r\n    | RIGHT_PARENTHESIS ->\r\n        Lwt_io.print \")\"\r\n    | TIMES ->\r\n        Lwt_io.print \"*\"\r\n  done >> Lwt_io.printl \"\"\r\n\r\nlet () = Lwt_main.run (driver ())\r\n}\r\n```"}}