Prototype Language Implementation

I originally set out with two primary aims:

1. learning for its own sake
2. address some deficiencies in the programming languages I use

The first one will take care of itself as long as I stay on task. The second one is something I needed to define, so here's the elevator pitch:

A vector-oriented language based on K with transparent multi-core and GPU acceleration.

The longer explanation is that I want to work with tensors and machine learning but Python isn't great at it. Libraries like Jax, PyTorch, and Tensorflow are incredibly useful but not as enjoyable to use as languages which are natively array-oriented (like APL/J/K/Q/BQN/Uiua). I still want to implement machine learning models, just with a more pleasant language.

This leads to some follow-up questions and answers:

1. Pick an implementation language that supports the GPU I have. ⇒ I have an NVIDIA GPU, therefore: CUDA/C++
2. Pick an implementation language that makes multi-core easy. ⇒ no idea
3. Based on K? Find a reference implementation (ideally open-source) to compare against. ⇒ ngn/k

My first attempt involved writing some CUDA C++ code to attempt to do parsing. Being new to CUDA (and coming back to C++ after a long hiatus) this was slow going. Then I took a step back and realized I was trying to do too many unfamiliar things at once.

So rather than dive straight in to the CUDA implementation, I decided to switch gears and do a naive implementation in a more familiar language: Python.

While part of the point of this project is to move away from Python, familiar technology can mitigate some risks. By virtue of being familiar you move a lot of the risks from "unknown" to "known".

Rather than implement all of ngn/k, I wanted to implement some smaller fraction of it. The choice now is what is the smallest fraction that is still useful for a prototype?

For me, the most interesting parts of K are its notation for lambdas and vectors, its support for heterogeneous lists and dictionaries, and its terse ascii-based primitive functions and iterators.

The less interesting parts are:

• interaction with the host system
• imports

Some features I wish it had:

• lexical scope
• closures

I made a checklist and am gradually working through it: [3/6]

• [X] lexical analysis (scanning or tokenizing)
  • [X] names
  • [X] built-in symbols
  • [X] strands
• [X] parsing
  • [X] recognizing unary vs binary symbols
  • [X] juxtaposition is application
  • [X] projections like (2+)
  • [X] compositions like (*-)
  • [X] lambda definitions
  • [X] iterators (or "adverbs")
• [-] semantic analysis
  • [ ] arity checking
  • [ ] enforce immutable/mutable semantics
  • [ ] iterator overloads
  • [X] lambda arguments (implicit) {x}
  • [ ] lambda arguments (explicit) {[a]a}
  • [ ] lambda partial application {z}[1;2;] ⇒ {x}
  • [X] projection ⇒ lambda
  • [X] composition ⇒ lambda
  • [ ] type inference
  • [ ] type-based operator overloads
• [-] evaluation
  • [X] name binding (in scope)
  • [X] name lookup (in scope)
  • [X] lambda definition
  • [X] application
  • [ ] operator overloads
  • [ ] conditionals
  • [ ] iterators
• [ ] runtime environment
  • [ ] pre-defined globals (none)
  • [ ] argument scope 3~a+{y}[a:2;1]
  • [ ] global scope access (interactive vs repl?)
• [X] some unit tests (never truly "done")
  • [X] scan
  • [X] parse
  • [X] semantic analysis
  • [X] eval

Not surprisingly, it's hard to implement part of a scanner so that part is complete. It's possible to implement a partial parser but I finished it anyway because I'm not sure which parts of the language I can omit while still getting a good feeling for what the final version will need.

On the other hand, it's very easy to omit features from the evaluation/runtime part of the project. For example, I know I want to support all the arithmetic operators, all the structural operators, and all the iterators.

But for the prototype I only need to implement one arithmetic operator to get a good sense of how they will all work. The obvious first choice might have been addition, but I chose subtraction because it's not commutative. It's also possible to implement addition in terms of only subtraction: a+b is 0-((0-a)-b), but it's not possible to implement subtraction only in terms of addition (you also need negative numbers), so this universality is also aesthetically appealing in a way I can't quite define.

Similarly, I only need to implement maybe one structural operator to get a good feeling for how all of them should work. Here I chose the join/list operator (,) but I'm not sure if it's the most universal structural primitive, so I will likely implement another like _ or #.

Based on my checklist I know approximately which parts need the most work, and as I make progress I am getting a better sense of which tasks are most essential. Currently I have been working on operator overloads. I have a gut feeling that implementing conditionals will be easy but iterators will be hard.