Algebroire

Algebroire (Official pronounciation: [ˈaldʒɪbɹɯ̯ɐɾ]) is a programming language designed by PSTF.

It is greatly inspired by Esomath and APL.

Basic Mathematical Things

Data storage

Variables are declared with := and reassigned by ←. For example,

x := 10
x ← 20

If you don't want to declare with initial value, you can use ∈, for example,

x ∈ Nat

A variable can be represented by a name made up of multiple symbols, and the same goes for sets, so we’ve pretty much stopped using double-struck capital letters. For example, Nat represents the set of natural numbers, Int represents integers, Rat represents rational numbers, Alg represents algebraic numbers (numbers that can be expressed with a finite number of roots), Float represents real numbers, and Comp represents complex numbers. Similarly, Str stands for strings, Bool for boolean values, Null for null (it's not equal to ∅), Lambda for functions, List for lists, Set for sets, Dict for dictionaries, Tuple for typles, Vec for vectors, and so on.

Function Definition

The most important thing in standard algebraic language is functions, and Algebroire is no different. Here is the syntax for defining functions.

function_name(argument) := {body}

For example,

F(n) := { 0               if n = 0;
          1               if n = 1;
          F(n−1)+F(n−2)   otherwise }

And you can also "declare" a function without body:

function_name : argument types → returning type

For example,

F : Nat → Nat
F(n) := { 0               if n = 0;
          1               if n = 1;
          F(n−1)+F(n−2)   otherwise }

And we even have lambda functions:

arguments |→ return_expression

Evaluation is pure and demand-driven. Definitions do not mutate.

E where arg1 := v1, arg2 := v2, ...

This is a temporary expression. It uses the parameters defined after 'where' when evaluated, and they are discarded once the evaluation is complete and the result is returned.

Piecewise Expressions

{ E₁ if C₁; E₂ if C₂; E₀ otherwise }

This is a piecewise expression. It evaluates into different expressions if conditions are met. If no conditions are met, then evaluates into E₀. The Fibonacci function mentioned above uses this expression.

Big Expressions and D&I stuffs

The “big expression” referred to here doesn’t mean it has a large value, but that it has a symbol that usually appears bigger than regular symbols in LaTeX, like sum, product, coproduct, integral, etc.

In plain text mode, since it’s impossible to accurately place the top and bottom markers, we use some special symbols.

∑_{i=m}^{n} E means adding up the results of E for values from m to n. If you replace ∑ with ∏, it means multiplying the results of E for values from m to n.

∫_{a}^{b} E dx is a definite integral function. We don't support indefinite integral one now.

d/dx E, ∂E/∂x, and E′ represent the differential, partial derivative, and derivative of E, respectively. Taking the derivative of any constant gives 0. Taking the derivative of e^x gives e^x.

lim_{x→a} E represents the value of E (an expression in terms of x) as x gradually approaches a. For example, the value of lim_{x→∞} 1/2^x is 2.

{ x ∈ S | P(x) } and { E | x ∈ S } are both set comprehensions. The first one represents generating a set containing only P(x) for all x in S, while the second one generates a set of all expressions E for x that belong to S.

∀ x ∈ S, P(x) and ∃ x ∈ S : P(x) represent, respectively, all the values in S that make P(x) true and whether there exists an x that makes P(x) true.

Matrices

A = [ a₁₁ a₁₂;
      a₂₁ a₂₂ ]

This defines a matrix. We recommend to use the syntax above to make the matrix readable.

Aᵀ, A⁻¹, AB, and det(A) are all matrix transformations, with Aᵀ being the most common matrix transpose.

Vectors

x := *(1, 2, 3)

Vectors are declared like this. Only those with preceeding asterisks can be called vector in Algebroire, while those without it should be called "tuple".

x · y, ‖x‖

These are vector operations. It should be mentioned that x·y is not equal to x×y in vector.

More Data Types

There are also characters, units, results, ports, and threads.

Result(α, ε) # OK(alpha) or Error(epsilon)
Task(α)      # concurrent computation
IO(α)

Programming Things

IO and do

print     : α → IO(Unit)
readLine  : IO(String)
readFile  : String → IO(String)
writeFile : String × String → IO(Unit)
args      : IO(List(String))
getEnv    : String → IO(String)
exit      : Int → IO(⊥)
return    : α → IO(α)

A do block sequences effects. Use ← for effectful bind, := for pure local definitions, and ⇐ for assignment to a mutable local.

For example,

main : IO(Unit)
main := do
  print("What is your name?")
  name ← readLine
  print("Hello, " + name + "!")

If main : IO(α), it is executed. If main : α, it is evaluated and printed.

Loops

Algebroire already has these:

sumTo(n) := ∑_{i=1}^{n} i
squares  := [ i² | i ∈ 1..n ]

For effectful programming, Algebroire adds for, while, and repeat.

for i ∈ 1..10 do
  print(i)

while x < 100 do
  print(x)
  x ⇐ x + 1

repeat
  line ← readLine
until line = "quit"

Loop rules:

• for i ∈ S do E iterates over a finite list, range, or set.
• If the body has type IO(α), the loop has type IO(List(α)); as a statement, the result is discarded.
• while C do E repeats while C is true and returns IO(Unit).
• break exits the nearest loop; continue skips to the next iteration.
• Mutable locals are scoped to the nearest do block and desugar to explicit state.

Other programming constructs

Pattern Matching

length : List(α) → Nat
length([])     := 0
length(x : xs) := 1 + length(xs)

map : (α → β) × List(α) → List(β)
map(f, [])     := []
map(f, x : xs) := f(x) : map(f, xs)

Records

Point := { x : Float, y : Float }

p := { x: 1, y: 2 }
p.x

Modules and Imports

module Math {
  π := 3.141592653589793
  sin : Float → Float
  cos : Float → Float
}

import Math

Error Handling

parseInt : String → Result(Int, String)

safeDiv : Float × Float → Result(Float, String)
safeDiv(a, b) := {
  Ok(a ÷ b)            if b ≠ 0;
  Error("division by 0") otherwise
}

Or maybe...

try
  text ← readFile("data.txt")
  print(text)
catch e
  print("error: " + e)

Command-line and environment

main := do
  argv ← args
  print("arguments: " + show(argv))
  home ← getEnv("HOME")
  print("home: " + home)

Examples

Fibonacci

φ := (1 + √5) / 2
F(n) := round( (φⁿ − (−φ)⁻ⁿ) / √5 )

Sieve of Erathosthenes

sieve : Nat → List(Nat)
sieve(N) := [ n | n ∈ 2..N, ¬composite[n] ]
  where
    var composite := array(N + 1, false)
    for p ∈ 2..⌊√N⌋ do
      if ¬composite[p] then
        for m ∈ p²..N step p do
          composite[m] ⇐ true

Sudoku Solver

solve : Grid → Option(Grid)
solve(g) :=
  if complete(g) then Some(g)
  else first([ solve(g′) | (i, j) := nextEmpty(g),
                           d ∈ 1..9,
                           valid(g, i, j, d),
                           g′ := set(g, i, j, d) ])

Turing-Completeness Proof

bfFast : String × String → IO(String)
bfFast(prog, inp) := do
  jumps := matchBrackets(prog)          // pure binding inside do
  tape  := array(30000, 0)
  var ptr := 0
  var pos := 0
  var ins := chars(inp)
  var out := ""

  while pos < |prog| do
    c := prog[pos]
    if      c = '>' then ptr ⇐ ptr + 1
    else if c = '<' then ptr ⇐ ptr − 1
    else if c = '+' then tape[ptr] ⇐ (tape[ptr] + 1) mod 256
    else if c = '-' then tape[ptr] ⇐ (tape[ptr] − 1) mod 256
    else if c = '.' then out ⇐ out ++ [chr(tape[ptr])]
    else if c = ',' then
      if ¬empty(ins) then do
        tape[ptr] ⇐ ord(head(ins))
        ins ⇐ tail(ins)
    else if c = '[' then
      if tape[ptr] = 0 then pos ⇐ jumps[pos]
    else if c = ']' then
      if tape[ptr] ≠ 0 then pos ⇐ jumps[pos]
    pos ⇐ pos + 1

  return out

See Also

• APL