Unlambda interpreter implemented in TypeScript's type system.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

72 lines
2.0 KiB

12 months ago
# type-unlambda
2 years ago
[![MIT License][]](LICENSE)
2 years ago
[Unlambda][] interpreter implemented in TypeScript's type system.
2 years ago
## Getting Started
Installation:
```sh
npm install --save-dev typescript
2 years ago
npm install --save-dev @esolangs/type-unlambda
```
Example usage:
2 years ago
```typescript
import Unlambda from '@esolangs/type-unlambda';
type Code = '``@c`d``s`|k`@c';
type Input = 'Hello!';
type Output = Unlambda<Code, Input>; // Output == '!olleH'
2 years ago
```
Screenshots (from Visual Studio Code):
2 years ago
![Example](assets/example.png)
2 years ago
## Notes
You're likely to get the following error when trying to run a program with
type-unlambda:
2 years ago
> Type instantiation is excessively deep and possibly infinite.ts(2589).
To write loops in TypeScript's type system, we have to use recursions,
like we do in other purely functional programming languages. Meanwhile, we use
[CPS][] to implement continuations, which also introduces heavy recursion.
12 months ago
However, TypeScript's type system is not meant for general purpose programming.
There is no [TCE][Tail Call], and recursion has its limits.
2 years ago
In [src/compiler/checker.ts][TSC checker], there is a hard-coded limit for
type instantiation:
2 years ago
```typescript
if (instantiationDepth === 50 || instantiationCount >= 5000000) {
// ...
return errorType;
}
```
You may expect that there is an option somewhere that this limit can be
configured, like `-ftemplate-depth=n` in gcc/clang. Unfortunately, there isn't,
[and it's likely to stay that way][PR 29602].
2 years ago
To workaround this limitation, we modify the code of `tsserver` or `tsc`
in `node_modules`, until the error no longer applies. Changing
`instantiationDepth` to `1000` is sufficient to run the example above.
<!-- Reference Links -->
[MIT License]: https://img.shields.io/badge/license-MIT-blue.svg
[Unlambda]: http://www.madore.org/~david/programs/unlambda/
3 months ago
[CPS]: https://en.wikipedia.org/wiki/Continuation-passing_style
[Tail Call]: https://en.wikipedia.org/wiki/Tail_call
[TSC checker]:
https://github.com/microsoft/TypeScript/blob/v4.1.2/src/compiler/checker.ts
[PR 29602]: https://github.com/microsoft/TypeScript/pull/29602