Header only library that provides functions to create, rename, and beta reduce lambda calculus expressions.
Made for c++20 but may work on earlier standards
Front matter:
Copy the insides of "include" directory into your include directory, depending on how you structure your project.
To include library in standard way:
#include "lambda_lib/lambda_lib.hpp"
Basic way to create expressions:
std::make_unique<LambdaBase> node = std::make_unique<LambdaVariable>('f');
Using shortcuts it's easier.
std::make_unique<LambdaBase> node = VARIABLE('f');
Use rename to make sure all operations will be completed correctly.
Use reduce to fully reduce it.
Use print the result.
std::make_unique<LambdaBase> node =
APPLICATION(
FUNCTION(
'x',
VARIABLE('x')
),
VARIABLE('y')
);
rename(node);
reduce(node);
print(node);Every class and function provided will be located in lambda namespace.
Some headerfiles have namespaces that start with _ (_print namespace).
Those are used inside the library itself and sometimes contain unsafe functions, only use function that are directly in lambda namespace.
Library provides these classes:
- LambdaBase - virtual
- LambdaVariable : LambdaBase
- LambdaFunction : LambdaBase
- LambdaApplication : LambdaBase
Provides virtual destructor and virtual function that return the type of the object from LambdaType enum class.
virtual inline LambdaType getType() const noexcept = 0;Stores a char name and uint16_t count. LambdaVariable are the same only if both of these values are the same.
LambdaVariable::LambdaVariable(char name, uint16_t count = 0);Also provides == operator overload.
inline bool operator==(const LambdaVariable& other) const noexcept;Stores a LambdaVariable as a parameter (bound) and std::unique_ptr<LambdaBase> as a body.
Constructor throws std::runtime_error if body is nullptr
LambdaFunction::LambdaFunction(LambdaVariable bound, std::unique_ptr<LambdaBase> body);Stores std::unique_ptr<LambdaBase> for both left and right arguments.
Constructor throws std::runtime_error if any argument is nullptr.
LambdaApplication::LambdaApplication(std::unique_ptr<LambdaBase> left,
std::unique_ptr<LambdaBase> right);Library provides these functions:
inline size_t getSize(std::unique_ptr<LambdaBase>& node) noexcept;Walks the tree and returns the abount of bytes the tree is taking up.
Returns 0 if failed. (if node is nullptr)
inline std::unique_ptr<LambdaBase> copy(std::unique_ptr<LambdaBase>& node);Walks the tree and returns copy of the tree.
Return nullptr if failed. (if node is nullptr)
May throw exception if allocation fails. (stdlib fail)
inline void print(std::unique_ptr<LambdaBase>& node) noexcept;Walks the tree and prints it. (lambda symbol is &)
Does nothing if failed. (if node is nullptr)
inline void rename(std::unique_ptr<LambdaBase>& node) noexcept;Walks the tree and does alpha conversion on all fuctions to make names unique.
Does nothing if failed. (if node is nullptr)
inline void apply(std::unique_ptr<LambdaBase>& node, const LambdaVariable& target,
std::unique_ptr<LambdaBase> value);Walks the tree and replaces all instances of target by value. Via the rules of beta reduction.
Does nothing if failed. (if node or value is nullptr)
May throw exception if allocation fails. (stdlib fail)
inline bool reduceOnce(std::unique_ptr<LambdaBase>& node);Does one beta reduction with "standard" algoritm.
Returns true if beta reduction was done.
Returns false if it's fully reduced or if node is nullptr.
May throw exception if allocation fails. (stdlib fail)
inline void reduce(std::unique_ptr<LambdaBase>& node)Calls reduceOnce until fully reduced.
Library throws std::runtime_error if the state of the program is ill formed.
You can define special names to change how library works:
Turns off variable padding for lambda classes, makes them take up less space.
Makes access to variables slower.
default.hpp will be included.
The license for this project is in LICENSE file.
Creator:
GitHub: UAPROGRAMER
Email: stasyatskiu2008@gmail.com