Element

A data-oriented language for parallel hardware.

• what: syntax and semantics based on K (and Goal) with implicit multi-core and GPU acceleration
• why: fun?
• how: first build a Python prototype, then implement in CUDA/C++ (or perhaps Zig or Odin?)
• maybe one day: a fast DSL for data-intensive kernels embedded in a distributed system environment like Gleam

PL jargon: array-oriented interpreted functional automatic memory management eager

types

• built-in types - float, integer, string, symbol
• special values - 0w (infinity), 0n (null float), 0N (null integer)
• compound types
  • dict - list of key-value pairs; keys must be symbols, values can be any type
  • list-like
    • vector - 1-dimensional contiguous storage for values of one type e.g: “vector of integers”
    • list - 1-dimensional storage for any types

k crash course

K is a vector language descended from APL, with hints of lisp.

• Expressions evaluate right-to-left.
• Operators have equal precedence, so a*-b+c is a*(-(b+c)).
• Some operators are heavily overloaded based on number and type of their arguments. For example * has just two meanings (for *x and x*y) but ! has 7 variants. These overloaded meanings are usually (but not always) related.
• Iterators like ' (each) / (reduce) and \ (scan) take the place of for/while loops.

 1+2 3 4                  /no-nonsense vectors
3 4 5
 +\(1 2;3 4;5 6)          /iterators modify verbs. "\" is "scan"
(1 2
 4 6
 9 12)
 -1_(+9(|+\)\1 1)1        /first 9 fibonacci numbers
1 1 2 3 5 8 13 21 34
 {-1_(+9(|+\)\1 1)1}[]    /as above, but as a function
 {-1_(+x(|+\)\1 1)1}[9]   /parameterized with default first arg "x"
 f:{-1_(+x(|+\)\1 1)1}[9] /save function to the name "f"
 f'2 8 9                  /apply "f" to each (') item in vector 2 8 9, producing a list of results
(1 1
 1 1 2 3 5 8 13 21
 1 1 2 3 5 8 13 21 34)

typical K features

Most Ks have:

• 1-dimensional vectors, nested lists, dictionaries
• value semantics
• an interpreter
• eager evaluation
• simple scoping rules (names are exclusively local or global)
• basic interaction with the host system
  • \cd to change directory without leaving the interpreter
  • run commands on the host system like \ls, \pwd
  • built-in file and socket I/O
• a method for loading/executing other K scripts
• dynamic typing:
  • no user-defined types
  • atomic types: integer, float, string, symbol (“booleans” use integers 0 and 1)
  • 1-d homogeneous vectors of any of the atomic types
  • implicit numeric promotion: 1+2.0 is 3.0
  • heterogeneous lists containing any type
  • dictionaries with atomic type keys and values of any type
• mutable variables (but operations do not mutate their arguments)
• arithmetic operations defined for single values as well as collections. 1+2 is 3, 1+2 0 3 is 3 1 4
• structural operations on collections. (1 2),`a`b is (1;2;`a;`b)
• right-to-left evaluation, no operator precedence: 2*3+4 is 2*(3+4)
• partial application or “projections” instead of closures: {x+y+z}[1;;3] is {1+x+3}

Element is different from K

There are multiple K dialects with slightly different features. Element is a direct descendant of ngn/k, but there are some differences.

Planned features:

• implicit hardware acceleration by default
  • small data processed on one CPU
  • big irregular data processed on multiple CPUs
  • big regular data processed on GPU
• lexical scope
• closures
• string data type (distinct from “list of char”) as in goal
• keywords:
  • short-circuiting and and or (from goal)
  • in membership test like Python
  • import and export for modules
• In Element, a;b is always two separate expressions evaluated left to right regardless of context. This is most noticeable when you have assignments in lists or function calls. For example (a:3;a+1) is fine in Element but not K.

Aspirational features:

• type annotations {[a:dict;b:int]:int a.f + b}
• dict literal syntax
• mutable value semantics as in Boomla
• REPL-specific:
  • cd function to change directory as in cd "../relative/path"
  • del function to forget a defined variable

Install

Compile for GPU with NVIDIA’s nvcc compiler:

cd element/src && make
./element

Or for CPU with g++:

CPU=1 cd element && make
./element

Why the name “Element”?

• chemistry puns: K is potassium, CUDA (Cu) is copper
• vector languages deal with “elements of a vector” frequently
• naming is hard

Development Roadmap

This project is in the experimental, pre-alpha stage. Some doctest tests exist, but no coverage goals yet. Some unit tests exist in the prototype folder.

prototype implementation [2/4]

• [X] lex/scan/tokenize
• [X] parse
• [-] semantic analysis [3/12]
  • [ ] rank polymorphic verbs
  • [ ] iterators
  • [ ] type checking
  • [-] type inference
    • [X] primitive types (int|float|string|symbol)
    • [X] vec
    • [ ] list
    • [ ] expression
    • [ ] lambda
    • [ ] dict
  • [ ] name binding
  • [ ] function application
  • [ ] variable names and lexical scope
  • [X] composition/projection (2+)1
  • [X] projection ⇒ lambda
  • [X] composition ⇒ lambda
  • [ ] partial application reduction {x+y}[0;] ⇒ {0+x}
  • [ ] errors (mutable, rank, unused, …)
• [ ] code generation [0/5]
  • [ ] tree-walk interpreter
  • [ ] simple arithmetic 1+2
  • [ ] array arithmetic 1 2+3 4
  • [ ] iterators +/1 2 3
  • [ ] structural functions 4 3#!5

hardware accelerated implementation [0/2]

• [ ] full test suite compatibility with prototype
• [ ] benchmarks showing it is faster

stable release(s) [0/5]

• [ ] pick a version numbering system (and stick to it)
• [ ] formal grammar
• [ ] standard library
• [ ] package management
• [ ] documentation, playground, tutorials