Giter Club home page Giter Club logo

butter's Introduction

Currently in hiatus

Butter

Documents | Contributing Guidelines

A tasty language for building efficient software.

Note: Still work in progress and experimental. Contributions are welcome.

A small taste

-- reverses an array in place
reverse(mut arr) => {
    len = arr^.len;
    for i in [0.< len // 2] {
        mut elem = &arr^[i];
        mut opposite = &arr^[len - i - 1];
        elem^, opposite^ <- >opposite^, >elem^;
    }
}

Goals

Butter is a personal and experimental language that seeks balance for these aspects:

Note: Being an experimental language, these are all subject to change

  • Concise: The language constructs should be simple and have a feel of scripting language.
  • Explicit: There should be little-to-no vagueness syntax-wise nor semantic-wise.
  • High-level: Low-level concepts that are hard to understand should be abstracted.
  • Efficient: The added runtime code for compiled programs should be minimal both in size and runtime impact.
  • Correct: Detectable errors should be caught on compile-time.

I also to want to experiment with novel features deemed necessary for these goals such refinement types.

Being my personal project, designs and features are ultimately up for my decision and taste. Some features can help with some aspect while also hurt other, this is where I weigh in the pros and cons. Of course, this doesn't mean I won't listen to suggestions, I can be naive on these decisions, I'll be happy to hear your thoughts about Butter's design by opening an issue.

Road map

A road map for the Butter programming language, depicted in the form style a retro video game map. A single road snakes from right-to-left, with multiple stops, ending with a causeway leading to a castle in the middle of a lake. A flag is placed on the first stop. The project mascot (a cute yellow bear) is at the second stop and exclaims "Let's Go!". The stops on the road are: parser, Hindley-Milner with row polymorphism, IR, lifetime analysis, refinement types, and finally LLVM. An enormous dragon looms behind the castle.

More details

Planned features

Note: These are subject to change

Features to be implemented

  • Hindley-Milner type inference and checking
  • Structural typing with row polymorphism
  • Mix of ownership systems and automatic reference counting — data that are immutable and never moved are shareable, otherwise they are owned
  • Reference types with "no shared mutable" rule
  • Mutability/Shareability polymorphism of references
  • Lifetime inference and analysis
  • Refinement types

Features to be implemented later on

  • Type annotation and type aliases
  • Traits or type classes
  • Module and visibility system
  • newtype for nominally typed record types
  • Shareable and interiorly mutable containers — this is an escape hatch for "no shared mutable" rule of reference types
  • Low-level representation heuristics — as an example, the compiler will try to infer if such array can be just a stack array or if it needs to be allocated on heap. Refinement type is used to check if such array exceeds certain capacity

butter's People

Contributors

brendanzab avatar dependabot[bot] avatar neverrare avatar vain0x avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar

butter's Issues

Type inference

Expressions

  • Regular array
  • Range array
  • Len
  • Concat
  • Index
  • Slice
  • Boolean literal
  • Logical operator
    • !
    • |
    • ||
    • &
    • &&
  • Clone
  • Function expression
  • Function call
  • Move operator
  • Integer literal
  • Float literal
  • Arithmetic operator
    • Prefix -
    • +
    • -
    • *
    • /
    • //
    • %
  • Comparison operator
    • ==
    • !=
    • <
    • >
    • <=
    • >=
  • Tuple
  • Record
  • Field Access
  • Tagged expression
  • Variable
  • Reference
  • Deref
  • Break
  • Continue
  • Return
  • Block
  • If
  • For
  • While
  • Loop
  • Match
  • Assignment

Statements

  • Variable declaration
  • Function declaration
  • Expression statement

Pattern

  • Number
  • Boolean
  • Ignore
  • Variable
  • Array
  • Record
  • Tuple
  • Tagged variant
  • Reference
  • Function parameter

Reduce stack frame size for parser functions

As found out in #14, the parser functions have huge stack frame size that causes stack overflow too early even for parsing codes that isn't deeply nested.

