Meadow
| Paradigm(s) | Functional |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2021 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
Meadow is a computational model invented by User:Hakerh400 in 2021.
Overview
Interpreter creates a database of all expressions that are ever constructued (implicitly or explicitly) during the program execution. Comparing two previously constructed expressions always has constant time, independently of the length or depth of the expressions.
Memory cannot be deallocated until the program halts. This can speed up the program by deduplicating computation, but it may result in memory overflow.
Paradigm
This computational model inherently has functional paradigm. Recursive implementation perfectly fits with caching previous results, because recursive implementations of most algorithms depend on the results of previous recursive calls. For example, if you want to compute n-th fibonacci number, you may do it like this:
fib 0 = 0 fib 1 = 1 fib (n + 2) = (fib (n + 1)) + (fib n)
You may think that this has exponential time complexity. However, in Meadow this has linear time complexity, because the result of each call is cached and it is not computed again. Moreover, even partially-applied functions are cached.
Despite being pure functional, Meadow is not lazy. It eagerly evaluates all arguments before entering a function call. However, this is not observable from the program itself.
Details
There are only four different things in the program:
- Symbol - A unique value that is associated to a constant global identifier. Two symbols are equal iff the have the same name.
- Struct - A structural pair of two reduced expressions. A reduced expression is either a symbol, or a struct. Two structs are equal iff their corresponding first and second elements are equal.
- Call - A pair of two reduced expressions. Each call is then reduced either to a symbol, or to a struct, and the mapping between each call and its reduced expression is preserved. Two calls are equal iff their reduced expressions are equal (not the two expressions that are in their pairs, but the two resulting expressions).
- Alias - Similar to a call, but instead of having two elements, it has a name, which is unique for each alias. Two aliases are equal iff their reduced expressions are equal.
Since Meadow is a framework for programming languages, an interpreter for a programming language simply defined a handler for expressions and then feeds the Meadow with expressions. Meadow then recursively calls the handler and builds up the database until all expressions are reduced.
Comparing to Haskell, data constructor names are symbols, nullary functions are aliases, unary functions are symbols, partially-applied binary (and other multi-argument) functions are structs and fully-applied (except nullary) functions are calls.