Element

Combining the most delightful parts of K with good ideas from functional and mainstream programming languages.

• What: a close descendant of K (and Goal) with implicit multi-core/GPU acceleration.
• Why: fun?
• How: Python prototype, then “for real” in CUDA/C++ (or perhaps Zig or Odin?)
• Dream: a fast DSL for data-intensive kernels embedded in a distributed system environment like Gleam.

types

• base types - int, float, string, symbol
• compound types
  • list-like
    • tensor - same type, N dimensional
    • vector - same type, 1 dimensional (simplest tensor)
    • list - any types, any shape
  • dict-like
    • table - keys (column names) are symbols, values are same-shape vectors
    • dict - keys are any fundamental type, values are arbitrary

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
• 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
• x:y assign (immutable) variable
• x::y assign (mutable) variable
• No modified assignment operators. Use a::a+1 instead of a+:1. Meanwhile, verb-plus-colon still invokes the unary version of that verb, so a-:1 is a (- 1).
• Lists and function arguments evaluate left-to-right, top-to-bottom. For example, f[a+b;a:1;b:2] or (a+b;a:1;b:2) are valid in K but not in Element. In Element, a;b always parses as two separate expressions evaluated left to right regardless of being wrapped in any kind of parentheses. Alternatives: use a:1;b:2;(a+b;a;b) or 2_(a:1;b:2;a+b;a;b).

Aspirational features:

• module system: require x, provide x
• \cd etc. provided by REPL, not runtime

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.

[0/3]

• [-] prototype implementation
  • [X] lex/scan/tokenize
  • [X] parse
  • [-] semantic analysis
    • [ ] verbs
    • [ ] iterators
    • [ ] type checking
    • [-] type inference
      • [X] (int|float|string|symbol)
      • [X] vec of (int|float|string|symbol)
      • [X] list
      • [ ] tensor
      • [ ] dict
      • [ ] table
    • [X] name binding
    • [X] function application
    • [X] variable names and lexical scope
    • [X] composition/projection (2+)1
    • [X] projection ⇒ lambda
    • [ ] composition ⇒ lambda
    • [ ] errors (mutable, rank, unused, …)
  • [-] codegen
    • [X] tree-walk interpreter
    • [X] simple arithmetic 1+2
    • [X] array arithmetic 1 2+3 4
    • [ ] iterators +/1 2 3
    • [ ] structural functions =3#”hi”“world”=
• [-] hardware accelerated implementation
  • [X] lex/scan/tokenize
  • [ ] parse
  • [ ] semantic analysis
  • [ ] optimization
  • [ ] codegen
• [ ] stable release(s)
  • [ ] pick a version numbering system (and stick to it)
  • [ ] formal grammar
  • [ ] standard library
  • [ ] package management
  • [ ] documentation, playground, tutorials