High-level interface for low-level programming

Overview

Singeli

Singeli is now able to compile useful programs to C, but it's very rough around the edges, with poor error reporting. We are beginning to use it for CBQN, where it can be enabled from the singeli git branch.

Singeli is a domain-specific language for building SIMD algorithms with flexible abstractions and control over every instruction emitted. It's implemented in BQN, with a frontend that emits IR and a backend that converts it to C. Other backends like LLVM or machine code are possible—it should be easy to support other CPU architectures but there are no plans to target GPUs.

To compile input.singeli:

$ singeli input.singeli [-o output.c]

For options see $ singeli -h. To run ./singeli as an executable, ensure that CBQN is installed as bqn in your executable path, or call as /path/to/bqn singeli ….

Early design discussion for Singeli took place at topanswers.xyz; now it's in the BQN forums (links and instructions).

Language overview

Singeli is primarily a metaprogramming language. Its purpose is to build abstractions around CPU instructions in order to create large amounts of specialized code. Programs will tend to do complicated things at compile time to emit programs that do relatively simple things at runtime, so it's probably better to orient your thinking around what happens at compile time.

The primary tool for abstraction is the generator. Written with {parameters}, generators perform similar tasks as C macros, C++ templates, or generics, but offer more flexibility. They are expanded at runtime, and form a Turing-complete language. Generators use lexical scoping and allow recursive calls. Here's a generator that calls another one:

def gen{fn, arg} = fn{arg, arg + 1}

In fact, + is also a generator, if it's defined. Singeli has no built-in operators but allows the user to define infix or prefix operator syntax for a generator. For example, the following line from include/skin/c.singeli makes + a left-associative infix operator with precedence 30 (there can be one infix and one prefix definition).

oper infix left  +  __add 30

Generators can be extended with additional definitions. Each definition overrides the previous ones on its domain, which means that applying a generator searches backwards through all definitions visible in the current scope until it finds one that fits. gen above applies to any two arguments, but a definition can be narrowed using types and conditions:

def gen{x:T, n, n, S & 'number'==kind{n} & T<=S} = {
  cast{S, x} + n
}

Here, x must be a typed value, and have type T, and the two n parameters must match. Furthermore, the conditions that follow each & must hold. Otherwise, previous definitions are tried and you get an error if there aren't any left. In this context : and & are syntax, not operators.

The end goal here is to define functions for use by some other program. Functions are declared with a parenthesis syntax at the top level, possibly with generator-like parameters. Types use value:type syntax rather than type value.

fn{T}(a:T, len:u64) : {
  while (len > 0) {
    a = a + 1
    len = len - 1
  }
}

Here you can see that compile-time code is written in an imperative style. if, else, and while control structures are provided. Statements are separated by newlines or semicolons; these two characters are equivalent.

If possible, iteration should be done with for-each loops. In SIMD programming these loops are very important and come in many varieties, taking vectorization and unrolling into account. So Singeli doesn't provide a single for loop structure, but rather a general mechanism for defining loops. Here's what a definition looks like:

def for{vars,begin,end,block} = {
  i:u64 = begin
  while (i<end) {
    exec{i, vars,block}
    i = i+1
  }
}

While this loop is an ordinary generator (allowing other loops to call it), special syntax is used to invoke it on variables and a code block. Here's an example with two pointers:

@for (src,dst over i from 0 to len) {
  src = 1 + dst
}

Outside the loop, these variables are pointers, and inside it, they are individual values. It's exec in the loops definition that performs this conversion, using the given index i to index into each pointer in vars. Each variable tracks whether its value was set inside the loop and writes to memory if this is the case.

Operators

Operators are formed from the characters !$%&*+-/<=>?\^|~. Any number of these will stick together to form a single token unless separated by spaces. Additionally, non-ASCII characters can be used as operators, and don't stick to each other.

The oper statement, which can only appear at the top level in the program, defines a new operator, and applies to all code later in the program (operators are handled with a Pratt parser, which naturally allows this). Here are the two declarations of - taken from include/skin/c.singeli.

oper prefix      -  __neg 30
oper infix left  -  __sub 30

