chancehudson/ashlang

ashlang

A language designed to run on any computer that can exist.

Design

ashlang is described by a regex-like grammar. This grammar is parsed into an AST. The AST is designed to be compatible with both traditional computers, as well as more restrictive executors like R1CS and PLONK.

Targets

The included compiler supports tasm assembly and executes on the Triton VM.

The compiler is designed to be multi-stage/partially re-usable.

Language

The language is designed to efficiently express mathematical relationships between sets. Main features:

• element-wise vector operations
• throws if vectors of mismatched size are used in an operation e.g. val[0..10] * lav[0..5]
• functions cannot be declared, each file is a single function
• files are not imported, function calls match the filename and tell the compiler what files are needed

The language has a single type: field element. This is effectively an unsigned number with max value depending on the system executing the program. e.g. on an m3 macbook the max size is 2^64. In triton vm the max size is 2^64 - 2^32 + 1 or approximately 2^64.

Below is the poseidon hash function implemented in a few different languages:

• circom
• solidity (naive)
• solidity (optimized)
• javascript

Below is the ashlang implementation poseidon. See examples/poseidon.ash for a commented version. Note that vectors can be manipulated using the *+-/ operators directly.

########################
# poseidon
# -
# Grassi, Khovratovich,
# Rechberger, Roy, Schofnegger

(T, inputs)

let state[T]
state[0] = 0 # unnecessary, added for clarity
state[1..T] = inputs

const C = poseidon_C(T)
const M = poseidon_M(T)
const N_F = poseidon_N_F(T)
const N_P = poseidon_N_P(T)

let c_i
let round_i
let mix_i

: full_round N_F + N_P

    state = state * C[c_i]

    c_i = c_i + T

    if round_i < N_F / 2 || round_i >= N_F / 2 + N_P
        state = pow5(state)
    else
        state[0] = pow5(state[0])

    mix_i = 0

    : mix_inner T
        state[mix_i] = sum(M[mix_i] * state)
        mix_i = mix_i + 1
        mix_inner()
      
    round_i = round_i + 1

    full_round()

return state

ashlang's Issues

compiler linter

Statements currently disallow semicolons as a terminating character. Writing rust has conditioned me to add semicolons. The compiler could lint the files in place. This seems like a natural extension of the language providing a pre-built linter. Such a linter must be well defined to prevent unwanted changes to files, especially during development.

Proposed features:

• semicolon removal: trailing semicolons on statements will be removed from the file

language feature tracking

• scalar math operations
• tuple inputs
• let variables
• re-assigned variables
• const variables
• function support
  • let assignment
  • const assignment (static evaluation)
  • return function content directly
  • arguments
• function auto-import
• if statement
  • equality
  • comparison
  • block support
• general block support
• builtin functions
  • assert
  • crash
• vector tracking support
• vector math support
• jump dest support

`return` keyword

As currently designed the return keyword may be used at most 1 time in an ashlang file, and must be the last instruction.

This is designed to allow the user to output a single scalar or vector. This design likely won't be great, instead the return keyword should be allowed anywhere in the script. There are two cases:

• the script is the entrypoint, meaning return creates public outputs from the STARK
• the script is a function, meaning return returns some value to the caller

Allowing multiple return invocations causes problems in the second case. There is currently no syntax for declaring tuples in a single statement.