[RFC] DDlog 2.0 Syntax

[Kixiron]

The syntax is described in an EBNF flavor loosely based off of W3C's EBNF

Note: As of now this grammar is not complete or final, it's just what I've implemented. A lot of the constraints are much loser than they seem like they should be, that's just because of the error recovery I've implemented in the parser, things accepted within parsing are not always valid and errors are emitted

Root = Item*

Item = FunctionDef | RelationDef | TypeDef

RelationDef = Attributes Modifiers keyword:RelKw name:RelName columns:RelCols
RelKw = 'relation' | 'multiset' | 'stream'
RelName = 'ident'
RelCols = '(' columns:RelCol* ')'
RelCol = Attributes binding:Pattern ':' ty:Type ','*

FunctionDef = Attributes Modifiers keyword:'function' name:FunctionName Generics args:FunctionArgs ret:FunctionReturn? body:Block
FunctionName = 'ident'
FunctionArgs = '(' args:FunctionArg* ')'
FunctionArg = Attributes binding:Pattern ':' ty:Type ','*
FunctionReturn = ':' return_ty:Type

TypeDef = Attributes Modifiers keyword:'typedef' name:TypeName '=' body:TypeBody
TypeName = 'ident'

TypeBody = RecordType | SumType
RecordType = constructor:RecordName ('{' fields:RecordField* '}')?
RecordName = 'ident'
RecordField = Attributes name:Pattern ':' ty:Type ','*
SumType = ('|' RecordType)*

Attributes = Attribute*
Attribute = '#[' AttrPair* ']'
AttrPair = 'ident' '=' Expr ','*

Modifiers = Modifier*
Modifier = 'input' | 'output' | 'extern'

Type = GenericType | TupleType | FunctionType

GenericType = 'ident' Generics?
Generics = '<' generics:GenericArg* '>'
GenericArg = Type ','*

TupleType = '(' elements:TupleTypeElem* ')'
TupleTypeElem = Type ','*

FunctionType = 'function' args:FunctionTypeArgs ret:FunctionReturnType?
FunctionTypeArgs = '(' args:FunctionTypeArg* ')'
FunctionTypeArg = Type ','*
FunctionReturnType = ':' Type

Block = '{' statements:Stmt* '}'
Stmt =
    ExprStmt
    | VarDecl
    | IfStmt

ExprStmt = Expr ';'
VarDecl = 'var' binding:Pattern '=' value:Expr ';'

IfStmt = IfBlock* ElseBlock?
IfBlock = leading_else:'else'? 'if' cond:Expr Block
ElseBlock = 'else' Block

Pattern = VarRef | TuplePattern
TuplePattern = '(' elements:TuplePatternElem* ')'
TuplePatternElem = Pattern ','*

Expr =
    Literal
    | VarRef
    | Assign
    | ParenExpr
    | BinExpr
    | IfStmt
    | RetExpr
    | UnaryExpr
    | Block

VarRef = 'ident'

Assign = binding:Pattern '=' value:Expr

ParenExpr = '(' inner:Expr ')'

// TODO: Floats
Literal = Bool | Number | String
Bool = True | False
Number = 'number'
String = 'string'

RetExpr = 'return' expr:Expr

UnaryExpr = op:UnaryOp expr:Expr
UnaryOp = Bang | Minus

BinExpr = lhs:Expr op:BinOp rhs:Expr
BinOp =
    Plus
    | Minus
    | Star
    | Slash 
    | Percent
    | RightRocket
    | Pipe
    | Caret
    | Ampersand
    | Shl
    | Shr
    | And
    | Or
    | EqEq
    | Neq
    | RAngle
    | RAngleEq
    | LAngle
    | LAngleEq

Or = 'or'
And = 'and'
True = 'true'
False = 'false'

Eq = '='
Bang = '!'
Pipe = '|'
Plus = '+'
Star = '*'
Neq = '!='
Shl = '<<'
Shr = '>>'
Caret = '^'
Comma = ','
Colon = ':'
Minus = '-'
Slash = '/'
EqEq = '=='
LAngle = '<'
RAngle = '>'
LBrack = '['
RBrack = ']'
LCurly = '{'
RCurly = '}'
LParen = '('
RParen = ')'
Percent = '%'
Ampersand = '&'
Semicolon = ';'
LAngleEq = '<='
RAngleEq = '>='
RightRocket = '=>'

[ryzhyk]

Some suggestions.

Meta

• I suggest that, except when there are specific reason to diverge, we stick to a subset of the Rust syntax.
• Do we want a purely functional language or a mostly functional language like Rust? In particular, do we bind variables once let x = 5 or do we allow mutable variables and function arguments (let mut x = 0; x = 5)?

Type system

• I vote we drop arbitrary-width bit vectors (bit<5>) and bigint's. They are non-standard, complicate the compiler and haven't proved very useful in practice. I think we can achieve most of the benefits using libraries, while simplifying the compiler, and unifying our type system with Rust.
• Replace DDlog's Haskell-style structs with Rust-style structs, tuple structs, and enums.

[mihaibudiu]

bigint is useful. But it could be a library - although you lose the literals.

[Kixiron]

Yah, I totally agree with those sentiments. Purity is a tricky question, it's a tradeoff between user control and compiler freedom. However, since we have the ability to drop into writing and using Rust code within ddlog, I think that making the surface language pure can sidestep that particular drawback

[mihaibudiu]

I have no problems with mutable variables in imperative code. It should be clear that you cannot mutate any value that is in a relation, though.

[ryzhyk]

I have no problems with mutable variables in imperative code. It should be clear that you cannot mutate any value that is in a relation, though.

There will no longer be any distinction between imperative and relational code at the language level. Relation<> is just a type like any other. However, since there is no API to get a mutable reference to a record in a relation, its contents is immutable.

[mihaibudiu]

I thought you gave up on embedding the language in Rust or something else. So then we still have these two clear layers imperative/relational. Except some functions can compute on relations. Then there is no "main", and you still want input and output relations. That is also more modular - you cannot just add arguments to an existing function.

[ryzhyk]

Yah, I totally agree with those sentiments. Purity is a tricky question, it's a tradeoff between user control and compiler freedom. However, since we have the ability to drop into writing and using Rust code within ddlog, I think that making the surface language pure can sidestep that particular drawback

You can always convert mutable variables to single static assignment form.

I guess if we want to allow loops, then we want mutable variables. Loops are not very useful if you cannot modify variables in the body of the loop :)

[mihaibudiu]

Variables are not as interesting as containers. Do you want mutable vectors and maps?

[ryzhyk]

Variables are not as interesting as containers. Do you want mutable vectors and maps?

That's a library design question. Assuming we have mutable arguments, you can define methods that mutate the container. You can also have immutable containers, where mutator methods return a new container.

[ryzhyk]

I thought you gave up on embedding the language in Rust or something else.

We're not embedding in an existing language, but are designing our own functional language. Relations are first-class objects that can be passed to functions and back. All relational operators are just methods (#2); Datalog-style rules will be implemented as syntactic sugar on top of this language.

At least this is the current proposal.

Not sure exactly what main looks like in this world.

Upd: but I still like the idea that input and output relations are just inputs and outputs of a function.

[Kixiron]

Opened #4