candy-lang/candy

🍭 A sweet, functional programming language that is robust, minimalistic, and expressive.

candy's Issues

Package support breaks candy on Windows

Describe the bug
#390 introduced a bug where the module resolution inside packages fails to detect if a file is located in the package on Windows.

The underlying problem is the platform specific behavior of fs::canonicalize (see the documentation). This function returns a UNC-Path prefixed with \\?\ while package.to_path returns a DOS-Path without the prefix. strip_prefix then returns an error and the compiler thinks the file is not located in the package.

The dunce crate was created to combat this issue, but converting the UNC-path to a URL and back to a file path seems to be a quick workaround.

let canonicalized = Url::from_file_path(canonicalized)
    .expect("Invalid file path.")
    .to_file_path()
    .expect("File path conversion error.");

Smarter stringification of VM values

Track the precedence to avoid superfluous parentheses around a tag's value

Improve memory representation

Ideas:

• inlining of ints/etc.
• reduce size of an object
• heap management

Expand IDE support

Lifecycle Messages

Beta Give feedback

1. Initialize
2. Initialized
3. Register Capability
4. Unregister Capability
5. Set Trace
6. Log Trace
7. Shutdown
8. Exit

Document Synchronization

Beta Give feedback

1. Did Open Text Document
2. Did Change Text Document
3. Will Save Text Document
4. Will Save Document Wait Until
5. Did Save Text Document
6. Did Close Text Document
7. Rename a Text Document
8. Overview - Notebook Document
9. Did Open Notebook Document
10. Did Change Notebook Document
11. Did Save Notebook Document
12. Did Close Notebook Document

Language Features

Beta Give feedback

1. Go to Declaration
2. Go to Definition
3. Go to Type Definition
4. Go to Implementation
5. Find References: #155
6. Prepare Call Hierarchy
7. Call Hierarchy Incoming Calls
8. Call Hierarchy Outgoing Calls
9. Prepare Type Hierarchy
10. Type Hierarchy Super Types
11. Type Hierarchy Sub Types
12. Document Highlight: #155
13. Document Link
14. Document Link Resolve
15. Hover
16. Code Lens
17. Code Lens Refresh
18. Folding Range
19. Selection Range
20. Document Symbols
21. Semantic Tokens
22. Inline Value
23. Inline Value Refresh
24. Inlay Hint
25. Inlay Hint Resolve
26. Inlay Hint Refresh
27. Moniker
28. Completion Proposals
29. Completion Item Resolve
30. Publish Diagnostics
31. Pull Diagnostics
32. Signature Help
33. Code Action
34. Code Action Resolve
35. Document Color
36. Color Presentation
37. Formatting: #371
38. Range Formatting
39. On type Formatting
40. Rename: #417
41. Prepare Rename: #417
42. Linked Editing Range

Workspace Features

Beta Give feedback

1. Workspace Symbols
2. Workspace Symbol Resolve
3. Get Configuration
4. Did Change Configuration
5. Workspace Folders
6. Did Change Workspace Folders
7. Will Create Files
8. Did Create Files
9. Will Rename Files
10. Did Rename Files
11. Will Delete Files
12. Did Delete Files
13. Did Change Watched Files
14. Execute Command
15. Apply Edit

Remove `builtinPrint`

Builtin print should no longer be needed once we have robust stdio and can visualize traces.

Replace occurrences of `Id::complicated_responsibility()`

Pattern Matching

Tasks

Beta Give feedback

1. Destructuring #257
   P: Compiler: Frontend P: Compiler: VS Code Extension P: Core T: Feature +4
   
2. Match #278
   P: Compiler: Frontend T: Feature +2
   
3. Or patterns #280
   P: Compiler P: Compiler: Frontend P: Compiler: Language Server T: Feature +4
   
4. Fix identifiers in or patterns #315
   P: Compiler: Frontend T: Fix +2
5. Support destructuring in lamdba parameters #295
   P: Compiler: Frontend T: Feature +2
   

Support tags in MIR

Allow constant evaluation to create tags in the MIR

The formatter puts comments in functions on the first line, even in multiline functions

Currently, the formatter formats this code:

