snordgren / fjord Goto Github PK
View Code? Open in Web Editor NEWA strict, linearly typed functional programming language that compiles to JS.
A strict, linearly typed functional programming language that compiles to JS.
This is an issue with code generation, where the JavaScript doesn't actually treat the numbers as integers. We need to insert a | 0
after the value whenever an Int
-returning expression is referenced.
Sharing a unique value can be expressed using a function
share : a. b. (&a -> b) -> a -> (a, b)
enum A
B : A
C Int : A
This is the more concise syntax, that doesn't cause issues with having both ->
and -*
. In types without type arguments, the : A
-part should be optional.
Case expressions which do not include patterns for all constructors and do not have a wildcard pattern should be a compile error.
I'd like the a b -> a
syntax to be valid and equivalent to the currently working lambda expression a -> b -> a
.
record Point
x : Int
y : Int
pointX : Point -> Int
pointX p =
p.x
(myRec | x = 1, y = 2) : (MyRec, Int, Int)
zero : forall a. implicit Zero a -> a
zero ev =
ev.zero
The implicit
type is resolved at compile-time. The module wherein Zero
was declared and the module wherein the current value of a
was declared are searched. In other words, only the modules which declare the types which are present in the implicit
declaration are searched for a matching implicit
definition of the appropriate type.
This means that the implicit
value is always either resolved to the same value (instance), or the compiler raises an error.
implicit
intInstance : Zero Int
intInstance =
0
Values that are declared implicit
may not have any parameters.
\n
, \t
, etc should be set to their expected values when encountered in code. Add test case and make sure it passes.
All values except those
frugal : & a -> & (& a, & a)
frugal x =
(x, x)
type Int =
& BuiltInInt
Shared values can be defined using the &
wrapper type. These values must be immutable. A function which uses only shared values can be safely shared, even as a partially applied closure. This has some interactions with field access which requires special care in the compiler, accessing a field on a &
value should return the field as &
too.
Values are implicitly converted to their &
-form when passed. Only lambdas that take only &
values as parameters can be implicitly converted to &
; only tuples whose components are all shared can be shared. Shared enums only provide shared access to their fields, except for function members, which can only be accessed * at all * if their parameters are all shared.
One solution to this issue is to decide that functions cannot be invoked if they are placed in &
and have their own wrapper named something like Pure
to show that the function does not reference any mutable state and can be safely invoked multiple times.
Another possible design is that functions in &
cannot be invoked at all. You'd have to implement callbacks as functions that return a new function every time they are invoked. a -> IO b
would have to be implemented as type Callback m a b = a -> m (b, Callback m a b)
.
Top-level definitions would be implicitly converted to their borrowed counterparts just like some variables, which has implications on type inference. Requiring borrowing to be explicit with a keyword share
would make it easier to write very efficient, resource-aware code, but would also break as top-level definitions are referenced multiple times in one function. You could fix this by requiring that top-level definitions are referenced only once, or by interpreting top-level definitions as "macros" that you mentally inline when they are referenced, lambda-calculus style.
Some types belong to a unique kind, some belong to the regular kind of types. This means that we have to abstract over the type of kind at some points, which might make it difficult to comply with the limitations of the unique kind. And abstracting over kind isn't something I'm too happy about doing.
This is what Haskell uses. A linear arrow a -* b
does not require that a
is unique, it only requires that a
is only used once in the body of the function. This has some disadvantages when it comes to implementation, because it is harder to implement record updates as mutation, because the individual function does not know whether its parameter is
Another weakness of the arrow-based approach is that it's hard to determine the potential linearity of returned values. You might want to return a unique point from a function Int -> Point
, while a -> (a, a)
should be an immutable value.
This is another approach, in some ways a dual to linear arrows: all returned values are unique. -o
functions only take unique arguments and only use them once. All values are unique except those taken as parameters in ->
functions, and those values cannot be returned because ->
functions also have unique returns. Values can go from unique to shared by being passed to a ->
function.
This approach has the issue of deciding what happens to a value after being passed to a ->
function. The unique reference to the value has been lost, which is problematic when dealing with things like file handles which should be unique at all times. One way to fix this is to only allow some types to be passed to ->
functions. Another is to allow mutable access to a value that is borrowed in the same expression, as long as the mutable access happens after the immutable access.
One downside to this approach is that all types, even integers, need to be explicitly dropped. This can be fixed by adding a "magic method" forget
, that, when defined, is automatically inserted. For most types this value should be an alias for drop
, effectively degrading types with forget
to affine.
share : forall a . a -> (forall b . a -> b) -> b
share a f =
f a
illegal : a -* (forall b . a -> b) -> b
illegal a =
drop (share a) a
To avoid use-after-free in the above, add the following restriction: a partially applied ->
may not be unique. There is no way to copy a function, so it is not possible to from non-unique closure to unique closure. Another necessary restriction is that you can't reference a unique value in the body of a ->
function. illlegal
is illegal because share a
is non-unique but drop
requires a unique argument.
So this option becomes "every return is unique except a partially applied ->
", so you sacrifice some consistency for ergonomics.
Use three kinds to support uniqueness typing: T (base type, e.g. Int
, String
), U (uniqueness attribute unique
, non-unique
), and * (the inhabited of the three, meaning it has values, and requires a T and a U).
You might want to abstract over usage.
If you pass a unique value to const
, you can only use that value once. If you pass a non-unique value to const
, you may use the value as often as you want to.
const :: u : a -> u : (b -> a)
Here, u
is a type of kind uniqueness attribute, that is shared by the input and the returned function. This makes sense but I want to be able to share values freely before de-allocating them, and I don't want to force all their usage to be inside a closure.
Below notation is courtesy of edsko.net, with ฯ: swapped to & for typability. One could also remove the 1: and let uniqueness be the default.
drop :: 1:a -> 1:b -> 1:a -- magic
share :: &a -> &(&a -> 1:b) -> 1:b
share a f = f a
illegal :: 1:a -> &(&a -> 1:b) -> 1:b
illegal a =
drop (share a) a
->
takes and returns shared, -*
takes and returns uniqueAny function which takes a unique argument must return a unique result. A partially applied ->
is never unique, which prevents illegal
from being valid. drop
necessarily takes two unique arguments. A ->
cannot reference unique values and cannot invoke a -*
passed as an argument, a -*
can reference non-unique values. This enforces a certain ordering, where ->
must come before -*
.
If value constructors always return unique values, we get the useful distinction that ->
can never allocate memory, on the other hand that severely limits the usefulness of ->
to only accessing the values in its arguments.
Managing stack-allocated values like Int
: a function copy : forall a . Copy a => a -> () -* a
, that the compiler automatically inserts. (+)
receives the type Int -* Int -* Int
and the compiler automatically inserts copy
invocations.
Granule, have a look at that.
As of right now, I think this design space is full of unwanted tradeoffs, which I suppose is why this design has never taken off in any other programming language apart from Rust.
Let bindings should support destructuring of records, with the same syntax as tuples. So let bindings should add a new ADT for the kind of binding it is (single name, multiple destructured names).
posToTuple : Point -* (Int, Int)
let (x, y) = pos in (x, y)
Destructuring a record deallocates it, and returns the unique references to their contents, while accessing a field only gives a shared reference.
Both opaque types and functions should be importable from JS. Opaque types can be declared in a tuple to save space.
foreign "express-fj" (Express, Request, Response)
express : () -> Express
get : String -> (Request -> Response -> (Request, Response)) -> Express -> Express
We define a foreign "block" with a set of types within parentheses, a string noting where the functions belong, and some declarations that are found in the foreign module.
This is a prioritized feature, because I'd like to start writing the Fjord website using Express and use that experience to prioritize feature implementation.
f : Int -> Int
f a b =
a
I need a compiler message to tell me that I have too many arguments in my definition for f
.
A record update whose source expression is another record expression could be reduced to just one record update, concatenating the field updates. This should probably be implemented as part of an optimization step of AST.Typed -> AST.Typed
, called Transform.OptimizeTyped
.
id : a => a -> a -> a
id x = x
swap : a => b => (a, b) -> (b, a)
swap (x, y) = (y, x)
All enum constructors need to return a value with the type or type constructor of the enum.
It's currently not possible to invoke the compiler, but it should be.
Tuples simplify returning multiple values from a function. They should be usable as an HList-type structure, but that lies in the future.
Add new syntax to the parser for recognizing tuples in types and expressions. Then add code generation support for tuples (they should be represented as immutable arrays). Tuples themselves are not mutable (there is no syntax support), but may contain mutable values.
By #26, implement uniqueness typing with unique returns for two arrows -*
and ->
.
Node doesn't support the import and export syntax, which is why dependencies use require
instead. They use the export
syntax, though.
Remove export
prefix, and instead generate an exports.<name> = <name>
declaration under each declaration. Also remove arrow functions and const declarations, because they aren't supported by all browsers.
This is a great feature for writing things like GLSL shaders, that I have used before in JavaScript with WebGL. The include
keyword is suitable for this functionality.
vertexShaderSource : String
vertexShaderSource =
include "../shaders/basic.vert"
The above code should paste the contents of ../shaders/basic.vert
as the value of vertexShaderSource
.
Currently declaration and initialization of variables is separated, but it would be more efficient and the code clearer if they were joined. Change the blockDeclarations
field in Block
to have the type [(String, Type, Maybe Expression])
, where the Maybe Expression
is the optional initializer for the variable.
Today:
var x;
var y;
x = 0;
y = 1;
Wanted:
var x = 0;
var y = 1;
[1, 2, 3] # : Array Int
The Array a
type is the default data structure for sequential data.
These can be created as records with a parameterized type containing the type for AST.Typed and the int offset for AST.Contextual and AST.Resolved. Additionally, name resolution does not require its own AST type, so we can merge AST.Contextual and AST.Resolve and make the resolution phase a AST.Contextual -> AST.Contextual transform.
Also rename the AST.Contextual to AST.Untyped.
Add support for specifying exactly which types, value constructors, and functions should be imported into the module scope.
import MyModule (MyType (MyConstructor), myFunction)
Case expressions are currently compiled to a set of if-statements.
export const maybeToInt = m => (() => {
var target = m;
var tag = (target)[0];
if ((target === $TagNone)) {
return 0;
} else if ((target === $TagSome)) {
var a = (target)[1];
return a;
}
})();
Because it is a statement, it is compiled as an IIFE already, so replacing the if statements with a switch would not reduce performance, instead it would allow the JIT compiler to generate a table switch for O(1) switching. This requires that we have all constructors in our patterns and that they are ordered correctly.
A new test case should be added with a few constructor patterns in a random order, that requires the output JS to have a switch with labels in the correct order.
The above should instead be :
export const maybeToInt = m => (() => {
var target = m;
var tag = (target)[0];
switch (tag) {
case $TagNone: {
return 0;
}
case $TagSome: {
var a = (target)[1];
return a;
}
}
})();
When JS code is generated, a .d.fj
file containing type information should also be generated. This file is the same as the .fj
it is generated from, but includes only types and type signatures.
The compiler should be able to use this information in combination with the .js
file to invoke modules that are not defined in the current project. This mechanism can be used to create bindings between JavaScript and Fjord, without requiring an FFI within the language itself.
This step should come in after type checking.
When a value is shared, if the result is a partially applied function, it must be shown be evaluated before the shared value is used in a unique context. The compiler needs to conservatively infer the lifetime of chunks with shared values, and error if it suspects a potential shared use after unique use.
This display name would be used while presenting the type to the user, allowing the compiler to use whatever name it wants internally.
let x = 5 in
x
This is not currently part of a test case, but should be added to the test/typedef/TypeDef.fj
file. An implicit value of type, say, OneMember
, and another value that consumes that implicit value, to ensure that the correct types are generated.
case a of
A -> "A"
B -> "B"
_ -> "something else"
The _
indicates a default pattern, meaning that any constructor not covered in existing patterns should use this value. Case expressions should either have patterns for all constructors or a wildcard pattern. The wildcard pattern is also a prerequisite for non-enum constructor pattern matching later on.
User defined operators should behave similar to Scala: precedence is based on what the first character is, and associativity is always left unless the operator ends in :, then it's right. This greatly simplifies parsing, and looking up operator definitions is just another scope lookup. An example of how operators should be declared:
(++) : String -> String -> String
(++) a b = ...
The parentheses around the operator signify that we are defining an operator and should not be valid syntax for non-operator functions. Only symbols are permitted in operator names.
type Point = (Int, Int)
The above should create a binding from Point
to (Int, Int)
during name resolution and type checking.
The lambda test cases have been broken for a while now.
Currently, no variables are actually bound in the case expressions. Local variables should be assigned to the array elements of the ADT, allowing the rest of the compilation to reference them as regular names.
Booleans should be implemented as an enum in the standard library, with some extra inlining work by the compiler like for ints.
Syntax example:
module app.HasDependencies
import library.Module
useLibraryModule : Int -> Int
useLibraryModule x = myLibraryFunction x
The import
keyword is better than use
or open
, though I'd rather use them as they're shorter, but import
doesn't have as many other uses as the latter two, so we'll use that. The above syntax example should generate something like this JS:
var library_Module = require("../library/Module");
var useMyLibraryModule = function (x) {
return library_Module.myLibraryFunction (x);
}
module.exports = {
useMyLibraryModule : useMyLibraryModule
};
A Fjord function of Request -> Request
, where Request
is a unique type, should translate into a JavaScript function function (a: Request): void
, as unique arguments are updated through mutation and the caller already has a reference to them. This is especially important for function types that return tuples, because we can avoid boxing the tuple.
This requires #4 before it can be added.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.