This may also be an opportunity to refactor the parser codes.


Update: With handful of guess-works without actually measuring stack usage, I found out that building in release mode helps significantly. It seems like majority of stack values are debug stuffs. Even better, using Linux (I'm using Alpine WSL) instead of Windows also help even in debug mode. Thus, this seems like a Windows issue (MSVC issue?). Nevertheless, this still hints memory issue within the parser and could annoy contributors using Windows, so it is still better to address this issue, but this wouldn't be prioritized.

WebAssembly

Does the compiler run on WebAssembly (wasm)? Is such feature planned?

Typed hir pretty printer

This is necessary for testing out type inference/checking especially for complex codes. We already have REPL which outputs type for given expression but this wasn't enough, it can only handle a subset of code. So we need typed hir printer. It must be pretty!

Implement Parser

  • Comment

Statements

  • Function declaration
  • Parallel Assignment
  • Expression Statement
  • Variable Declaration

Expressions

  • Regular array
  • Range array
  • Concat
  • Indexing
  • Slice
  • Boolean literal
  • And
  • Or
  • Lazy And
  • Lazy Or
  • Not
  • Clone
  • Block
  • If
  • For
  • While
  • Loop
  • Break
  • Continue
  • Function expression
  • Group
  • Return
  • Function call
  • Null literal
  • Null coalesce
  • Optional Field Access
  • Optional indexing
  • Optional slice
  • Integer literal
  • Float literal
  • Addition
  • Subtraction
  • Division
  • Floor Division
  • Modulo
  • Unary Plus
  • Unary Minus
  • Equal
  • Not equal
  • Greater than
  • Less than
  • Greater than or equal
  • Less than or equal
  • Reference
  • String literal
  • Char literal
  • Struct
  • Field Access
  • Variable
  • Assignment

Unpack (Pattern)

  • Variable
  • Ignore _
  • Array
  • Struct
  • Group

Re-enable record call parser

Record call syntax, more specifically function calls with named arguments (e.g. fun(arg = 10)), is currently disabled due to a bug where the parser would stack overflow when parsing certain codes: tuple with splat (e.g. (10, *(20,))) and record with splat (e.g. (a = 10, *(b = 20))).

This bug is hard to debug, at least for myself. Desperately, I tried to disable some part of the parser and found out by doing so to some extent would "fix" the bug at the expense that some syntax wouldn't be supported for now. I found out that disabling record call is the most minimum I could disable to "fix" this bug.

The problem doesn't make sense for me, nevertheless I'll continue to develop other parts of butter such as type inference. I tried to fix this problem without disabling some part of the parser (which also doesn't make sense for me) but it wasn't fruitful and haven't come to conclusion for some time.

If you like to tackle this issue (how courageous of you), please be wary that this issue isn't approachable for contributors due to factors such as the parser is quite complex and there isn't a clear instruction for reproducing this bug. I'm sorry for that, I'll work on it with the following todo list.

todo for myself:

  • make parser more approachable for contributor (this method could be my own rubber duck)
  • make an instruction for testing and reproducing this bug

Steps to reproduce this bug

  1. Obtain a local clone of Butter and install Cargo.

  2. Open parser/src/expr/infix.rs in the text editor of your choice. There, you'll see the following code along with the line number. The code may recently be updated and the line number may not match, just use it as a reference.

    105 // #14
    106 tuple().map(PartialAst::TupleCall),
    107
    108 // attempt(tuple()).map(PartialAst::TupleCall),
    109 // super::record::record().map(PartialAst::RecordCall),

    Put the line 106 in comment then uncomment the line 108 and 109, this will re-enable the record call parser and the bug.

  3. Run the command cargo run -- parser-repl, this will start the parser REPL after the compilation is done, then enter either (10, *(20,)) or (a = 10, *(b = 20)).

This is expected to parse correctly and output the ast, but instead, the parser stack overflows.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.