# Infilisp

Paradigm(s) | functional |
---|---|

Designed by | User:Orisphera |

Appeared in | Category:2024:2024 |

Type system | dynamic, duck |

Computational class | Turing-complete |

Reference implementation | Unimplemented |

Influenced by | Lisp |

File extension(s) | {{{files}}} |

**Infilisp** is a language by Orisphera. It has an incomplete specification given below; the way to complete it may influence how procedurally generated programs work.

## History

Before Infilisp, Orisphera had another idea based on Lisp. In it, everything would be expressed through lists. Also, the last argument of the built-in functions wouldn't be added to the expression as an element; instead, its contents would be added to it. (For example, `(car (quote a) quote (b))`

would evaluate to `(a b)`

. Note that the language wouldn't actually use words, and that code, passed to the interpreter, would actually be treated as `(()())`

and evaluate to `(())`

. The words would have to be replaced with strings of parentheses according to the specification.)

Later, Orisphera came up with two ideas for procedural generation in computer games to implement in some future. One was procedurally generating structures. In it, smaller structures would be combined into larger ones, which would then be combined into even larger ones, and so on. The same structures could be repeated several times in a larger one and across different ones. This idea is not very important to Infilisp, although it can be combined with the other one.

The other one is procedurally generated code. For it, Orisphera decided to create their own language. Later, they decided that it would be a Lisp derivative. (They also considered Nix and Haskell, but decided to stick to Lisp.) Then, they decided to make the last argument of functions unpacked, like in the older idea. This idea evolved into Infilisp.

## Working

In Infilisp, the program is internally represented as an infinite binary tree. The nodes contain some information, but any finite change under which it remains correct doesn't matter. The tree is dynamically generated. The language standard library provides some basic instructions that can be used to write Infilisp code to generate it. The node types should follow the below specification:

The types should have the following methods (as they're called in the (incomplete) reference implementation): `get car cdr apply eval to_bool to_ll`

. Except for `to_bool to_ll`

, they should return Infilisp objects. The `to_bool`

method should return a boolean, and `to_int`

should return an integer. (The exact type may depend on the use case.) The `apply`

method also takes an object as an argument. Any types added to the library must obey the following rules (note: in the reference implementation, objects are `InfilispOP`

, but types should inherit from `InfilispObNorm`

or `InfilispObEOU`

and implement methods that take the reference to the object as the (first) argument):

- These rules use the notion of equivalent objects. This notion is defined axiomatically. A library designer should make it so that, assuming that existing types allow for a definition that works, they should also allow for one after adding their types.
- Every object
*a*is equivalent to*a*. - If an object
*a*is equivalent to objects*b*and*c*,*b*is equivalent to*c*.

- Every object
- Methods of objects (in the above implementation —
`InfilispOP`

) that are equivalent to each other should give objects that are also equivalent to each other.- In case of
`to_bool`

and`to_ll`

, they should give the same result instead. - Similarly,
`apply`

of the same object applied to objects that are equivalent to each other should also give objects that are also equivalent to each other.

- In case of
- For any object
`self`

:`self.get()`

should be equivalent to`self`

;`self.apply(other)`

should be equivalent to`self.eval().apply(other)`

for any`other`

;`self.eval(other)`

should be equivalent to`self.car().apply(self.cdr().eval())`

;`self.to_ll()`

should be equal to`self.cdr().to_ll() * 2`

if`self.car.to_bool()`

is false and 1 more otherwise;`self.to_bool()`

should be equal to`self.car.to_bool() || self.cdr.to_bool()`

.

- If
`self.car()`

is equivalent to`other.car()`

and`self.cdr()`

is equivalent to`other.cdr()`

, then`self`

and`other`

must be equivalent.

The `to_bool()`

method may return the true value for all objects not equivalent to a certain one; whether it does is up to whoever completes the specification.

The implementation should preferably provide two intermediate classes to inherit from. In one (`InfilispObEOU`

in the reference implementation), all operations except for `get`

should be defined, and in the other one (`InfilispObNorm`

in the reference implementation), all operations except for `car`

and `cdr`

should be defined.

It is advised to avoid infinite loops as much as possible. However, avoiding them completely is, unfortunately, impossible.

## Types

Infilisp includes the folowing types:

- Integer (the exact type is implementation-defined, but it must include 0 and -1):
`car`

gives -1 for odd numbers and 0 for even numbers;`cdr`

gives the number divided by 2, rounding down (3 -> 1, -3 -> -2);`apply`

gives`other.car()`

for negative numbers and`other.cdr()`

for non-negative ones;`eval`

gives -1 for negative numbers and 0 for non-negative ones;`to_bool`

gives the true value iff it isn't 0;`to_ll`

gives the number.

- List (
`std::shared_ptr<std::vector<InfilispOP>>`

) with a starting index and a "next" object:`car`

returns the item at the starting index;`cdr`

returns the list with the starting index increased by 1, but if that increased index is the length, it returns the "next" object.

Other types should be specified in the complete specification.

## Syntax

There are l-expressions and r-expressions. L-expressions can be assigned to to create an updated namespace, and r-expressions represent objects.

There are the following l-expressions:

- An identifier like in normal PLs denotes a variable value;
- Identifiers starting with
`c`

, ending with`r`

, and otherwise consisting of`a`

and`d`

(such as`caddr`

) are equivalent to`x: `([-1 for each a and 0 for each d] x)`

; - A library identifier (see below) is imported from its library;
- A number denotes that number;
- One or more expressions enclosed in
`()`

define a list with 0 as the starting index and 0 as the "next" object; - One or more expressions followed by
`.`

and enclosed in`()`

define a list with 0 as the starting index and the specified "next" object; - An l-expression followed by
`:`

and then an r-expression define a lambda that, when called, will assign the argument to the l-expression and return the r-expression with it; - An l-expression followed by
`=`

and then two r-expressions returns the second r-expression with the first one assigned to the l-expression; - An r-expression preceded by
`'`

denotes an object for which`eval`

returns the specified object; - An r-expression preceded by
```

denotes the result of using`eval`

on the specified object.

There are the following r-expressions:

- An identifier like in normal PLs denotes a variable that's defined to the assigned value when assigned;
- One or more expressions enclosed in
`()`

assigns the`car cdar cddar ...`

of the assigned value to its parts; - One or more expressions followed by
`.`

does the same, but assigns`c[as many d's as there are parts before the .]r`

to the part after the`.`

.

Built-in identifiers are:

`quote`

, when applied to an object, returns an object that`eval`

's to it;`eval`

, when applied to an object, returns the output of that object's`eval`

;`cons`

, when applied to an object, returns the object that`car`

's to that object's`car().eval()`

and`cdr`

's to that object's`cdr().eval()`

;`bool`

, when applied to an object, returns -1 for ones that have true`to_bool()`

and 0 for others.

Library identifiers are constructed by joining identifiers using `::`

. The library is a tree, and the identifier is a path in it. Using `localfs::"..."`

where `...`

is a file path allows one to import from the local file system.

## External links

- Reference implementation (It's unknown if it will actually be used; it may be re-written in Lua. Also, some applications may require using
`mpz_class`

instead of`long long`

. Also, some implementation may use caching for better performance.)