# Trivial

Paradigm(s) Functional User:Hakerh400 2021 Turing complete Interpreter `.txt`

Trivial is a pure functional Haskell-like programming language based on the Hot calculus. Each Trivial program is internally compiled directly to a Hot combinator.

## Overview

Source code consists of functions. Unlike in Haskell, Trivial has no types (everything is a function and everything can be called). Each function technically takes exactly one argument, but multi-argument functions can be implemented using currying. Each function has a name, formal arguments and resulting expression. This is an example of a function:

```func x y z = x z (y z);
```

The name of this function is `func` and it takes three arguments (technically takes only one argument and returns a function that takes the remaining two arguments). Arguments are also functions, so they can be called. The resulting expression is `x z (y z)`, which means: call `x` with argument `z` and then call the result of `x z` with the result of calling `y` with `z`. Semicolon is mandatory after each function definition.

Function name and identifiers (arguments) can contain any character except whitespace, parentheses and semicolons. Also, an identifier cannot consist of a single `=` character (but `==` or `!=` are allowed). All functions are in prefix notation. We can implement operators (literally name a function `+`), but it is still a prefix function, not an infix operator (so we must use `+ x y` to add two numbers).

One important thing to note is that functional Eta reduction is always implicit in Hot calculus (because of the way Hot reduction rules work). Therefore, any two Eta-equivalent functions in Trivial are interchangeable. For example, if we have a function that calculates a square of a number, like this:

```square x = * x x;
```

It basically calls function `*` (assuming we already implemented it) and passes arguments `x` and `x`, which multiplies number `x` by itself. The result is, of course, a number. However, according to the Eta reduction, the following function is equivalent:

```square' x y = * x x y;
```

Function `square'` is equivalent to `square` and it is totally interchangeable with `square`. At first sight, `* x x` is a number and it looks weird to have `* x x y`, which is basically `(* x x) y`. It means that we are calling number `* x x` with argument `y`. However, as we said, everything in this language is a function, so calling a number is perfectly fine. Also, the only way to inspect a value is to call it, so the only way to inspect a number (or a list, or a pair, or any other structure) is to call it.

There are no local function definitions or lambda functions. All functions are global and all values are constants (there are no variables).

## Builtin functions

There are literally no builtin functions. The first function that appears in the source code is the main function (it can have any name). It is transformed to a Hot combinator and evaluated according to the Hot's reduction rules.

## I/O format

If bit stream is used, then I/O format is the same as Hot's I/O format. If ASCII text is used as I/O, then convert each byte to 8 bits (padded with zeros), then reverse bits in each byte, concatenate all bits and parse according to the Hot's I/O format.

## Example

Instead of providing many smaller examples, we provide one large example. In this example, we read an array of space-separated non-negative integers in base-10 and output the sum of odd integers from the array. It should be trivial from this example how to implement pairs, lists, integers, list operations, integer operations, etc. We also show how to implement most of the Haskell's built-in list functions (such as `map`, `foldl`, `foldr`, etc).

There are some exceptions. For example, in Haskell `++` is concatenation, while in this example `++` stands for incrementing an integer and concatenation is `join`. Also, `uncons` in this example has different purpose than Haskell's `uncons`.

Input: `0 1 10 6 67 5 5 97 559 911 44 8 696 8 5 763 8 590 100`
Output: `2413`