Syzygy Language - Complete Syntax Reference

Language Overview

Syzygy is an algebraic programming language designed for mathematical computation with strong static typing and algebraic data types.

// Complete program example
ring Z5 = integers_mod 5
module V = free_module(Z5, 3)

generators {
  v1 = (1, 0, 0) in V
  v2 = (0, 1, 0) in V
}

relations {
  2*v1 + 3*v2 == 0
}

define factorial as n .
  case n of {
    0 -> 1;
    _ -> n * factorial(n - 1);
  }

Lexical Structure

Identifiers

identifier ::= [a-zA-Z_][a-zA-Z0-9_]*

// Valid identifiers
x
module_name
v1
VectorSpace2
_is_valid

Keywords

ring, module, generators, relations

define, as, where, case, of

recursive, fixed_point, lambda

integers_mod, rationals, free_module

in, with, initial

morphism, endomorphism, kernel, image

compose, apply, map, fold, unfold

colimit, limit, filter

Literals

integer ::= [0-9]+
string ::= " [^"]* "
tuple ::= ( expression ( , expression )* )

// Numeric literals
0
42
1000

// String literals
"hello world"
"algebraic computation"

// Tuple literals
(1, 2, 3)
(x, y, z)
(1,)

Comments

// Single-line comment

/*
* Multi-line comment
* Supports nested /* comments */
*/

ring Z5 = integers_mod 5 // End-of-line comment

Ring Declarations

ring_decl ::= "ring" identifier "=" ring_type
ring_type ::= "integers_mod" integer | "rationals"

Finite Fields

// Finite field Z/nZ
ring Z5 = integers_mod 5
ring Z7 = integers_mod 7
ring Z11 = integers_mod 11

// Operations in finite fields
define add_in_Z5 as (a, b) . (a + b) % 5

Rational Numbers

// Field of rational numbers
ring Q = rationals

// Rational arithmetic
define half as x . x / 2

Note: Rings form the algebraic foundation for module definitions and must be declared before use.

Module Declarations

module_decl ::= "module" identifier "=" "free_module" "(" ring_ref "," integer ")"
ring_ref ::= identifier

// Module over finite field
ring Z5 = integers_mod 5
module V3 = free_module(Z5, 3)

// Module over rationals
ring Q = rationals
module VectorSpace = free_module(Q, 4)

// Higher-dimensional modules
module BigSpace = free_module(Z5, 100)

Module Properties

Modules are defined over a base ring
Dimension specifies the number of coordinates
Free modules have no relations by default
Generators define basis elements

Generator Declarations

generators_block ::= "generators" "{" generator_decl* "}"
generator_decl ::= identifier "=" tuple "in" module_ref ( ";" )?
module_ref ::= identifier

ring Z5 = integers_mod 5
module V = free_module(Z5, 3)

generators {
  // Standard basis vectors
  e1 = (1, 0, 0) in V
  e2 = (0, 1, 0) in V
  e3 = (0, 0, 1) in V

  // Custom generators
  v1 = (1, 1, 0) in V
  v2 = (0, 1, 1) in V
  v3 = (1, 0, 1) in V;
}

Generator Rules

Generator names must be unique within a module
Tuple dimension must match module dimension
Generators are automatically added to the module
Semicolons are optional between generators

Relation Declarations

relations_block ::= "relations" "{" relation* "}"
relation ::= expression ( "==" | "!=" | "<" | ">" | "<=" | ">=" ) expression ( ";" )?

ring Z5 = integers_mod 5
module M = free_module(Z5, 2)

generators {
  e1 = (1, 0) in M
  e2 = (0, 1) in M
}

relations {
  // Linear relations
  2*e1 + 3*e2 == 0
  e1 - e2 == 0

  // Multiple relations
  4*e1 == e2;
  e1 + e2 != 0;
}

Advanced Relations

// Complex algebraic relations
relations {
  (a + b) * x == c * y
  f(g(x)) == h(x)
  composition(m1, m2) == identity
  kernel(f) == {0}
}

Function Definitions

function_def ::= "define" identifier "as" parameters "." expression
parameters ::= identifier | "(" identifier ( "," identifier )* ")"

Simple Functions

// Identity function
define identity as x . x

// Constant function
define constant as x . 42

// Arithmetic operations
define square as x . x * x
define add as (x, y) . x + y
define multiply as (a, b) . a * b

Multi-parameter Functions

// Two parameters
define distance as (x, y) . sqrt(x*x + y*y)

// Three parameters
define linear_combination as (a, b, c) . a*x + b*y + c*z

// Function composition
define compose as (f, g) . lambda x . f(g(x))

Recursive Definitions

recursive_def ::= "recursive" identifier "where" "{" function_def+ "}"

// Fibonacci sequence
recursive fibonacci where {
  define fib as n .
    case n of {
      0 -> 0;
      1 -> 1;
      _ -> fib(n-1) + fib(n-2);
    }
}

// Factorial
recursive factorial where {
  define fact as n .
    case n of {
      0 -> 1;
      _ -> n * fact(n-1);
    }
}

Mutual Recursion

recursive mutual where {
  define is_even as n .
    case n of {
      0 -> true;
      _ -> is_odd(n-1);
    }

  define is_odd as n .
    case n of {
      0 -> false;
      _ -> is_even(n-1);
    }
}

Case Expressions

case_expr ::= "case" expression "of" "{" case_arm+ "}"
case_arm ::= pattern "->" expression ( ";" )?
pattern ::= integer | "_" | identifier | tuple

