I decided to make a programming language in macro_rules!.
Some things I learned:
Things I learned
- I learned about how macros are matched with literal prefixes.
- I learned about how to do the continuation passing style in macros using explicit commands.
- I learned that macros aren't all like C macros.
And here is the code:
The code
#![recursion_limit = "4096"]
#![feature(macro_metavar_expr)]
macro_rules! mulang {
// entry
(program {
$code:tt
}) => {
mulang!(
@eval
$code
[]
()
@k
[@print [] ()]
);
};
// choosing
(@eval (repeat $n:tt $x:tt $f:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $n $p $e @k [@repeat_num $x $f $p $e @k [$($c)*]]);
};
(@eval (par $level:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $level $p $e @k [@par_level $p $e @k [$($c)*]]);
};
(@eval (define $body:tt $input:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $input $p $e @k [@define_input $body $p $e @k [$($c)*]]);
};
(@eval (- $a:tt $b:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $a $p $e @k [@sub_left $b $p $e @k [$($c)*]]);
};
(@eval (let_in $x:ident $val:tt $body:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $val $p $e @k [@bind_let $x $body $p $e @k [$($c)*]]);
};
(@eval (var $var:ident) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@lookup $var $e @k [$($c)*]);
};
(@eval (n $($digits:tt)*) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@convert [] [$($digits)*] $p $e @k [$($c)*]);
};
(@eval (+ $a:tt $b:tt) $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!(@eval $a $p $e @k [@add_left $b $p $e @k [$($c)*]]);
};
(@eval $incomplete:tt $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!($($c)* $incomplete);
};
// intermediate
(@repeat_num $x:tt $f:tt $p:tt $e:tt @k [$($c:tt)*] $n:tt) => {
mulang!(@eval $x $p $e @k [@repeat_x $f $n $p $e @k [$($c)*]]);
};
(@repeat_x $f:tt $n:tt $p:tt $e:tt @k [$($c:tt)*] $x:tt) => {
mulang!(@eval $f $p $e @k [@repeat_f $n $x $p $e @k [$($c)*]]);
};
(@repeat_f [] $x:tt $p:tt $e:tt @k [$($c:tt)*] $f:tt) => {
mulang!(@inert $x @k [$($c)*]);
};
(@repeat_f $n:tt $x:tt $p:tt $e:tt @k [$($c:tt)*] ($($f:tt)*)) => {
mulang!(@eval (repeat (- $n (n 1)) ($($f)* $x) ($($f)*)) $p $e @k [$($c)*]);
};
(@par_level [$($p_inner:tt)*] $e:tt @k [$($c:tt)*] $idx:tt) => {
mulang!(@par_lookup $idx [$($p_inner)*] @k [$($c)*]);
};
(@par_lookup [] [$v:tt $($rest:tt)*] @k [$($c:tt)*]) => {
mulang!($($c)* $v);
};
(@par_lookup [() $($idx_rest:tt)*] [$_:tt $v:tt $($rest:tt)*] @k [$($c:tt)*]) => {
mulang!(@par_lookup [$($idx_rest)*] [$v $($rest)*] @k [$($c)*]);
};
(@par_lookup [() $($idx_rest:tt)*] [] @k [$($c:tt)*]) => {
compile_error!("de Bruijn index out of bounds");
};
(@define_input $body:tt [$($p:tt)*] $e:tt @k [$($c:tt)*] $input:tt) => {
mulang!(@eval $body [$input $($p)*] $e @k [$($c)*]);
};
(@sub_left $right:tt $p:tt $e:tt @k [$($c:tt)*] $left:tt) => {
mulang!(@eval $right $p $e @k [@sub_right $left $p $e @k [$($c)*]]);
};
(@sub_right [$($A:tt)*] $p:tt $e:tt @k [$($c:tt)*] [$($B:tt)*]) => {
macro_rules! _sub {
() => {
mulang!($($c)* []);
};
($$aefore:tt $$($$a:tt)*) => {
macro_rules! _sub2 {
() => {
mulang!($($c)* [$$aefore $$($$a)*]);
};
($$$$before:tt $$$$($$$$b_final:tt)*) => {
mulang!(@sub_right [$$($$a)*] $p $e @k [$($c)*] [$$$$($$$$b_final)*]);
};
};
_sub2!($($B)*);
};
}
_sub!($($A)*);
};
(@lookup $var:ident () @k [$($c:tt)*]) => {
compile_error!(concat!("unbound variable '", stringify!($var), "'"))
};
(@lookup $var:ident (($name:ident $val:tt) $($rest:tt)*) @k [$($c:tt)*]) => {
macro_rules! _cmp {
($var, [$$found:tt]) => { mulang!($($c)* $$found); };
($_other:ident, [$_miss:tt]) => {
mulang!(@lookup $var ($($rest)*) @k [$($c)*]);
};
}
_cmp!($name, [$val]);
};
(@bind_let $x:ident $body:tt $p:tt $e:tt @k [$($c:tt)*] $v:tt) => {
mulang!(@eval $body $p (($x $v) $e) @k [$($c)*]);
};
(@add_left $right:tt $p:tt $e:tt @k [$($c:tt)*] $left:tt) => {
mulang!(@eval $right $p $e @k [@add_right $left $p $e @k [$($c)*]]);
};
(@add_right [$($left:tt)*] $p:tt $e:tt @k [$($c:tt)*] [$($right:tt)*]) => {
mulang!($($c)* [$($left)* $($right)*]);
};
(@convert [$($acc:tt)*] [$first:tt $($rest:tt)*] $p:tt $e:tt @k [$($c:tt)*]) => {
macro_rules! _choose {
(0, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)*] [$($rest)*] $p $e @k [$($c)*]);};
(1, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* ()] [$($rest)*] $p $e @k [$($c)*]);};
(2, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () ()] [$($rest)*] $p $e @k [$($c)*]);};
(3, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(4, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(5, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(6, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(7, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(8, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () () () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
(9, [$$($$before:tt)*]) => { mulang!(@convert [$$($$before)* () () () () () () () () ()] [$($rest)*] $p $e @k [$($c)*]);};
}
_choose!($first, [$($acc)* $($acc)* $($acc)* $($acc)* $($acc)* $($acc)* $($acc)* $($acc)* $($acc)* $($acc)*]);
};
(@convert [$($acc:tt)*] [] $p:tt $e:tt @k [$($c:tt)*]) => {
mulang!($($c)* [$($acc)*]);
};
// exit
(@print $p:tt $e:tt [$($t:tt)*]) => {
println!("{}", (&[$($t),*] as &[()]).len());
};
// special
(@inert $item:tt @k [$($c:tt)*]) => {
mulang!($($c)* $item);
};
(@output $item:tt) => {
$item
};
}
Main function example:
fn main() {
mulang!(program {
(let_in f (define (+ (par (n 0)) (n 2)))
(repeat (n 5) (n 0) (var f)))
}); // Result is 10
}
If you are wondering what this does:
- It defines a function that adds 2 to what you give and names it f
- and repeats that function f 5 times on 0, giving 10
The way this works is using continuation passing style, that is the main core piece of this interpreter.
The interpreter doesn't generate equivalent rust code. Instead it is executed with macro expansion. The only time when rust code is generated is with stdout.
Here is the spec:
The spec
µlang is a functional programming language that is written in a macro.
This is how to use µlang:
(n digits...)makes a unary number from the digits written- aka
(n 2)turns into[() ()]and(n 1 0)turns into[() () () () () () () () () ()]
- aka
(+ x y)adds two numbers together(- x y)subtracts two numbers(var name)looks up the name of the variable and returns it(let_in name value body)adds a variable to the lookup table of the body and runs the body(define body input)calls body with input(par num)gets the De Bruijn indexed parameter of the defines(repeat n x f)runs f(f(...x)) where the number of f's is nprogram {...}starts the actual execution
The most important part of this language is incomplete expressions.
Incomplete expressions (IE) are expressions that dont have all of their inputs, for instance(+ (n 5))is an IE, functions are also IE when they don't have their input parameter, I am planning on making default "incomplete" expressions just like there is ticked expressions in lisp, but right now, that's all there is.
Here are some more examples of IE:
(- (n 3))
(define (- (par (n 0)) (n 3)))
(repeat (n 3) (n 0))