Skip to content

Commit 33033f5

Browse files
UAPROGRAMERUAPROGRAMER
committed
added readme and some things cleaned up
1 parent ca0aa97 commit 33033f5

11 files changed

Lines changed: 667 additions & 300 deletions

File tree

‎README.md‎

Lines changed: 234 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,234 @@
1+
# Lambda lib
2+
3+
Header only library that provides functions to create, rename, and beta reduce lambda calculus expressions.
4+
5+
Made for c++20 but may work on earlier standards
6+
7+
Front matter:
8+
- [Instalation](#instalation)
9+
- [Usage](#usage)
10+
- [Namespaces](#namespaces)
11+
- [Classes](#classes)
12+
- [Functions](#functions)
13+
- [Errors](#errors)
14+
- [Special Definitions](#special-definitions)
15+
16+
## Instalation
17+
18+
Copy the insides of "include" directory into your include directory, depending on how you structure your project.
19+
20+
## Usage
21+
22+
To include library in standard way:
23+
24+
`#include "lambda_lib/lambda_lib.hpp"`
25+
26+
Basic way to create expressions:
27+
28+
`std::make_unique<LambdaBase> node = std::make_unique<Variable>('f');`
29+
30+
Using `defaults.hpp` it's easier.
31+
32+
`std::make_unique<LambdaBase> node = VARIABLE('f');`
33+
34+
Use `rename` to make sure all operations will be completed correctly.
35+
36+
Use `reduce` to fully reduce it.
37+
38+
Use `print` the result.
39+
40+
```cpp
41+
std::make_unique<LambdaBase> node =
42+
APPLICATION(
43+
FUNCTION(
44+
'x',
45+
VARIABLE('x')
46+
),
47+
VARIABLE('y')
48+
);
49+
50+
rename(node);
51+
52+
reduce(node);
53+
54+
print(node);
55+
```
56+
57+
## Namespaces
58+
59+
Every class and function provided will be located in `lambda` namespace.
60+
61+
Some headerfiles have namespaces that start with `_` (`_print` namespace).
62+
Those are used inside the library itself and sometimes contain unsafe functions, only use function that are directly in `lambda` namespace.
63+
64+
## Classes
65+
66+
Library provides these classes:
67+
- [LambdaBase](#lambdabase) - virtual
68+
- [Variable](#variable) : LambdaBase
69+
- [Function](#function) : LambdaBase
70+
- [Application](#application) : LambdaBase
71+
72+
### LambdaBase
73+
74+
Provides virtual destructor and virtual function that return the type of the object from `LambdaType` class enum.
75+
76+
```cpp
77+
virtual inline LambdaType getType() const noexcept = 0;
78+
```
79+
80+
### Variable
81+
82+
Stores a `char` name and `uint16_t` count. Variable are the same only if both of these values are the same.
83+
84+
```cpp
85+
Variable::Variable(char name, uint16_t count = 0);
86+
```
87+
88+
Also provides `==` operator overload.
89+
90+
```cpp
91+
inline bool operator==(const Variable& other) const noexcept;
92+
```
93+
94+
### Function
95+
96+
Stores a `Variable` as a parameter (bound) and `std::unique_ptr<LambdaBase>` as a body.
97+
98+
Constructor throws `LambdaLibError` if body is `nullptr`
99+
100+
```cpp
101+
Function::Function(Variable bound, std::unique_ptr<LambdaBase> body);
102+
```
103+
104+
### Application
105+
106+
Stores `std::unique_ptr<LambdaBase>` for both left and right arguments.
107+
108+
```cpp
109+
Application::Application(std::unique_ptr<LambdaBase> left,
110+
std::unique_ptr<LambdaBase> right);
111+
```
112+
113+
## Functions
114+
115+
Library provides these functions:
116+
- [getSize](#getsize)
117+
- [copy](#copy)
118+
- [print](#print)
119+
- [rename](#rename)
120+
- [apply](#apply)
121+
- [reduceOnce](#reduceonce)
122+
- [reduce](#reduce)
123+
124+
### getSize
125+
126+
```cpp
127+
inline size_t getSize(std::unique_ptr<LambdaBase>& node) noexcept;
128+
```
129+
130+
Walks the tree and returns the abount of bytes the tree is taking up.
131+
132+
Returns `0` if failed. (if `node` is `nullptr`)
133+
134+
### copy
135+
136+
```cpp
137+
inline std::unique_ptr<LambdaBase> copy(std::unique_ptr<LambdaBase>& node);
138+
```
139+
140+
Walks the tree and returns copy of the tree.
141+
142+
Return `nullptr` if failed. (if `node` is `nullptr`)
143+
144+
May throw exception if allocation fails. (stdlib fail)
145+
146+
### print
147+
148+
```cpp
149+
inline void print(std::unique_ptr<LambdaBase>& node) noexcept;
150+
```
151+
152+
Walks the tree and prints it. (lambda symbol is `&`)
153+
154+
Does nothing if failed. (if `node` is `nullptr`)
155+
156+
### rename
157+
158+
```cpp
159+
inline void rename(std::unique_ptr<LambdaBase>& node) noexcept;
160+
```
161+
162+
Walks the tree and does alpha conversion on all fuctions to make names unique.
163+
164+
Does nothing if failed. (if `node` is `nullptr`)
165+
166+
### apply
167+
168+
```cpp
169+
inline void apply(std::unique_ptr<LambdaBase>& node, const Variable& target,
170+
std::unique_ptr<LambdaBase> value);
171+
```
172+
173+
Walks the tree and replaces all instances of `target` by `value`. Via the rules of beta reduction.
174+
175+
Does nothing if failed. (if `node` or `value` is `nullptr`)
176+
177+
May throw exception if allocation fails. (stdlib fail)
178+
179+
### reduceOnce
180+
181+
```cpp
182+
inline bool reduceOnce(std::unique_ptr<LambdaBase>& node);
183+
```
184+
185+
Does one beta reduction with "standard" algoritm.
186+
187+
Returns `true` if beta reduction was done.
188+
189+
Returns `false` if it's fully reduced or if `node` is `nullptr`.
190+
191+
May throw exception if allocation fails. (stdlib fail)
192+
193+
### reduce
194+
195+
```cpp
196+
inline void reduce(std::unique_ptr<LambdaBase>& node)
197+
```
198+
199+
Calls `reduceOnce` until fully reduced.
200+
201+
## Errors
202+
203+
Library has a custom exception `LambdaLibException` that holds a string with error message. Inherites from `std::exception`.
204+
205+
```cpp
206+
LambdaLibException::LambdaLibException(std::string msg);
207+
```
208+
209+
Contains `std::exception::what()` overload.
210+
211+
```cpp
212+
inline const char* LambdaLibException::what() const noexcept override;
213+
```
214+
215+
## Special Definitions
216+
217+
You can define special names to change how library works:
218+
- [LAMBDA_NOALIGN](#lambda_noalign)
219+
- [LAMBDA_NODEFAULTS](#lambda_nodefaults)
220+
- [LAMBDA_ADDITIONALS](#lambda_additionals)
221+
222+
### LAMBDA_NOALIGN
223+
224+
Turns off variable padding for lambda classes, makes them take up less space.
225+
226+
Makes access to variables slower.
227+
228+
### LAMBDA_NODEFAULTS
229+
230+
`default.hpp` will no be included.
231+
232+
### LAMBDA_ADDITIONALS
233+
234+
If `LAMBDA_NODEFAULTS` not defined, includes `additionals.hpp`.

‎examples/src/solving.cpp‎

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,19 @@
11
#include "lambda_lib/lambda_lib.hpp"
22

33
using namespace lambda;
4-
using namespace lambda::defaults;
54

65
int main(void) {
76
std::unique_ptr<LambdaBase> node = //
8-
std::make_unique<Application>( //
9-
std::make_unique<Application>( //
10-
LEQ(), //
11-
NATURAL_NUMBER(5) //
12-
), //
13-
NATURAL_NUMBER(3) //
7+
APPLICATION( //
8+
FIRST(), //
9+
APPLICATION( //
10+
SECOND(), //
11+
LIST( //
12+
NATURAL_NUMBER(0), //
13+
NATURAL_NUMBER(1), //
14+
NATURAL_NUMBER(2) //
15+
) //
16+
) //
1417
); //
1518

1619
std::cout << "original (" << getSize(node) << " bytes): ";

‎include/lambda_lib/additionals.hpp‎

Lines changed: 3 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -5,10 +5,7 @@
55

66
namespace lambda {
77

8-
namespace additionals {
9-
108
// Compound, less efficient
11-
129
inline std::unique_ptr<LambdaBase> PLUS_C() {
1310
return //
1411
std::make_unique<Function>( //
@@ -18,7 +15,7 @@ inline std::unique_ptr<LambdaBase> PLUS_C() {
1815
std::make_unique<Application>( //
1916
std::make_unique<Application>( //
2017
std::make_unique<Variable>('m'), //
21-
defaults::SUCC() //
18+
SUCC() //
2219
), //
2320
std::make_unique<Variable>('n') //
2421
) //
@@ -27,7 +24,6 @@ inline std::unique_ptr<LambdaBase> PLUS_C() {
2724
}
2825

2926
// Compound, less efficient
30-
3127
inline std::unique_ptr<LambdaBase> MULT_C() {
3228
return //
3329
std::make_unique<Function>( //
@@ -42,14 +38,13 @@ inline std::unique_ptr<LambdaBase> MULT_C() {
4238
std::make_unique<Variable>('n') //
4339
) //
4440
), //
45-
defaults::NATURAL_NUMBER(0) //
41+
NATURAL_NUMBER(0) //
4642
) //
4743
) //
4844
); //
4945
}
5046

5147
// Compound, less efficient
52-
5348
inline std::unique_ptr<LambdaBase> POW_C() {
5449
return //
5550
std::make_unique<Function>( //
@@ -64,12 +59,10 @@ inline std::unique_ptr<LambdaBase> POW_C() {
6459
std::make_unique<Variable>('b') //
6560
) //
6661
), //
67-
defaults::NATURAL_NUMBER(1) //
62+
NATURAL_NUMBER(1) //
6863
) //
6964
) //
7065
); //
7166
}
7267

73-
} // namespace additionals
74-
7568
} // namespace lambda

0 commit comments

Comments
 (0)