Jump to content

Wikifunctions:Function model

From Wikifunctions
Translate this page

Wikifunctions is a multilingual catalog of functions that anyone can contribute to, where anyone can create, maintain, call, and use functions. Every function can have several implementations, e.g. in different programming languages or using different algorithms. It is a “Wikipedia of functions”, and a sister project run by the Wikimedia Foundation.

This document covers the data model and the evaluation model of Wikifunctions.

Throughout this model description, capitalized terms refer to terms defined in the glossary.
Reading the walkthrough of a previous prototype has been very helpful to get a better intuition of what is going on here before reading the following model.

Z1/ZObjects

Wikifunctions is a wiki. As in all wikis, the content of Wikifunctions is mainly stored in wiki pages. Wiki pages can be individually edited, and yet the project as a whole must retain a certain consistency. Also, wiki pages should be individually editable without having to understand all of the other pages.

We introduce ZObjects to represent the content of Wikifunctions. Each wiki page of the main namespace of Wikifunctions contains exactly one ZObject of type Z2/Persistent object. Other namespaces can contain other content, such as policy pages, user pages, discussion pages, etc. A ZObject can be serialized as a JSON object.

A ZObject consists of a list of Key/value pairs.

  • Every value in a Key/value pair is a ZObject.
  • 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.
  • Every Key can only appear once on each ZObject (but may reappear on an embedded ZObject).

ZObjects are basically abstract syntax trees. If there was a TLDR of the project it would probably be “something like LISP in JSON”. The goal is to provide an easy UX to allow the creation and manipulation of ZObjects through a wiki interface, and thus create a coding environment that can reach a large number of contributors in order to grow to become a Wikimedia project with an active community.

Every ZObject must have a key Z1K1/type with a value that evaluates to a Z4/Type.

We use the notation ZID/label to refer to ZIDs in a more or less readable fashion where ‘ZID’ is a ZObject id or a key on such an object, and ‘label’ is the (English language) label attached to that language-neutral id or key.

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.

Canonical form

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/Typed 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 references are replaced with an English label, and on the right hand side with the ZIDs and key references 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.

Representation in JSON

A ZObject can be represented in JSON using as keys the abstract ZID keys (“Z1K1”, etc.), and the JSON representation of the value.

An more readable representation can be given by replacing the abstract keys and ZIDs with their labels in a given language, the “labelized” representation. The labelized version is often ambiguous and can not always be translated to the machine-readable representation.

The following table gives an example of a ZObject representing the natural number 2. On the left we see the ZObject labelized in English, in the middle labelized in German, and on the right we see the ZObject using ZIDs.

{
  "type": "natural number",
  "base 10 representation": "2"
}

{
  "Typ": "natürliche Zahl",
  "Dezimaldarstellung": "2"
}

{
  "Z1K1": "Z10",
  "Z10K1": "2"
}

As you can see, the labels don’t have to be in English, but can be in any of the more than 300 languages Wikifunctions supports.

Normal form

For the processing of ZObjects by the evaluator, all ZObjects are turned into the normal form described above. The normal form doesn't rely on any implicitness regarding whether to interpret a string value as a Z6/String or a Z9/Reference, but they are all expressed as explicit ZObjects.

This means the normal form of a ZObject is a tree where all leaves are either of the type Z6/String or Z9/Reference.

This also means that all Lists are represented as ZObjects, not as arrays.

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(
  is zero(right),
  left,
  add(
    successor(left),
    predecessor(right)
  )
)		 Z802(
  Z782(Z781K2),
  Z781K1,
  Z781(
    Z783(Z781K1),
    Z784(Z781K2)
  )
)

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.

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:

  1. Quote a ZObject when we believe it may be invalid in some way.
  2. But do not quote Z1K1 by itself. If its value is in doubt, quote the entire object that contains it.
  3. Quote resolvable keys (keys whose values contain instances of Z7, Z9, or Z18) that might inappropriately be ingested as the input to a function.
  4. 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

See also

Retrieved from "https://www.wikifunctions.org/w/index.php?title=Wikifunctions:Function_model&oldid=182057"