Ludwig Grammar Specification

About This Notation

This Ludwig grammar specification uses an informal extended BNF.

  • [foo] means a list of foo.
  • BLOCK[foo] means a list of foo, where the items in the list have the same indentation level.
  • SEP[foo ","] means a list of foo, separated by commas.
  • If 1 is appended to one of the macros, it means that Ludwig expects at least one item in the list. For example, SEP1 and BLOCK1.
  • This guide disregards any problems that might come with infinite left-recursion in top-down parsers.
  • In some places, indentation is specified in plain English to make things more readable.

Grammar

Sheets (modules)

Statements must all start at the top level, which means their first lines cannot have any indentation.

sheet
    = annotations [statement]

statement
    = statement_composition
    | statement_import
    | statement_export
    | statement_type
    | statement_operator
    | statement_binding
    | statement_validate

Note that the second form of composition statements is being deprecated.

statement_composition
    = "composition"
    | "composition" string

Import statements

An import statement allows you to import another module (library) into your composition.

statement_import
    = "import" BLOCK1[import_item]

import_item
    | import_item_single
    | module_name "{" SEP[import_item_single ","] "}"

import_item_single
    = module_name "as" module_alias
    | module_name "as" "."

Export statements

An export statement allows you to export types or even an entire module so that you can use it in another module.

statement_export
    = "export" BLOCK1[export_item]

export_item
    = "module" module_name "as" "."
    | "module" module_name "as" module_alias
    | "type" qualified_type_name
    | "operator" qualified_operator
    | qualified_variable

Type statements

A type statement defines a type.

statement_type
    = "type" type_name "<" SEP1[type_variable ","] ">" ":" type_body
    | "type" type_name ":" type_body

type_body
    = type_body_sum
    | type_body_alias

type_body_sum
    = BLOCK1[type_body_sum_con]

type_body_sum_con
    = "|" constructor (block_record_type | type)

type_body_alias
    = block_record_type
    | type

Types

The block_record_type can only appear in definitions, not in normal “usage” of types.

block_record_type
    = BLOCK1[annotated_record_type_element]

type
    = type "<" SEP1[type_variable ","] ">"
    | "(" SEP1[type ","] ")"
    | "fun" type "(" SEP1 [type ","] ")"
    | "fun" "(" SEP1 [type ","] ")" "->" type
    | qualified_type_name
    | type_variable
    | "{" SEP1[record_type_element ","] "}"
    | "{" SEP1[record_type_element ","] "," type_variable "}"

annotated_record_type_element
    = key ":" type
    | key ":" annotations type

record_type_element
    = key ":" type

Bindings

A binding consists of a name, a body, and optionally a type annotation.

statement_binding
    = variable ":" expr
    | type variable ":" expr
    | type variable "(" SEP1[binding_argument ","] ")" ":" expr
    | type variable "{" SEP1[record_type_element ","] "}" ":" expr
    | "fun" variable "(" SEP1[record_type_element] ")" "->" type ":" expr
    | "fun" variable "{" SEP1[record_type_element] "}" "->" type ":" expr

Expressions

Expressions include literals, case statements, conditionals (if, then, elif, and else statements), lambda functions, local variables (let statements), sequence (seq statement), lists, records, dictionaries, operators, function calls (app statements), selects, and updates (with statements).

expr
    = "(" expr ")"
    | expr_case
    | expr_if
    | expr_lambda
    | expr_let
    | expr_seq
    | expr_list
    | expr_record
    | expr_dict
    | expr_operator
    | expr_app
    | expr_select
    | expr_with
    | qualified_variable
    | qualified_constructor

Literals

Literals include the common primitive types integer, float, Boolean, and string.

literal
    = int
    | float
    | boolean
    | string

Case statements

case statements are one approach to handling conditionals.

expr_case
    = "case" expr "of" [expr_case_alternative]

expr_case_alternative
    = "|" expr_case_pattern "->" expr

expr_case_pattern
    = "(" SEP[expr_case_pattern ","] ")"
    | "_"
    | literal
    | variable
    | constructor [expr_case_pattern]

Conditionals

if expressions can live on one line, or they can be spread over multiple lines with correct indentation. Ludwig also supports then, elif, and else conditional statements.

expr_if
    = "if" expr "then" expr ["elif" expr "then" expr] "else" expr
    | INDENT "if" expr "then" expr
      [INDENT "elif" expr "then" expr]
      INDENT "else" expr

Lambdas

Ludwig supports lambdas, or anonymous functions.

expr_lambda
    = "fun" "(" SEP[variable ","] ")" ":" expr

Local variables

let expressions allow you to define local variables within functions or bindings. They need to be properly indented.

expr_let
    = INDENT "let" variable ":" expr
      INDENT expr

Sequences

seq (“sequence”) expressions allow you to evaluate one expression before the next, like print statements.

