Syntax proposal : Product Types

Product types to model tuples and units.

examples

a function returning the unit type (empty tuple)

fn main() {
    // implementation
}

a function returning a product type (tuple)

fn main() -> (f32, i32) {
    return (0.0, 1);
}

constructing a product type

this example creates a product type (f32, i32, Foo).

let my_product_type_value = (0.0, 1, Foo::new());

destructuring a product type

both values of the tuple are available as local foo and bar

fn get_foo_bar() -> (Foo, Bar) {
    return (Foo::new(), Bar::new());
}

fn main() {
    let (foo, bar) = get_foo_bar();
}

omitting a value during destructuring

only foo is available since the second value was discarded with the _ operator

fn get_foo_bar() -> (Foo, Bar) {
    return (Foo::new(), Bar::new());
}

fn main() {
    let (foo, _) = get_foo_bar();
}

accessing single values from a product type

let my_product_type_value = (0.0, 1, Foo::new());
let foo = my_product_type_value.2;

• Create a pass in passes/ast/type_checking
• Type check function signatures (not the function block)
• Test the pass

Feature: Name

parse_function

Summary

Add a short summary.

Each BlockDeclaration has a Span attached to it, which gives the offset, length, line and column of the respective "first character" of the block.
It is default initialized and returned from parsing.

Examples

Give some examples.

