Nasper
Nasper is a small, native, linearly typed, performant functional programming language. I created this over my time in undergrad, as I was annoyed every time I used a programming language because the semantics in my head, learned from theory, were so much cleaner than what I was forced to write in imperative languages.
At the same time, I was dissatisfied by the lack of hardware awareness in functional languages, which prevented their use in serious engineering endeavors. So I used linear typing and stream/closure monomorphization to create hardware-aware primitives in a language with functional semantics: allowing for the speed of systems programming languages, the nice semantic properties of functional languages, combined together with the craft and simplicity of languages like C or Go (at least of old Go; nowadays Go has lost the Thompson and Pike touch and made some really overly complex decisions).
I was able to achieve some nice results with this language design. The self-hosted compiler bootstraps itself from its own 65,000 lines in 5.5 seconds, including LLVM lowering, clang, and linking, with a warm runtime cache. One thread of the HTTP server on an M5 Pro MacBook handles 225k requests a second over HTTP/1.1 and 852k over HTTP/2, in 4 MB of memory. On the same machine and the same handler, Rust's hyper on one thread does 220k and 772k in 19 MB, Go's net/http 127k and 292k, and Node 132k and 213k. All of this in a language without mutation is pretty cool.
main (streams, print) # A record, and a method that consumes it.# The result type names the case that fails.<account: owner str, balance int> (a account) withdraw(amount int) account ? str from a if amount > a.balance "insufficient funds" <*a, balance int: balance - amount> # An infinite stream: only what is pulled is built.fibs(a int, b int) |int| |int: a, *fibs(b, a + b)| evenSum(count int) int first = streams.take(fibs(0, 1), count) even = streams.filter(first, (x int: x % 2 == 0)) update sum = 0 to sum + e for e in even sum main() acc = <account: owner = "Ada", balance = 100> total = evenSum(20) when acc.withdraw(30) is left print.line("{left.owner}: {left.balance}, {total}") problem print.line("{problem}")Ada: 70, 3382Nasper
range + reductionmain (c, print)
c.cant_optimize(value c.long) c.long
cantOptimize(value int) int
int(cant_optimize(c.long(value)))
range(a int, b int) |int|
if a == b
|int:|
|int: a, *range(a + 1, b)|
sum*() int
update total = 0 to total + cantOptimize(i) for i in range(0, 100)
main()
print.line("{sum()}")_np.sum:
stp x20, x19, [sp, #-32]!
stp x29, x30, [sp, #16]
mov x0, #0
bl _cant_optimize
mov x19, x0
mov w0, #1
LBB317_1:
add x20, x0, #1
bl _cant_optimize
add x19, x0, x19
mov x0, x20
cmp x20, #100
b.ne LBB317_1
mov x0, x19
ldp x29, x30, [sp, #16]
ldp x20, x19, [sp], #32
retC
for loop#include <stdint.h>
extern int64_t cant_optimize(int64_t value);
int64_t sum(void) {
int64_t total = 0;
for (int64_t i = 0; i < 100; i++)
total += cant_optimize(i);
return total;
}_sum:
stp x20, x19, [sp, #-32]!
stp x29, x30, [sp, #16]
mov x20, #0
mov x19, #0
LBB0_1:
mov x0, x20
bl _cant_optimize
add x19, x0, x19
add x20, x20, #1
cmp x20, #100
b.ne LBB0_1
mov x0, x19
ldp x29, x30, [sp, #16]
ldp x20, x19, [sp], #32
retThis is generic machinery with nothing specialized for range in particular. There is a stream lowering algorithm that monomorphizes the stream instances into a non-allocating state machine with static size, and then a state machine lowering algorithm lowers the state machine into nice register-aware loops.
Nasper
main (streams, print)
fibonacci(a int, b int) |int|
|int: a, *fibonacci(b, a + b)|
filter(source |t Any|, keep (&t -> bool)) |t| from source or keep
when source is
|t:| |t:|
|t: head, *tail|
if keep(head)
|t: head, *filter(tail, keep)|
filter(tail, keep)
sumEvenFibonacci*(count int) int
values = filter(streams.take(fibonacci(0, 1), count), (n &int: n % 2 == 0))
update total = 0 to total + n for n in values
main()
print.line("{sumEvenFibonacci(20)}")_np.sumEvenFibonacci:
cmp x0, #1
b.lt LBB324_4
mov x8, x0
mov x10, #0
mov x0, #0
add x8, x8, #1
mov w9, #1
LBB324_2:
add x11, x9, x10
tst x10, #0x1
csel x10, x10, xzr, eq
add x0, x10, x0
sub x8, x8, #1
mov x10, x9
mov x9, x11
cmp x8, #1
b.hi LBB324_2
ret
LBB324_4:
mov x0, #0
retRust
struct Fibonacci {
a: i64,
b: i64,
}
impl Iterator for Fibonacci {
type Item = i64;
fn next(&mut self) -> Option<Self::Item> {
let value = self.a;
(self.a, self.b) = (self.b, self.a + self.b);
Some(value)
}
}
struct Filter<I, P> {
source: I,
keep: P,
}
impl<I, P> Iterator for Filter<I, P>
where
I: Iterator,
P: FnMut(&I::Item) -> bool,
{
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
for item in self.source.by_ref() {
if (self.keep)(&item) {
return Some(item);
}
}
None
}
}
#[unsafe(no_mangle)]
pub fn sum_even_fibonacci(count: usize) -> i64 {
let values = Filter {
source: Fibonacci { a: 0, b: 1 }.take(count),
keep: |n: &i64| n % 2 == 0,
};
let mut total = 0;
for n in values {
total += n;
}
total
}
fn main() {
println!("{}", sum_even_fibonacci(20));
}_sum_even_fibonacci:
mov x8, x0
mov x9, #0
mov x0, #0
mov w10, #1
LBB5_1:
neg x8, x8
LBB5_2:
add x8, x8, #1
cmp x8, #1
b.eq LBB5_5
mov x11, x9
mov x9, x10
add x10, x11, x10
tbnz w11, #0, LBB5_2
add x0, x11, x0
neg x8, x8
b LBB5_1
LBB5_5:
retWhat are this approach's limitations?
Since a stream compiles down to a non-allocating, statically sized state machine optimized for register use, a stream's state must have a finite size that is known at compile time. This means a stream cannot contain itself in the mapped representation, just as a struct cannot contain itself. Streams can contain themselves in the source representation, as fibonacci does above. The distinction:
doubled is wrapped in scaled, whose state holds another doubled, whose tail is wrapped in another scaled. The mapped state has no finite size, so the compiler rejects the spread (E7003).main (streams, print)
# Each tail is fed through scaled, which wraps another doubled:
# the state of doubled would have to hold a scaled over doubled
# over scaled over doubled, without end.
doubled(n int) |int|
if n == 0
|int:|
|int: n, *scaled(doubled(n - 1))|
scaled(source |int|) |int| from source
when source is
|int:| |int:|
|int: head, *tail| |int: head * 2, *scaled(tail)|
main()
print.line("{streams.sum(doubled(3), 0)}")countdown is another countdown. That is the same state continued, not a nested one, so the stream is one loop.main (streams, print)
# The tail is another countdown: the same state, continued.
countdown(n int) |int|
if n == 0
|int:|
|int: n, *countdown(n - 1)|
main()
print.line("{streams.sum(countdown(4), 0)}")rising and falling hand off to each other. Both are entry points into one state, so the pair is still one loop; taking eight elements prints [0, 1, 2, 3, 2, 1, 0, 1].main (streams, print)
# A triangle wave: rising hands off to falling and back.
rising(n int, top int) |int|
if n == top
falling(n, top)
|int: n, *rising(n + 1, top)|
falling(n int, top int) |int|
if n == 0
rising(n, top)
|int: n, *falling(n - 1, top)|
main()
wave = streams.collect(streams.take(rising(0, 3), 8), [int:])
print.line("{wave}")It also means the compiler has to see the shape. A stream built and consumed in the same function, or handed to functions that only pull from it, becomes registers. A stream stored in a record or returned from a function the consumer cannot see through runs as the general state machine instead: the same loop, with its state in stack slots.
main (print) # What this formatter knows, said in terms of itself: an int, a bool, and# a list of known things. The set is closed at compile time, so `known`# is written once and instantiated for every depth the program uses.{Known: int | bool | [Known]} format(value &t Any) [byte] when t is Known known(value) otherwise text([byte:], "unknown") known(value &t Known) [byte] when t is int digits(value, [byte:]) bool text([byte:], flag(value)) [element Known] items(value, 0, [byte: 0x5b]) items(xs &[t Known], at int, out [byte]) [byte] if at >= len(xs) [*out, 0x5d] item = recur known(xs[at]) if at == 0 items(xs, at + 1, text(out, item)) items(xs, at + 1, text(text(out, ", "), item)) digits(n int, out [byte]) [byte] if n < 0 digits(0 - n, [*out, 0x2d]) if n >= 10 high = recur digits(n / 10, out) [*high, byte(48 + n % 10)] [*out, byte(48 + n % 10)] flag(b bool) str if b "true" "false" text(out [byte], s str) [byte] textFrom(out, s, 0) textFrom(out [byte], s str, at int) [byte] if at >= len(s) out textFrom([*out, s[at]], s, at + 1) main() answer = format(42) print.line(answer) yes = format(true) print.line(yes) xs = [int: 1, 2, 3] ones = format(xs) print.line(ones) # four levels deep: four instances of `known`, none written by hand nested = [[[[int]]]: [[[int]]: [[int]: [int: 1, 2], [int: 3]], [[int]: [int: 4]]]] deep = format(nested) print.line(deep) other = format(2.5) print.line(other)42
true
[1, 2, 3]
[[[[1, 2], [3]], [[4]]]]
unknownmain (template, streams, print) # A template keeps its literal text apart from the values in its holes and# hands both to whoever reads it. The reader decides what a hole becomes,# so escaping and parameterization are not something a caller remembers# to do: with this approach they happen by default, because a hole can# only ever be data. # HTML: the literal text is the author's markup, every hole is escapedhtml(page &t Any, index int, out [byte]) [byte] when template.partAt(page, index) is part html(page, index + 1, encoded(out, part)) absent out encoded(out [byte], part template.part) [byte] when part is <template.part: literal as markup> raw(out, markup) <template.part: text as s> escaped(out, s, 0) <template.part: integer as n> digits(n, out) <template.part: boolean as b> raw(out, flag(b)) otherwise raw(out, "?") escaped(out [byte], s str, at int) [byte] if at >= len(s) out b = s[at] if b == 0x3c escaped(raw(out, "<"), s, at + 1) if b == 0x3e escaped(raw(out, ">"), s, at + 1) if b == 0x26 escaped(raw(out, "&"), s, at + 1) if b == 0x22 escaped(raw(out, """), s, at + 1) escaped([*out, b], s, at + 1) # SQL: the literal text is the statement, every hole becomes a placeholder# and a bound parameter; a value never touches the statement text, so# there is no injection to guard against<query: statement [byte], params [[byte]]> sql(text &t Any, index int, q query) query when template.partAt(text, index) is part sql(text, index + 1, bound(q, part)) absent q bound(q query, part template.part) query when part is <template.part: literal as s> <*q, statement [byte]: raw(statement, s)> otherwise <*q, statement [byte]: [*statement, 0x3f], params [[byte]]: [*params, rendered(part)]> rendered(part template.part) [byte] when part is <template.part: text as s> raw([byte:], s) <template.part: integer as n> digits(n, [byte:]) <template.part: boolean as b> raw([byte:], flag(b)) otherwise raw([byte:], "?") digits(n int, out [byte]) [byte] if n < 0 digits(0 - n, [*out, 0x2d]) if n >= 10 high = recur digits(n / 10, out) [*high, byte(48 + n % 10)] [*out, byte(48 + n % 10)] flag(b bool) str if b "true" "false" raw(out [byte], s str) [byte] update grown = out to [*grown, s[i]] for i in streams.range(0, len(s)) main() name = "<script>alert(1)</script>" page = html("<p>Hello, {name}</p>", 0, [byte:]) print.line(page) city = "Paris'; DROP TABLE users; --" age = 21 q = sql("SELECT name FROM users WHERE city = {city} AND age > {age}", 0, <query: statement = [byte:], params = [[byte]:]>) print.line(q.statement) print.line(q.params[0]) print.line(q.params[1])<p>Hello, <script>alert(1)</script></p>
SELECT name FROM users WHERE city = ? AND age > ?
Paris'; DROP TABLE users; --
21Nasper
main (print)
<page: title str, body str>
# a view into the page: `from` names where the bytes live
title(p &page) str from p
p.title
# the longer of two views, from either
longer(a str, b str) str from a or b
if len(a) >= len(b)
a
b
# a view into a view
firstWord(text str) str from text
text[0:wordEnd(text, 0)]
wordEnd(text str, at int) int
if at >= len(text) or text[at] == 0x20
at
wordEnd(text, at + 1)
main()
p = <page: title = "Nasper streams", body = "compile to loops">
print.line(firstWord(longer(title(p), p.body)))Rust
struct Page<'a> {
title: &'a str,
body: &'a str,
}
// a view into the page: a &Page carries two lifetimes, so the
// result has to say it borrows the page's text, not the reference
fn title<'a>(p: &Page<'a>) -> &'a str {
p.title
}
// the longer of two views, from either: two inputs, so the
// lifetime has to be written out
fn longer<'a>(a: &'a str, b: &'a str) -> &'a str {
if a.len() >= b.len() { a } else { b }
}
// a view into a view
fn first_word(text: &str) -> &str {
text.split(' ').next().unwrap_or(text)
}
fn main() {
let p = Page { title: "Nasper streams", body: "compile to loops" };
println!("{}", first_word(longer(title(&p), p.body)));
}A returned view says where its bytes live: from p, from a or b. That is the whole annotation. Values that own their bytes need nothing at all.
Nasper
tail callmain (c, print)
c.cant_optimize(value c.long) c.long
cantOptimize(value int) int
int(cant_optimize(c.long(value)))
sum*() int
sumFrom(0, 0)
sumFrom(i int, total int) int
if i == 100
total
sumFrom(i + 1, total + cantOptimize(i))
main()
print.line("{sum()}")_np.sum:
stp x20, x19, [sp, #-32]!
stp x29, x30, [sp, #16]
mov x0, #0
mov x19, #0
LBB317_1:
add x20, x0, #1
bl _cant_optimize
add x19, x0, x19
mov x0, x20
cmp x20, #100
b.ne LBB317_1
mov x0, x19
ldp x29, x30, [sp, #16]
ldp x20, x19, [sp], #32
retC
for loop#include <stdint.h>
extern int64_t cant_optimize(int64_t value);
int64_t sum(void) {
int64_t total = 0;
for (int64_t i = 0; i < 100; i++)
total += cant_optimize(i);
return total;
}_sum:
stp x20, x19, [sp, #-32]!
stp x29, x30, [sp, #16]
mov x20, #0
mov x19, #0
LBB0_1:
mov x0, x20
bl _cant_optimize
add x19, x0, x19
add x20, x20, #1
cmp x20, #100
b.ne LBB0_1
mov x0, x19
ldp x29, x30, [sp, #16]
ldp x20, x19, [sp], #32
retWhat if I need non-tail recursion?
Write recur in front of the call. A call that is not in tail position, or that closes a cycle between functions, is marked so the reader sees the loop and the compiler checks that it terminates along a decreasing path. Everything else is a jump.
Nasper
main (os, print, streams)
# p(n), the number of ways to write n as a sum of positive integers, by
# Euler's pentagonal recurrence. Every earlier value is read back, so
# the table has to exist; nothing keeps it after the answer, so the
# compiler gives it a stack region instead of the heap.
partitions(n int) int
table = build([int: 1], n)
table[n]
build(table [int], n int) [int]
if len(table) > n
table
next = term(table, len(table), 1, 0)
build([*table, next], n)
# the k-th pair of pentagonal terms of p(i), with Euler's alternating sign
term(table &[int], i int, k int, acc int) int
g1 = k * (3 * k - 1) / 2
if g1 > i
acc
both = table[i - g1] + earlier(table, i - k * (3 * k + 1) / 2)
if k % 2 == 1
term(table, i, k + 1, (acc + both) % 1000000007)
term(table, i, k + 1, (acc - both + 1000000007) % 1000000007)
earlier(table &[int], at int) int
if at < 0
0
table[at]
total(rounds int, n int) int
update acc = 0 to (acc + partitions(n)) % 1000000007 for r in streams.range(0, rounds)
main()
args = os.args()
rounds = parseDecimal(args[0], 0, 0)
n = parseDecimal(args[1], 0, 0)
droppedArgs = args
print.line(total(rounds, n))
parseDecimal(text &[byte], at int, acc int) int
if at >= len(text)
acc
parseDecimal(text, at + 1, acc * 10 + int(text[at]) - 48)Rust
// p(n) by Euler's pentagonal recurrence. The table is built, read back
// at every step, and dropped: one heap allocation per call.
fn partitions(n: usize) -> i64 {
let mut table: Vec<i64> = vec![1];
for i in 1..=n {
let mut acc = 0i64;
let mut k = 1usize;
loop {
let g1 = k * (3 * k - 1) / 2;
if g1 > i {
break;
}
let g2 = k * (3 * k + 1) / 2;
let both = table[i - g1] + if g2 <= i { table[i - g2] } else { 0 };
acc = if k % 2 == 1 { (acc + both) % 1_000_000_007 } else { (acc - both + 1_000_000_007) % 1_000_000_007 };
k += 1;
}
table.push(acc);
}
table[n]
}
fn total(rounds: i64, n: usize) -> i64 {
(0..rounds).fold(0, |acc, _| (acc + partitions(n)) % 1_000_000_007)
}
fn main() {
let rounds: i64 = std::env::args().nth(1).and_then(|s| s.parse().ok()).unwrap_or(20);
let n: usize = std::env::args().nth(2).and_then(|s| s.parse().ok()).unwrap_or(8);
println!("{}", total(rounds, n));
}The table never leaves partitions, so the compiler proves it can live in a stack region. The whole function makes these runtime calls, np_rt_list_free, np_rt_list_new, np_rt_push, np_rt_scratch_enter, np_rt_scratch_leave: a region is opened, the table grows in it, the region is closed. No allocator ever sees it. Rust puts the same table on the heap, once per round, and pays malloc and free for it. 1,000,000 rounds of p(40), same answer: Nasper 0.608 s, Rust 0.695 s.
main (print) # Anything with these two methods is a Discount. Nothing declares it,# no record names it, and a value of the class is just the record.{Discount: (&self) apply(price int) int, (&self) label() str} <percentOff: off int> (d &percentOff) apply(price int) int price - price * d.off / 100 (d &percentOff) label() str "member price" <fixedOff: amount int> (d &fixedOff) apply(price int) int if d.amount > price 0 price - d.amount (d &fixedOff) label() str "coupon" <fullPrice:> (d &fullPrice) apply(price int) int price (d &fullPrice) label() str "full price" # the rule is picked at run time; the return type is the anonymous union# of the three records, decided here, and each call below dispatches on# it without a table or a boxed objectruleFor(member bool, coupon int) Discount if coupon > 0 <fixedOff: amount = coupon> if member <percentOff: off = 10> <fullPrice:> charge(price int, member bool, coupon int) int rule = ruleFor(member, coupon) due = rule.apply(price) print.line("{rule.label()}: {price} -> {due}") due main() total = charge(200, true, 0) + charge(200, false, 30) + charge(200, false, 0) print.line(total)member price: 200 -> 180
coupon: 200 -> 170
full price: 200 -> 200
550main (format, os) <point: x int, y int> main() name = "Ada" p = <point: x = 3, y = 4> xs = [int: 1, 2, 3] # A string with holes is a template; the holes take expressions. line = format.bytes("{name} is at ({p.x}, {p.y}), {len(xs)} steps in") # append consumes the buffer and hands it back, grown. line = format.append(line, "; ratio {7.0 / 2.0}, done {true}\n") shown = os.puts(line[:]) # Records, lists and dictionaries render on their own; a hole borrows them. ages = [str -> int: "Ada" -> 36] row = format.bytes("{p} {xs} {ages}\n") os.puts(row[:])Ada is at (3, 4), 3 steps in; ratio 3.5, done true
<point: x = 3, y = 4> [1, 2, 3] ["Ada" -> 36]I haven't released it publicly, but as you can see above, there is a working early stage compiler and some immature libraries for common web operations (this website's backend is hosted in Nasper, for example). I am not releasing the source at the moment due to AI cybersecurity risk. It is not obvious to me that it is safe to publish code on the internet without access to frontier cybersecurity models and a team pushing updates with those models as the risk continues to grow—though I could be convinced to change my mind on that.
Email me if you want to use it: jacobalbertschmidt@gmail.com