expr_seq
    = INDENT expr ";"
      INDENT expr

Lists

An list is a collection of variables.

expr_list
    = "[" SEP[expr ","] "]"

Records

A record is a special type of binding that contains key: expression attributes.

expr_record
    = "{" SEP[key ":" expr] "}"
    | BLOCK1[key ":" expr]

Dictionaries

Note that for dict, we’ve used SEP1. We cannot write the empty dictionary as {}, because that is the empty record. In order to have an empty dictionary, you can use library functions.

expr_dict
    = "{" SEP1[string ":" expr] "}"

Operator expressions

Ludwig supports prefix as well as infix operators.

expr_operator
    | operator expr
    | expr operator expr

Function calls

In addition to the normal function call syntax, Ludwig offers a few shorthands.

expr_app
    = expr "(" SEP[expr ","] ")"
    | expr string
    | expr expr_record
    | expr expr_dict
    | expr expr_list

Selects

Selects allow you to select fields from a sum type constructor.

expr_select
    = expr "." field_like

field_like is used for selections as well as with updates.

field_like
    = key
    | constructor
    | "(" qualified_constructor ")"

Updates

with is used for updating records.

expr_with
    = expr "with" "{" SEP[update ","] "}"
    | expr "with" BLOCK1[update]

update
    = SEP1[field_like "."] ":" expr

Operators

Operators include basic arithmetic operators (+, -, *, /), floating point operators (.+, .-, .*, ./), a string concatenation operator (++), and Boolean operators (&&, ||, !).

statement_operator
    = "operator" operator operator_fixity ":" qualified_variable

operator_fixity
    = "prefix"
    | "infixl" int
    | "infixr" int

Validations

The validation type indicates Success or Failure for a qualified variable.

statement_validate
    = "validate" qualified_variable
    | "validate" BLOCK1[qualified_variable]

Annotations

Annotations provide extra information about variables.

annotations
    = [annotation]

annotation
    = "@" variable
    | "@" variable "(" SEP[string ","] ")"

Tokens

The difference between “regular” grammar rules and tokens is that for tokens, Ludwig does not allow whitespace characters between the different characters. These can usually all be caught with a regular expression and are thus good candidates for syntax highlighting (or technically lexical highlighting). As you can see, we prefix them with token in Ludwig syntax.

Reserved keywords

token keyword
    = "False"
    | "True"
    | "as"
    | "case"
    | "composition"
    | "elif"
    | "else"
    | "export"
    | "if"
    | "import"
    | "fun"
    | "language"
    | "let"
    | "of"
    | "operator"
    | "requires"
    | "then"
    | "type"
    | "with"
    | "validate"

Variable-like tokens

token module_alias
    = module_name

token module_name
    = SEP1[single_module_name "."]

token single_module_name
    = upper [upper | lower | digit | "-"]

token qualified_operator
    = module_alias "." operator
    | operator

token operator
    = operator_start [operator_char]

token operator_start
    = "+" | "-" | "/" | "*" | "="
    | "%" | "$" | "!" | "&" | "|" | "^" | "<" | ">"

token operator_char
    = "+" | "-" | "/" | "*" | "="
    | "%" | "$" | "!" | "&" | "|" | "^" | "<" | ">" | "."

token qualified_variable
    = module_alias "." variable
    | variable

variable
    = (lower | digit | "_") [ident_char]

token ident_char
    = lower | upper | digit | "_" | "-"

token qualified_type_name
    = module_alias "." type_name
    | type_name

token type_name
    = (upper | digit | "_") [ident_char]

token qualified_constructor
    = module_alias "." constructor
    | constructor

token constructor
    = (upper | digit | "_") [ident_char]

token type_variable
    = variable

The main difference between a key and a variable is that a key can be a reserved keyword, since Ludwig has enough information to distinguish them (keys in programs usually start with . or with, etc.).

token key
    = variable

Literals

token int
    = digit [digit]

token float
    = digit [digit] "." [digit]

token boolean
    = "True" | "False"

Ludwig uses JSON string conventions. Here’s a convenient diagram:

From JSON.org

From JSON.org

token string
    = "'" [string_char] "'"
    | "\"" [string_char] "\""

Note that Ludwig supports two kinds of multiline strings. The syntax is straightforward:

foo = 'This is a
    pretty long
    multiline string'

The lines are joined with a single space. If you want to use proper newlines, you can use the following:

foo = 'This is a
    \pretty long
    \multiline string'

In the last case, the backslashes (\) are replaced by a single newline.

Note

Did you know that Fugue offers editor plug-ins so you can read and write Ludwig in your editor/IDE of choice? All plug-ins include Ludwig syntax highlighting, and some have additional features. See ludwig-mode for Emacs, ludwig-vim for vim, vscode-language-ludwig for VSCode, and language-ludwig for Atom.