Infilisp

Infilisp

Paradigm(s)	functional
Designed by	User:Orisphera
Appeared in	2024
Type system	dynamic, duck
Computational class	Turing-complete
Reference implementation	Unimplemented
Influenced by	Lisp

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.
• 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.
• 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.)