foo a :=
  # a comment
  bar

into this:

foo a := # a comment
  bar

While that is (not, #485) valid, I think the code shouldn't be formatted.

Support WebAssembly

Support destructuring in lamdba parameters

Support tag values in fuzzer

Tag matching with values

Create packages

Create packages:

Packages

Beta Give feedback

1. stdin/out utilities like a print function
2. FileSystem Package #905
   2 of 5
   Epic P: FileSystem T: Feature +3
3. logging
4. HTTP Package #787
   1 of 3
   Epic P: Http T: Feature +3
5. Markdown
6. custom binary serialization
7. Cap'n Proto
8. Chrono Package #732
   T: Feature +1
   
9. SI?
10. MongoDB?
11. CSV Package #883
    2 of 4
    Epic P: Csv T: Feature +3
12. Wasm VM #984
    T: Feature +1
    
13. Complex Number Package #935
    P: ComplexNumber T: Feature +2
    
14. ANSI Escape Sequences Package #938
    P: AnsiEscapeSequences T: Feature +2
    
15. ASCII Package #968
    P: Ascii T: Feature +2
    

Implement DAP (Debug Adapter Protocol)

Optimize VM Byte Code

Ideas:

Tasks

Beta Give feedback

1. More efficient argument preparation in function call (so we don't have to push references if the evaluation order doesn't change conceptually)
2. Avoid pushes for arguments by referring to them as offsets

Fuzz formatter

• check idempotence: running the formatter on formatted code shouldn't change anything
• check AST equality: the AST of formatted code should be the same as the AST of unformatted code

Tags

Instead of symbols, we want to have tags that can also have an optional associated value. Our current symbols will just be named tags. Tags without an associated value can be called just like functions to associate a value with them.

tagWithoutValue = Foo
tagWithValue = Foo 3
newResult = Ok 4
error = Error "That didn't work."
dynamicallyCreatedTag = tagWithoutValue 5
nestedTag = Foo (Bar 3)

Minimize inputs found through fuzzing

We fuzz Candy functions, but the fuzz cases can sometimes get large. It would be a better developer experience if we simplify them.

Formatter makes pattern match invalid

Currently, the formatter takes this code:

is value := value %
  Ok _ | Error _ -> True
  _ -> False

and turns it into this:

is value := value %
    Ok _ | Error _ -> True
    _ -> False

This code is invalid though.

Multithreading in the VM

Have multiple workers that execute multiple fibers in parallel

Generate debug files (as read-only VS Code views)

Save origins in VM Byte Code more efficiently

For example, in a tree.

Introduce packages and restructure the CLI

Our current CLI is kind of weird – you have to specify a .candy file including the extension and we just assume that the current working directory is the project. I want to look into optimizations (and in particular specifying custom optimization guidance using a scoring function) next.

Just to recap the distinction of packages vs. modules, I believe this is our current definition:

• Modules evaluate to a Candy value. For example, code modules evaluate to a struct containing the exported definitions, asset modules evaluate to a list containing the bytes. Modules are not necessarily self-contained because they can import other modules with use.
• Packages are a subset of modules. They are self-contained, so while modules inside of them can import each other, no relative import can cross the package boundary in either direction. Packages can also contain functionality for publishing them or building a binary.

I thought a bit about how Candy packages could work and how they could interact with our CLI.

What Makes a Package a Package

My proposal on how to distinguishing packages from modules: Packages can only be folders and next to the top-level _.candy file, they must also contain a package.candy file containing information on the package itself. Here's what a minimal package might look like:

foo/
  _.candy
  package.candy

When invoking the CLI, it will look if the current working directory is a package. If it isn't it will walk up the hierarchy and stop either if it finds a package.candy file or it doesn't find a _.candy file indicating a folder is a Candy module.

We probably also want to allow specifying packages that are not the current working directory, e.g. like this: candy --package path/to/package/folder build.

The Package Configuration File

The big remaining question is what the package.candy file contains. This depends on what you can do with the package. Later on, packages can be built into binaries or published for others. For now, the package.candy could contain information on how to optimize the module using a custom scoring function. For example, if we want to tell the MIR optimizer to optimize the Fibonacci program so that the binary executes fibonacci 610 as fast as possible, we might have the following files:

# _.candy

[int, list] = use "Core"

fibonacci n =
  ...

main environment :=
  n = environment.args | list.get 0 | int.parse
  fibonacci n | print

# package.candy (for me, GitHub hides it but you may have to scroll in this code section)

[int] = use "Core"

# Executed when running `candy publish`. The `environment` contains information about the
# dev environment such as the arguments given to the command, environment variables, etc.
publish environment :=
  # Assuming tags are supported, this only publishes the `Fibonacci` export from the
  # `_.candy` file. Alternatively, you can also use `Everything` to publish the entire
  # module. We may want to think about restricting this to export that statically resolve
  # to a struct (so that `use SomePublicPackage` is always a struct), but we could also
  # think about allowing exporting single values.
  [
    Value: Only Fibonacci,
    Name: "MyPackage",
    Description: (use "README.md") | string.parse,
    Version: 3,
    ...
  ]

# Executed when running `candy build`.
build environment :=
  [
    EntryPoint: Main,
    # A custom scoring function where lower scores are better.
    OptimizationScoring: { artifact ->
      int.add
        artifact.numInstructions
        artifact.run Main 610
    },
    Plugins: [
      Stdin,
      Stdout,
      Variables,
      Random,
      HttpsServer,
    ],
    Target: Wasm,
  ]

This way, we can completely customize the build using arguments (thereby replacing things such as Flutter flavors).

Commands

I think we should support these commands:

• candy analyze: Builds the project (maybe up until the HIR?) and reports all errors.
• candy build: Builds the project according to the build function in the package.candy.
• candy run: Builds the project and runs it with the given arguments.

For simple scripts, we may want to allow standalone modules that can be run independently. I'd suggest these are treated similarly to being the sole content of a package with a default build configuration.

candy --file my/Downloads/something.candy run

Because these are self-contained, they can't import any other files – to do that, you have to first create a package.

Running individual functions

Perhaps a bit unrelated, I think it would also be useful to have the ability to run arbitrary functions from the command line.

candy --function examples/fibonacci.candy:fibonacci run 610

Add caching while compile-time evaluating code

Add package manager

Package path dependencies

Does a grammar file 'candy.g' exist???

Hey guys,

I am looking quite excited at your 'new' programming language!

I just wanted to know if you use or have a grammar file for these Candy language? That grammar file could (!) be used to make Candy as an interpreted language as well.

Make Core library more comprehensive

Some ideas:

• io
• random
• timing
• environment variables
• HTTP, UDP

Complain about comment lines with too much indentation

Fix identifiers in or patterns

Propagate source location information to later compiler stages

In the MIR, all information about where functions come from is lost. We should keep that info around – if not for every expression, at least for every closure. This would also enable showing stack traces in code not compiled with tracing.

Add tests

While we do have fuzzing for the Core library, a few simple unit tests would also go a long way for catching obvious bugs.

Compiler: Use faster `HashMap` implementation for Common Subtree Elimination (CSE)

Remove `CombiningExecutionController` in favor of `impl ExecutionController for <Tuples>`

FEATURE: provide candy compiler/lsp server for linux/macosx

Hey guys,

I am quite more excited since the last issue! It`s fantastic that candy got it first release!!!! 👍 YEHA! 👯

I looked into the tools you provided with the first release and noticed that these tools are just for windows. Is it possible to provide these tools for linux and/or macosx in the next releases?

Btw your extension for visual studio code works just as expected, excellent!

Again, thank you very much for you work!

Fix the evaluation order of pipe expression by keeping it in the AST

Currently, foo 0 | (bar 1) first evaluates bar 1, then foo 0, and then calls the result of bar 1 with the result of foo 0. This is because pipes are not preserved in the AST, instead the expression gets lowered to the equivalent of (bar 1) (foo 0).

We should keep pipe expressions in the AST and then fix the AST to HIR lowering so that the above code evaluates foo 0, then bar 1, and then calls the result of bar 1 with the result of foo 0.

Fix renaming in lambda

Describe the bug

main := { _ ->
  foo = 123 # Rename doesn't work
  ✨.print foo # Rename works
}

Fix usage of pipes in indented code

foo
  bar | baz
## Currently, this is parsed as `baz (foo bar)`.

Potential optimizations

Some ideas about optimizations we could implement:

Tasks

Beta Give feedback

1. Compiler: Use faster HashMap implementation for Common Subtree Elimination (CSE) #270
   P: Compiler: Frontend T: Performance +2
   
2. Compiler: Function inlining
3. Compiler: Detect pure functions and deduplicate calls
4. MIR: Use FxHashSet in expression.captured_ids() and body.all_ids()
5. MIR: Remove responsible parameter if function can't panic
6. Optimize VM Byte Code #291
   0 of 2
   Epic P: Compiler: VM T: Feature +3
7. VM: Try deduplicating heap objects in BuiltinFunction::Equals Can break assumptions about ref-counting
8. Create unchecked mode with fewer asserts, etc.
9. Avoid clones in CSE #589
   P: Compiler: Frontend T: Performance +2
   
10. Disable reference counting for constants #583
    P: Compiler: CLI P: Compiler: Fuzzer P: Compiler: Language Server P: Compiler: VM T: Feature T: Performance +6
    
11. Symbol table #590
    P: Compiler: CLI P: Compiler: Formatter P: Compiler: Fuzzer P: Compiler: Language Server P: Compiler: VM T: Feature T: Performance +7
    
12. MIR: Deduplicate symbols
13. LIR: Remove drops after panic
14. MIR: Remove code after panic
15. MIR: Tracing mode to avoid call tracing if call can never panic
16. Inline iterators / recursive calls in generat
17. Remove unnecessary return type checks
18. VM: Inline objects for empty list and struct
19. Compile matches to nested if/elses to aid constant folding
20. InlineObject for non-capturing functions
21. Convert captures to parameters where possible

Visualize traces

Think about and implement visualizing Candy function executions.

Show stack trace when fuzzing

Currently, running candy fuzz doesn't show stack traces because that would cause segfaults. We should fix that.

Code Action ideas

Tasks

Beta Give feedback

1. Order imports alphabetically
2. Order struct keys in import destructuring alphabetically
3. Remove unused identifier
4. Extract common code
5. Extract selected code into variable/function
6. Constant evaluate and replace selected code
7. Inline and maybe const-evaluate dependents of constant value (e.g., to remove feature flag)

Clean up repo

Delete a bunch of files!

Support LLVM

Disallow passing named closures as parameters? Or auto-propagate the fault to the caller?

If functions were responsible for fulfilling the needs of functions given to them as arguments, every higher-order function would have to include a try block or something similar and then re-propagate that responsibility to the caller.

That's why we should establish the rule that inside higher-order functions, you shouldn't have to care about the needs of functions given as parameters. Instead, the caller is responsible for giving you only functions that accept the values that you call them with.

Semantically, this would equate to wrapping functions in closures.

bar a = ...

# A call to higher-order function foo:
foo bar

# Would really be equivalent to this:
foo { a -> bar a }

Parser doesn't parse function with comment on same line

Currently, the parser doesn't parse this code:

is value := # ✨.print "is result?"
  value %
    Ok _ | Error _ -> True
    _ -> False

It complains that value is not defined, so it seems like it stops parsing the function after the first line.

Improve pattern match panic messages

[Foo, 1, {a}] = [Foo, 2, {A: B]] could generate a message like Expected `[_, 1, _]`, got `[_, 2, _]`.

When checking individual cases of a match, we don't want to construct the error messages eagerly. For the vast majority of cases, at least one case will match, so concatenating (and thereby allocating) lots of strings slows down the code by a lot.
Instead, when no case matches, we should revisit all the cases and build a nice error message, detailing why each case doesn't match.

Hi, future me! Past me here :)
For performance, we take out building the error messages when cases don't match. We should revisit this in the future. Our current state where we build error messages for non-matching cases: a68dbb9

Format body with single assignment correctly

Describe the bug

foo =
  bar = 123

Gets formatted to the following, invalid code:

foo = bar = 123

Online playground