Re:Primitive Recursive Functions for a Working Programmer
by 4ad on Sunday August 04, 2024 @07:11AM
(#41152727)
> Cue has no functions so there is nothing to recurse.
CUE developer here. This is wrong. CUE doesn't have functions, but it does have abstraction and beta-reduction, just like lambda calculus. Types can refer to themselves. There is also mutual recursion between types. We have a termination checker than ensures CUE programs are total (although it works by very different principles compared to other total languages).
If you disable the CUE termination checker you get a a Turing complete language.
CUE developer here. This is wrong. CUE doesn't have functions, but it does have abstraction and beta-reduction, just like lambda calculus. Types can refer to themselves. There is also mutual recursion between types. We have a termination checker than ensures CUE programs are total (although it works by very different principles compared to other total languages).
If you disable the CUE termination checker you get a a Turing complete language.
If you leave it alone you get a primitive recursive language. Here is CUE implementing an arbitrary number of steps of rule 110 cellular automaton[1], which is Turing complete: https://cuelang.org/play/?id=Ityqia88Mvq#w=function&i=cue&f=...
[0] https://en.wikipedia.org/wiki/Rule_110