Can I write the Fibonacci sequence in cue?

[Peefy]

What version of CUE are you using (cue version)?

$ cue version
cue version v0.4.3 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

For the following code snippet (fib.cue), I run with cue export fib.cue

#Fib: {
    n: int,
    if n <= 2 {
        value: 1
    }
    if n > 2 {
        _n1: #Fib & {
            n: n - 1
        },
        _n2: #Fib & {
            n: n - 2
        }
        value: _n1.value + _n2.value
    }
}
fib8: #Fib & {
    n: 8
}

What did you expect to see?

{
    "fib8": {
        "n": 8,
        "value": 21
    }
}

What did you see instead?

cycle error:
    ../fib.cue:3:8
cycle error:
    ../fib.cue:6:8

It seems that for #Fib in different positions, cue treats them as the same instance?

[eadlam]

fib.cue

import (
    "strconv"
)

#Fib: {
    n: int
    value: #fib["\(n)"].val

    #seq: [int] * (n + 1)
    #fib: [Num=string]: {
        val: int

        let N = strconv.Atoi(Num)
        if N < 2 {
            val: N
        }
        if N >= 2 {
            val: #fib["\(N-1)"].val + #fib["\(N-2)"].val
        }
    }
    for idx, i in #seq {
        #fib: "\(idx)": _
    }
}

fib8: #Fib & {
    n: 8
}

cli

$ cue export fib.cue
{
    "fib8": {
        "n": 8,
        "value": 21
    }
}

[verdverm]

Generally speaking, you cannot do general recursion in CUE. This is an intentional limitation, to be Turing Incomplete, hence the cycle errors you are getting.

You can use an iterative method or the direct calculation like: https://github.com/hofstadter-io/cuetorials.com/blob/main/code/patterns/recursion/fib.cue

One problem with iterated solutions like these is the back references to previous list entries causing performance issues: #1795

[eadlam]

@verdverm, good point about the back reference. My answer above takes ~6 seconds on my machine if n=10000. However this iterated solution only takes ~0.5 second for n=10000. Perhaps by calculating forward, every dependency is already resolved, and thus doesn't need to unify a large graph? It's also much simpler:

import (
    "list"
)

#Fib: {
    n: int
    #seq: [for i in list.Range(0, n + 1, 1) {
        if i < 2 {
            i
        }
        if i >= 2 {
            #seq[i-1] + #seq[i-2]
        }
    }]
    value: #seq[n]
}

fib8: #Fib & {
    n: 10000
}

[verdverm]

My final version, seems my method reaches the limits of floating point accuracy

import (
	"list"
	"math"
)

_num: float | *23.0 @tag(N,type=number)

_s5:  math.Pow(5.0, 0.5)
_Phi: (_s5 + 1.0) / 2.0
_phi: _Phi - 1.0

#FibN: {
	n: number
	f: math.Round((math.Pow(_Phi, n) - math.Pow(_phi, n)) / _s5)
}

#Fib1: {
    n: number
    #seq: [for i in list.Range(0, n + 1, 1) {
        if i < 2 {
            i
        }
        if i >= 2 {
            #seq[i-1] + #seq[i-2]
        }
    }]
    value: #seq[n]
		l: len(#seq)
}
#Fib2: {
    n: number
    #seq: [ for i, I in list.Range(1, n+1, 1) { (#FibN & {n: I}).f } ]
    value: #seq[n-1]
		l: len(#seq)
}

fibN: (#FibN & {n: _num}).f
fib1: (#Fib1 & { n: math.Round(_num) }).value
fib2: (#Fib2 & { n: math.Round(_num) }).value

if you remove the .value suffix on those last 2 lines, you can see the entire sequences

[verdverm]

I'm curious if CUE, with the plan for arbitrary decimals, should not lose accuracy in this example (cc @mpvl @myitcv)

$ cue export fib.cue -t N=200.0
{
    "fibN": 280571172992510140037722000000000000000000,
    "fib1": 2.80571172992510140037617E+41,
    "fib2": 280571172992510140037722000000000000000000
}

// 280571172992510140037722
// 280571172992510140037617

[Peefy]

Thank you for all, very amazing solutions.

[mpvl]

@Peefy to take a step back: a core design principle in CUE is that computation and configuration should be strictly separated. In general, computation is better handled by a programming language. Also, the whole point of a configuration language is that there are benefits to declarative specification. From experience we know that specifying computation in a configuration language, and intermixing the two, results in a rather unmaintainable mess.

That said, we also know that, in practice, it is not possible to exclude computation from the configuration layer. Another approach is to allow users to specify their own functions, not unlike CUE's builtin functions, written in a programming language of choice. We plan to move into this direction with CUE.

The aim here is to keep CUE relatively simple and move the complexity to functions, not unlike how spreadsheets work.

We believe that wrapping computation with configuration, rather than wrapping data and configuration with computation, is a much more useful paradigm.

[Peefy]

@mpvl. Thanks for your answer. I'm very much in favor of separating the configuration data itself from the computational logic. In addition, using a programming language to write CUE functions sounds like a very cool thing, maybe it is a language such as Go, Python, etc. ? I am very much looking forward to it.