cdfa / frugel Goto Github PK

View Code? Open in Web Editor NEW

17.0 1.0 3.0 4.82 MB

An error-tolerant live programming environment (my Master's thesis)

License: GNU General Public License v3.0

Haskell 93.88% Nix 5.45% Dhall 0.12% HTML 0.10% CSS 0.44%

frugel's Introduction

Frugel: an error tolerant live programming environment

Frugel is an error tolerant live programming environment. With this we mean:

In contrast to traditional IDEs, language services keep functioning in the presence of errors. Most remarkably, any program can be interpreted to obtain (partial) runtime information, but the editor is not more restrictive in the programs it allows than standard text editors.
This programming environment supports live programming. The programmer is provided with continuous feedback on a focused part of the program behaviour.

With this combination, programmers can easily observe up-to-date dynamic context around errors, which is valuable for debugging and verification and generally "fuses" the edit-compile-run cycle.

To do this, the environment uses "construction sites" to isolate errors. See my master's thesis for more details.

At the moment, I do not have the time and energy to develop this prototype further. Please create an issue or pick an existing one if you would like to contribute.

Installation

Visit https://cdfa.github.io/frugel/ to try it out online, or download one of the native binaries (Recommended due to bad performance of the web version).

Regarding package managers, stack install and cabal install should work out of the box. You can install one of the nix derivations from default.nix with nix-env -f default.nix -iA <derivation>, e.g. nix-env -f default.nix -iA frugel-exe. If you add Frugel's package cache (see "Building"), you can also directly install a static Linux binary with nix-env -i <path>, where the <path> is mentioned in the release notes. Note that older binaries may not be available in the cache.

Usage

A demo video and a presentation can be found on the Internet Archive. The demo video shows the features of the programming environment in action with some examples. The presentation gives an overview of the design and motivations.

Building

You can build the programming environment with either stack, cabal or nix. Building with cabal has only been tested on Windows and the stack configuration was only tested on OSX. Nix is the only supported system for building the web-version and may provide better reproducibility than cabal or stack.

Nix

I recommend adding Frugel's package cache to you nix configuration with cachix use frugel. Building was tested with nix version 2.3.16. Build native executables for Linux (musl64) with nix-build -A frugel-static. The web version can be built with nix-build -A frugel-web. Building the web version may take more than 16GB of RAM. Part of this may be swapped.

Stack

stack build

Cabal

cabal build

Contributing

I recommend using the shell.nix environment when working on this project. It includes several tools and git hooks. I will try to provide complete documentation of the development environment on my machine soon.

The current implementation of evaluation is a bit of a mess (abuse of the ExprMeta fields), since I was in a rush to finish it. A less confusing version that implements some core functionality can be found in scout-src/BasicEvaluation.hs.

frugel's People

Contributors

Stargazers

Watchers

Forkers

jryans yairchu sureshajjagit

frugel's Issues

Build instructions

I saw that there is a stack.yaml file so I tried stack build, but it failed:

% stack build

Error: While constructing the build plan, the following exceptions were encountered:

In the dependencies for frugel-0.0.2.0:
    Interpolation needed, but the stack configuration has no specified version  (latest matching version is 0.3.0)
    QuickCheck needed, but the stack configuration has no specified version  (latest matching version is 2.14.2)
    aeson needed, but the stack configuration has no specified version  (latest matching version is 2.0.2.0)
    base-noprelude must match >=4.7 && <5, but the stack configuration has no specified version  (latest matching
                   version is 4.13.0.0)
    composition needed, but the stack configuration has no specified version  (latest matching version is 1.0.2.2)
    dictionary-sharing needed, but the stack configuration has no specified version  (latest matching version
                       is 0.1.0.0)
    generic-data must match >=0.8.0.0 && <0.9, but the stack configuration has no specified version  (latest matching
                 version is 0.8.3.0)
    genvalidity needed, but the stack configuration has no specified version  (latest matching version is 1.0.0.0)
    genvalidity-containers needed, but the stack configuration has no specified version  (latest matching version
                           is 1.0.0.0)
    genvalidity-text needed, but the stack configuration has no specified version  (latest matching version
                     is 1.0.0.0)
    indexed-profunctors needed, but the stack configuration has no specified version  (latest matching version
                        is 0.1.1)
    it-has needed, but the stack configuration has no specified version  (latest matching version is 0.2.0.0)
    jsaddle must match >=0.9.8 && <0.10, but the stack configuration has no specified version  (latest matching
            version is 0.9.8.0)
    jsaddle-warp must match ==0.9.*, but the stack configuration has no specified version  (latest matching version
                 is 0.9.8.0)
    lens needed, but the stack configuration has no specified version  (latest matching version is 5.1)
    megaparsec must match >=9.0.1 && <9.1, but the stack configuration has no specified version  (latest matching
               version is 9.0.1)
    miso must match >=1.8.0.0 && <1.9, but the stack configuration has no specified version  (latest matching version
         is 1.8.0.0)
    multiset needed, but the stack configuration has no specified version  (latest matching version is 0.3.4.3)
    optics must match ==0.4.*, but the stack configuration has no specified version  (latest matching version is 0.4)
    optics-core must match ==0.4.*, but the stack configuration has no specified version  (latest matching version
                is 0.4)
    optics-vl must match >=0.2.1 && <0.3, but the stack configuration has no specified version  (latest matching
              version is 0.2.1)
    parser-combinators needed, but the stack configuration has no specified version  (latest matching version
                       is 1.3.0)
    pretty-show needed, but the stack configuration has no specified version  (latest matching version is 1.10)
    prettyprinter must match >=1.7.0 && <1.8, but the stack configuration has no specified version  (latest matching
                  version is 1.7.1)
    profunctors needed, but the stack configuration has no specified version  (latest matching version is 5.6.2)
    relude must match >=1.0.0.0, but the stack configuration has no specified version  (latest matching version
           is 1.0.0.1)
    size-based needed, but the stack configuration has no specified version  (latest matching version is 0.1.2.0)
    testing-feat needed, but the stack configuration has no specified version  (latest matching version is 1.1.0.0)
    validity-containers needed, but the stack configuration has no specified version  (latest matching version
                        is 0.5.0.4)
    validity-text needed, but the stack configuration has no specified version  (latest matching version is 0.3.1.2)
    wai-app-static must match >=3.1.7 && <3.2, but the stack configuration has no specified version  (latest matching
                   version is 3.1.7.2)
    warp must match >=3.3.17 && <3.4, but the stack configuration has no specified version  (latest matching version
         is 3.3.18)
    websockets must match >=0.12.7 && <0.13, but the stack configuration has no specified version  (latest matching
               version is 0.12.7.3)
needed since frugel is a build target.

Some different approaches to resolving this:

  * Recommended action: try adding the following to your extra-deps in /Users/yairchu/dev/src/frugel/stack.yaml:

- Interpolation-0.3.0@sha256:b0381214e6036ed2b6a0a04b7e4ec89736ca531ef03e315a3ec2c494059ff8fb,1319
- QuickCheck-2.14.2@sha256:4ce29211223d5e6620ebceba34a3ca9ccf1c10c0cf387d48aea45599222ee5aa,7736
- aeson-2.0.2.0@sha256:5720fffb7289366029f2b7940e9f8b22a1b4c282f0cef4710685b1d14d76bdc7,6327
- base-noprelude-4.13.0.0@sha256:3cccbfda38e1422ca5cc436d58858ba51ff9114d2ed87915a6569be11e4e5a90,6842
- composition-1.0.2.2@sha256:fab25a9386057cdd83094109ac204c8aa7404e19fdfec6708ad383cd3a2d6fe5,659
- dictionary-sharing-0.1.0.0@sha256:6990c4cb6e5c7fd2b3c545576accc2c00a56cdc52ffe646f70680d781893c7d6,788
- generic-data-0.8.3.0@sha256:fef21320697370fa1fadc14f72ac3ad8092b021f5371b315be3c9f3bde44c274,3710
- genvalidity-1.0.0.0@sha256:3fc1b2069ed528e52338ad12a6ee41079bc151f22cc3dc33b5e317c4cd0046b5,2758
- genvalidity-containers-1.0.0.0@sha256:ff0948d748187a2aff2158a3aca8d5245813074deb6209ff44d3e80d38435c55,2230
- genvalidity-text-1.0.0.0@sha256:75e7c5dbb850598f627572698c06f795e896208b082c2c3070301ebf748654a7,1832
- indexed-profunctors-0.1.1@sha256:363e1bcd89f8498a770ae783e8388fcce35e6515b4c38dca47327aad81196a7b,1063
- it-has-0.2.0.0@sha256:e0dfa84dfba835d8616b817305a80878383b8ba7ebe3c9802f33b312e7110d76,1409
- jsaddle-0.9.8.0@sha256:d7acf2247cc93c2d8d0959eccf627077c4175c81b762c8d107c7006dda662d05,4418
- jsaddle-warp-0.9.8.0@sha256:d1c75ae6ab519f923bc8a13775abd779e584bd17c96a49a76f799860bd9174e9,2713
- lens-5.1@sha256:eb01fc4b1cfbad0e94c497eaf7b9f0e9b6c3dc7645c8b4597da7dc9d579f8500,14519
- megaparsec-9.0.1@sha256:2244ab77521a52a0083966c5405b3151f149e1db50b1a5b104cd9b1e56617203,3248
- miso-1.8.0.0@sha256:090e8702d6ffd096e79ea083f5f3293737e3ec44a68b21b8013dc445b92064f0,4339
- multiset-0.3.4.3@sha256:968192524bd38ffa29856e1e3f9f6f8a5704f98899d4b25f8ebd425001594f61,1790
- optics-0.4@sha256:9fb69bf0195b8d8f1f8cd0098000946868b8a3c3ffb51e5b64f79fc600c3eb4c,6568
- optics-core-0.4@sha256:59e04aebca536bd011ae50c781937f45af4c1456af1eb9fb578f9a69eee293cd,4995
- optics-vl-0.2.1@sha256:ccaf2713358c6940294b0979df0246af9a03c1410cd559c0a86f68d9c874462d,1406
- parser-combinators-1.3.0@sha256:edd54ba56cbae8fadbcceebcfef31b2c70a835e92e5eda41151b939c40647281,1570
- pretty-show-1.10@sha256:bfef8da0ac4db4fc7f41edfec9e9a701ac206418d70702bff1e40f20d6a2b1f1,1888
- prettyprinter-1.7.1@sha256:9c43c9d8c3cd9f445596e5a2379574bba87f935a4d1fa41b5407ee3cf4edc743,6987
- profunctors-5.6.2@sha256:3d3685119243a7ebf984fa6af03299d156ab7674a432e2e15ecee2a4fd420fb6,2483
- relude-1.0.0.1@sha256:35bcdaf14018e79f11e712b0e2314c1aac79976f28f4adc179985457493557d5,11569
- size-based-0.1.2.0@sha256:1b33da89d270189661dbbda49a88b0c21d2fc2f7a407e7a2b1933e2faf0f5d4d,1258
- testing-feat-1.1.0.0@sha256:7c7629c5014edf06aefbf30a061d1ee64c6ee15f438d868e34749fb22208ab0b,2466
- validity-containers-0.5.0.4@sha256:b7ae4711646de5f44ef92ce6ae01836bab219ac4f8ebd9a8e05dd073eb0c1d99,1154
- validity-text-0.3.1.2@sha256:37b91c473c148de41703d4a4bfdd9067924dde1ae7258c0d012dcf0404517fff,910
- wai-app-static-3.1.7.2@sha256:ad6b8b07777e6d63f5bf84da2522ac469ff66219a59cdb72baeb69af95e4ffe0,4170
- warp-3.3.18@sha256:e583b66084c7ecfd3f59349aeae72523b90e7887d3523868c6f22fe719172054,10910
- websockets-0.12.7.3@sha256:c4133af18fb420527b30507a69ff20d6819b79f02643051f1ed97aba0468846c,7976

Plan construction failed.

Weird variable disambiguation

Shadowing variables in evaluation results receive weird names, such as "x11" instead of "x2".
We should probably distinguish between original variable name and added numeric suffix in the variable datatype.

Allow recursive where clauses

Change cursor movement to rely on decomposition instead of display projection

Cursor is moved back after writing ... in a construction site

When we use the empty construction site syntax ... in a construction site that contains a syntax error (e.g. (...), the cursor is moved back 3 spaces. This happens because the editor needs to account for the disappearance of the 3 dots when they are replaced by a 0-width empty construction site, but it's erroneously also doing this when the parsing of the construction site with the 3 dots fails.

To fix this, we need to add custom state to the parser that backtracks when a parse fails (as described in the Megaparsec tutorial).

Add API for incremental parsers

Incremental parsers may be able to negate the performance cost of parsing the various linearization variations produced by the linearization step.
However, the current API only allows pure parser functions, while incremental parsers have side effects.

Integration with existing IDEs

Since the structure editor requires a parser for the document language, integration with text-based tools is easier than usual.
An LSP server could work in the background to support other IDE-functions and further program analysis, while the IDE still uses a text-based editor.
However, these text editors usually do not support the display of annotations that overlap in a clear manner, so the annotation of construction sites will not be as clear.
An intermediate solution between standard text editors and structure editors could be a text editor where there are multiple patterns of "red underlining" that can be alternated on a single line where annotations overlap.

Fuel-limited evaluation is slow with high fuel limits and many focused evaluation occurences

The number of focused evaluations is displayed in the panel, which forces evaluation of parts of evaluation results that are not displayed.
The range displayed in the selected evaluation panel should be limited.

Flatten *Meta hierarchy

With either GADT or type family

Add development packages to development environment

E.g. dump and recover-rtti

Using fuel-limited evaluation by default is turned off when render depth is changed

Show extent to which values in selected evaluation are evaluated

Most of the work to support this should already be done because evaluation status of expressions in non-strict positions is already controlled with references.

Migrate to Schpadoinkle?

Less boiler plate for small actions and generally seems to be thought through better than miso.

Sequential 0's not inserted

There is some weird behaviour when multiple 0's are inserted in sequence

Testing

Does shrinking of expressions even work currently?
Test extended linearization-parsing isomorphism: linearize -> parse = linearize -> parse -> linearize -> parse
Responsiveness: programming environment takes at most 100ms to respond to input
Text editor equivalence: insert/delete -> to plain text = to plain text -> insert/delete
Evaluation results are rendered to text correctly (automatic insertion of parentheses): eval -> linearize -> parse = eval
Evaluation results are normal forms: eval = eval (-> remove single node construction sites) -> eval
Evaluation uses call-by-need semantics (test by inspecting output from traces)
traverseComponents laws (see thesis)
Validity of custom lens combinators (in Optics.*.Extra)

Generate parsing and decomposition definitions based on grammar

The grammar is now defined in both the parsing definitions and Decomposable instances. A single source makes changes easier and reduces technical debt.

Nix derivation for native builds with www directory

Formatting style tends to cram to the right

Tried the following example and this is how it got formatted:

primeFactors 0 add 1234567
  where
    add = \x = \y = x + y
    primeFactors = primeFactorsH 2
    primeFactorsH = \bound = \acc = \step = \num = if bound * bound > num
                                                   then step acc num
                                                   else if num % bound == 0
                                                        then primeFactorsH bound
                                                            (step acc bound)
                                                            step (num / bound)
                                                        else primeFactorsH
                                                            (bound + 1) acc step
                                                            num

To me it's hard to read, as if the code is hiding to the right.
I prefer Rust's formatting style where things are more left-leaning and in more consistent locations.
But I know that it is a style choice so if you like this style, I can't argue :)

Btw, can I put a where clause inside a lambda?

More efficient linearization

Currently, the number of linearization variations grows exponentially with the number of construction sites (in the worst case where none are nested).
This could be improved by finding parts of the grammar which naturally isolate syntax errors (and corresponding AST nodes) and only reparsing linearized variations of those parts.

In more detail (probably only comprehensible to me):

Find stoppers by finding loops in the grammar. All parents outside the loop are stoppers.
Partition AST based on isolated loops. This isolates syntax errors and reduces the number of linearizations
Within each partition: decompose nodes on paths to (nested) construction sites instead of linearizing complete partition (combats exponential complexity of variations). Still generate exponential number of variations. This way, we can be conservative with the combination of ambiguity and nested construction sites
Parsing only has to consider partitions

Rework development environment to use stack configuration

Should give us less dependency compatibility issues

Look into whether ghcjs's -dedupe option affects performance

Allow trailing whitespace on all nodes

Currently, the root AST node is decomposed when we perform a syntax-error introducing edit at the end of the program when there is trailing whitespace.
The resulting construction site contains almost the whole program, but it could be limited to the right-most leaf-node in the AST.
This could be achieved by allowing all nodes to have trailing whitespace (in addition to interstitial whitespace).

Evaluation running in the background is aborted when selected runtime value is changed

Add toggle to export application model

So people can add the application state to bug reports

Improve debugging support based on existing work

Starting point here: https://github.com/hazelgrove/stepper-paper/blob/master/main.pdf

Add new expression representations for denotation and partially reified expressions

As described in the thesis. Would be much cleaner than cramming everything into ExprMeta. Implementation with GADTs can be found in scout-src/BasicEvaluation.hs, but a more extensible implementation may be better (e.g. to cleanly separate evaluation things from Node.hs).

Empty construction sites should be rendered in between characters

Empty construction sites contain no characters, so they should be rendered in between character positions

Reduce flickering of listed errors

Change selected evaluation index text to number input + slider

I/O support

Currently, the programming environment does not support languages with I/O, which would be necessary for any real-world language.
Combining I/O with live programming is challenging because running code automatically may cause unintentional or even destructive side effects.
Additionally, I/O actions may block execution indefinitely, which prevents the programming environment from providing runtime information for the whole program (in time).

The first issue is one of safety. Automatic program execution could be made safe by isolating the program from the rest of the system running on the computer using containers (as in Docker). Containers are already widely used for this purpose, so the remaining work is building an interactive system for defining container images based on the program's requirements and integrating this in a development environment.
For prototyping, it would also be nice to be able to approve I/O actions interactively instead of having to modify a container image.

If the runtime environment of the program is brought under control of the programming environment, the performance issue is also solved more easily. Snapshots of intermediate container states could be used to skip the computations and I/O actions that lead up to that state in later executions.