typed_sf/
lib.rs

1#![cfg_attr(feature = "no_std", no_std)]
2#![cfg_attr(feature = "require_docs", deny(missing_docs))]
3#![deny(warnings, clippy::all, clippy::pedantic)]
4#![doc(test(attr(deny(warnings))))]
5
6/*!
7    Type-level implementation of [SF](https://esolangs.org/wiki/Smallfuck).
8    Proving that type-system turing-complete. Highly inspired
9    by [this article](https://sdleffler.github.io/RustTypeSystemTuringComplete/).
10
11    # Features
12    `typed-sf` supports "no_std" feature with limitations. Runtime
13    representation of [`List`]'s and [`State`][StateTrait]'s unavailable
14    (they are using [`Vec`] to represent themselves).
15
16    Full list of unsupported features:
17    * [`List::val()`] (That includes [`Nil`] and [`Cons`]).
18    * [`RuntimeState`].
19    * [`StateTrait::val()`] (That includes [`State`] and [`DefaultState`]).
20
21    Also where is "require_docs" feature which forbids undocumented `pub` items.
22    If You want to contrubute, feel free to turn off this default feature.
23
24    # How it works
25    First, there's some traits that i'm calling type-level enums ([`Bit`], [`List`]).
26    Have a look at it:
27    ```
28    # #[derive(PartialEq, Debug)]
29    enum Bit {
30        True,
31        False
32    }
33
34    impl Bit {
35        fn neg(self) -> Bit {
36            match self {
37                Bit::True => Bit::False,
38                Bit::False => Bit::True
39            }
40        }
41    }
42
43    assert_eq!(Bit::True, Bit::False.neg());
44    assert_eq!(Bit::False, Bit::True.neg());
45    ```
46    ```
47    trait Bit {
48        type Neg: Bit;
49        fn real() -> bool;
50    }
51    struct True;
52    struct False;
53
54    impl Bit for True {
55        type Neg = False;
56        fn real() -> bool { true }
57    }
58
59    impl Bit for False {
60        type Neg = True;
61        fn real() -> bool { false }
62    }
63
64    assert_eq!(True::real(), <False as Bit>::Neg::real());
65    assert_eq!(False::real(), <True as Bit>::Neg::real());
66    ```
67    Of course, what's more bolierplate, but also instead of
68    matching in runtime, compiler solves type-equasions in
69    compile-time for us.
70
71    To type-encode functions i'm using something like this:
72    ```
73    # use std::ops::{Add, Sub};
74    #
75    // A and B are arguments to 'function'.
76    trait Call<A, B> { type Return; }
77
78    struct Sum;
79    struct Diff;
80
81    impl<A, B> Call<A, B> for Sum
82    where
83        A: Add<B>
84    {
85        type Return = <A as Add<B>>::Output;
86    }
87
88    impl<A, B> Call<A, B> for Diff
89    where
90        A: Sub<B>
91    {
92        type Return = <A as Sub<B>>::Output;
93    }
94
95    # #[allow(dead_code)]
96    type Apply<A, Fn, B> = <Fn as Call<A, B>>::Return;
97    ```
98    What we can use later as:
99    ```
100    # use std::ops::{Add, Sub};
101    # trait Call<A, B> { type Return; }
102    # struct Sum;
103    # struct Diff;
104    # impl<A, B> Call<A, B> for Sum where A: Add<B> { type Return = <A as Add<B>>::Output; }
105    # impl<A, B> Call<A, B> for Diff where A: Sub<B> { type Return = <A as Sub<B>>::Output; }
106    # type Apply<A, Fn, B> = <Fn as Call<A, B>>::Return;
107    #
108    struct X;
109    struct Y;
110    # #[derive(Debug, PartialEq)]
111    struct XaddY;
112    # #[derive(Debug, PartialEq)]
113    struct XsubY;
114
115    impl Add<Y> for X {
116        type Output = XaddY;
117        # #[allow(unused)]
118        # fn add(self, y: Y) -> XaddY {unimplemented!()}
119    }
120    impl Sub<Y> for X {
121        type Output = XsubY;
122        # #[allow(unused)]
123        # fn sub(self, y: Y) -> XsubY {unimplemented!()}
124    }
125
126    /* Add `::val() -> Self` function to all types... */
127    # impl XaddY { fn val() -> Self {XaddY} }
128    # impl XsubY { fn val() -> Self {XsubY} }
129
130    assert_eq!(
131        <Apply<X, Sum, Y>>::val(),
132        XaddY::val()
133    );
134
135    assert_eq!(
136        <Apply<X, Diff, Y>>::val(),
137        XsubY::val()
138    );
139    ```
140    That's basically how [`Runner`]`<`[`Left`][List]`, `[`Value`][Bit]`, `[`Right`][List]`>` works.
141    But commands such as [`Left`] take a generic argument, so it runs next command on
142    modified state which does the same and so on...
143
144    # Examples
145    Basic usage
146    ```
147    # use typed_sf::*;
148    type SetTrue<Next = EOF> = Cycle<Flip, Flip<Next>>;
149    // [*<<[*]*>>>] // Move any-sized chunk of True's 2 cells left
150    # #[allow(non_camel_case_types)]
151    type prog = Cycle<Flip<Left<Left<SetTrue<Right<Right<Right>>>>>>>;
152    # #[allow(non_camel_case_types)]
153    type result = Run<
154        prog,
155        State<Nil, True, Cons<True, Nil>, False>
156    >;
157
158    assert_eq!(
159        <result as StateTrait>::val(),
160        (vec![true, true, false, false], false, Vec::new())
161    ); //                 ^^^^^^^^^^^^
162       // Some waste, honestly don't why it is here...
163    ```
164*/
165
166#[cfg(test)]
167#[cfg(not(feature = "no_std"))]
168mod tests;
169#[cfg(test)]
170#[cfg(feature = "no_std")]
171#[path = "tests_no_std.rs"]
172mod tests;
173
174pub(crate) mod bit;
175pub(crate) mod core;
176pub(crate) mod list;
177pub(crate) mod cmds {
178    pub(crate) mod cycle;
179    pub use self::cycle::Cycle;
180
181    pub(crate) mod eof;
182    pub use self::eof::EOF;
183
184    pub(crate) mod flip;
185    pub use self::flip::Flip;
186
187    pub(crate) mod left;
188    pub use left::Left;
189
190    pub(crate) mod right;
191    pub use right::Right;
192
193    pub(crate) mod utils;
194    pub use utils::*;
195}
196
197pub use crate::bit::*;
198pub use crate::cmds::utils::*;
199pub use crate::cmds::*;
200pub use crate::core::*;
201pub use crate::list::*;
202
203#[cfg(not(feature = "no_std"))]
204pub use crate::core::RuntimeState;
typed_sf/lib.rs

typed_sf/
lib.rs
