Coder Social home page Coder Social logo

sfsl's People

Contributors

roldak avatar

Stargazers

 avatar

Watchers

 avatar  avatar

sfsl's Issues

Typechecking is slow with type erasure

Substituing the type parameters is slow

This code :

    type Box = [T] => class {
        value: T;
    }
    type Pair = [A, B] => class {
        first: A;
        second: B;
    }
    def main() => {
        x: Box[Pair[int, Box[Pair[Box[Pair[int, Box[Pair[Box[Pair[int, Box[Pair[Box[int], int]]]], int]]]], int]]]];
        x.value.second.value.first.value.second.value.first.value.second.value.first.value;
        x.value.second.value.first.value.second.value.first.value.second.value.first.value;
        x.value.second.value.first.value.second.value.first.value.second.value.first.value;
        // ... (300 times)
    }

Takes approximately 0.05 seconds to compile (debug mode).

About names of data structures or functions

Even though classes, functions and type constructor are created in an anonymous way, it would be nice to be able to attach them a name (not explicily done by the user but by the compiler). For now :

type T = class {}
def main() => {
    x: T;
}

Here, x's type name is " < anonymous > ". This can be worked around by doing :

type T = class T {}

But this is redundant, so the compiler should be able to infer the name of the class in this case.
Also, in the above code, "main" refers to the function () => { x: T; }, but the function itself has no name, which is problematic for displaying error messages. In this case, the compiler should also be able to infer the name of this function.
The same applies for type constructors.

Add traits

And make classes able to inherit from multiple traits :

type Drawable = trait {
    def draw()->unit
}
type Surface = trait {
    def area()->int
}

type Box = class : Drawable, Surface { ... }

Substitution is not applicable if the returned type of the function is inferred

In this code :

    type Box = [T] => class Box {
        x: T;
    }

    type Buildable = [F[K], T] => class Buildable {
        def builder() => {
            x: F[T];
            x;
        }
    }

    def main() => {
        b: Buildable[Box, int];
        b.builder();
    }

The returned type of main is inferred to F[K => T] while it should have been inferred to Box[T => int]. The reason is that in builder, the statement x; will result in applying the current environment to the ConstructorApplyType of x. Instead, the environment should be applied at the b.builder() call.

Need to restart from scratch typechecking

The current system is too complex to debug / reason about when type constructors are involved.

What needs to be done:

Step 1 : TypeParametrizable objects

Before Typechecking, assign to every TypeParametrizable objects (classes, traits (soon™), type constructors but also functions) which type parameters they each depend on. For example:

type A[T] =>                // Type Constructor A depends on T
        [] =>               // Anonymous Type Constructor depends on T
            class {         // Anonymous Class depends no T

    _val: class {           // Anonymous Class depends on T
        f: T;
        s: int;
    }

    def f[U]() => {         // Function f depends on T and U
        x: class {          // Anonymous Class depends on T and U
            a: T;
            b: U;
        }
    }

    def g[K]() => {}        // Function g depends on K          
}

Step 2 : Modify the Type interface

Each type (already) has its own subsitution table, describing by what types are the type parameters this type depends on instantiated by. What needs to be clarified is when do we "apply" the substitutions. Example of process:

type Buildable[Col: *->*, T: *] => class {
    def builder()->Builder[Col, T]
}

type Builder[Col: *->*, T: *] => class {
    def append(x: T)->unit
    def get()->Col[T]
}

type List[T] => class : Buildable[List, T] { }

def main1() => {
    x: Buildable[List, int];
    x                       // TCA(TCT(Buildable), [TCT(List), PT(int)])
    x.                      // PT(Buildable, {TCT(Col) => TCT(List), PT(T) => PT(int)})
    x.builder               // MT([], TCA(TCT(Builder), [TCT(List), PT(int)]))
    x.builder()             // TCA(TCT(Builder), [TCT(List), PT(int)])
    x.builder().            // PT(Builder, {TCT(Col) => TCT(List), PT(T) => TP(int)})
    x.builder().append      // MT([PT(int)], unit)
    x.builder().get         // MT([], TCA(TCT(List), [TP(int)])
}

As you can see, the subsitutions/type constructor call are applied only when the type is used.
x has type TCA(TCT(Buildable), [TCT(List), PT(int)]) and when you need something from x, if will be evaluated to PT(Buildable, {TCT(Col) => TCT(List), PT(T) => PT(int)}). The usage will be trigger by the followings (non-exhaustive):

  • Member Acess (x.)
  • Function Call (x())
  • Subtype Check (if condition..., here we need to get the real type of condition before trying to check whether it is a subtype of bool or not)
  • etc.

To implement this step, the type interface should be modified to have (at least) two methods:

  • substitute: Type* Type::substitute(const SubstitutionTable& table) const;
  • apply: Type* Type::apply(Comp_Ptr& ctx) const;

What has been done:

  • Step 1: TypeParametrizable objects
  • Step 2: Modify the Type interface

Current design is incompatible with higher order type constructors

The reason is that type constructor calls are applied directly. For example :

type Apply[F[K /*(will be removed later)*/], T] => F[T]

Here, F[T] is applied directly when the Typechecker visits this node, which means that the type constructor will never get substitued by the one passed to apply when invoked.

Bug in typechecking function calls where the return type is already applied

Introduced by 0bcb727 (nice commit message...)

Source:

module sfsl {
    module lang {
        type unit = class {}
        type bool = class {}
        type byte = class {}
        type int  = class {}
        type real = class {}
    }
}

module progam {
    type unit = sfsl.lang.unit
    type bool = sfsl.lang.bool
    type byte = sfsl.lang.byte
    type int  = sfsl.lang.int
    type real = sfsl.lang.real

    type Iterable[T] => class {
        def iterator() => x: Iterator[T]
    }

    type Iterator[T] => class {
        def hasNext() => x: bool
        def next() => x: T
    }

    type Buildable[Col: *->*, T: *] => class : Iterable[T] {
        def builder() => x: Builder[Col, T]

        def map(f: T->T) => {
            b: Builder[Col, T] = builder();
            it: Iterator[T] = iterator();
            if it.hasNext() {
                b.append(f(it.next()));
            }
            b.get();
        }
    }

    type Builder[Col: *->*, T: *] => class {
        def append(x: T) => ()
        def get() => x: Col[T]
    }

    type List[T] => class : Buildable[List, T] {
        redef iterator() => x: ListIterator[T]
        redef builder() => x: ListBuilder[T]
        def push(x: T) => ()
    }

    type ListIterator[T] => class : Iterator[T] {

    }

    type ListBuilder[T] => class : Builder[List, T] {
        inner: List[T];
        redef append(x: T) => inner.push(x)
        redef get() => inner
    }

    def main() => {
        x: List[int];   
        x.map((x: int) => 2).map((x: int) => 3).push(4);
    }
}

Add the `using` keyword

The block in which the keyword (followed by a module path) is used will be able to loop up symbols in the "used" module in addition to the default behavior which is to loop up inside itself and optionnally its parents. However, it should not loop up in the parent scopes of the "used" module:

module sfsl {
    module lang {
        type unit = class {}
        type bool = class {}
        type byte = class {}
        type int  = class {}
        type real = class {}
        type string = class {}
    }
}

module math {
    using sfsl.lang;

    extern def sin: real->real
    extern def sin: int->int
}

module program {
    using math;

    def main() => {
        x: real; // Illegal: Need sfsl.lang.real (for example "using sfsl.lang;");
        sin(x);
    }
}

Add sum types

For now, only product types are available :

type P = class {
    a: A;
    b: B;
}

It would be cool to have sum types too, something along the lines of :

type S = union {
    A, B
}

Then :

  • A or B can be substitutes of S.
  • Pattern matching on unions.
  • If A and B both extend a common interface, the union can be thought as extening the interface => A and B extending I (containing an method f), it is possible to do : def foo(x: S) => x.f()

Type inference for local variables

Right now, the programmer has to write variable declarations like this:

def f() => {
    x: int = 2;
}

The int should be inferred so that it is possible to simply write:

def f() => {
    x := 2;
}

Overloading

Currently, definitions and type definitions cannot be overloaded. Ideally, it would be legal to write something like this :

def f(x: int) => {...}
def f(x: Array[int]) => {...}
def f(x: int, y: real) => {...}

and

type Func[R] => class {...}
type Func[A1, R] => class {...}
type Func[A1, A2, R] => class {...}

The problems is that name analysis will have to be reworked, and be in some way combined with typechecking, since f(args) for example could refer to one of two functions, but we can't now at name analysis time since the type of the arguments is not yet known.

Design a higher level API for programmers using the compiler

Example usage:

#include "sfsl.h"

using namespace sfsl;

int main() {
    CompilerConfig config;
    config.reporter = new MyReporter(...);

    Compiler cmp(config);
    ProgramDefinition progdef = cmp.parse(src);
    Module lang = progdef.openModule("sfsl").openModule("lang");

    ClassBuilder classBuilder = cmp.buildClass("vec2")
        .addField("x", "T")
        .addField("x", "T");

    MethodSymbol vec2Constr = classBuilder.addConstructor({"T", "T"});
    MethodSymbol vec2Print = classBuilder.addMethod("print", {}, "vec2[T]");

    TypeConstructorBuilder tcBuilder = cmp.buildTypeConstructor("vec2")
        .addParameter("T", "*")
        .setBody(classBuilder.build());

    lang.defineType("vec2", tcBuilder.build());

    vm::Program prog = cmp.compile(progdef);
    vm::VirtualMachine vm(prog);

    vm::SymbolLocation printLoc = vm.find(vec2Print);

    vm.link(vec2Constr, [=](sfvm::RuntimeCtx& ctx, vm::Value self, vm::Value* args) {
        // set fields of `self` (this) ...
        ctx.callMethod(printLoc, self, args);
    });

    vm.link(vec2Print, [](sfvm::RuntimeCtx& ctx, vm::Value self, vm::Value* args) {
        // std::cout << ...
        return self;
    }
}

Subtyping

As of now, the only way type A can be a subtype of type B is if A = B. Need to change that and take into account inheritance, etc.

Allow setting bounds on type parameters

Default bound would be Any
But the bound can be specified :

type Tree = [T < Comparable[T]] => class { 
    def foo(...) => {
        if (x < left) { // is legal
            ...
        }
        ...
    }
}

Fix type constructor syntax

Right now :

type Apply = [F[A /*useless*/], B] => ...

Goal :

type Apply = [F: [*]->*, B: *] => ...

Which could be simplified to :

type Apply = [F: [*]->*, B] => ...

So that you don't have to specify the kind of a type parameter if the kind is a proper type :

type List = [T] => class ... 

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.