Lx Reference

Grammar

program = [ expression ] EOF .

expression = binding | selection | binary .

binding = "let" IDENTIFIER "=" expression "in" expression .

selection = "if" expression "then" expression "else" expression .

binary
    = application ("==" | "!=") binary
    | application ("+" | "-") binary
    | application ("*" | "/") binary
    | application
    .

application = primary { primary } .

primary
    = literal
    | IDENTIFIER
    | function
    | "(" expression ")"
    .

literal
    = "true"
    | "false"
    | NUMBER
    | STRING

function = ("\\" | "λ") IDENTIFIER "." expression .

Program

program = [ expression ] EOF .

A program is either empty or a single expression.

Expressions

expression = binding | selection | equality .

Bindings

binding = "let" IDENTIFIER "=" expression "in" expression .

A binding introduces a new variable, which is then available in the body.

Example: Binding

let var = 123 in
    var
# evaluates to
    123

Since bindings are expressions it is possible to chain them:

Example: Chained Bindings

let a = 123 in
let b = 456 in
let add = \a. \b. a + b in
    add a b
# evaluates to
    579

Selections

selection = "if" expression "then" expression "else" expression .

A selection expression chooses between two alternatives based on a condition.

Example: Selection

if a == b then
    "equal"
else
    "not equal"

Example: Chained Selection

if a == b then
    "equal"
else if a > b then
    "greater"
else
    "less"

Infix

equality = additive { ("==" | "!=") additive } .
additive = multiplicative { ("+" | "-") multiplicative } .
multiplicative = application { ("*" | "/") application } .

Example: Infix Expressions

1 + 2 * 3 == 7
# parsed as
    (1 + (2 * 3)) == 7

Application

application = primary { primary } .

An application expression applies a function to one or more arguments.

Example: Function Application

(λx. λy. x + y) 1 2  ==  ((λx. λy. x + y) 1) 2

Primary

primary
    = literal
    | IDENTIFIER
    | function
    | "(" expression ")"
    .

Literals

literal
    = "true"
    | "false"
    | NUMBER
    | STRING

• Boolean literals: true, false
• Numeric literals: integers (e.g. 123, 456, …)
• String literals: sequences of characters enclosed in quotes

Example: Literals

true
123
"hello"

Identifiers

Identifiers refer to variables bound in the current scope.

Example: Identifier

let foo = 42 in
    foo
# evaluates to
    42

Grouping

Parentheses can group subexpressions and override precedence.

Example: Parenthesized Expression

(1 + 2) * 3
# evaluates to
    9

Abstraction

function = ("\\" | "λ") IDENTIFIER "." expression .

A function abstraction introduces a parameter and a body. The parameter binds occurrences of the identifier within the body.

Example: Identity Function

let id = λx. x in
    id 1
# evaluates to
    1

let id = λx. x in
    id id
# evaluates to
    λx. x

Example: Curried Function

let add = λx. λy. x + y in
    add 1 2
# evaluates to
    3

let add = λx. λy. x + y in
    add 1
# evaluates to ...
    λy. 1 + y
# ... an expression where x is bound to the argument

let add = λx. λy. x + y in
    add (add 1 2) 3
# evaluates to
    6