Lazy expander

Lazy expander

Paradigm(s)	Functional, Declarative
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Unimplemented
File extension(s)	.txt

Lazy expander is a programming language which works by lazy evaluating recursive functions and extracting parts of the output until the whole output is obtained.

Overview

This language is strongly typed. There are no variables, only constants. Looping is possible by doing recursion (which can be unlimited).

There are types, aliases and functions. The order of defining them is not important.

Type

Type is a structure which can contain other types. Order is important (types are not sets, but rather more like arrays). Type can contain itself (directly, or indirectly).

Type definition consists of type name, then a colon follows and then inner types are in parenthesis. Example:

myType: (innerType1, innerType2, innerType3)
someOtherType: (A, singleton, empty)
singleton: (B)
empty: ()
recursive: (recursive, indirect)
indirect: (recursive)

It should be clear from this example how types can be defined. Ad-hoc type definitions are not allowed. For example

A: (B: (C))

is not allowed (syntax error).

Alias

Alias is basically a set of regular types. However, the term set may not be the best description, since an alias containing a single type is equivalent to that type. Alias containing other aliases is actually the union of those aliases.

Syntactically, it is represented similar to regular types, but instead of perentheses, we use braces. Example:

meow: ()
bark: ()
roar: ()
cat: (meow)
dog: (bark)
pet: {cat, dog}
lion: (roar)
animal: {pet, lion}

Here we declared alias pet that encapsulates both cat and dog. Then we defined animal that encapsulates both pet and lion. It is equivalent to animal: {cat, dog, lion}. Alias is used as a generalization. We can use pet or lionwhere animal is expected and we can use cat or dog where pet or animal is expected.

Alias is not allowed to contain itself (directly or indirectly). Also, alias cannot be empty. Singleton aliases are allowed (we will see later that this can be useful).

Function

Function takes zero or more arguments and returns a value. Types must match. The return type is not specified explicitly (interpreter will figure out types).

Example of some functions:

main(): whatSays(cat(meow()))
whatSays(animal a): getWhatSays(a)
getWhatSays(cat c): meow()
getWhatSays(dog d): bark()
getWhatSays(lion l): roar()

Explanation: we have the main function main, which calls whatSays. It passes cat(meow()) as the argument to whatSays. As can be seen, constructing a type and calling a function is syntactically identical. Function is not allowed to have the same name as some type or alias.

The part meow() is a type construction (the type is defined as meow: (), so it does not take any arguments). It is allowed to omit parentheses when constructing a type or calling a function which does not take arguments (so whatSays(cat(meow)) is valid).

It would be wrong if we said "instantiating an object of the given type", because there are no pointers or references. We cannot compare two "objects" or determine whether two "objects" of the same type are equal or not. However, all types are considered to be different (if one type is not an alias for the other, we cannot use one type where the other is expected, and vice versa). There are no runtime errors, only compile-time errors (syntax errors and type errors (when types do not match)).

We can check what type the argument is by calling a polymorphic function (in this example it is getWhatSays). We can also remove whatSays and call getWhatSays directly from the main (no changes to main itself are required).

Here is another example:

A: ()
B: ()
C: {A, B}
main(): func(A)
func(B): A
func(C): B

The question is: what is the return type of main? We can see that main returns the same type that func returns when called with type A as argument. Now, what does func returns when called with A? We do not have definition for func(A), but we have definition for func(C) and C is alias for {A, B}. So, func(C): B will be invoked and it returns B, so the return type of main is B.

Here are more examples:

// ERROR: No matching definition for func(A)
A: ()
B: ()
main(): func(A)
func(B): A

// Valid, but `func(C)` cannot be invoked in any condition
A: ()
B: ()
C: {A, B}
main(): func(A)
func(A): A
func(B): B
func(C): B

/**
 * This is valid.
 * `func(B)` will be invoked, because `B`
 * is more specific than `C`
 */
A: ()
B: ()
C: {A, B}
main(): func(B)
func(B): B
func(C): C

// ERROR: Alias cannot be constructed like a type
A: ()
B: {A}
main(): B()

// Valid, aliases are equivalent
A: ()
B: {A}
C: {A}
main(): func1(A)
func1(B x): func2(x)
func2(C x): x

