Regiux

Fork

* Milestones
  - Lexer complete
  - Parser complete
  * Parser parses one *.nix file in this repo
  * Parser parses all *.nix files in this repo
  * Evaluator is lazy
  * Builtins are set up
  * ...
  * Evaluator can load this flake
  * ...
  * Evaluator can load nixpkgs
  * ...
  * Evaluator can load nixpkgs faster than CppNix
  * ...
  * Evaluator can emit derivations from nixpkgs
  * ...
  * Evaluator can emit derivations from nixpkgs faster than CppNix
* Lexer & Parser
  * Gonna just transliterate from yacc/bison to rply
    * Going great! Many regexes can be reused as-is
    * Some semantic actions are copied, like str->int
    * Some semantic actions are optimizations!
  * Parser bugs/incompatibilities
    * I am *not* implementing the `or` hack
      * Might need to revisit this in order to parse nixpkgs
    * Attrsets don't parse correctly
      * There's conflicts between binds and formals
      * When we see '{' ID ...
        * Is this a bind (attrset) or formal (lambda)?
* Parser AST
  * Gonna use the recipe developed in cammy-sampler, bf
    * AST nodes are instances of subclasses of BaseBox
    * Any katamorphisms on ASTs are given as methods
  * Optimizations? Consider Frances' list:
    * CSE
      * Basically shouldn't ever happen
    * DCE
      * Beta reduction
      * Shouldn't be common
    * Strength reduction
      * CppNix desugaring examples
        * Recognize multi-arg apps
          * Good idea, very common in library code
          * Long-standing CAM/STG lore: don't build intermediate thunks when
            doing immediate calls with multiple args
        * Builtins
          * Negation: -x => builtins.sub 0 x
        * Scalar comparison: x > y => y < x, x >= y => !(x < y), etc.
        * Attrset bindings
      * My ideas
        * Eliminate `with`
          * Motivation: It was bugging somebody (Irenes? Xe? Infinisil?)
          * with ns; [ x y ]
            * Key observation: scope is statically known *around* `with`
            * Suppose x is in scope, y is not
            * => [ (ns.x or x) ns.y ]
* Evaluation
  * Will need to transform parser AST to something lower-level
    * The ancient question: AST or bytecode?
  * How to be lazy?
    * Graph reduction?
      * Bytecode might be a good fit here! Push-enter, etc.
  * How to builtins?
    * Either set up a special instruction for them or add `builtins` to scope
      * Probably the latter, given that `builtins.derivation` is actually Nix code
        * This is the case in both Nix and Tvix
* Store operations
  * Might not be our problem at first
    * Because if we can emit derivations, then the system daemon can take over?
    * But will be an issue later
    * Would need to parse ATerms or JSON
  * Need to bind SQLite?
* Builtins
  * We'll need to be ad-hoc; some are easy and some are big integration tasks
  * Any guiding principles?
    * I don't want to bind libraries with FFI, but it may be easier overall
    * I want to reuse *somebody's* work where possible
      * e.g. JSON and XML parsing support could be borrowed from PyPy?
  * Tracking progress? We already have a non-trivial fraction
* Looking forward
  * Recursive evaluation
    * Recursive Nix?
    * IFD?
  * Better reporting of syntax errors
  * Better reporting of simple type errors
    * Can print short/small values
  * Benchmarks
    * https://github.com/infinisil/nixlisp