//... ],
                                block: BlockDeclaration {
                                    span: Span::new(0, 0, 1, 1),
                                    statements: [
                                        Return(

References

Give some references about research or otherwise relevant information.

• reference

We need to write up a whitepaper describing our goals and non-goals with xshade.

custom constant variants like bindable constants, samplers etc should not be it's own AST node, they are specialized variants of const nodes and the AST should reflect this. Also i'm too lazy to implement independent type checking for all of them!

• Create a pass in passes/ast/type_checking
• Check against circular structs
• Test the pass

We currently use the parser combinator library nom, which doesn't give us spans (text locations) by default. There is one other open source project which uses nom for lexing/parsing: monkey-rust. We should look at how they solve this. We need the spans to give useful compile errors to the user.

The old TypeEnvironment was encapsulated inside our SymbolTable for convenience, this lead to an unclear API. We first make the TypeEnvironment shared so old code doesn't break:

• Make TypeEnvironment shared like SymbolTable: https://github.com/xshade-lang/xshade/blob/master/src/type_system/symbol_table.rs#L10
• Make SymbolTable use a shared reference to the TypeEnvironment: https://github.com/xshade-lang/xshade/blob/master/src/type_system/symbol_table.rs#L71

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L242-L369

• Create a pass in passes/ast/type_checking
• Type check all expressions
• Test the pass

Syntax proposal : invert keyword

Summary

Automatically inverts a one-parameter function. This feature can be refined over time, for the start it would be sufficient to only invert simple operations like sin, cos, exp, log or sqrt.

Examples

A conversion function and its inverted variant:

fn main() {
  let to_u = (x) => x * 2.0 - 1.0;
  let from_u = invert to_u;
}

References

TODO

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L57-L80

• Create a pass in passes/ast/type_checking
• Add the casts to the given types
• Test the pass

As talked before, we need a simple string interner. Currently the compiler copies strings all across the place.

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L94-L124

• Create a pass in passes/ast/type_checking
• Add function type to symbol table
• Add function as symbol to the symbol table
• Type check arguments
• Type check return type (not if it actually returns the correct type)
• Set call signature for function type
• Test the pass

Currently the parser returns the smallest valid program, it should provide an error when it's not able to parse the whole input.

Recursion is dangerous on the gpu as it quickly leads to diverging executions. It is forbidden in GLSL and HLSL. We will forbid it too and have to make sure the compiler detects it correctly.

Refactor FunctionArgumentDeclaration etc into a CallableSignature featuring both arguments and return type.

Syntax proposal

We need syntax to make things from other modules accessible. This proposal shows a possible solution.

• Parser parses import syntax
• Parser parses export syntax
• Identifiers in AST need to be replaced with Paths (module path + identifier)
• Compiler needs to process imported files (once)

implementation

import and export are top-level constructs and cannot exist inside of blocks, however they can be placed at any position within a file. There are no syntax for default exports or imports as this leads to issues when IDEs try to refactor code.

Allowed exports and imports are:

• Functions
• Structs

example

index.xs

import { Foo, Bar } from other_module;

struct Foobar {
    x: Foo;
    y: Bar;
}

other_module.xs

struct Foo {
    x: f32,
    y: f32,
}

struct Bar {
    x: f32,
    y: f32,
}

fn doFoo(in: Input) -> Output {
    // ...
}

export { Foo, Bar, doFoo };

export syntax

export a single item

export Foo;

export multiple items

export { Foo, Bar };

import syntax

import a single item

import Foo from bar;

import multiple items

import { Foo, Bar } from bar;

import all

import * from bar;

import from submodules

import * from foo/bar;

file resolution

File resolution is a tricky thing for module systems. How do we resolve the standard library? How do we resolve libraries from a potential package manager?

other module systems

• ES2015
• rust
• hlsl
• unity3d

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L126-L218

• Create a pass in passes/ast/type_checking
• Check the given programs like in old code
• Test the pass

Syntax proposal : Parametric Polymorphism

Summary

Also known as generics or templates.

Examples

A struct type which takes in a type parameter:

struct MyStruct<T> {
    foo: T,
}

References

• generics in rust
• generics in c#

Hi!

Are you familiar with other projects targeting GPU graphics using functional programming approach?
i.e.

• http://lambdacube3d.com/
• https://github.com/tobbebex/GPipe-Core

How is your system different?

Missing: Assignment statement

Summary

We're missing a basic (re-) assignment expression.

Examples

fn test() -> f32 {
    let x = 1.0;
    x = 2.0;
    return x;
}

Refactor operator in parser and ast, currently two implementations, one for operator declaration for types and one in expression trees.

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L82-L92

• Create a pass in passes/ast/type_checking
• Add constant to symbol table
• Type check constant
• Test the pass

Syntax proposal : Loops

Summary

On GPUs loops can quickly cause performance issues by branching or diverging kernels. To avoid such issues xshade limits the power of loop constructs. One of those limitations is the number of iterations needs to be known at compile time.

Examples

for i in 0..16 {
    samples[i] = sample(i);
}

References

• to be added

This issue tracks ideas and conversation about posibilities of testing in shaders

Assertions

Often times while developing shaders we want to be sure that our functions return values of a certain range when given input of a certain range, especially when converting from/to uv space into data (we encountered this while implementing procedural sky rendering).

let samples = from_distribution(PlanetHeight, AtmosphereHeight);
let results = samples.map(convert_from_height);
assert_range(results, 0.0, PI);

Where from_distribution returns a list of values within the range of its two parameters, map is your typical mapping function, assert_range asserts that a list of values is within the given range of parameters.

Interpreter

One idea is to build an interpreter for xshade, running xshade code on the CPU.

Compiling into another language, then execute

Another aproach can be to translate xshade code into another CPU language to run the tests.

Try to use compute shaders

It could also be possible to use compute shaders to test xshade code.

Feature: Better Compiler Errors

Summary

After all AST nodes have spans we should add nice error messages.

Examples

An example error message.

error: type `vec3` is unknown or not included.
D:\Workspace\xshade\examples\phong.xs:2:15
 1 | struct VertexInput {
 2 |     position: vec3,
   |               ^^^^ unknown type `vec3`
 3 | }
implementations for `vec3` are found in:
* std::vec3 (type alias for `Vector<f32; 3>`)

References

• rust error messages

Syntax proposal : Dependent Types

Summary

Types with terms applied to them.

Examples

A Vector type with type parameter T and term parameter N. N is used to determine the number of components this Vector has. A Vector<f32; 4> for instance is a Vector with 4 components (x, y, z, w), each of type f32.

struct Vector<T; N> {
    values: [T; N],
}

A more extensive example with implementation blocks and limits to types and type terms.

struct Vector<T, N>
    where T: Numeric,
    N <= 4
{
    values: [T; N],
}

impl operator * for Vector<T, 4> {
    #[native_impl] // <- compiler tries to substitute a native implementation instead
    fn mul(self, scalar: T) -> Self {
        // optional implementation
    }

    #[native_impl]
    fn mul(self, other: Self) -> Self {
        // optional implementation
    }

    #[native_impl]
    fn mul(self, other: Matrix<T; 4, 4>) -> Self {
        // optional implementation
    }
}

References

• wikipedia on dependend types

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L220-L240

• Create a pass in passes/ast/type_checking
• Type check block
• Test the pass

Syntax proposal : Sum Types

Summary

A type representing multiple possible values, like union structs in C, enums in rust. This concept requires pattern matching support from the language to be useful.

This feature should be discussed, as it requires branching which is a bad thing on GPU programs.

Examples

An Option<T> representing the posibility of a value not being present.

enum Option<T> {
    Some(T),
    None,
}

Matching on an Option<T>.

match query_some_api() { 
    Some(my_val) => { //* ... *// },
    None => { //* ... *// },
}

References

• options in rust

• Create a pass in passes/ast/type_checking
• Check that every instruction that leaves the current function has the correct return type
• Test the pass

Syntax proposal : Programs

Summary

In the domain of shaders, a program is considered a collection of functions for different shader stages. As a shading language we should implement this concept as a first class citizen.

Stages

The parser should allow for any shader stages, later a program checker (similar to a type checker) should validate that the stage is one of vertex or fragment for now. The syntax is stage <stage name>(<arguments>) { <body> }.

Examples

A shader program with vertex and fragment stages.

program VertexColored {

    stage vertex(in: VertexInput) -> VertexOutput {
        return VertexOutput {
            position: in.position * mvp,
            color: in.color,
        }
    }

    stage fragment(in: VertexOutput) -> vec4 {
        return in.color;
    }
}

References

• openGL shaders

• Create a pass in passes/ast/type_checking
• Check against recursion in function calls
• Test the pass

Old code: https://github.com/Vengarioth/xshade/blob/master/src/type_system/type_check.rs#L371-L410

• Create a pass in passes/ast/type_checking
• Type check exports
• Test the pass

There is currently no precedence for operations, the parser will parse expressions from right to left (to avoid left recursion). We first need to define precedence for all expressions, then implement it in the compiler.