维基函数:函数模型
维基函数是函数的多语言目录，任何人都可以参与其中，任何人都可以创建、维护、调用和使用函数。 每个函数可以有多种实现，例如使用不同的编程语言或使用不同的算法。 它是一个“功能的维基百科”，也是维基媒体基金会的一个姊妹项目。
本文档涵盖了维基函数的数据模型和评估模型。
Z1/Z 对象
维基函数是一个维基。与所有维基中一样，维基函数主要存于维基页面中。 维基页面可以单独编辑，但整个项目必须保持某种一致性。 此外，维基页面应可单独编辑，而不必了解所有其他页面。
我们引入 Z 对象来表示维基函数的内容。 维基函数主命名空间的每个维基页面都严格包含一个类型为 Z2/持久的对象 Z 对象。 其他命名空间可以包含其他内容，如策略页、用户页、讨论页等。 一个 Z 对象可被序列化为一个 JSON 对象。
一个 Z 对象由一系列键/值对组成。
- 键/值对中的每个值均为一个 Z 对象。
- 值既可以是一个 Z6/字符串，一个 Z9/引用，还可是任何其他类型。Z6/字符串和 Z9/引用被称作终端值。它们不会进一步扩展。
- Z6/字符串对象有二键，Z1K1/类型对象值为“Z6”，和 Z6K1/字符串对象的值，一个任意字符串。
- 一个 Z9/引用有两个键：值为“Z9”的Z1K1/类型和 Z9K1/引用编号，代表一个 Z 编号的一个字符串。
- 每个键只能在每个 Z 对象上出现一次（但可能在一个嵌入的 Z 对象上再次出现）。
Z 对象基本上是抽象句法树。 如果该项目有一简介，那可能是“如同 JSON 中的 LISP”。 我们的目标是提供一简易用户研究以允许通过一个维基界面创建和操作 Z 对象，并由此创建一个能够覆盖大量贡献者的编码环境以发展成一个拥有活跃社区的维基媒体项目。
每个 Z 对象都需含一值必解为 Z4/类型的 Z1K1/类型键。
我们使用“Z 编号/标签”记号来表示 Z 编号，其中‘Z 编号’是一个 Z 对象编号或该对象上的一个键，而‘标签’则是附加在该语言中立代码或键上的（英语）标签。
一个 Z 对象的表示仅代表键/值对的记录，且只以终端节点结束的，被称作一个范式。 一个 Z 对象的范式常是用于评估的那个。
规范形式
为了使 Z 对象们更好读和更紧凑，我们通常以所谓规范形式存储和传输它们。
规范形式使用三种句法转换：Z9/引用，Z6/字符串，和Z881/类化列表。
规范引用
一个引用通过它的 Z 编号指向一个 Z 对象。 一个 Z 编号以字母 Z 开头，后跟一自然数。 引用的常式如下（这里，以及整个文档中，我们总是显示 Z 对象两次：左侧是标签化版本，即均被一个英文标签替换的所有 Z 编号和关键引用；右侧是未替换的 Z 编号和关键引用）。
{
"type": "reference",
"reference id": "natural number"
}
|
{
"Z1K1": "Z9",
"Z9K1": "Z10"
}
|
规范形式用带有 Z 编号的单个字符串替换该对象。 这样上述引用的规范形式如下：
"natural number"
|
"Z10"
|
注意范式和规范式具相同含义。
规范字符串
一个字符串是一串统一码代码点，常表一个单词或一段文字。 它可包括空格和除控制字符之外的任何其他字符。
一个字符串的范式如下。 注意第二个键的值实为字符串，而不是 Z 代码的标签化版本，如右侧所示。
{
"type": "string",
"string value": "Wikifunctions"
}
|
{
"Z1K1": "Z6",
"Z6K1": "Wikifunctions"
}
|
字符串通常可仅通过它们的字符串而非整个对象进行规范化。 上述字符串可被规范化如下。
"Wikifunctions"
|
"Wikifunctions"
|
注意以一大写拉丁字母开头且后跟自然数的字符串需转义，否则会与引用的范式相冲突。
例如，字符串“Z1”有如下表示，以范式和规范式。
这是因为其他方式下的 “Z1” 不论指代字符串 Z1，还是对具有 Z 代码 Z1 的对象的一个引用都可能多义。
{
"type": "string",
"string value": "Z1"
}
|
{
"Z1K1": "Z6",
"Z6K1": "Z1"
}
|
规范列表
列表通过所谓本杰明数组来表示。 它们的说明可在下面的Z881/类型化列表部分找到。
JSON 中的表示
一个 Z 对象可用 JSON 表示，其键是抽象 Z 代码键（“Z1K1 ”，诸此之类。），及值的 JSON 表示。
将抽象键和 Z 代码替换为给定语言中的标签，即“标签化”表示法可以得到更易读的表示。 标签化的版本往往模棱两可并不总能翻译成机器可读的表示。
下表给出了一个 Z 对象表示自然数2的示例。 在左边我们看到用英语标注的 Z 对象，中间是用德语标注的，在右边我们看到使用 Z 代码的 Z 对象。
{
"type": "natural number",
"base 10 representation": "2"
}
|
{
"Typ": "natürliche Zahl",
"Dezimaldarstellung": "2"
}
|
{
"Z1K1": "Z10",
"Z10K1": "2"
}
|
如你所见，标签不一定是英文的，也可以是“维基函数”支持的300多种语言中的任何一种。
范式
在评估器处理 Z 对象时，所有 Z 对象都会转换成上述范式。 将一个字符串值解释为 Z6/字符串还是 Z9/引用时范式均不依赖任何隐化，但其均以显式 Z 对象的形式表示。
这意味着一个 Z 对象的范式是一棵树，其中全叶要么是 Z6/字符串要么是 Z9/引用类型。
这也意味着所有列表都用 Z 对象代表，而不是数组。
The following normal form represents the ZObject above, which has the value of the natural number 2.
{
"type": {
"type": "reference",
"reference id": "natural number"
},
"base 10 representation": {
"type": "string",
"string value": "2"
}
}
|
{
"Z1K1": {
"Z1K1": "Z9",
"Z9K1": "Z10"
},
"Z10K1": {
"Z1K1": "Z6",
"Z6K1": "2"
}
}
|
Normal forms are used as inputs for the evaluation engine. They ensure that the input for evaluation is always uniform and easy to process, and that it requires a minimal amount of special cases.
Persistent and transient
Every top-level ZObject stored in a Wikifunctions wiki page is a Z2/Persistent object. ZObjects that are not stored on their own wiki page are called transient ZObjects.
Every persistent ZObject must have a Z2K1/id, a Z6/String for the ZID, which is equivalent to the name of the wiki page where it is stored. Let’s assume that there is a ZObject for the natural number 2 that we saw previously and that it is stored on the page Z702. This is what it could look like (note that the three digit ZIDs starting with Z7xx are just placeholders until we have the right ZIDs for them in Wikifunctions).
{
"type": "persistent object",
"id": {
"type": "string",
"string value": "Z702"
},
"value": {
"type": "natural number",
"base 10 representation": "2"
},
"label": {
"type": "multilingual text",
"texts": [
"monolingual text",
{
"type": "monolingual text",
"language": "English",
"text": "two"
},
{
"type": "monolingual text",
"language": "German",
"text": "zwei"
}
]
}
}
|
{
"Z1K1": "Z2",
"Z2K1": {
"Z1K1": "Z6",
"Z6K1": "Z702"
},
"Z2K2": {
"Z1K1": "Z10",
"Z10K1": "2"
},
"Z2K3": {
"Z1K1": "Z12",
"Z12K1": [
"Z11",
{
"Z1K1": "Z11",
"Z11K1": "Z1002",
"Z11K2": "two"
},
{
"Z1K1": "Z11",
"Z11K1": "Z1430",
"Z11K2": "zwei"
}
]
}
}
|
All JSON objects stored on Wikifunctions are stored in Unicode normalization form C. All values before evaluation must also be Unicode-normalized to Unicode normal form C.
The Z2/Persistent object is an envelope providing metadata for the ZObject embedded in the Z2K2/value.
The Z2K3/label is a ZObject of the type Z12/multilingual text which has one Z3/Key, Z12K1/texts, pointing to a list of Z11/monolingual text ZObjects (remember that a list is represented as an array in the JSON representation). The label allows for the labelization.
There are further Z3/Keys on Z2/Persistent object which we omit here. They are all defined on Z2/Persistent object.
Z9/References
A Z9/Reference is a reference to the Z2K2/value of the ZObject with the given ID, and means that this Z2K2/value has the same meaning as the reference. To give an example, take the following reference:
"two"
|
"Z702"
|
This is a short-form Z9/Reference, that would look like this in its expanded form (as explained in the Section on deserialization):
{
"type": "reference",
"reference id": "two"
}
|
{
"Z1K1": "Z9",
"Z9K1": "Z702"
}
|
And since this object is a Z9/Reference, the object is to be replaced by the Z2K2/value from the Z2/Persistent object that has the Z2K1/id "Z702" (as given above), so it would look as follows:
{
"type": "natural number",
"base 10 representation": "2"
}
|
{
"Z1K1": "Z10",
"Z10K1": "2"
}
|
All three JSON representations in this section have the same meaning for Wikifunctions. They all refer to the natural number 2.
Note that if a Z8/Function has an argument type of Z2/Persistent object, then, instead of the Z2K2/value, the Z2/Persistent object itself is being substituted in.
Z4/Types
Types are ZObjects of type Z4/Type. ZObjects of a type are called instances of that type. So Z702/two we saw above was an instance of the type Z10/positive integer.
A Type tells us how to interpret a value. A Type also provides us with the means to check the validity of a ZObject of that type. A Type usually declares the keys available for its instances and a Function that is used to validate the Instances.
Here is the type for natural numbers (simplified, as it skips the short description and aliases, and all but the first three keys on Z4/Type).
{
"type": "persistent object",
"id": {
"type": "String",
"string value": "Z10"
},
"value": {
"type": "type",
"identity": "natural number",
"keys": [
"key",
{
"type": "key",
"value type": "string",
"key id": "Z10K1",
"label": {
"type": "multilingual text",
"texts": [
"monolingual text",
{
"type": "monolingual text",
"language": "English",
"text": "base 10 representation"
},
{
"type": "monolingual text",
"language": "German",
"text": "Dezimaldarstellung"
}
]
}
}
],
"validator": "validate natural number"
},
"label": {
"type": "multilingual text",
"texts": [
"monolingual text",
{
"type": "monolingual text",
"language": "English",
"text": "natural number"
},
{
"type": "monolingual text",
"language": "German",
"text": "natürliche Zahl"
}
]
}
}
|
{
"Z1K1": "Z2",
"Z2K1": {
"Z1K1": "Z6",
"Z6K1": "Z10"
},
"Z2K2": {
"Z1K1": "Z4",
"Z4K1": "Z10070",
"Z4K2": [
"Z3",
{
"Z1K1": "Z3",
"Z3K1": "Z6",
"Z3K2": "Z10K1",
"Z3K3": {
"Z1K1": "Z12",
"Z12K1": [
"Z11",
{
"Z1K1": "Z11",
"Z11K1": "Z1251",
"Z11K2": "base 10 representation"
},
{
"Z1K1": "Z11",
"Z11K1": "Z1254",
"Z11K2": "Dezimaldarstellung"
}
]
}
}
],
"Z4K3": "Z110"
},
"Z2K3": {
"Z1K1": "Z12",
"Z12K1": [
"Z11",
{
"Z1K1": "Z11",
"Z11K1": "Z1251",
"Z11K2": "positive integer"
},
{
"Z1K1": "Z11",
"Z11K1": "Z1254",
"Z11K2": "natürliche Zahl"
}
]
}
}
|
To make the core of the Type easier visible, let’s just look at the Z4/Type and remove the labels:
{
"type": "type",
"identity": "natural number",
"keys": [
"key",
{
"type": "key",
"value type": "string",
"keyid": "Z10K1"
}
],
"validator": "validate natural number"
}
|
{
"Z1K1": "Z4",
"Z4K1": "Z10",
"Z4K2": [
"Z3",
{
"Z1K1": "Z3",
"Z3K1": "Z6",
"Z3K2": "Z10K1"
}
],
"Z4K3": "Z110"
}
|
Type Z10/natural number defines in Z4K2/keys the new Z3/Key Z10K1/base 10 representation, which we had used above in the instance representing the number 2.
Z4K3/validator points to a Z8/Function that takes an instance as its argument and returns either an error or the value itself, in case there is no error. If no errors are returned, the instance has passed the validation. In the given case, the Z8/Function could do the following checks:
- There is one and only one Key, Z10K1/base 10 representation, on the instance, besides the Z1K1/type.
- The value of the base 10 representation has the type Z6/String.
- The base 10 representation contains only digits.
- The base 10 representation does not start with a 0, unless it is only the 0.
Note that all these checks are done by Z8/Functions that are provided by contributors, and that all Types can be defined and modified by contributors. There is nothing hardcoded regarding the number type that we use here.
An instance might use keys that are not defined on the Type. It is up to the validator function to allow that or not. For example, instances of Z7/Function call often use keys not defined on Z7/Function call, as can be seen in the Section on Z7/Function calls. Most validators are expected to require that all keys are defined, though.
But a few things are hardcoded, such as the behavior of Z7/function call. More about this later.
Z3/Keys
All keys must have a K followed by a natural number, and are usually preceded by a ZID. If they are preceded by a ZID they are called Global Keys, if they are not they are called Local Keys. For example, the following two representations are equivalent.
{
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": "Z702",
"Z781K2": "Z702"
}
|
{
"Z1K1": "Z7",
"Z7K1": "Z10000",
"K1": "Z702",
"K2": "Z702"
}
|
Global Keys are named arguments whereas Local Keys are positional arguments.
- The rule of thumb is to use Global Keys whenever possible.
- The main use case for Local Keys is when a Z8/Function or Z4/Type is being created on the fly, and thus cannot have Global Keys because the created Z8/Function or Z4/Type itself is not persistent.
A Global Key is always defined on the ZObject the ZID part of its ID refers to.
In their definition, a Key contains information of what type of object it must contain (Z3K1), the global ID that identifies that key (Z3K2), its human-readable labels (Z3K3) and whether this key is an identity field (Z3K4).
An identity key allows objects to store their persisted ID. For example, Functions and Types contain an identity field. Also planned types, particularly enumerations, such as grammatical features, require identity.
Enumerations
An enumeration is a type that has a limited number of values. Examples of enumerations are the type Boolean (with the values "false" and "true"), or Integer sign (with the values "positive", "neutral" or "negative"). Enumerations are also an important tool to support linguistic functions.
Every enumeration type has one key that is marked as an identity field. For example, let's look at the Type definition for Boolean (removing key labels for simplicity):
{
"type": "Type",
"identity": "Boolean",
"keys": [
"Key",
{
"type": "Key",
"value type": "Boolean",
"key id": "Z40K1",
"label": { /* "identity" */ },
"is identity": "True"
}
],
...
}
|
{
"Z1K1": "Z4",
"Z4K1": "Z40",
"Z4K2": [
"Z3",
{
"Z1K1": "Z3",
"Z3K1": "Z40",
"Z3K2": "Z40K1",
"Z3K3": { /* "identity" */ },
"Z3K4": "Z41"
}
],
...
}
|
All limited values for Boolean will assign their ZID as the value for their identity/Z40K1 key. See, for example, True, which contains its identity and additionally the multilingual data (name, description, aliases) as part of the Persistent Object keys.
{
"type": "Persistent object",
"identity": {
"type": "String",
"value": "Z41"
},
"value": {
"type": "Boolean",
"identity": "True"
},
"labels": {
"type": "Multilingual text",
"texts": [
"Monolingual text",
{
"type": "Monolingual text",
"language": "English",
"text": "true"
}
]
}
}
|
{
"Z1K1": "Z2",
"Z2K1": {
"Z1K1": "Z6",
"Z6K1": "Z41"
},
"Z2K2": {
"Z1K1": "Z40",
"Z40K1": "Z41"
},
"Z2K3": {
"Z1K1": "Z12",
"Z12K1": [
"Z11",
{
"Z1K1": "Z11",
"Z11K1": "Z1002",
"Z11K2": "true"
}
]
}
}
|
Z8/Functions
In the definition of Z10/natural number we saw a first reference to a Z8/Function, Z110/validate natural number. Here, we will use a much simpler function, Z781/add. Z781/add is a Z8/Function which takes two Z10/natural numbers and returns a Z10/natural number.
We only show the value.
{
"type": "function",
"arguments": [
"argument declaration",
{
"type": "argument declaration",
"argument type": "natural number",
"key id": "Z781K1",
"label": { ... }
},
{
"type": "argument declaration",
"argument type": "natural number",
"key id": "Z781K2",
"label": { ... }
}
],
"return type": "natural number",
"tests": [
"testers",
"add one and zero",
"add two and two"
],
"implementations": [
"implementation",
"+ in Python",
"recursive addition",
"+ in JavaScript"
],
"identity": "add"
}
|
{
"Z1K1": "Z8",
"Z8K1": [
"Z17",
{
"Z1K1": "Z17",
"Z17K1": "Z10",
"Z17K2": "Z781K1",
"Z17K3": { ... }
},
{
"Z1K1": "Z17",
"Z17K1": "Z10",
"Z17K2": "Z781K2",
"Z17K3": { ... }
}
],
"Z8K2": "Z10",
"Z8K3": [
"Z20",
"Z711",
"Z712"
],
"Z8K4": [
"Z14",
"Z721",
"Z722",
"Z723"
],
"Z8K5": "Z144"
}
|
To remain concise, we removed the Z17K3/labels from the Z17/Argument declarations, which are identified using Z17K2/key IDs. But just like the Z3/Keys on Z4/Types, they have labels in all supported languages. The Keys are Global when the Z8/Function is persistent, and Local when transient.
The Function is specified through the (omitted) documentation, but also through the Z8K3/tests and the Z8K1/type declarations on the arguments and the Z8K2/return type. Furthermore, since a Function can have several Z8K4/Implementations, the Implementations confirm each other.
Z8/Functions are not allowed to have state-changing side effects.
Z7/Function calls
The following ZObject represents a function call. In the second row, we see a more compact representation of the function call, that uses a syntax that is more familiar for function calls.
{
"type": "function call",
"function": "add",
"left": "two",
"right": "two"
}
|
{
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": "Z702",
"Z781K2": "Z702"
}
|
add(two, two)
|
Z781(Z702, Z702)
|
Using literals instead of persistent ZObjects for the arguments, this would look as follows.
- Note that we are creating the literals using the Z10/positive integer as a constructor.
- All Z4/Types can be called like this, providing a value for each of their keys.
- This is not a Z7/Function call, but a notation for the object of the given Z4/Type.
{
"type": "function call",
"function": "add",
"left": {
"type": "natural number",
"base 10 representation": "2"
},
"right": {
"type": "natural number",
"base 10 representation": "2"
}
}
|
{
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": {
"Z1K1": "Z10",
"Z10K1": "2"
},
"Z781K2": {
"Z1K1": "Z10",
"Z10K1": "2"
}
}
|
add(natural number<"2">, natural number<"2">)
|
Z781(Z10<"2">, Z10<"2">)
|
When this Z7/Function call gets evaluated, it results as expected in the number four.
{
"type": "natural number",
"base 10 representation": "4"
}
|
{
"Z1K1": "Z10",
"Z10K1": "4"
}
|
natural number<"4">
|
Z10<"4">
|
Evaluation is performed repeatedly on the evaluation result until a fixpoint is reached.
Z14/Implementations
Every Z8/Function can have a number of different Z14/Implementations. There are three main types of Z14/Implementations: builtins, Z16/code, or through composition of other Z8/Functions.
Let us take a look at the Z781/add Function and four different Z14/Implementations for it.
Builtin implementations
A builtin implementation tells the evaluator to return an appropriate evaluation result. Builtins are hardcoded into the evaluator. Z14K4/builtin refers to the hard-coded builtin-ID (which has to be the ZID of the Z2/Persistent object).
{
"type": "implementation",
"implements": "add",
"builtin": "Z791"
}
|
{
"Z1K1": "Z14",
"Z14K1": "Z781",
"Z14K4": "Z791"
}
|
An evaluator is aware of all its own builtins and can use them at will. Note that addition would not be a function that would get a builtin. This is provided here just for illustrative purposes.
Z16/Code
An implementation in Z16/Code represents a code snippet in a given programming language.
{
"type": "implementation",
"implements": "add",
"code": {
"type": "code",
"language": "javascript",
"source": "function add(left, right) {
return left + right;
}"
}
}
|
{
"Z1K1": "Z14",
"Z14K1": "Z781",
"Z14K3": {
"Z1K1": "Z16",
"Z16K1": "Z600",
"Z16K2": "function Z781(Z781K1, Z781K2) {
return Z781K1 + Z781K2;
}"
}
}
|
{
"type": "implementation",
"implements": "add",
"code": {
"type": "code",
"language": "python",
"source": "def add(left, right):
return left + right"
}
}
|
{
"Z1K1": "Z14",
"Z14K1": "Z781",
"Z14K3": {
"Z1K1": "Z16",
"Z16K1": "Z610",
"Z16K2": "def Z781(Z781K1, Z781K2):
return Z781K1 + Z781K2"
}
}
|
The evaluator would know how to transform the given ZObjects representing the arguments into the supported programming languages, how to execute the provided code snippet, and then how to transform the result back into a ZObject representing the result.
Eventually, the translation of ZObjects to the native values of the supported programming languages would be handled inside Wikifunctions itself (which will require a new design document). Until then, we only support Z16/Code for arguments and return types that have hard-coded support by the evaluator.
Z46/Deserializer
A Z46/Deserializer takes a ZObject of a specific Type and turns it into a value for a given programming language.
For example, the following Z46/Deserializers takes a ZObject of type Z10/Natural number and turns it into a JavaScript BigInt value.
{
"type": "deserializer",
"identity": "to BigInt",
"type": "Natural number"
"converter": {
"type": "code",
"language": "javascript",
"source": "function deserialize( value ) {
return BigInt( value.decimal_representation.string_value );
}"
},
"native type": "BigInt"
}
|
{
"Z1K1": "Z46",
"Z46K1": "Z787",
"Z46K2": "Z10",
"Z46K3": {
"Z1K1": "Z16",
"Z16K1": "Z600",
"Z16K2": "function Z787(Z787K1) {
return BigInt( Z787K1.Z10K1.Z6K1 );
}"
},
"Z46K4": "BigInt"
}
|
The Z46K4/native type says in which type the deserializer will result. This allows us to use natural implementations like above for addition.
Z64/Serializer
The reverse operation of a Z46/Deserializer is the Z64/Serializer. A Z64/Serializer takes a value in the given programming language and turns it into a ZObject of the requested type.
{
"type": "serializer",
"identity": "from BigInt",
"type": "Natural number"
"converter": {
"type": "code",
"language": "javascript",
"source": "function serialize( value ) {
return {
'type': {
'type': 'reference',
'reference id': 'natural number'
},
'base 10 representation': {
'type': 'string',
'string value': value.toString()
}
}
}"
},
"native type": "BigInt"
}
|
{
"Z1K1": "Z64",
"Z64K1": "Z789",
"Z64K2": "Z10",
"Z64K3": {
"Z1K1": "Z16",
"Z16K1": "Z600",
"Z16K2": "function Z789(Z789K1) {
return {
'Z1K1': {
'Z1K1': 'Z9',
'Z9K1': 'Z10'
},
'Z10K1': {
'Z1K1': 'Z6',
'Z6K1': Z789K1.toString()
}
}
}"
},
"Z64K4": "BigInt"
}
|
Composition
The most portable (but often also the slowest) Z14/Implementation is achieved through composition of other Z8/Functions.
We show both the ZObject of the implementation, as well as an easier to read notation based on function call syntax.
{
"type": "implementation",
"implements": "add",
"composition": {
"type": "function call",
"function": "if",
"condition": {
"type": "function call",
"function": "is zero",
"arg": {
"type": "argument reference",
"reference": "right"
}
},
"consequent": {
"type": "argument reference",
"reference": "left"
},
"alternative": {
"type": "function call",
"function": "add",
"left": {
"type": "function call",
"function": "successor",
"arg": {
"type": "argument reference",
"reference": "left"
}
},
"right": {
"type": "function call",
"function": "predecessor",
"arg": {
"type": "argument reference",
"reference": "right"
}
}
}
}
}
|
{
"Z1K1": "Z14",
"Z14K1": "Z781",
"Z14K2": {
"Z1K1": "Z7",
"Z7K1": "Z802",
"Z802K1": {
"Z1K1": "Z7",
"Z7K1": "Z782",
"Z782K1": {
"Z1K1": "Z18",
"Z18K1": "Z781K2"
}
},
"Z802K2": {
"Z1K1": "Z18",
"Z18K1": "Z781K1"
},
"Z802K3": {
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": {
"Z1K1": "Z7",
"Z7K1": "Z783",
"Z783K1": {
"Z1K1": "Z18",
"Z18K1": "Z781K1"
}
},
"Z781K2": {
"Z1K1": "Z7",
"Z7K1": "Z784",
"Z784K1": {
"Z1K1": "Z18",
"Z18K1": "Z781K2"
}
}
}
}
}
|
if(
|
Z802(
|
This composition relies on a number of other Z8/Functions: Z782/is zero, Z783/successor, Z784/predecessor, Z801/if, and, most interestingly — itself. It is entirely OK for an Z14/Implementation to call its own Z8/Function recursively. Note though that the evaluator does not have to call the Z14/Implementation recursively — an evaluator is free to choose any implementation at each recursion step.
This is anything but fast — but it allows us to use a well-understood formalism and a very simple implementation of it in order to ensure that the other implementations of Z781/add are correct — admittedly, probably of less interest for addition, but we can imagine that there are Z8/Functions that have more obviously correct implementations and much cleverer faster implementations. Wikifunctions can cross-test these implementations against each other and thus give us some sense of security regarding their correctness.
Example evaluation
In the following we evaluate the above composition. We start with the following Z7/function call (we only stick to the functional syntax due to its brevity).
add(Natural number<"2">, Natural number<"2">)
|
Z781(Z10<"2">, Z10<"2">)
|
We replace the function call with the composition given above, and replace the arguments with the given values. That results in the following code.
if(
is zero(Natural number<"2">),
Natural number<"2">,
add(
successor(Natural number<"2">),
predecessor(Natural number<"2">)
)
)
|
Z802(
Z782(Z10<"2">),
Z10<"2">,
Z781(
Z783(Z10<"2">),
Z784(Z10<"2">)
)
)
|
We evaluate the Z782/is zero(Z10/Natural number<"2">) to the Z40/Boolean value of Z42/false (since 2 is not zero).
That results in:
if(
false,
Natural number<"2">,
add(
successor(Natural number<"2">),
predecessor(Natural number<"2">)
)
)
|
Z802(
Z42,
Z10<"2">,
Z781(
Z783(Z10<"2">),
Z784(Z10<"2">)
)
)
|
This allows us to replace the call to Z802/if with the Z802K3/alternative, since the Z802K1/condition is false. That results in:
add(
successor(Natural number<"2">),
predecessor(Natural number<"2">)
)
|
Z781(
Z783(Z10<"2">),
Z784(Z10<"2">)
)
|
The Z783/successor function just adds one to a number, and the Z784/predecessor function removes one. Any of these functions may or may not be implemented in code or in some other way, this does not really matter. If we replace both these function calls, we get to the following call:
add(
Natural number<"3">,
Natural number<"1">
)
|
Z781(
Z10<"3">,
Z10<"1">
)
|
Again we substitute the call to Z781/add with its composition, and replace the arguments with the new values. 结果是：
if(
is zero(Natural number<"1">),
Natural number<"3">,
add(
successor(Natural number<"3">),
predecessor(Natural number<"1">)
)
)
|
Z802(
Z782(Z10<"1">),
Z10<"3">,
Z781(
Z783(Z10<"3">),
Z784(Z10<"1">)
)
)
|
We again check if the value given to Z782/is zero (it is not, it is one). So we replace the call to Z782/is zero again with Z42/false.
if(
false,
Natural number<"3">,
add(
successor(Natural number<"3">),
predecessor(Natural number<"1">)
)
)
|
Z802(
Z42,
Z10<"3">,
Z781(
Z783(Z10<"3">),
Z784(Z10<"1">)
)
)
|
Since the Z802K1/condition is again false, we replace the call to Z802/if with the Z802K3/alternative.
add(
successor(Natural number<"3">),
predecessor(Natural number<"1">)
)
|
Z781(
Z783(Z10<"3">),
Z784(Z10<"1">)
)
|
Again we replace the function calls to Z783/successor and Z784/predecessor with the respective results, one number more, one number less.
add(
Natural number<"4">,
Natural number<"0">
)
|
Z781(
Z10<"4">,
Z10<"0">
)
|
We are now again at the point where we replace the call to Z781/add with its composition. 结果是：
if(
is zero(Natural number<"0">),
Natural number<"4">,
add(
successor(Natural number<"4">),
predecessor(Natural number<"0">)
)
)
|
Z802(
Z782(Z10<"0">),
Z10<"4">,
Z781(
Z783(Z10<"4">),
Z784(Z10<"0">)
)
)
|
The call to Z782/is zero now got the argument Z10/natural number<"0"> which is indeed zero. So the call to Z782/is zero results in a Z41/true. 结果是：
if(
true,
Natural number<"4">,
add(
successor(Natural number<"4">),
predecessor(Natural number<"0">)
)
)
|
Z802(
Z41,
Z10<"4">,
Z781(
Z783(Z10<"4">),
Z784(Z10<"0">)
)
)
|
The Z802/if function call now has a Z41/true Z802K1/condition, which means we replace the whole call with the Z802K2/consequence, not the Z802K3/alternative. 结果是：
Natural number<"4">
|
Z10<"4">
|
This is a fixpoint, i.e. it does not change when evaluated, and thus is the result of our function call.
2加2是4。
Evaluation order
The evaluation order is up to the evaluator. Since all Z8/Functions are not allowed to have side-effects, this will always lead to the same result. But an unwise evaluation strategy can lead to much more computation than necessary or even to the evaluator not terminating. Z722/recursive addition provides us with an example that might end up in an endless loop if we try a complete evaluation order:
For the call to Z802/if in Z722/recursive addition it would be unwise to first evaluate all three arguments and then to return either the second or the third argument. Depending on the first argument Z802K1/condition we will only need to return either Z802K2/consequent or Z802K3/alternative. There is never the case that we need to evaluate both the second and the third argument.
In fact we could even return the second or third argument unevaluated. Remember that the evaluator will evaluate each result again anyway until a fixpoint is reached. So Z802/if can be implemented lazily, drop the irrelevant branch, and return the relevant branch as an unevaluated ZObject.
A lazy evaluation strategy is in general recommended, but for example when the evaluator wants to use a Z16/Code based implementation, it might not be feasible. And then the evaluator might decide to first evaluate the arguments and then the outer call. In the end, there are opportunities to experiment with different evaluation strategies.
Z20/Testers
Z20/Testers are ZObjects that make a Z20K2/call and then use a Z20K3/validator on the result. Z20K3/Validator is an incomplete Z7/function call that gets the result of the Z20K2/call injected as the first argument. If the Z20K3/validator returns an Z41/true, the Z20/Tester passes, otherwise it fails.
Tests are used to ensure that all Z14/Implementations behave as they should, and should be considered similar to unit tests. A Z8/Function should list all the Z20/Testers that need to pass for an Z14/Implementation to be compliant. Additionally, the different Z14/Implementations can be cross-tested against each other for consistency.
{
"type": "tester",
"function": "add",
"call": {
"type": "function call",
"function": "add",
"left": "two",
"right": "two"
},
"result validator": {
"type": "function call",
"function": "equivalent natural number",
"right": "four"
}
}
|
{
"Z1K1": "Z20",
"Z20K1": "Z781",
"Z20K2": {
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": "Z702",
"Z781K2": "Z702"
},
"Z20K3": {
"Z1K1": "Z7",
"Z7K1": "Z788",
"Z788K2": "Z704"
}
}
|
In this case we evaluate first the Z20K2/call, which is Z781/add(Z702/two, Z702/two), resulting in Z10/Natural number<"4">.
That, in turn, is then used in the Z20K3/result validator, where it is injected as the first argument, resulting in Z788/natural number equality(Z10/Natural number<"4">, Z704/four).
That call should result in Z41/true, and thus the Z20/Tester should pass.
Generic types
A generic type is realized by a Z7/Function call to a Z8/Function which takes some arguments and returns a Z4/Type.
For example, Z882/typed pair is a function that takes two Z4/Types as its arguments, one for the first and one for the second element, and returns an inline Z4/Type.
So to make a pair of Z10/Natural numbers, we call Z882/typed pair(Z10/Natural number, Z10/Natural number) and the result is a Z4/Type which we can use for the Z1K1 field of a ZObject.
{
"type": {
"type": "function call",
"function": "typed pair",
"first": "natural number",
"second": "natural number"
},
"first": "one",
"second": "two"
}
|
{
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z10",
"Z882K2": "Z10"
},
"K1": "Z701",
"K2": "Z702"
}
|
The result of the Z7/Function call is a dynamically created Z4/Type that ensures that the two elements of the Pair have the right Z4/Type. The result of that Z7/Function call looks like this.
{
"type": "type",
"identity": {
"type": "function call",
"function": "typed pair",
"first": "natural number",
"second": "natural number"
},
"keys": [
"key",
{
"type": "key",
"id": "K1",
"value type": "natural number"
},
{
"type": "key",
"id": "K2",
"value type": "natural number"
}
],
"validator": "validate typed pair"
}
|
{
"Z1K1": "Z4",
"Z4K1": {
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z10",
"Z882K2": "Z10"
},
"Z4K2": [
"Z3",
{
"Z1K1": "Z3",
"Z1K2": "K1",
"Z3K1": "Z10"
},
{
"Z1K1": "Z3",
"Z1K2": "K2",
"Z3K1": "Z10"
}
],
"Z4K3": "Z892"
}
|
This also is an example of the use of the Z4K1/identity field on Z4/Type: it describes how the Z4/Type was created, and allows us to access the arguments used for Type creation. Keeping this information declaratively is very helpful for validating a Function call statically, and for comparing types.
If we want a Z882/Typed pair that doesn’t restrict the Z4/Type of one or both of its elements, one could call the Z882/Typed pair function with Z1/ZObject as one or both arguments.
Z881/Typed lists
Here is a list of two strings.
[
"string",
"a",
"b"
]
|
[
"Z6",
"a",
"b"
]
|
If we turn this into ZObjects, it looks as follows.
{
"type": {
"type": "function call",
"function": "typed list",
"elementtype": "string"
},
"head": "a",
"tail": {
"type": {
"type": "function call",
"function": "typed list",
"elementtype": "string"
},
"head": "b"
}
}
|
{
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z881",
"Z881K1": "Z6"
},
"K1": "a",
"K2": {
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z881",
"Z10K1": "Z6"
},
"K1": "b"
}
}
|
A JSON array literal always starts with the type used for the Z881/Typed list. This is not the first element of the list, but just the type for the typed list. These arrays are called Benjamin Arrays. If we want an untyped list, we would use Z1/Object as the argument. An untyped empty list would look as follows.
[
"object"
]
|
[
"Z1"
]
|
Z22/Evaluation result
A Z7/Function call executed in Wikifunctions always returns an object of type Z22/Evaluation result.
An Evaluation result object always contains the value returned from the execution of a Function Call and a collection of metadata gathered during the evaluation. Here's an example of a successful response:
{
"type": "evaluation result",
"result": "Hello, World!",
"metadata": {
"type": {
"type": "function call",
"function": "typed map",
"key type": "string",
"value type": "object"
},
"map": [
{
"type": "function call",
"function": "typed pair",
"first type": "string",
"second type": "object"
},
{
"type": {
"type": "function call",
"function": "typed pair",
"first type": "string",
"second type": "object"
},
"key": "orchestrationDuration",
"value": "139 ms"
}
]
}
}
|
{
"Z1K1": "Z22",
"Z22K1": "Hello, World!",
"Z22K2": {
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z883",
"Z883K1": "Z6",
"Z883K2": "Z1"
},
"K1": [
{
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z6",
"Z882K2": "Z1"
},
{
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z6",
"Z882K2": "Z1"
},
"K1": "orchestrationDuration",
"K2": "139 ms"
}
]
}
}
|
If the evaluation is unsuccessful, the response field will contain Z24/Void, while the metadata field will contain an "error" key with the details of the failure. This is an example of a failed Evaluation result object:
{
"type": "evaluation result",
"result": "void",
"metadata": {
"type": {
"type": "function call",
"function": "typed map",
"key type": "string",
"value type": "object"
},
"map": [
{
"type": "function call",
"function": "typed pair",
"first type": "string",
"second type": "object"
},
{
"type": {
"type": "function call",
"function": "typed pair",
"first type": "string",
"second type": "object"
},
"key": "errors",
"value": {
"type": "error",
"error type": "unspecified error",
"error value": {
"type": {
"type": "function call",
"function": "errortype to type",
"errortype": "unspecified error"
},
"error information": "Some error happened"
}
}
}
]
}
}
|
{
"Z1K1": "Z22",
"Z22K1": "Z24",
"Z22K2": {
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z883",
"Z883K1": "Z6",
"Z883K2": "Z1"
},
"K1": [
{
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z6",
"Z882K2": "Z1"
},
{
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z882",
"Z882K1": "Z6",
"Z882K2": "Z1"
},
"K1": "errors",
"K2": {
"Z1K1": "Z5",
"Z5K1": "Z500",
"Z5K2": {
"Z1K1": {
"Z1K1": "Z7",
"Z7K1": "Z885",
"Z885K1": "Z500"
},
"Z500K1": "Some error happened"
}
}
}
]
}
}
|
These examples are just condensed versions of the real Evaluation result objects and only contain one example key in the Metadata field. In real examples, the metadata collection will return all the metrics gathered by the backend services, including the run's duration, CPU usage, and memory usage.
For a more detailed description of all the possible metadata returned in the Evaluation result object, see the Function call metadata guide in Mediawiki.
Z5/Errors
A Z7/Function call can result in a Z5/Error. This happens when the function call cannot be executed properly, and is unrecoverable (e.g., division by zero or a failure due to insufficient memory).
Z5 is a generic type. Each instance of Z5 references the ZID of an error type (in Z5K1/error type), and that error type determines the type of Z5K2/error value, and the keys that will be present therein. Each error type is an instance of Z50/error type, and ZIDs Z500–Z599 are reserved for error types.
Additional information is available at Abstract Wikipedia/Representation of errors.
Z99/Quote
Z99/Quote is used as a wrapper around another ZObject, to indicate that it should not be evaluated ("resolved"). (This is similar to quoting in Lisp.) Z99/Quote has a single key, Z99K1/quotation, of type Z1/Object.
To illustrate, some parts of error objects (instances of Z5/Error) are quoted when they get created during the execution of a function call. For example, an error of type Z507/Error in evaluation includes a copy of the entire function call whose execution caused the error (as the value of Z507K1/function call). Because this function call is very likely to be malformed in some way, we ensure that no further attempt is made to evaluate it, by quoting it inside the error object. (Thus, the type of Z507K1 is declared as Z99, and its value is always quoted.)
We use the following guidelines for when to use Z99/Quote:
- Quote a ZObject when we believe it may be invalid in some way.
- But do not quote Z1K1 by itself. If its value is in doubt, quote the entire object that contains it.
- Quote resolvable keys (keys whose values contain instances of Z7, Z9, or Z18) that might inappropriately be ingested as the input to a function.
- Quote when resolving a value might cause a catastrophe (e.g. infinite recursion).
Note: as our resolution strategy evolves, it's possible that (3) and (4) could become unnecessary.
Non-functional Functions
No Z8/Function is allowed to have side effects. All Z8/Functions must be functional. I.e. they must return the same value when being called with the same arguments. This means that Z8/Functions such as “return a random number” or “return the current time” are not possible.
This might change in the future. This will be handled in a later document.
Zx/Sum types
A particularly useful generic type is the Zx/Sum type, which takes a list of Z4/Types and returns a Z4/Type that can take exactly one instance of any of the given types.
This will also allow for non-required parameters in function calls.
This will be handled in a later document.
Some questions and tasks to do
- Do we need “required/option” for keys anywhere in the beginning? — no
- Replace defaults on Z3/Key with Zx/Sum? (Or at least make it consistent with Z17/argument declaration)
- Could be left for later if we don’t need default on Z3 for now
- Make a note that all is Unicode and that all is the normalization required by MediaWiki
- Rewrite intro to start with normal and then canonicalize