New single-file Earley implementation

 After reviewing my old code for an Earley parser, I thought I would try to write a new version following my preferences for OCaml coding in 2021. The result is here:

https://github.com/tomjridge/tjr_simple_earley/blob/master/src/earley_2021q1.ml



Compared to previous versions, the code is pleasingly easy to read (due to use of mutability everywhere). For example, the following are the types and implementations for sets and "map to set"s:


Timings:

time ./earley_main.exe earley_2021q1 :1x100
begin -------------------------------------------------
earley_2021q1; grammar=EEE; input_length=100 (bin/earley_main.ml)
Tjr_simple_earley__Earley_2021q1: count is 15756
end ---------------------------------------------------

real 0m0.110s
user 0m0.090s
sys 0m0.004s
time ./earley_main.exe earley_2021q1 :1x200
begin -------------------------------------------------
earley_2021q1; grammar=EEE; input_length=200 (bin/earley_main.ml)
Tjr_simple_earley__Earley_2021q1: count is 61506
end ---------------------------------------------------

real 0m0.548s
user 0m0.534s
sys 0m0.008s
time ./earley_main.exe earley_2021q1 :1x300
begin -------------------------------------------------
earley_2021q1; grammar=EEE; input_length=300 (bin/earley_main.ml)
Tjr_simple_earley__Earley_2021q1: count is 137256
end ---------------------------------------------------

real 0m2.500s
user 0m2.470s
sys 0m0.020s
time ./earley_main.exe earley_2021q1 :1x400
begin -------------------------------------------------
earley_2021q1; grammar=EEE; input_length=400 (bin/earley_main.ml)
Tjr_simple_earley__Earley_2021q1: count is 243006
end ---------------------------------------------------

real 0m6.867s
user 0m6.833s
sys 0m0.024s

Comments

Post a Comment

Popular posts from this blog

The Economics of Writing (Good) Code Documentation

TL;DR: Writing documentation can be beneficial even for a lone programmer writing code that will never be read by anyone else; however, the benefits, when other programmers are involved, are cumulative and potentially huge in terms of time saved (of those programmers) when trying to grok the existing codebase.  It is well known that programmers in general hate to write documentation. There are lots of reasons for this. For example, in the heat of writing code, the programmer simply cannot envisage what it would be like for someone else to come along in a couple of years and try to understand the code from scratch... And anyway, what does the programmer owe to that future person? (The programmer will likely have moved on by that point...) etc. etc. So, poor documentation (or lack of documentation altogether) is a problem that stems from the programmer, and probably left unfixed by the managers of the programmer, right up the chain of responsibility. This post isn't an attempt to add
Read more

A model of file update

I wanted to document (part of) the model of file behaviour that I use. This model is important to understand for people writing reliable crash-safe systems. Simple scenario, no file length update We consider the case of a single file, whose existence at a given path has been made persistent (i.e., after a crash, the file will still be found at that path).  We restrict to the case where we write over existing data, without extending the file length (again, the file length is assumed to already be persistent).  The model of the file data is as follows: There is an array of bytes which represents the data which is definitely on disk. There is also a "partial" (some entries may be missing) array of bytes which have been written by the application (eg via a call to pwrite), but which have not yet made it to disk, and so are "pending". An example: the file contents are initially: abcdefghij (10 bytes), and we use pwrite to write hello (5 bytes) at offset 2. Then the pendi
Read more

What is so special about cross-directory rename of a directory?

This is a short note to detail the issues that are raised by the filesystem operation of renaming a directory from its parent directory to some other directory. Background A filesystem typically allows a nested collection directories: the root directory contains subdirectories, which in turn contain subdirectories, and so on.  The on-disk state of the filesystem will typically lag the in-memory state. Indeed, more advanced filesystems may even permit the on-disk state to diverge from the in-memory state, so that the on-disk state may not represent any state that occurred in-memory. For example, we create a file "foo.txt" then a file "bar.txt". It is quite possible that a filesystem that then crashed might restart in a state where the file "bar.txt" exists, but "foo.txt" does not, even though this state was never seen in-memory. Implementation optimizations Implementations of filesystems would like to treat every file and every directory as indepe
Read more