Wikifunctions:Function model

From Wikifunctions
Translate this page
Other languages:

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[1] of type Z2/Persistent object. Other namespaces can contain other content, such as policy pages, user pages, discussion pages, etc. A ZObject[1] can be serialized as a JSON object.

A ZObject[1] consists of a list of Key/value pairs.

  • Every value in a Key/value pair is a ZObject[2].
  • Every Key can only appear once on each ZObject[1] (but may reappear on an embedded ZObject[1]).

ZObjects[1] 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[1] through a wiki interface, and thus create a coding environment that can reach a large number of contributors and may become a Wikimedia project with an active community.

Every ZObject[1] must have a key Z1K1/type with a value that evaluates to a Z4/Type (this will be explained soon).

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

Syntax

The canonical representation of a ZObject[2] is a subset of JSON. A well-formed ZObject[2] has the following syntax:

ZObject := String | List | Record
String  := "Character*" // to be specific, as in JSON / ECMA-404
List  := [ ( ZObject ( , ZObject )* )? ]
Record  := { "Z1K1": ZObject ( , "Key": ZObject )* }
Key  := ZNumber KNumber | KNumber
ZNumber := Z Number
KNumber := K Number
Number  := [1-9][0-9]* // a positive non-zero decimal integer

where:

  • bold characters are terminal symbols;
  • italic characters are used for non-terminal symbols;
  • ( ) are used to surround a group which may contain one or several alternatives separated by |;
  • a group can be repeated using * which means repeat 0..n times, or + which means repeat 1..n times;
  • a group followed by ? is optional;
  • whitespaces can be used as in JSON.

That results in the subset of JSON without numbers, null, booleans, and with limited keys.

In order to be well-formed, the Z1K1 key must have a value that may evaluate to a Z4 Type, i.e. either is a well-formed literal of type Z4, a reference, or a function call.

Serialization

A ZObject[1] is serialized to its canonical JSON representation using as keys the abstract ZID keys (“Z1K1”, etc.), and for values either:

  • the canonical JSON representation of another (transient) ZObject[1],
  • the ZID[3] of a persistent (Z2) ZObject[1] (i.e. a string value with a leading capital letter of the latin alphabet and digits following),
  • a simple string value, which can alternatively be represented as a ZObject[1] itself (Z6/string type), or
  • a JSON array as a representation for Z10/list objects.

An alternate more readable representation can be given by replacing the abstract keys and ZIDs with their labels in a given language, the “labelized” representation.

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

{
  "type": "positive integer",
  "base 10 representation": "2"
}

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

