Re: [Nix-dev] Writing a Nix evaluator in Haskell
Peter Simons sim...@cryp.to writes: At some point, however, I felt like Parsec became a bit of a burden, i.e. adding features like full support for antiquotation ceased to be fun. :-) Interesting. I'll work on this next, so that I know whether the path I've chosen is viable or not. Anyway, the code is online again. I hope it's useful in one way or another! I've downloaded it and will look it over for reference. Thanks! John ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
Hi John, Peter, did you it move [the repository] to someplace else? I have re-created the repository at https://github.com/peti/language-nix. Originally, I attempted to parse Nix with Parsec, and I got quite far. The code in 'master' can parse almost all of all-packages.nix correctly. At some point, however, I felt like Parsec became a bit of a burden, i.e. adding features like full support for antiquotation ceased to be fun. :-) At some point I decided that uuparsinglib looked more promising, and I also started a re-write, but then I lost interest in the project and didn't pursue it any further. Anyway, the code is online again. I hope it's useful in one way or another! Best regards, Peter ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
modeled very simply as a loeb function over memoized IO actions John, that might be simple for you :). Would you say a few words to demystify for the rest of us? Well, for me at least :$. Cheers, Steve. ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
On 06/30/2014 10:51 PM, Steven Shaw wrote: modeled very simply as a loeb function over memoized IO actions John, that might be simple for you :). Would you say a few words to demystify for the rest of us? Well, for me at least :$. I don't know these concepts, but I'd recommend reading sigfpe's account, as his explanations are nice in my experience. http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet.html Vlada smime.p7s Description: S/MIME Cryptographic Signature ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
Steven Shaw ste...@steshaw.org writes: modeled very simply as a loeb function over memoized IO actions John, that might be simple for you :). Would you say a few words to demystify for the rest of us? Well, for me at least :$. So, after trying to implement this idea, I discovered that loeb is too one-dimensional for this to work. But in case it helps, below is the blog post I was going to upload about it. Now I'll have to modify it to remove the parts about Nix. John --- title: Demystifying the loeb function description: desc here tags: haskell date: [2014-06-18 Wed 21:07] category: Haskell --- Recently I was reading some articles by Chris Done, Dan Piponi and others about a mysterious, yet curiously useful function: the `loeb` function: ``` haskell loeb :: Functor f = f (f a - a) - f a ``` The type of this function models a logical proposition by ___ Loeb, which states ___. Most explanations of one use of function involves an analogy about spreadsheets, but this never clicked for me, until I realized that something else I use often is actually a loeb function in disguise. So I wanted to share my alternate insight, in case it might offer clarify for others. But first, the loeb function can be stated plainly as: Given a list of functor algebras (i.e., evaluators), produce a list of pending evaluations. These pending evaluations, when forced, take that same list of pending evaulations as input, and evaluate recursively until a result is produced. There are some immediate consequences of this: 1. Self-referencing elements (unless they are themselves lazy) will result in non-termination. 2. If any evaluation terminates, the total set of evaluations performed will describe a directed, acyclic graph. 3. Only those elements required to satisfy the evaulation of the requested element (and so on, recursively) are evaluated. The place where I encounter this every day is when I use the Nix package manager. Consider: Nix is a purely functional language that defines a system's package set as a mapping of names to values, which describe each package. Those values are lazy (that is, left unevaluated until forced), and many of them are functions which take as input that same, entire package set. When you ask to install a package, Nix needs to know is what build actions to perform, so it forces evaluation of the package's function to determine the source URL, build scripts, etc. That package almost always has dependencies, which themselves are defined by attributes in that same, global package set. Since these may need to be installed too, Nix forces their evaluation and performs the same install step, recursively, until it works it way through the dependency graph, and finally is able to install the top-level dependencies that you initially asked for. This process of dependency resolution: by evaluating lazy, pure functions from a list of pending evaluations that each take as input the entire list, is precisely the loeb function. Another thing I've noticed about the loeb function is that unless self-references are themselves lazy, the only interesting functors for loeb to act on are those in which the type mapped by the Functor occurs more than once, as with lists. This means that for `Identity`, `Maybe`, the tuple functor, `Reader`, `State`, etc., there is really not much interesting that `loeb` can do. For example: ``` haskell main = print $ take 10 $ runIdentity $ loeb (Identity ((1 :) . runIdentity)) ``` This is just a fancy way of writing the `cycle` function. The innermost function, when evaluated, is passed an `Identity` value that contains itself, so all it can do is lazily build some value that ties the knot. You would think functions might provide an interesting `loeb`: ``` haskell f_loeb :: (e - (e - a) - a) - e - a f_loeb f x = f x g where g y = f y g ``` But this is just `fix . flip`: ``` :t fix . flip fix . flip :: (a - (a - c) - c) - a - c ``` What if we move to `Comonad`? ``` haskell w_loeb :: Comonad w = w (w a - a) - w a w_loeb w = fix (flip extend w . flip extract) ``` This seems to be not much more useful than plain loeb, except that now we're forced to use something which contains at least a single evaluator: ``` haskell import Control.Comonad import Data.List.NonEmpty as NE w_loeb ( (\xs - NE.length xs) :| [ (\xs - xs NE.!! 0) , (\xs - xs NE.!! 1 + 3) ] ) -- prints: 3 :| [3,6] ``` ## An ordering-independent parser Another way that loeb could be used is to parse a language syntax where declarations are ordering independent, such as Haskell. Instead of parsing each construct into its AST, parse the definitions into pending AST reductions, and then use loeb to reduce it to ASTs. This will give you graph reduction on the declarations such that they occur in naturally sorted order if possible. ___ nix-dev mailing list nix-dev@lists.science.uu.nl
Re: [Nix-dev] Writing a Nix evaluator in Haskell
Thanks Vladimír and John for the infos. I've added them to my backlog :) ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
As such, I've started a project call hnix which will implement a parser and evaluator for Nix in Haskell. I have the parser working for simple expressions already (using either Parsec or Trifecta, it works with both). AFAIK Peter Simons has written a parser previously, too. Maybe search in the mailinglist archives to join efforts See here: Subject: Haskell Parser for (subset of) Nix http://article.gmane.org/gmane.linux.distributions.nixos/10538/match=nix+parser+haskell My first goal is a syntax verification vim-addon-nix has been using it for ages: nix-instantiate --parse-only foo.nix does a syntax-check You may want to use it till your alternative is ready. Comparing with an Haskell implementation would be fun for many reasons, using multiple cores for instance. Marc Weber ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
Wow John you weren't kidding just a few hours ago. Good luck with the project, was hoping to see a Quickcheck tests directory. Aloha, RK. On Sun, Jun 29, 2014 at 10:03 AM, John Wiegley jo...@newartisans.com wrote: Since the Nix language is such a nice and simple pure functional language, I thought it would be nice to have tooling support for it in Haskell, to aid writing lint utilities, etc. As such, I've started a project call hnix which will implement a parser and evaluator for Nix in Haskell. I have the parser working for simple expressions already (using either Parsec or Trifecta, it works with both). My first goal is a syntax verification and linting tool; after that to see I want to see if I can get an evaluator working for Nix programs. I have a strong feeling that a Nix evaluator can be modeled very simply as a loeb function over memoized IO actions, which is a theory I want to explore in this code. http://github.com/jwiegley/hnix John ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
On 29/06/14 01:03, John Wiegley wrote: Since the Nix language is such a nice and simple pure functional language, I thought it would be nice to have tooling support for it in Haskell, to aid writing lint utilities, etc. As such, I've started a project call hnix which will implement a parser and evaluator for Nix in Haskell. I have the parser working for simple expressions already (using either Parsec or Trifecta, it works with both). Weird, I started exactly this project yesterday! I was using uu-parsinglib, but yours is much further ahead than mine, so I'll ditch it and try and switch over to yours. My first goal is a syntax verification and linting tool; after that to see I want to see if I can get an evaluator working for Nix programs. My goal is not really parsing though, but building Nix files by working with an AST rather than gluing a bunch of Strings together. Keep up the good work! - ocharles signature.asc Description: OpenPGP digital signature ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
Re: [Nix-dev] Writing a Nix evaluator in Haskell
Hah, I also started to write a parser for nix expressions as an exercise! But now that there is already a parser, I'll probably just use yours. -- Benno 2014-06-29 16:37 GMT+02:00 Oliver Charles ol...@ocharles.org.uk: On 29/06/14 01:03, John Wiegley wrote: Since the Nix language is such a nice and simple pure functional language, I thought it would be nice to have tooling support for it in Haskell, to aid writing lint utilities, etc. As such, I've started a project call hnix which will implement a parser and evaluator for Nix in Haskell. I have the parser working for simple expressions already (using either Parsec or Trifecta, it works with both). Weird, I started exactly this project yesterday! I was using uu-parsinglib, but yours is much further ahead than mine, so I'll ditch it and try and switch over to yours. My first goal is a syntax verification and linting tool; after that to see I want to see if I can get an evaluator working for Nix programs. My goal is not really parsing though, but building Nix files by working with an AST rather than gluing a bunch of Strings together. Keep up the good work! - ocharles ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
[Nix-dev] Writing a Nix evaluator in Haskell
Since the Nix language is such a nice and simple pure functional language, I thought it would be nice to have tooling support for it in Haskell, to aid writing lint utilities, etc. As such, I've started a project call hnix which will implement a parser and evaluator for Nix in Haskell. I have the parser working for simple expressions already (using either Parsec or Trifecta, it works with both). My first goal is a syntax verification and linting tool; after that to see I want to see if I can get an evaluator working for Nix programs. I have a strong feeling that a Nix evaluator can be modeled very simply as a loeb function over memoized IO actions, which is a theory I want to explore in this code. http://github.com/jwiegley/hnix John ___ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev
