Wikifunctions:Modèle de fonctions
Wikifonctions (Wikifunctions en anglais) est un catalogue multilingue de fonctions auquel chacun peut contribuer, où chacun peut créer, maintenir, appeler et utiliser des fonctions. Chaque fonction peut avoir plusieurs mises en œuvre, par exemple dans des langages de programmation différents ou en utilisant des algorithmes différents. C’est une « Wikipédie des fonctions » et un projet frère soutenu et conduit par la Fondation Wikimédia.
Ce document couvre le modèle de données et le modèle d’évaluation de Wikifonctions.
- Tout au long de cette description de modèle, les termes capitalisés se réfèrent à des termes définis dans le glossaire.
- La lecture de la procédure pas à pas d’un précédent prototype a été très utile pour obtenir une meilleure intuition de ce qui s’y passe avant de lire le modèle suivant.
Z1/Z-Objets (ZObjects)
Wikifonctions est un wiki. Comme dans tous les wikis, le contenu de Wikifonctions est principalement stocké dans des pages wiki. Les pages wiki peuvent être modifiées individuellement et pourtant le projet dans son entier doit conserver une certaine consistance. Aussi les pages devraient être individuellement modifiables sans avoir à comprendre toutes les autres pages.
Nous introduisons les Z-Objets pour représenter le contenu de Wikifonctions. Chaque page wiki de l’espace de noms principal de Wikifonctions contient exactement un Z-Objet, de type Z2/Objet persistant. D’autres espaces de noms peuvent contenir d’autres contenus, comme les pages de politique, les pages d’utilisateurs, les pages de discussion, etc. Un Z-Objet peut être sérialisé sous forme d’un objet JSON.
Un Z-Objet consiste en une liste de paires Clé/valeur.
- Chaque valeur dans une pair Clé/valeur est un Z-Objet.
- Values can be either a Z6/String, a Z9/Reference, or have any other type. Z6/String and Z9/Reference are called terminal values. They don't expand further.
- A Z6/String has exactly two keys, Z1K1/type with the value "Z6", and Z6K1/string value, with an arbitrary string.
- A Z9/Reference has exactly two keys, Z1K1/type with the value "Z9", and Z9K1/reference ID, with a string representing a ZID.
- Chaque Clé ne peut apparaître qu’une fois dans chaque Z-Objet (mais peut réapparaître dans un Z-Objet encapsulé).
Les Z-Objets sont à la base des arbres de syntaxe abstraite.
S’il y avait un terme
(« trop long : ne pas lire ») pour le projet, ce serait probablement « quelque chose comme LISP en JSON ».
Le but est de fournir une interface utilisateur facile qui permet la création et la manipulation des Z-Objets au moyen d’une interface wiki, et donc de créer un environnement de codage qui peut atteindre un large nombre de contributeurs et qui puisse devenir un projet Wikimédia avec une communauté active.
Chaque Z-Objet doit avoir une clé Z1K1/type avec une valeur qui s’évalue en un Z4/Type.
Nous utilisons la notation « Z-ID/libellé » pour nous référer aux Z-ID d’une façon plus ou moins agréable, où « Z-ID » est un identifiant de Z-Objet (ou une clé sur un tel objet) et « libellé » est le libellé en clair (par exemple en langue anglaise ou française) attaché à cette identifiant ou clé en langue neutre.
The representation of a ZObject that is represented only as records of key/value pairs, and that only ends in terminal nodes, is called a normal form. The normal form of a ZObject is usually the one used for evaluation.
Forme canonique
In order to make ZObjects more readable and more compact, we usually store and transmit them in the so-called canonical form.
Canonical forms use three syntactic transformations: for Z9/references, Z6/strings, and Z881/lists.
Canonical References
A reference refers to a ZObject by its ZID. A ZID starts with the letter Z, followed by a natural number. The normal form of a reference looks as follows (here, and throughout the document, we display ZObjects always twice: on the left hand side in the labelized version, i.e. where all ZIDs and key IDs are replaced with an English label, and on the right hand side with the ZIDs and key IDs unreplaced).
{
"type": "reference",
"reference id": "natural number"
}
|
{
"Z1K1": "Z9",
"Z9K1": "Z10"
}
|
The canonical form replaces that object with a single string with the ZID. The canonical form of the above reference is thus the following:
"natural number"
|
"Z10"
|
Note that the normal and canonical form have the same meaning.
Canonical Strings
A String is a sequence of Unicode Code Points, representing usually a word or a text. It can include spaces and any other character besides control characters.
The normal form of a String looks as follows. Note that the value of the second key is indeed the string, and not the labelized version of a ZID, as can be seen on the right hand side.
{
"type": "string",
"string value": "Wikifunctions"
}
|
{
"Z1K1": "Z6",
"Z6K1": "Wikifunctions"
}
|
Strings can usually be canonicalized by just their string instead of the whole object. The above string can be canonicalized as follows.
"Wikifunctions"
|
"Wikifunctions"
|
Note that Strings that start with a capital Latin letter and are followed by a natural number need to be escaped, as they would otherwise clash with the normal representation of a Reference.
For example, the String "Z1" would have the following representation, both in the normal and canonical form.
This is because otherwise it would be ambiguous whether "Z1" refers to the String Z1 or is a reference to the object with the ZID Z1.
{
"type": "string",
"string value": "Z1"
}
|
{
"Z1K1": "Z6",
"Z6K1": "Z1"
}
|
Canonical lists
Lists are represented through so-called Benjamin Arrays. Their description can be found below in the section Z881/Typed lists.
Sérialisation
Un Z-Objet[1] est sérialisé vers sa représentation JSON canonique, en utilisant comme clés des clés Z-ID abstraites (« Z1K1 », etc.) et pour les valeurs une des représentations suivantes :
Une représentation plus lisible peut être donnée en remplaçant les clés abstraites et les Z-ID par leurs libellés dans une langue donnée, la représentation « libellée ». The labelized version is often ambiguous and can not always be translated to the machine-readable representation.
La table suivante donne un exemple pour un Z-Objet qui représente l’entier positif 2. Sur la gauche nous voyons le Z-Objet libellé en anglais, au milieu libellé en allemand et à droite nous voyons le Z-Objet utilisant des Z-ID.
{
"type": "natural number",
"base 10 representation": "2"
}
|
{
"Typ": "natürliche Zahl",
"Dezimaldarstellung": "2"
}
|
{
"Z1K1": "Z10",
"Z10K1": "2"
}
|
Comme vous pouvez le voir, les libellés ne sont pas nécessairement en anglais, mais doivent être dans une des plus de 300 langues que Wikifunctions prend en charge.
Forme normale
Pour le traitement des ZObjets par l’évaluateur, tous les ZObjets sont convertis en version normalisée d’eux-mêmes. La version normalisée est similaire à la version désérialisée, mais nous ne comptons sur aucune implication pour savoir s’il faut interpréter une valeur chaîne comme une Z6/Chaîne ou comme une Z9/Référence, mais elles sont toutes exprimées comme des ZObjets explicites.
Cela signifie que la représentation normalisée d’un ZObjet est un arbre dont toutes les feuilles sont soit de type Z6/Chaîne, soit de type Z9/Référence.
Cela signifie également que toutes les Listes sont représentées comme des ZObjets, et non comme des tableaux.
La forme normale suivante représente le ZObjet ci-dessus, qui a pour valeur l’entier naturel 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"
}
}
|
Les vues normalisées sont utilisées comme entrées pour le moteur d’évaluation. Elles assurent que l’entrée à évaluer est toujours uniforme et facile à traiter et que cela exige un nombre minimum de cas spéciaux.
Persistant et transitoire
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/Références
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. Pour donner un exemple, en donnant le tableau suivant avec un seul élément :
"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. Ils se réfèrent tous au nombre naturel 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.
Voici un type (simplifié) pour les entiers positifs.
{
"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.
- La représentation en base 10 ne contient que des chiffres.
- La représentation en base 10 ne commence pas par un 0, à moins qu'elle soit de longueur 1.
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. Rien n’est codé en dur concernant le type de nombre que nous utilisons ici.
Une instance pourrait utiliser des clés qui ne sont pas définies dans le Type. Il appartient à la fonction validateur de le permettre ou pas. Par exemple, les instances de Z7/Appel de fonction utilisent souvent des clés non définies sur Z7/Appel de fonction, comme on peut le voir dans la section sur Z7/Appel de fonction. Il est cependant attendu que la plupart des validateurs exigent que toutes les clés soit définies.
Mais un petit nombre de choses sont codées en dur, tel que le comportement d’un Z7/appel de fonction. Plus de détails viendront ultérieurement.
Z3/Clés
Toutes les clés doivent avoir un K suivi par un nombre naturel et peuvent être précédées par un Z-ID. Si elles sont précédées d'un Z-ID, elles sont appelées clés globales, si elles ne le sont pas elles sont appelées clés locales. Par exemple les deux représentations suivantes sont équivalentes.
{
"Z1K1": "Z7",
"Z7K1": "Z781",
"Z781K1": "Z702",
"Z781K2": "Z702"
}
|
{
"Z1K1": "Z7",
"Z7K1": "Z10000",
"K1": "Z702",
"K2": "Z702"
}
|
Les clés globales sont des arguments nommés alors que les clés locales sont des arguments positionnels.
- La règle de base est d'utiliser les clés globales à chaque fois que c'est possible.
- L'utilisation principale pour les clés locales est quand une Z8/Fonction ou un Z4/Type est crée à la volée, et ne peuvent donc pas avoir de clé globale parce que la Z8/Fonction ou le Z4/Type créé n'est lui-même pas persistant.
A Global Key is always defined on the ZObject the ZID part of its ID refers to.
Z8/Fonctions
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.
Nous ne montrons que la valeur.
{
"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/Appels de fonctions
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/Mises en œuvre
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.
Mises en œuvre intégrées
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. That results in:
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. That results in:
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. That results in:
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. That results in:
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 and 2 is 4.
Ordre d’évaluation
L’ordre d’évaluation est laissé au gré de l’évaluateur. Puisque toutes les Z8/Fonctions ne sont pas autorisées à avoir des effets de bord, ceci conduira toujours au même résultat. Mais une stratégie d’évaluation imprudente peut conduire à bien plus de calculs que nécessaire ou même conduire l’évaluateur à ne jamais se terminer. Z1445/ajouter récursivement nous fournit un exemple qui pourrait aboutir à une boucle sans fin si nous essayons un ordre complet d’évaluation :
Pour l’appel à Z31/si dans Z1445/ajouter récursivement, il serait imprudent d’évaluer tous les trois arguments et de retourner alors soit le deuxième, soit le troisième argument. Selon la Z31K1/condition du premier argument, nous avons besoin de ne retourner soit uniquement le Z31K2/conséquent, soit uniquement la Z31K3/alternative. Il n’y aura jamais le cas où nous avons besoin d’évaluer à la fois le deuxième et le troisième argument.
En fait, nous pourrions même retourner le deuxième ou le troisième argument non évalué. Souvenez-vous que l’évaluateur évaluera chaque résultat à nouveau de toute façon jusqu’à ce qu’un point fixe soit atteint. Aussi, Z31/si peut être mise en œuvre de façon paresseuse, en jetant la branche inappropriée, et ne retourner que la branche appropriée en tant que Z-Objet[1] non évalué.
Une stratégie paresseuse est en général recommandée, mais par exemple quand l’évaluateur veut utiliser une mise en œuvre basée sur Z16/Code, ceci pourrait ne pas être réalisable. Et alors l’évaluateur pourrait décider d’évaluer d’abord les arguments puis ensuite l’appel englobant. À fin de compte, il existe des opportunités pour expérimenter différentes stratégies d’évaluation.
Z20/Tests
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.
Types génériques
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. Le résultat de cet Z7/Appel de fonction ressemble à ceci.
{
"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/Listes
Voici une liste de deux chaînes.
[
"string",
"a",
"b"
]
|
[
"Z6",
"a",
"b"
]
|
Si nous transformons ceci en Z-Objets, cela ressemble à ce qui suit.
{
"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"
}
}
|
Notez que la désérialisation d’un littéral tableau JSON doit d’abord vérifier que tous les éléments du tableau ont le même Z1K1/type. Si oui, nous créons une Z10/Liste en utilisant ce type comme argument. Sinon nous créons la Z10/Liste en utilisant Z1/Z-Objet[1] comme argument.
[
"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/Erreurs
Un Z7/Appel de fonction pourrait toujours retourner une Z5/Erreur. Ceci peut être pour des cas plus ou moins irrécupérables (par ex. la division par zéro ou le manque de mémoire sont traités tous les deux de la même façon).
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.
Fonctions non fonctionnelles
Aucune Z8/Fonction n’est autorisée à avoir des effets de bord. Toutes les Z8/Fonctions doivent être fonctionnelles. Cela veut dire qu’elles doivent retourner les mêmes valeurs lorsqu’elles sont appelées avec les mêmes paramètres. Celle signifie que des Z8/Fonctions comme « retourner un nombre aléatoire » ou « retourner l’horodatage actuel » sont impossibles.
This might change in the future. Ce sera traité dans un document ultérieur.
Zx/Types sommes
Un type générique particulièrement utile est le Zx/Type somme (ou Type agrégat), qui prend une liste de Z4/Types et retourne un Z4/Type qui prend une seule instance des types donnés.
Ceci permettra également des paramètres facultatifs dans les appels de fonctions.
Ce sera traité dans un document ultérieur.
Quelques questions et tâches à faire
- Avons-nous besoin de « nécessaire / option » pour des clés quelconques au début ? — non.
- Remplacer les valeurs par défaut syr Z3/Clé par Zx/Type somme (ou au moins rendre ceci cohérent avec la Z17/déclaration de paramètre) ?
- Pourrait être laissé à faire plus tard si nous n ’avons pas besoin de Z3 pour le moment.
- 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