{
  "Z1K1": "Z10070",
  "Z10070K1": "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.

Also note that if the key is Z2K1/id or Z6K1/string value, then the value is always serialized as a simple string value.

Deserialization

The canonical JSON representation for a ZObject[1] is converted into its computational equivalent essentially through standard JSON parsing — that is the JSON object becomes a ZObject[1] with the same (abstract) keys. The four different allowed value formats are parsed as follows:

If the value is another JSON object, that in turn should follow the same deserialization rules, recursively.

For string values, if the value is a simple string that starts with a capital letter of the latin alphabet followed by a number then it is interpreted as a reference to a persistent ZObject[1], a Z9/Reference. In the above example, the value of Z1K1/type is given as the string "Z10070", but it should be parsed as a reference ZObject[1] which would itself be represented as follows: 

{
  "type": "reference",
  "reference id": "positive integer"
}

{
  "Z1K1": "Z9",
  "Z9K1": "Z10070"
}

On the other hand if the value is a simple string that does not start with a capital letter of the latin alphabet followed by a number, the string is understood as a ZObject[1] of the type Z6/String and the given value. I.e. the value of Z10070K1/base 10 representation is given as the string "2", but it should be parsed as a ZObject[1] that looks as follows: 

{
  "type": "string",
  "string value": "2"
}

{
  "Z1K1": "Z6",
  "Z6K1": "2"
}

Note that the deserialization process should not be repeated as it could in these cases (the value of the Z1K1/type key would be interpreted as of type Z9/Reference, and the value of Z6K1/string value again as of type Z6/string) as that would lead to an infinite recursion; these are internally represented ZObjects[1], not serialized JSON at this point.

Given these deserialization rules, if we need to write an actual string that starts with a capital letter of the latin alphabet and is followed by a number, we need to escape this. This uses the exception regarding Z6K1/string value above. Here is the string value "Z1" on the key Z11K2/text. 

{
  "type": "text",
  "language": "English",
  "text": {
    "type": "string",
    "string value": "Z1"
  }
}

{
  "Z1K1": "Z11",
  "Z11K1": "Z1251",
  "Z11K2": {
    "Z1K1": "Z6",
    "Z6K1": "Z1"
  }
}

Finally, note that JSON arrays are deserialized as Z10/List ZObjects[1]. The full interpretation of JSON arrays is explained in the section on Z10/Lists below.

Normalization

For the processing of ZObjects[1] by the evaluator, all ZObjects[1] are turned into a normalized version of themselves. The normalized version is similar to the deserialized version, but we don'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.[1]

This means the normalized representation of a ZObject[1] is a tree where all leaves are either of the type Z6/String or Z9/Reference.

This also means that all Z10/Lists are represented as ZObjects[1], not as an array. Furthermore, all Z10/List objects must have both the (Z10)K1/head and (Z10)K2/tail keys. An empty list (including the tail of a list with one element) is a Z13/Empty[4].

The following normalized form represents the positive integer 2. 

{
  "type": {
    "type": "reference",
    "reference id": "positive integer"
   },
   "base 10 representation": {
     "type": "string",
     "string value": "2"
   }
}

{
  "Z1K1": {
    "Z1K1": "Z9",
    "Z9K1": "Z10070"
   },
   "Z10070K1": {
     "Z1K1": "Z6",
     "Z6K1": "2"
   }
}

Normalized views are used only 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[1] stored in a Wikifunctions wiki page is a Z2/Persistent object. ZObjects[2] that are not stored on their own wiki page are called transient ZObjects[2].

Every persistent ZObject[1] must have a Z2K1/id, a ZID which is equivalent to the name of the wiki page where it is stored. Let’s assume that there is a ZObject[1] for the positive integer 2 that we saw previously and that it is stored on the page Z382/two. This is what it could look like (note that the ZIDs are not necessarily the ones we will use in Wikifunctions). 

{
  "type": "persistent object",
  "id": "Z382",
  "value": {
    "type": "positive integer",
    "base 10 representation": "2"
  },
  "label": {
    "type": "multilingual text",
    "texts": [
      {
        "type": "text",
        "language": "English",
        "text": "two"
      },
      {
        "type": "text",
        "language": "German",
        "text": "zwei"
      }
    ]
  }
}

{
  "Z1K1": "Z2",
  "Z2K1": "Z382",
  "Z2K2": {
    "Z1K1": "Z10070",
    "Z10070K1": "2"
  },
  "Z2K3": {
    "Z1K1": "Z12",
    "Z12K1": [
      {
        "Z1K1": "Z11",
        "Z11K1": "Z1251",
        "Z11K2": "two"
      },
      {
        "Z1K1": "Z11",
        "Z11K1": "Z1254",
        "Z11K2": "zwei"
      }
    ]
  }
}

The Z2/Persistent object provides metadata for the ZObject[1] embedded in the Z2K2/value.

The Z2K3/label is a ZObject[1] of the type Z12/multilingual text which has one Z3/Key, Z12K1/texts, pointing to a Z10/list of Z11/monolingual text ZObjects[1] (remember that a Z10/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 that provide metadata, which are for documentation, presentation in the wiki, and to improve findability. They are all defined on Z2/Persistent object.

Z9/References

As we have seen on the positive number 2 is that the value of Z1K1/type is a ZObject[1] of type Z9/Reference. If we extend that, it would look like this. 

{
  "type": {
    "type": "reference",
    "reference id": "positive integer"
  },
  "base 10 representation": "2"
}

{
  "Z1K1": {
    "Z1K1": "Z9",
    "Z9K1": "Z10070"
  },
  "Z10070K1": "2"
}

A Z9/Reference is a reference to the Z2K2/value of the ZObject[1] with the given ID, and means that this Z2K2/value should be inserted here. To give an example, given the following array with a single element: 

[
  "two"
]

[
  "Z382"
]

The element is a shortcut Z9/Reference, that would look like this in the expanded form (as explained in the Section on deserialization): 

[
  {
    "type": "reference",
    "reference id": "two"
  }
]

[
  {
    "Z1K1": "Z9",
    "Z9K1": "Z382"
  }
]

And since this is a reference, this is to be replaced with the Z2K2/value of the Z2/Persistent object with the ZID Z382 (as given above), i.e. it would look as follow: 

[
  {
    "type": "positive integer",
    "base 10 representation": "2"
  }
]

[
  {
    "Z1K1": "Z10070",
    "Z10070K1": "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[1] of type Z4/Type. ZObjects[1] of a type are called instances of that type. So Z382/two we saw above was an instance of the type Z10070/positive integer.

A Type provides us with the means to check the validity of a ZObject[1] 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 (a simplified) type for positive integers. 

{
  "type": "persistent object",
  "id": "Z10070",
  "value": {
    "type": "type",
    "identity": "positive integer",
    "keys": [
      {
        "type": "key",
        "value type": "string",
        "key id": "Z10070K1",
        "label": {
          "type": "multilingual text",
          "texts": [
            {
              "type": "text",
              "language": "English",
              "text": "base 10 representation"
            },
            {
              "type": "text",
              "language": "German",
              "text": "Dezimaldarstellung"
            }
          ]
        },
        "default": "value required"
      }
    ],
    "validator": "validate positive integer"
  },
  "label": {
    "type": "multilingual text",
    "texts": [
      {
        "type": "text",
        "language": "English",
        "text": "positive integer"
      },
      {
        "type": "text",
        "language": "German",
        "text": "natürliche Zahl"
      }
    ]
  }
}

{
  "Z1K1": "Z2",
  "Z2K1": "Z10070",
  "Z2K2": {
    "Z1K1": "Z4",
    "Z4K1": "Z10070",
    "Z4K2": [
      {
        "Z1K1": "Z3",
        "Z3K1": "Z6",
        "Z3K2": "Z10070K1",
        "Z3K3": {
          "Z1K1": "Z12",
          "Z12K1": [
            {
              "Z1K1": "Z11",
              "Z11K1": "Z1251",
              "Z11K2": "base 10 representation"
            },
            {
              "Z1K1": "Z11",
              "Z11K1": "Z1254",
              "Z11K2": "Dezimaldarstellung"
            }
          ]
        },
        "Z3K4": "Z25"
      }
    ],
    "Z4K3": "Z10559"
  },
  "Z2K3": {
    "Z1K1": "Z12",
    "Z12K1": [
      {
        "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": "positive integer",
  "keys": [
    {
      "type": "key",
      "value type": "string",
      "keyid": "Z10070K1",
      "default": "value required"
    }
  ],
  "validator": "validate positive integer"
}

{
  "Z1K1": "Z4",
  "Z4K1": "Z10070",
  "Z4K2": [
    {
      "Z1K1": "Z3",
      "Z3K1": "Z6",
      "Z3K2": "Z10070K1",
      "Z3K4": "Z25"
    }
  ],
  "Z4K3": "Z10559"
}

Type Z10070/positive integer defines in Z4K2/keys the new Z3/Key Z10070K1/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 a Z10/List of Z5/errors. If the Z10/List is empty then the instance has passed the validation. In the given case, the Z8/Function would do the following checks:

  • There is one and only one Key, Z10070K1/base 10 representation, on the instance, besides the metadata.
  • 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 has a length of 1.
  • The base 10 representation is below 232 (or whatever else the limit is for this Type).

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 may be 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": "Z144",
  "Z144K1": "Z382",
  "Z144K2": "Z382"
}

{
  "Z1K1": "Z7",
  "Z7K1": "Z144",
  "K1": "Z382",
  "K2": "Z382"
}

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.

One example is given by the call to Z79/curry right in the Section on Z20/Tests below.

A Global Key is always defined on the ZObject[1] the ZID part of its ID refers to.

Z8/Functions

In the definition of Z10070/positive integer we saw a first reference to a Z8/Function, Z10559/validate positive integer. Here, we will use a much simpler function, Z144/add. Z144/add is a Z8/Function which takes two Z10070/positive integers and returns a Z10070/positive integer.

Note that we leave the value of Z1K1/Type empty for the moment. We will get back to this in a later section. We only show the value. 

{
 "type": { ... },
 "arguments": [
   {
     "type": "argument declaration",
     "argument type": "positive integer",
     "key id": "Z144K1",
     "label": { ... }
   },
   {
     "type": "argument declaration",
     "argument type": "positive integer",
     "key id": "Z144K2",
     "label": { ... }
   }
 ],
 "return type": "positive integer",
 "tests": [
   "add one and zero",
   "add two and two"
 ],
 "identity": "Z144"
}

{
 "Z1K1": { ... },
 "K1": [
   {
     "Z1K1": "Z17",
     "Z17K1": "Z10070",
     "Z17K2": "Z144K1",
     "Z17K3": { ... }
   },
   {
     "Z1K1": "Z17",
     "Z17K1": "Z10070",
     "Z17K2": "Z144K2",
     "Z17K3": { ... }
   }
 ],
 "K2": "Z10070",
 "K3": [
   "Z1441",
   "Z1442"
 ],
 "K5": "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 K3/tests and the K1/type declarations on the arguments and the K2/return type. Furthermore, since a Function can have several Z14/Implementations (see below), the Implementations confirm each other.

Z8/Functions are not allowed to have state-changing side effects.

Z7/Function calls

The following ZObject[1] 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": "Z144",
  "Z144K1": "Z382",
  "Z144K2": "Z382"
}
add(two, two) Z144(Z382, Z382)

Using literals instead of persistent ZObjects[1] for the arguments, this would look as follows.

  • Note that we are creating the literals using the Z10070/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": "positive integer",
    "base 10 representation": "2"
  },
  "right": {
    "type": "positive integer",
    "base 10 representation": "2"
  }
}

{
  "Z1K1": "Z7",
  "Z7K1": "Z144",
  "Z144K1": {
    "Z1K1": "Z10070",
    "Z10070K1": "2"
  },
  "Z144K2": {
    "Z1K1": "Z10070",
    "Z10070K1": "2"
  }
}
add(positive_integer("2"), positive_integer("2")) Z144(Z10070("2"), Z10070("2"))

When this Z7/Function call gets evaluated, it results as expected in the number four. 

{
  "type": "positive integer",
  "base 10 representation": "4"
}

{
  "Z1K1": "Z10070",
  "Z10070K1": "4"
}
positive_integer("4") Z10070("4")

Evaluation is performed repeatedly on the evaluation result until a fixpoint is reached.

A Z8/Function has an optional K4/implementation key that points to the Z14/Implementation to be used. This is usually filled by the evaluation engine as part of the evaluation step, but if a specific implementation is given, the evaluator will honor it.

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 the Z144/add Function and look at five different Z14/Implementations.

Builtin implementations

A builtin implementation tells the evaluator, i.e. the runtime, to return an appropriate evaluation result. Builtins are hardcoded into the evaluator. Z14K4/builtin refers to the hard-coded builtin-ID (which usually should be ZID of the Z2/Persistent object, but does not have to). 

{
  "type": "implementation",
  "implements": "add",
  "builtin": "Z1443"
}

{
  "Z1K1": "Z14",
  "Z14K1": "Z144",
  "Z14K4": "Z1443"
}
// implementation(add, , , Z1443)

Builtins do not have to be declared as ZObjects[1] in order to be used. An evaluator would be aware of all its own builtins and could use them at will. It is still useful to declare a builtin in order to call them directly.

Z16/Code

Note: This section might need to be reworked, in order to let different programming languages have different implementations.

An implementation in Z16/Code represents a code snippet in a given programming language. 

{
  "type": "implementation",
  "implements": "add",
  "code": {
    "type": "code",
    "language": "javascript",
    "source": "K0 = Z144K1 + Z144K2"
  }
}

{
  "Z1K1": "Z14",
  "Z14K1": "Z144",
  "Z14K3": {
    "Z1K1": "Z16",
    "Z16K1": "Z100701",
    "Z16K2": "K0 = Z144K1 + Z144K2"
  }
}
// implementation(add, , code(javascript, "_0 = _1 + _2")) 
{
  "type": "implementation",
  "implements": "add",
  "code": {
    "type": "code",
    "language": "python3",
    "source": "K0 = Z144K1 + Z144K2"
  }
}

{
  "Z1K1": "Z14",
  "Z14K1": "Z144",
  "Z14K3": {
    "Z1K1": "Z16",
    "Z16K1": "Z100703",
    "Z16K2": "K0 = Z144K1 + Z144K2"
  }
}
// implementation(add, , code(python3, "_0 = _1 + _2"))

In this case, the implementations are the same for JavaScript and Python, but that is obviously rarely the case.

The evaluator would know how to transform the given ZObjects[1] representing the arguments into the supported programming languages (which is also the reason we limit the positive integer type to 32 bit — as the behavior for the two supported languages is equivalent in that range), how to execute the provided code snippet, and then how to transform the result back into a ZObject[1] representing the result.

Eventually, the translation of ZObjects[1] 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.

Composition

The most portable (but often also the slowest) Z14/Implementation is achieved through composition of other Z8/Functions. We will look at two different implementations.

We show both the ZObject[1] of the implementation, as well as an easier to read notation based on function call syntax (note that this syntax also replaces spaces in labels with underscores). 

{
 "type": "implementation",
 "implements": "add",
 "composition": {
   "type": "function call",
   "function": "lambda to integer",
   "arg": {
     "type": "function call",
     "function": "lambda add",
     "left": {
       "type": "function call",
       "function": "integer to lambda",
       "arg": {
         "type": "argument reference",
         "reference": "left"
       }
     },
     "right": {
       "type": "function call",
       "function": "integer to lambda",
       "arg": {
         "type": "argument reference",
         "reference": "right"
       }
     }
   }
 }
}

{
 "Z1K1": "Z14",
 "Z14K1": "Z144",
 "Z14K2": {
   "Z1K1": "Z7",
   "Z7K1": "Z71",
   "Z71K1": {
     "Z1K1": "Z7",
     "Z7K1": "Z77",
     "Z77K1": {
       "Z1K1": "Z7",
       "Z7K1": "Z72",
       "Z72K1": {
         "Z1K1": "Z18",
         "Z18K1": "Z144K1"
       }
     },
     "Z77K2": {
       "Z1K1": "Z7",
       "Z7K1": "Z72",
       "Z72K1": {
         "Z1K1": "Z18",
         "Z18K1": "Z144K2"
       }
     }
   }
 }
}
lambda_to_positive_integer(
  lambda_add(
    positive_integer_to_lambda(left),
    positive_integer_to_lambda(right)
  )
) 		Z71(
  Z77(
    Z72(Z144K1),
    Z72(Z144K2)
  )
)

Wikifunctions contains a full implementation of the lambda-calculus (in fact, that’s one of the inspirations for the extension name). This composition translates the Z10070/positive integers into Church numerals using Z72/positive integer to lambda, then uses the addition as it is implemented in the lambda-calculus of Wikifunctions (Z77/lambda add), and the result is translated to a Z10070/positive integer from a Church numeral using Z71/lambda to positive integer. (In case you’re curious - Z77/lambda add is implemented the same way as Z1445/add recursive below, but using lambda-based functions as defined over Church numerals).

This relies entirely on the Lambda calculus. 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 Z144/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. 

{
 "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": "Z144",
 "Z14K2": {
   "Z1K1": "Z7",
   "Z7K1": "Z31",
   "Z31K1": {
     "Z1K1": "Z7",
     "Z7K1": "Z145",
     "Z145K1": {
       "Z1K1": "Z18",
       "Z18K1": "Z144K2"
     }
   },
   "Z31K2": {
     "Z1K1": "Z18",
     "Z18K1": "Z144K1"
   },
   "Z31K3": {
     "Z1K1": "Z7",
     "Z7K1": "Z144",
     "Z144K1": {
       "Z1K1": "Z7",
       "Z7K1": "Z146",
       "Z146K1": {
         "Z1K1": "Z18",
         "Z18K1": "Z144K1"
       }
     },
     "Z144K2": {
       "Z1K1": "Z7",
       "Z7K1": "Z147",
       "Z147K1": {
         "Z1K1": "Z18",
         "Z18K1": "Z144K2"
       }
     }
   }
 }
}
if(
  is_zero(right),
  left,
  add(
    successor(left),
    predecessor(right)
  )
) 		Z31(
  Z145(Z144K2),
  Z144K1,
  Z144(
    Z146(Z144K1),
    Z147(Z144K2)
  )
)

This composition relies on a number of other Z8/Functions: Z145/is zero, Z146/successor, Z147/predecessor, Z31/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.

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. Z1445/add recursive provides us with an example that might end up in an endless loop if we try a complete evaluation order:

For the call to Z31/if in Z1445/add recursive 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 Z31K1/condition we will only need to return either Z31K2/consequent or Z31K3/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 Z31/if can be implemented lazily, drop the irrelevant branch, and return the relevant branch as an unevaluated ZObject[1].

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/Tests

Z20/Tests are ZObjects[1] that call a Z7/function call and then test the result using a Z8/Function. If the Z8/Function returns an Z54/true, the Z20/Test 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/Tests 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": "test",
 "call": {
   "type": "function call",
   "function": "add",
   "left": "two",
   "right": "two"
 },
 "check": {
   "type": "function call",
   "function": "curry right",
   "function to curry": "equal positive integer",
   "right": "four"
 }
}

{
 "Z1K1": "Z20",
 "Z20K1": {
   "Z1K1": "Z7",
   "Z7K1": "Z144",
   "Z144K1": "Z382",
   "Z144K2": "Z382"
 },
 "Z20K2": {
   "Z1K1": "Z7",
   "Z7K1": "Z79",
   "Z79K1": "Z150",
   "Z79K2": "Z384"
 }
}

Z1442/Add two and two exhibits an interesting pattern: the Z20K2/check Function is created on the fly by currying the function Z150/equal positive integer. We would not want to write a Z8/Function called “equals four”, but instead use the Z150/equal positive integer function and fix (curry) one of its arguments with a constant value, Z384/four in this case. So when it runs, Z20K2/check will have the value of a dynamically created Z8/Function, which in turn will be used to validate the result of the function call in Z20K1/call.

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, perhaps Z10022/Pair is a function that takes two Z4/Types as its parameters, one for the first and one for the second element, and returns an inline Z4/Type. So if we want to make a pair of Z10070/Positive integers, we would call Z10022/Pair(Z10070/Positive Integer, Z10070/Positive integer) and the result would be a Z4 which we can use for the Z1K1 field of a ZObject.[1] 

{
 "type": {
   "type": "function call",
   "function": "pair",
   "first": "positive integer",
   "second": "positive integer"
 },
 "first": "one",
 "second": "two"
}

{
 "Z1K1": {
   "Z1K1": "Z7",
   "Z7K1": "Z10022",
   "Z10022K1": "Z10070",
   "Z10022K2": "Z10070"
 },
 "K1": "Z381",
 "K2": "Z382"
}

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": "pair",
   "first": "positive integer",
   "second": "positive integer"
 },
 "keys": [
   {
     "type": "key",
     "id": "K1",
     "value type": "positive integer",
     "required": "true"
   },
   {
     "type": "key",
     "id": "K2",
     "value type": "positive integer",
     "required": "true"
   }
 ],
 "validator": "validate pair"
}

{
 "Z1K1": "Z4",
 "Z4K1": {
   "Z1K1": "Z7",
   "Z7K1": "Z10022",
   "Z10022K1": "Z10070",
   "Z10022K2": "Z10070"
 },
 "Z4K2": [
   {
     "Z1K1": "Z3",
     "Z1K2": "K1",
     "Z3K1": "Z10070",
     "Z3K2": "Z54"
   },
   {
     "Z1K1": "Z3",
     "Z1K2": "K2",
     "Z3K1": "Z10070",
     "Z3K2": "Z54"
   }
 ],
 "Z4K3": "Z100702"
}

This also explains 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 Z10022/Pair that doesn’t restrict the Z4/Type of one or both of its elements, one could call the Z10022/Pair function with Z1/ZObject[5] as one or both arguments.

Z10/Lists

Here is a list of two strings. 

[
 "a",
 "b"
]

[
 "a",
 "b"
]

If we turn this into ZObjects[1], it looks as follows. 

{
 "type": {
   "type": "function call",
   "function": "list",
   "elementtype": "string"
 },
 "head": "a",
 "tail": {
   "type": {
     "type": "function call",
     "function": "list",
     "elementtype": "string"
   },
   "head": "b",
   "tail": "nil"
 }
}

{
 "Z1K1": {
   "Z1K1": "Z7",
   "Z7K1": "Z10",
   "Z10K1": "Z6"
 },
 "K1": "a",
 "K2": {
   "Z1K1": {
     "Z1K1": "Z7",
     "Z7K1": "Z10",
     "Z10K1": "Z6"
   },
   "K1": "b",
   "K2": "Z13"
 }
}

Note that the deserialization of a JSON array literal has to first check whether all elements of the array have the same Z1K1/type. If yes, we create a Z10/List using that type as the argument. If not, we create a Z10 using Z1/ZObject[5] as the argument.

Z8/Function types

Functions are using the same mechanism as generic types to be concrete Function types. I.e. Z8/Function is not the Z4/Type of a Function, but rather is a Function itself that creates a Z4/Type that can be used for a Function.

On Z144/add, we previously skipped the Z1K1/type field. Here is the field. 

{
 "type": {
   "type": "function call",
   "function": "function",
   "return type": "positive integer",
   "argument types": [
     "positive integer",
     "positive integer"
   ]
 },
 ... 
}

{
 "Z1K1": {
   "Z1K1": "Z7",
   "Z7K1": "Z8",
   "Z8K1": "Z10070",
   "Z8K2": [
     "Z10070",
     "Z10070"
   ]
 },
 ... 
}

This will return the Z4/Type that also contains its return and argument types.

If you need a Z4/Type for a Z8/Function that works with any Z8K1/return type and Z8K2/argument types, then we would use Z1/ZObject[5] for Z8K1/return type or the empty list as the Z8K2/argument type. This is useful, e.g., for a Z8/Function that tells you the number of arguments a Z8/Function has. Obviously, if you would already need to know what the number of arguments is in order to select the right function, this would be quite useless.

The validator on Z4/Function ensures that the types as given on the Z7/function call to Z8/Function are consistent with the types given on the Z4K2/key declaration.

Z5/Errors

A Z7/Function call could always result in a Z5/Error. This can be for more or less unrecoverable cases (i.e. division by zero or out of memory both are handled the same way). A Z5/Error is a generic type called with a Z15/Error type.

Normally, when a Z5/Error is being given as an argument to a Z7/Function call, the Z5/Error will be wrapped to enable tracing and passed through. The evaluator won’t even call the Z14/Implementation.

If a Z8/Function wants to catch a Z5/Error, it has to explicitly list all the Z15/Error types it wants to catch in its signature. If then a Z5/Error of the listed Z15/Error types shows up, the Z14/Implementation will still be called and can now handle the Z5/Error.

An Z5/Error is an instance of Z4/Type Z5/Error(Z15/Error type). The resulting type has further Z3/Keys, as specified by the Z15/Error type, in order to keep useful information about the Z5/Error.

Example: if you call the Z157/division function with a Z380/zero for the Z157K2/denominator, you would get back the the following object: Z5/error(Z442/division_by_zero)(Z384/four)

Non-functional Functions

Whereas no Z8/Function is allowed to have side effects, some Z8/Functions might not be entirely functional. I.e. they might return different values when being called with the same parameters. Typical such Z8/Functions are “return a random number”, “return the current time”, or “return a value from Wikidata”.

We also see that it would make sense not only to say whether a Z8/Function is functional or not, but in fact to specify a caching regime for each Z8/Function.

All these Z8/Functions need to be marked, and no Z8/Function that is fully functional may call a Function that is not. The evaluator has to make sure that this condition is being fulfilled, or else results might be stale or otherwise unexpected.

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.

REPL

This follows the definition of REPL: Read, Evaluate, Print, Loop:

  • The REPL, or command line interface, takes an input Z6/string.
  • It then runs a Z8/Function over that input string which parses and preprocesses the input and returns a ZObject[1].
  • That ZObject[1] gets validated by the validator of the Z4/Type of the ZObject[1]. If valid, the result then evaluates until it reaches a fix point.
  • Then the REPL calls a Z8/Function to linearize the resulting ZObject[1] to a Z6/string. This string is then displayed or printed out to the user.
  • And the REPL asks for new input.

A good Wikifunctions REPL should allow to:

  • set the parsing function;
  • switch validation on or off;
  • switch evaluation on or off;
  • set the linearization function.

This allows for many interesting patterns. For example, there could be parsers for many different syntaxes. Simple function call syntaxes as we have seen above, a Haskell-like syntax without many brackets, a syntax that is closer to mathematics using infix operators, translations from labels to ZIDs, or entirely domain specific syntaxes. The parser can also include a preprocessor. One example of preprocessing is to automatically add type coercions, thus making it easier to write Z7/Function calls, or specify the Z14/Implementation on a Z8/Function, and thus force the evaluator to use a specific Z14/Implementation.

Also the linearizer can be highly flexible towards a given use case. Parsers and linearizers will be Z8/Functions in Wikifunctions, which will allow anyone to create new parsers and linearizers and use them in a wide range of interfaces, thus enabling interesting usage patterns.

Reference index of central Z4/Types and their Z3/Keys

  • Z1/ZObject[1]
    • Z1K1/type (Z4/Type)
  • Z2/Persistent object
    • Z2K1/id (Z6/string)
    • Z2K2/value (Z1/ZObject[1])
    • Z2K3/label (Z12/Multilingual text)
  • Z3/Key
    • Z3K1/value type (Z4/Type)
    • Z3K2/key id (Z6/String)
    • Z3K3/label (Z12/Multilingual text)
  • Z4/Type
    • Z4K1/identity (Z4/Type)
    • Z4K2/keys (Z10/List(Z3/Key))
    • Z4K3/validator (Z8/Function(...))
  • Z5/Error
    • Z5K1/error type
  • Z6/String
    • Z6K1/string value (Z6/String)
  • Z7/Function call
    • Z7K1/function (Z8/Function)
    • Others based on Z8/Function
  • Z8/Function (generic)
    • K1/arguments (Z10/List(Z17/Argument declaration))
    • K2/return type (Z4/Type)
    • K3/tests (Z10/List(Z20/Test))
    • K4/implementation (Z14/Implementation)
    • K5/identity (Z8/Function)
  • Z9/Reference
    • Z9K1/reference ID (Z6/String)
  • Z10/List (generic)
    • K1/head
    • K2/tail

Main differences to AbstractText

  • Only Z7/Function calls get evaluated. Everything else does not get evaluated.
  • Introduction of generic types
  • Z10/String and Z22/Pair are now generic types.
  • Z8/Function is a generic type, based on the types of the inputs and outputs.
  • Added a K5 to Z8s
  • Changed Z3K2 from validator to keyid, Z3K3 from required to label, added Z3K4-Z3K6
  • Removed Z4K4-Z4K7
  • Subtle change to Z4K1
  • Changed all keys on Z14/Implementation, got rid of Z19/builtin
  • Turn Z20/Test into top level ZObjects[1] instead of subobjects of Z8/Function
  • By using autoquote on Z20/Test, got rid of Z21/Argumentlist
  • Turn Z14/Implementation into top level ZObjects[1] instead of subobjects of Z8/Function
  • ZID of Pair was changed from Z2 to Z22 (in order to give space for Z2/Persistent object)
  • Z5/Error and Z15/Exception have been folded together into Z5/Error
  • Z5/Error is now generic type.
  • Specified REPL behavior
  • Break out Z2/Persistent object from Z1
  • Added Z17K2/Keyid and Z17K3/Label to Z17
  • Builtins can now change their ZID

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
  • Remove Z2K4 for now?
  • Break out Z16/Implementation by programming language?
  • If Errors can have their own fields, programming languages should too
  • Make it generic on programming language. That’s for later.

Notes

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 1.32 1.33 1.34 1.35 1.36 1.37 1.38 1.39 1.40 1.41 1.42 1.43 1.44 1.45 1.46 1.47 1.48 1.49 1.50 1.51 1.52 1.53 1.54 1.55 1.56 1.57 1.58 1.59 explicitly typed – beginning with a Z1K1/type.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 as defined in #Syntax.
  3. ↑ Z2K1
  4. ↑ or a Z23/Nothing?
  5. ↑ 5.0 5.1 5.2 literally with "Z1" as the value.

See also

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