// ERROR: Ambiguous function definition
A: ()
B: {A}
C: {A}
main(): func(A())
func(B x): x
func(C x): x

// ERROR: Argument is not a function
A: ()
main(A a): a()

It is also possible to construct an infinite type. For example

main(): main()

is a valid program. Or, another example

A: (A)
main(): A(main)

When interpreter starts analyzing the code, it implicitly defines internal types as returns values for each function definition (not only for each function name, but for each polymorphic definition). Then it tries to match the return types with actual user-defined types and aliases. If it encounters two different types that are equal to the implicitly defined internal return type, it is an error. However, if there are no matches with user-define types (like in main(): main()), then the function has a new type that is not equal to any user-defined type (but the program itself is not aware of that, otherwise the type will already be equal to some user-defined type).

This is a valid code:

A: (A)
main(): func(rec)
func(A a): a
rec(): rec()

because rec, when called without arguments, returns a new type (implicitly defined by the interpreter) and the interpreter tries to match it with user-defined types to make the program runnable. We see from func(rec) that the return value of rec is passed as an argument to func, but the only definition of func takes an argument of type A, therefore rec returns a value of type A (it will never halt, but the program will not throw an error).

Destructuring

It is, of course, possible to extract data from a constructed type. It can be done by destructuring:

A: ()
B: ()
C: {A, B}
D: (C)
main(D d): extract(d)
extract(D(C c)): c

If main is called with argument of type D, it will return the value of type C. To be more precise, it returns a value of type A if D contains A and returns a value of type B if D contains B.

It is also possible to perform deeper destructuring:

A: ()
B: (A)
C: (B)
main(C(B(A a))): a

Aliases can be defined to encapsulate complex types, like this:

A: ()
B: ()
C: {A, B}
D: (C)
E: {D(A)}
main(): func(D(A))
func(E e): extract(e)
extract(D(A a)): a

However, it is not allowed to have an aliases as the destructured type:

// ERROR: Alias cannot be destructured
A: ()
B: ()
C: {A, B}
D: (C)
E: {D(A)}
main(): func(D(A))
func(E e): extract(e)
extract(E(A a)): a

I/O

Input and output format is implementation-dependent. Interpreter may require some types to be defined and main to take specific number of arguments of specific types and return a value of specific type.

As an example, if we work with strings of bits as the I/O format, an interpreter may have some predefined types (0, 1, String, etc) and require main to take String and return String.

Inverting all bits in the string can be done like this:

0: ()
1: ()
Bit: {0, 1}
EmptyString: ()
NonEmptyString: (Bit, String)
String: {EmptyString, NonEmptyString}

main(String str):
  invert(str)

invert(EmptyString):
  EmptyString

invert(NonEmptyString(Bit bit, String str)):
  NonEmptyString(invert(bit), invert(str))

invert(0): 1
invert(1): 0

Here is how the computation goes. We start from the input string. Let the input string be 01, then the interpreter constructs the following type:

NonEmptyString(0, NonEmptyString(1, EmptyString))

and invoke our main function. Here is the computation step-by-step:

1. main(NonEmptyString(0, NonEmptyString(1, EmptyString)))
2. invert(NonEmptyString(0, NonEmptyString(1, EmptyString)))
3. NonEmptyString(invert(0), invert(NonEmptyString(1, EmptyString)))
4. NonEmptyString(1, invert(NonEmptyString(1, EmptyString)))
5. NonEmptyString(1, NonEmptyString(invert(1), invert(EmptyString)))
6. NonEmptyString(1, NonEmptyString(0, invert(EmptyString)))
7. NonEmptyString(1, NonEmptyString(0, EmptyString))

The final output is NonEmptyString(1, NonEmptyString(0, EmptyString)), which is binary string 10.

Interpreter can define any other I/O format (but the implementation should be upfront about it). It is also allowed to have infinite recursion. For example, interpreter may pass an infinite string of bits (no EmptyString is present in there), the recursion will never stop, but interpreter may be interested only in the first n bits, and can terminate the program after that (for example, interpreter can read pairs of bits, if the first bit of the pair is 1, output the next bit and keep expanding the recursion; if the first bit of the pair is 0, terminate the program).