Return to Answer

[A draft for Build a Turing *incomplete* language]

[A draft for the expansion of a deleted answer in Build a Turing *incomplete* language]

This is the full list of predefined macros (it's possible to see that only __DATE__, __TIME__ and __TIMESTAMP__ are not deterministic. Remark: defining SOURCE_DATE_EPOCH will not affect the __TIMESTAMP__)

The directives that can read the hard drive is #include, #include_next and #import.

This is the full list of directives.

[A draft for https://codegolf.stackexchange.com/questions/204891/build-a-turing-incomplete-language]

#define a() X b()
#define b() X a()

$M($M(f, f(args)))
$M(f, f(f(args)))
f, f(f(f(args)))

Then, use the previous macro $P to evaluate $M $n$ times on f, args..., and it's possible to get f applied on args... $n$ times.

[A draft for Build a Turing *incomplete* language]

#define a() X b()
#define b() X a()

$M($M(f, f(args)))
$M(f, f(f(args)))
f, f(f(f(args)))

Then, use the previous macro $P to evaluate $M $n$ times on f, args..., and it's possible to get f applied on args... $n$ times.

At the moment, it's possible to use $P to implement the multiplication function:

#define mul_1(x,y) x y, y
#define mul(x,y) $P(x,mul_1, ,y)

In this example, mul_1 is repeatedly applied on the argument (<empty>, y) $x$ times. For each application, mul_1 transforms (accumulator, y) to (accumulator+y, y); therefore after $x$ iterations the result is (x*y, y).

Let's say, you want to implement a function that uses $P based on another function that uses $P.

#define add(x,y) x y
#define pre_1(x,y) y,y()
#define pre(x) $P(x,pre_1,,) // <-- this function uses `$P`
#define sub(x,y) $P(y,pre,x) // <-- this function uses `pre`
// similar to the implementation of subtraction using pair in lambda calculus
// returns x-y if x>=y, 0 otherwise.
// (terribly inefficient.)

This will immediately raises a problem -- the inner $P is not expanded.

Which makes sense, because the inner $P is created during the expansion of the outer $P.

There's a trivial workaround for that problem, however -- define a function $P2 with the same definition as $P (and its helper functions)

This restriction makes sense, because cpp is not Turing-complete and it should not be possible for two functions to call each other.

Some example functions

With these tools, it should not be too hard to build some simple functions. Ideas from lambda calculus should be useful here.

#define equ(x,y) sub((),sub(x,y) sub(y,x))
// return 1 == () if x and y are equal, 0 == <empty> otherwise.

#define modz_1(result, x, y, value) result equ(x, i), x, y, y value
// modz_1(result, x, y, value) = (result + [x == value], x, y, value + y)
// x and y are the dividend and the divisor.
// value iterates through the first x positive multiples of y,
// and check if any of them are equal to x.

#define modz(x,y) $P3(x,modz_1,,x,y,y)
// returns 1 if x is a multiple of y, 0 otherwise.
// apply modz_1 on (0, x, y, y) x times, then return the first value of the result.

[A draft for https://codegolf.stackexchange.com/questions/204891/build-a-turing-incomplete-language]

While it's sufficient to provide an implementation of some basic arithmetic operations, I'd like to explain the method in more details.

Input-dependent computation

In order to make the program powerful enough, it must be possible to make the amount of computation dependent on the size of the input.

This can be achieved by encoding a natural number $n$ as a sequence of $n$ pair of brackets ()()()...()()().

So if there are two macros defined like this (there must be two to avoid it being blue-painted)

#define a() X b()
#define b() X a()

Then a()()...()() will expand to X X ... X X a.

It's usually convenient to remove the last a. That can be done by pasting the whole thing with something like _delete_this and #define a_delete_this.

Repeated fixed function call

Let x be a parameter, with its value being a sequence of $n$ ()s.

Then it's possible to generate f( repeated $n$ times and ) repeated $n$ times.

With some simple manipulation, it's not hard to define some macro $P(n, args...) to expand to f(f(...(f(args))...)) for a fixed function f.

Repeated dynamic function call

Unfortunately, this technique alone won't be able to implement $P(n, f, args...) = f(f(...(f(args))...)).

(this is not necessary for the computations, but it's more convenient this way)

Define an auxiliary macro $M: $M(f, args...) expands to f, f(args).  (note that args... is a GNU CPP extension)

[A draft for https://codegolf.stackexchange.com/questions/204891/build-a-turing-incomplete-language]

While it's sufficient to provide an implementation of some basic arithmetic operations, I'd like to explain the method in more details.

Input-dependent computation

In order to make the program powerful enough, it must be possible to make the amount of computation dependent on the size of the input.

This can be achieved by encoding a natural number $n$ as a sequence of $n$ pair of brackets ()()()...()()().

So if there are two macros defined like this (there must be two to avoid it being blue-painted)

#define a() X b()
#define b() X a()

Then a()()...()() will expand to X X ... X X a.

It's usually convenient to remove the last a. That can be done by pasting the whole thing with something like _delete_this and #define a_delete_this.

Repeated fixed function call

Let x be a parameter, with its value being a sequence of $n$ ()s.

Then it's possible to generate f( repeated $n$ times and ) repeated $n$ times.

With some simple manipulation, it's not hard to define some macro $P(n, args...) to expand to f(f(...(f(args))...)) for a fixed function f.

Repeated dynamic function call

Unfortunately, this technique alone won't be able to implement $P(n, f, args...) = f(f(...(f(args))...)).

(this is not necessary for the computations, but it's more convenient this way)

Define an auxiliary macro $M: $M(f, args...) expands to f, f(args). 

(note that args... is a GNU CPP extension; however this is only for convenience, all usages of it can be replaced with the standard __VA_ARGS__ identifier)

Observe that $M($M($M(f, args...))) will expands to:

$M($M(f, f(args)))
$M(f, f(f(args)))
f, f(f(f(args)))

Taking the second argument will result in f(f(f(args))).

In reality, some defer/eval is required to make the expression expands correctly.

Then, use the previous macro $P to evaluate $M $n$ times on f, args..., and it's possible to get f applied on args... $n$ times.

Blue-painting/Recursion