blob: 7d0378d525788c8c07622c7a78aa2e6fdb89763b (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
# mili
> Minimal linear lambda calculus with linear types, de Bruijn indices
> and unbounded iteration/minimization
Linear lambda calculus is a restricted version of the lambda calculus in
which every variable occurs exactly once. This typically implies ptime
normalization and therefore Turing incompleteness.
We extend the linear lambda calculus with unbounded
iteration/minimization such that it barely becomes Turing complete,
while still benefitting from the advantages of syntactic linearity.
## core
Mili's core syntactic representation consists of only five constructs:
``` haskell
data Term = Abs Int Term -- | Abstraction at level
| App Term Term -- | Application
| Lvl Int -- | de Bruijn level
| Num Nat -- | Peano numeral
| Rec (Term, Term) Term Term Term -- | Unbounded iteration
```
Lets and Pairs are only used in the higher-level syntax. This allows us
to use a minimal abstract reduction machine.
## roadmap
- [x] basic syntax
- [x] linearity check
- [x] basic reduction
- [ ] type syntax
- [ ] type checking
- [ ] reduction shortcut
- [ ] preprocessor
- [ ] `:test`
- [ ] `:import`
- [ ] more examples
- [ ] compile to LLVM stack machine
## references
- Alves, Sandra, et al. "Linear recursion." arXiv preprint
arXiv:1001.3368 (2010).
- Lincoln, Patrick, and John C. Mitchell. "Operational aspects of
linear lambda calculus." LICS. Vol. 92. 1992.
- Mairson, Harry G. "Linear lambda calculus and PTIME-completeness."
Journal of Functional Programming 14.6 (2004): 623-633.
|
