Comments (4)
Hi,
Thanks for your interest! This code base isn't actively maintained anymore, and from a cursory look, it appears to have bit-rotted: at least the first thing that fails is due to the fact that the latest version of Coq no longer supports the omega
tactic, so FSCQ would need to be updated to use lia
instead.
I think the Ocaml extraction did work at one point, but I don't remember what its state was when we last worked on FSCQ. The main thing to look at is whether the Ocaml native code (e.g., in mllib
) is up-to-date with the Haskell equivalent (e.g., in hslib
). There's also an Ocaml fuse wrapper in ocamlfuse
, which we imported from a third party; I don't recall how robust it is compared to the Haskell fuse wrapper we used, but this part might not matter as much for your use case.
Our more recent work on verifying file systems is https://github.com/mit-pdos/daisy-nfsd and its underlying components like https://github.com/mit-pdos/go-journal but it's written in Go, so it might be less appealing for your Ocaml use case.
from fscq.
Thanks for the quick answer and for the details!
I'll keep you updated wrt what I manage to do regarding bitrot. Comparing the status of the current ocaml code with the haskell equivalent is also good advice, thanks.
(Your more recent work looks indeed interesting as well, but as you mention it is probably harder to directly compile it as an OCaml library.)
from fscq.
Hello again! Reporting back from the progress I made during the retreat :-).
- I made the Coq proofs work again, after some minor tweaks. I submitted this as PR #17. This is still with Coq 8.13, and there are still warnings (related to uses of omega and hint declarations) -- I worked on fixing the warnings in another branch, but got stuck near the end; I'll try to revisit this at some point later.
- I refreshed the OCaml wrapper code to be up-to-date with the Haskell equivalent, and fixed the bugs I could find through light testing (as always, fixing the bugs took more time than writing the bugs, especially ones caused by slightly wrong implementations in
word.ml
:-)). I've attached the current state of that work as PR #18 (based on top of #17). - The main remaining issue seem to be performance. The main common cause seems to be differences between eager and lazy evaluation. Some cases I could easily fix using +/- ad-hoc ways; but there seem to be a more general issue of the code doing list manipulations that are (I assume?) efficient enough with lazy lists, but terribly inefficient with strict lists. This is e.g. repeatedly appending lists, or, a more surprising instance, calling
repeat
to create a list with ~200M elements (indread
inBlockPtr.v
). - Possible ways to address the performance issues could be to swap out at extraction time the lists with lazy lists (but I wouldn't be surprised if OCaml lazy lists are less efficient than Haskell lazy lists), or maybe a (lazy) data-structure with good complexity for e.g. append as well? But I would like to understand the code better before going that way blind. It would be helpful to get some intuition about whether one could "just" tweak the code to do list manipulations differently, in a way that would be efficient in OCaml... any clues? :-)
from fscq.
Thanks for the two PRs!
The lack of lazy evaluation sounds familiar -- I think we also ran into issues there and stopped trying to use the Ocaml extraction. Lazy evaluation has its own performance overheads, and we were hoping to avoid some of these issues by switching to Ocaml, but our FSCQ implementation seems to effectively rely on it for reasonable performance in a number of places, so it was easier to instead improve performance in Haskell by adding strictness annotations, instead of getting the Ocaml implementation to run fast.
It's certainly a possibility to change the FSCQ implementation so that it doesn't generate huge data structures in the first place (like the giant repeat
in indread
, as you discovered), but it would require tweaking the proofs, which is time-consuming. Replacing the list with a more complex data structure at extraction time would avoid the need to tweak proofs, but my intuition is that you won't get great performance that way (but perhaps still better than the degenerate cases you're seeing now), and the complexity of these data structures might undermine the supposed verification guarantees.
from fscq.
Related Issues (15)
- Multiuser/permissions support HOT 1
- sync() fails to persist a new directory entry HOT 2
- Potential crash consistency bug - fsync fails to persist directory entry HOT 9
- Potential logic bug: renaming an emptied directory fails HOT 4
- fdatasync not working as expected on fscq? HOT 4
- ftruncate to grow a file does not allocate blocks HOT 1
- truncate extension sometimes extends with file names instead of zeros HOT 4
- Removing a non-empty directory results in EIO HOT 3
- Subdirectories do not increment parent directory's link count
- chmod has no effect and does not return an error HOT 2
- Renaming a directory to a non-empty directory results in EIO HOT 1
- Symlink support
- Hard link support HOT 1
- Time support
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from fscq.