递归

CUE 不允许一般递归，它是 图灵非完备 的。

但是，在 CUE 中仍然有几种不同形式的递归。

结构递归

CUE 不允许循环引用。然而，它不会限制定义无限的结构体，比如说链表或二叉树。

我们称之为结构递归，这个过程在有限的数据上执行。

linked-list.cue

// Definition of an infinite linked list
#List: {
	data: _
	next: #List | *null
	// note, the default to null is required
	// otherwise it looks like a cyclic reference
}

// manually construct a linked list
l: #List & {data: 1, next: #List & {data: 2}}

ds: [1, 2, 4, 8]
// comprehend a linked list from some data
ll: [ for i, d in ds {
	data: d
	if i < len(ds)-1 {
		next: ll[i+1] // note how we reference "future" list elements!
	}
}]

L: ll[0] // we really only want the first element

cue eval linked-list.cue

#List: {
	data: _
	next: null
}

l: {
	data: 1
	next: {
		data: 2
		next: null
	}
}

ds: [1, 2, 4, 8]

ll: [{
	data: 1
	next: {
		data: 2
		next: {
			data: 4
			next: {
				data: 8
			}
		}
	}
}, {
	data: 2
	next: {
		data: 4
		next: {
			data: 8
		}
	}
}, {
	data: 4
	next: {
		data: 8
	}
}, {
	data: 8
}]

L: {
	data: 1
	next: {
		data: 2
		next: {
			data: 4
			next: {
				data: 8
			}
		}
	}
}

有界递归

有界递归是一般递归或生成递归的限定形式。

CUE 的问题所在是一般递归很难或这不可能执行求值器并验证你的 CUE 代码。

有界递归会限制递归的深度，因此问题并不是无解并且在 CUE 的理论下也是被允许的。

这里有关于允许有界递归的讨论：https://github.com/cue-lang/cue/issues/990

与此同时，作为实验，你可以通过推导和函数生成器来模拟有界递归。

你可以在 GitHub/cuetils 这个项目中找到相关代码和例子，以及很多关于 “递归” 的辅助函数，在那你也可以找到函数的 Go 版本。

对于任何正规的使用，强烈建议使用有递归支持的语言。Cuetils 以 Go 包也提供相同的辅助函数，支持 CUE 值作为参数。

当使用 RecurseN 的 CUE 版本和用它构建的“递归”函数时，可能会出现性能问题。

recurse.cue

package r

import "list"

#RecurseN: {
	// this is the bound on our recursion
	#maxiter: uint | *4

	// This is the function list element
	// we generate this to simulate recursion
	#funcFactory: {
		#next: _
		#func: _
	}

	// this is our "recursion unrolling"
	for k, v in list.Range(0, #maxiter, 1) {
		// this is where we build up our indexed functions and the references between them
		#funcs: "\(k)": (#funcFactory & {#next: #funcs["\(k+1)"]}).#func
	}

	// our final value needs to be null
	#funcs: "\(#maxiter)": null

	// we embed the head of the list so that the values
	// we write this into can be used like other CUE "functions"
	#funcs["0"]
}

depth.cue

package r

import "list"

#DepthF: {
	#next: _
	#func: {
		#in:    _
		#basic: int | number | string | bytes | null
		out: {
			// if we have a basic type, we are at a leaf, depth is 1
			if (#in & #basic) != _|_ {1}

			// if we are not a basic type, then we are 1 + the max of children
			if (#in & #basic) == _|_ {
				// this is our "recursion" for each child
				let depths = [ for k, v in #in {(#next & {#in: v}).out}]
				list.Max(depths) + 1
			}
		}
	}
}

#Depth: #RecurseN & {#maxiter: 11, #funcFactory: #DepthF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

d: #Depth & {#in: tree}

注意 let depths = ... 这一行的 {(#next & {#in: v}).out}，这是递归，或者实际上是从一个生成的函数到下一个。

todo, 展示展开的 #Depth 什么样，将会帮助理解。

我们应该明白，这里没有函数、没有调用，也没有递归。

我们真正做的是，将一个未完成的定义然后创建一个排列，让他们指向自己的邻居（#RecurseN 中的 for 推导）。

这是减少代码的方法，但是每个 “函数” 都有他自己的标签和分隔的值。

所以我们本质上可以使用字段推导（for 循环），展开一个 “有界递归” 到 struct 的字段中，然后使用索引的后缀来命名，也因此它们是独立的值。

更多例子：

pick.cue

package r

#pickF: {
	#next: _
	#func: {
		#X: _
		#P: _
		pick: {
			// if P is not a complex type
			if (#P & ({...} | [...])) == _|_ {
				// then take the leaf value if it unifies (note to dev, should there be an if here?)
				#P & #X
			}

			// if P is a complex type
			if (#P & ({...} | [...])) != _|_ {
				// for each field in P
				for i, p in #P {
					let x = #X[i]

					// if they unify (samish type)
					if (x & p) != _|_ {
						// if not a struct, pick the value
						if (x & {...}) == _|_ {
							"\(i)": x
						}

						// if it is a struct, then "recurse"
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

					// if they do not unify
					if (x & p) == _|_ {
						// and if struct, then recurse
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

				}

			}
		}
	}
}

#Pick: #RecurseN & {#funcFactory: #pickF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

P: {
	a: foo: string
	cow: "moo"
}

p: #pick & {#X: tree, #P: P}

package r

#pickF: {
	#next: _
	#func: {
		#X: _
		#P: _
		pick: {
			// if P is not a complex type
			if (#P & ({...} | [...])) == _|_ {
				// then take the leaf value if it unifies (note to dev, should there be an if here?)
				#P & #X
			}

// if P is a complex type
			if (#P & ({...} | [...])) != _|_ {
				// for each field in P
				for i, p in #P {
					let x = #X[i]

// if they unify (samish type)
					if (x & p) != _|_ {
						// if not a struct, pick the value
						if (x & {...}) == _|_ {
							"\(i)": x
						}

// if it is a struct, then "recurse"
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

// if they do not unify
					if (x & p) == _|_ {
						// and if struct, then recurse
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

}

}
		}
	}
}

#Pick: #RecurseN & {#funcFactory: #pickF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

P: {
	a: foo: string
	cow: "moo"
}

p: #pick & {#X: tree, #P: P}

diff.cue

package r

#DiffF: {
	#next: _
	#func: {
		#X: _
		#Y: _
		diff: {
			{
				for i, x in #X {
					let y = #Y[i]
					if y == _|_ {
						"-": "\(i)": x
					}
					if y != _|_ {
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #Y: y}).diff
						}
						if (x & {...}) == _|_ {
							if (x & y) == _|_ {
								"-": "\(i)": x
								"+": "\(i)": y
							}
						}
					}
				}
			}
			"+": {
				for i, y in #Y {
					if #X[i] == _|_ {
						"\(i)": y
					}
				}
			}
		}
	}
}

#diff: #RecurseN & {#funcFactory: #DiffF}

ex: {
	x: {
		a: "a"
		b: "b"
		d: "d"
		e: {
			a: "a"
			b: "b"
			d: "d"
		}
	}
	y: {
		b: "b"
		c: "c"
		d: "D"
		e: {
			b: "b"
			c: "c"
			d: 1
		}
	}
	diff: (#diff & {#X: x, #Y: y}).diff
}

代码生成

默认值

Hofstadter CUE 支持和培训

发布时间: 2024-03-31

编辑本页创建页面 issue 创建项目 issue