The declaration lists the operator's form (arity, and associativity for infix operators), spelling, generator, and precedence. After the declaration, applying the operator runs the associated generator.

An operator can have at most one infix and one prefix definition. Prefix operators have no associativity (as operators can't be used as operands, they always run from right to left), while infix operators can be declared left, right, or none. With none, an error occurs in ambiguous cases where the operator is applied multiple times. The precedence is any number, and higher numbers bind tighter.

Built-in generators

The following generators are pre-defined in any program. They're placed in a parent scope of the main program, so these names can be shadowed by the program.

Program

Syntax Result
emit{type,op,args…} Call instruction op (a symbol, to be interpreted by the backend)
call{fun,args…} Call a function
return{result} Return result (optional if return type is void) from current function
exec{ind,vars,block} Execute block on pointers vars at index i
load{ptr,ind} Return value at ptr+ind
store{ptr,ind,val} Store val at ptr+ind

Values

Syntax Result
match{a,b} Return 1 if the parameters match and 0 otherwise
hastype{val,type} Return 1 if val is a typed value of the given type
type{val} Return the type of val
kind{val} Return a symbol indicating the kind of value
show{vals…} For debugging: print the parameters, and return it if there's exactly one

Types

Syntax Result
width{type} The number of bits taken up by type
eltype{type} The underlying type of a vector or pointer type
vcount{[n]t} The number of elements n in a vector type
cast{type,val} val converted to the given type
isfloat{type} 1 if type is floating point and 0 otherwise
issigned{type} 1 if type is signed integer and 0 otherwise
isint{type} 1 if type is integer and 0 otherwise
typekind{type} A symbol indicating the nature of the type
__pnt{t} Pointer type with element t
__vec{n,t} Vector type with element t and length n; equivalent to [n]t

Generators

Syntax Result
bind{gen,param…} Bind/curry the given parameters to the generator

Tuples

Syntax Result
tup{elems…} Create a tuple of the parameters
tupsel{ind,tuple} Select the indth element (0-indexed) from the tuple
apply{gen,tuple} Apply a generator to a tuple of parameters

Arithmetic

Arithmetic functions are named with a double underscore, as they're meant to be aliased to operators. The default definitions work on compile-time numbers, and sometimes types. The definitions for numbers are shown, with a C-like syntax but using ^ for exponentiation and // for floored division.

__neg __shr __shl __add __sub __mul __div
-y x//2^y x*2^y x+y x-y x*y x/y
__and __or __xor __not
x*y x*y-(x+y) x!=y 1-y
__eq __ne __lt __gt __le __ge
x==y x!=y x<y x>y x<=y x>=y
Issues
  • Float2 precision bug

    Float2 precision bug

    I think that float2 may have a bug. It seems to have inaccurate results earlier than it should. There is also a possibility this is just a printing issue. Essentially, I wrote a program with float2 and then with big nat and got different results. I am still very much a beginner so I wouldn't be surprised if something else is wrong.

    Float2 version in BQN Repl

    BigNat version Note: does not actually run on web repl, requires cbqn

    Both of these just copied the needed functions from the related .bqn files. The float2 version fails because it generally has slightly off answers that I believe should fit within it's range. This code and test case comes from a rosalind problem where bignat passes, but float2 fails.

    For the current code these are the outputs: float2 - 353368918335207361428 bignat - 353368918335207375428

    2 digits are different here: 61 -> 75

    The final value here has 69 binary digits and is the largest number generated, so I don't think there should be any precision loss with float2.

    opened by bhansconnect 2
Owner
Marshall Lochbaum
Array programmer
Marshall Lochbaum
A water tank level sensor **Built With WisBlock** to detect overflow and low level conditions.

RAK12014 Laser TOF sensor coming soon WisBlock Watertank Level Sensor Watertank Overflow detection using the RAKwireless WisBlock modules. It implemen

Bernd Giesecke 3 Feb 3, 2022
CC2500 Low-Cost Low-Power 2.4 GHz RF Transceiver driver for esp-idf

esp-idf-cc2500 CC2500 Low-Cost Low-Power 2.4 GHz RF Transceiver driver for esp-idf. I ported from this. 2.00mm pitch External Antena 1.27mm pitch PCB

null 3 May 29, 2022
frost is a programming language with a focus on low-friction systems programming.

❄️ frost frost programming language About frost is a programming language with a focus on low-friction systems programming.

null 4 Nov 12, 2021
An AI for playing NES Tetris at a high level. Based primarily on search & heuristic, with high quality board evaluation through value iteration.

StackRabbit An AI that plays NES Tetris at a high level. Primarily based on search & heuristic, with high-quality board eval through value iteration.

Greg Cannon 200 Jun 18, 2022
A list of excellent resources for anyone to deepen their understanding with regards to Windows Kernel Exploitation and general low level security.

WinKernel-Resources A list of excellent resources for anyone trying to deepen their understanding with regards to Windows Kernel Exploitation and gene

Vector Security 36 May 30, 2022
A low level Operating System designed using Linux Kernel

Conqueror A low level Operating System designed using Linux Kernel To develop the basic low level operating system, we need following Virtual Machine

mahendra gandham 8 May 27, 2022
S2-LP driver library, low-level and easy-to-port

S2-LP Library This library provides a simple way to use S2-LP transciever module. This library is WIP, but mostly done. https://www.st.com/en/wireless

Wojciech Olech 2 Feb 26, 2022
Low level library to develop GBA games that can also be built for PC.

Universal GBA Library 1. Introduction This is a library for development of GBA games. It can be used to build actual GBA game ROMs, but it can also ta

Antonio Niño Díaz 31 Jun 25, 2022
Volatile ELF payloads generator with Metasploit integrations for testing GNU/Linux ecosystems against low-level threats

Revenant Intro This tool combines SCC runtime, rofi, Msfvenom, Ngrok and a dynamic template processor, offering an easy to use interface for compiling

Red Code Labs 54 Jun 15, 2022
Tiny - low-level library for minimizing the size of your types

foonathan/tiny Note: This project is currently WIP, no guarantees are made until an 0.1 release. This project is a C++11 library for putting every las

Jonathan Müller 96 May 21, 2022
An extremely basic Python script to split word-based data into high and low byte files.

An extremely basic Python script to split word-based data into high and low byte files. This is for use in programming 16 bit computer ROMs.

null 1 Dec 26, 2021
PLP Project Programming Language | Programming for projects and computer science and research on computer and programming.

PLPv2b PLP Project Programming Language Programming Language for projects and computer science and research on computer and programming. What is PLP L

PLP Language 5 Jun 23, 2022
rlua -- High level bindings between Rust and Lua

rlua -- High level bindings between Rust and Lua

Amethyst Foundation 1.2k Jun 22, 2022
DISLIN is a high-level plotting library developed by Helmut Michels at the Max Planck Institute.

Harbour bindings for DISLIN, is a high level library of subroutines and functions that display data graphically.

Rafał Jopek 2 Dec 10, 2021
Program your micro-controllers in a fast and robust high-level language.

Toit language implementation This repository contains the Toit language implementation. It is fully open source and consists of the compiler, virtual

Toit language 919 Jun 23, 2022
NavMeshComponents - High Level API Components for Runtime NavMesh Building

Status of the project Development This project is now developed as part of the AI Navigation package. Please add that package to your project in order

Unity Technologies 2.5k Jun 27, 2022
A Visual Studio extension that provides enhanced support for editing High Level Shading Language (HLSL) files

HLSL Tools for Visual Studio This extension is for Visual Studio 2017 / 2019. Go here for the Visual Studio Code extension. HLSL Tools is a Visual Stu

Tim Jones 398 Jun 22, 2022
An eventing framework for building high performance and high scalability systems in C.

NOTE: THIS PROJECT HAS BEEN DEPRECATED AND IS NO LONGER ACTIVELY MAINTAINED As of 2019-03-08, this project will no longer be maintained and will be ar

Meta Archive 1.7k Jun 15, 2022
Kit: a magical, high performance programming language, designed for game development

Kit: a magical, high performance programming language, designed for game development

Kit Programming Language 990 Jun 25, 2022