Basic Pattern Matching

// Integer patterns
define is_zero as n .
  case n of {
    0 -> true;
    _ -> false;
  }

// Multiple patterns
define sign as x .
  case x of {
    0 -> "zero";
    x if x > 0 -> "positive";
    _ -> "negative";
  }

Tuple Patterns

// Deconstructing tuples
define first as pair .
  case pair of {
    (x, y) -> x;
  }

// Nested patterns
define sum_nested as t .
  case t of {
    ((a, b), (c, d)) -> a + b + c + d;
    (x, y) -> x + y;
    _ -> 0;
  }

Wildcard Patterns

// Catch-all pattern
define safe_head as list .
  case list of {
    (x, _) -> x;
    _ -> 0; // default case
  }

Expressions

Basic Expressions

// Literals
42
"hello"
(1, 2, 3)

// Variables
x
module_name
generator

// Arithmetic
a + b
x * y - z
(a + b) * c

Function Applications

// Single argument
f(x)
factorial(5)

// Multiple arguments
add(x, y)
multiply(a, b, c)

// Nested applications
f(g(x))
compose(f, g)(x)
map(square, list)

Operators

Operator	Description	Associativity	Precedence
() []	Grouping, tuples	Left	Highest
* / %	Multiplication, division, modulus	Left	High
+ -	Addition, subtraction	Left	Medium
== != < > <= >=	Comparison	Left	Low
->	Case arrow	Right	Lowest
.	Function definition	Right	Lowest

Arithmetic Operators

// Basic arithmetic
a + b // Addition
x - y // Subtraction
p * q // Multiplication
m / n // Division
a % b // Modulus

// Compound expressions
(a + b) * c - d / e
x % modulus + offset

Comparison Operators

// Equality and inequality
x == y // Equal
a != b // Not equal
p < q // Less than
m > n // Greater than
x <= y // Less than or equal
z >= w // Greater than or equal

// Chained comparisons
0 < x && x < 10
a == b || c == d

Special Operators

// Function definition
define f as x . x + 1

// Case expressions
case x of { pattern -> expression }

// Module membership
generator in module

Category Theory Constructs

Morphisms

// Morphism definition
morphism f: A -> B where {
define apply as x . transform(x)
}

// Endomorphism
endomorphism g: M -> M where {
define action as x . x * 2
}

// Composition
define h as compose(f, g)

// Application
define result as apply(f, x)

Limits and Colimits

// Limit construction
limit diagram where {
  define cone as ...
  define universal as ...
}

// Colimit construction
colimit cocone where {
  define cocone as ...
  define universal as ...
}

Kernel and Image

// Kernel computation
define K as kernel(f)

// Image computation
define Im as image(f)

// Exact sequences
relations {
kernel(g) == image(f)
composition(f, g) == zero_morphism
}

Advanced Features

Fixed Point Combinators

fixed_point Y where {
  define combinator as f . (lambda x . f(x(x)))(lambda x . f(x(x)))
}

// Using fixed point for recursion
define factorial as Y(lambda f . lambda n .
  case n of {
    0 -> 1;
    _ -> n * f(n-1);
  })

Higher-Order Functions

// Map function
define map as (f, list) .
  case list of {
    [] -> [];
    (x, xs) -> (f(x), map(f, xs));
  }

// Fold function
define fold as (f, acc, list) .
  case list of {
    [] -> acc;
    (x, xs) -> fold(f, f(acc, x), xs);
  }

// Filter function
define filter as (pred, list) .
  case list of {
    [] -> [];
    (x, xs) -> case pred(x) of {
      true -> (x, filter(pred, xs));
      false -> filter(pred, xs);
    };
  }

Lambda Expressions

// Anonymous functions
lambda x . x * x
lambda (x, y) . x + y
lambda f . lambda g . lambda x . f(g(x))

// Immediate application
(lambda x . x + 1)(5)
(lambda (a, b) . a * b)(3, 4)

Full BNF Grammar

program ::= ( declaration )*

declaration ::= ring_decl
  | module_decl
  | generators_block
  | relations_block
  | function_def
  | recursive_def
  | morphism_def
  | limit_def
  | fixed_point_def

ring_decl ::= "ring" identifier "=" ( "integers_mod" integer | "rationals" )

module_decl ::= "module" identifier "=" "free_module" "(" identifier "," integer ")"

generators_block ::= "generators" "{" ( identifier "=" tuple "in" identifier ( ";" )? )* "}"

relations_block ::= "relations" "{" ( expression ( "==" | "!=" | "<" | ">" | "<=" | ">=" ) expression ( ";" )? )* "}"

function_def ::= "define" identifier "as" ( identifier | "(" identifier ( "," identifier )* ")" ) "." expression

recursive_def ::= "recursive" identifier "where" "{" ( function_def )+ "}"

expression ::= literal
  | identifier
  | tuple
  | expression operator expression
  | function_call
  | case_expr
  | "(" expression ")"
  | "lambda" parameters "." expression

case_expr ::= "case" expression "of" "{" ( pattern "->" expression ( ";" )? )+ "}"

pattern ::= integer | "_" | identifier | tuple

operator ::= "+" | "-" | "*" | "/" | "%" | "==" | "!=" | "<" | ">" | "<=" | ">=" | "->"

literal ::= integer | string

tuple ::= "(" ( expression ( "," expression )* )? ")"

function_call ::= identifier "(" ( expression ( "," expression )* )? ")"