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<Variable>('f');
Using defaults.hpp 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
- Variable : LambdaBase
- Function : LambdaBase
- Application : LambdaBase
Provides virtual destructor and virtual function that return the type of the object from LambdaType class enum.
virtual inline LambdaType getType() const noexcept = 0;Stores a char name and uint16_t count. Variable are the same only if both of these values are the same.
Variable::Variable(char name, uint16_t count = 0);Also provides == operator overload.
inline bool operator==(const Variable& other) const noexcept;Stores a Variable as a parameter (bound) and std::unique_ptr<LambdaBase> as a body.
Constructor throws LambdaLibError if body is nullptr
Function::Function(Variable bound, std::unique_ptr<LambdaBase> body);Stores std::unique_ptr<LambdaBase> for both left and right arguments.
Application::Application(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 Variable& 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 has a custom exception LambdaLibException that holds a string with error message. Inherites from std::exception.
LambdaLibException::LambdaLibException(std::string msg);Contains std::exception::what() overload.
inline const char* LambdaLibException::what() const noexcept override;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 no be included.
If LAMBDA_NODEFAULTS not defined, includes additionals.hpp.