# Simplee.Goa 1.0.11

Lambda calculus implementation using FSharp. The library exposes the classic combinators, boolean algebra, numeral agebra using Church numerals, pairs algebra.
Combinators: S, K, I, M, KI, C, B, Th, B1, V
Boolean: GTrue, GFalse, GAnd, GOr, GBeq
Numerals: G0, G1, G2, GSucc, GPred, GAdd, GSum, GMul, GPow, LEq, Eq, Gr
Pairs: GPair, GFst, GSnd, GPhi

There is a newer version of this package available.
See the version list below for details.
`Install-Package Simplee.Goa -Version 1.0.11`
`dotnet add package Simplee.Goa --version 1.0.11`
`<PackageReference Include="Simplee.Goa" Version="1.0.11" />`
For projects that support PackageReference, copy this XML node into the project file to reference the package.
`paket add Simplee.Goa --version 1.0.11`

## simplee |> goa

Project which implements lambda calculus parser, and interpreter.

#### goa |> ast

Contains the definitions of the lambda calculus grammar. Here is an example of the lambda terms:

``````type GIdentifier = string

type GExpression =
| GVar      of GIdentifier
| GApp      of GExpression * GExpression
| GLambda   of GIdentifier * GExpression
``````

#### goa |> ofstr

Parses strings and converts them to lambda expressions. The implementation is using the FParse library.
Here are several examples of valid strings which are parsed into lambda expressions.
In the following example, we get a lambda expression from a given string.

``````"""\x -> (x y)""" |> gexpr
"""\a b -> b""" |> gexpr
``````

The results of parsing these strings are equivalent to the following lambda expressions built using the provided infix operators:

``````"x" .>> ("x" .<<. "y")
"a" .>> ("b" .>> ("b" |> gvar))
``````

#### goa |> combinators

The library provides the standard lambda combinators: S, K, I, M, KI, C, B, Th, B1, V, Y

``````let sum = "f" .>> ("n" .>> (GIs0 <<. "n" << G0 << ("n" .<< GSucc << ("f" .<< (GPred <<. "n")))))
let g6 = Y << sum << G3
``````

#### goa |> eval

The library implements normalization function for lambda expression using beta reduction.
There are several convenience variations for such evaluation function where you can pass
a logging function, the depth of the evaluation, and a lookup function to replace variables.

``````// Function with complete list of arguments: logger, depth, lookup
GAnd << GTrue << GTrue |> evalLR logr 100 (fun _ -> None)

// Slim function where the logger is skipped and the depth is set by default to 1000.
// In this example the lookup will replace the 'myID' variable with the ID combinator.
GAnd << GTrue << GTrue |> evald0 (fun s -> if s = "myID" then I |> Some else None)
``````

#### goa |> bool

The library defines Boolean algebra (GTrue, GFalse, GNot, GOr, GAnd, GBeq)

``````let gfalse = GNot << GTrue |> evald0
let gfalse1 = GAnd << GTrue << GFalse |> evald0
``````

#### goa |> numerals

The library defines Numerals algebra:

G0, G1, G2, ... - Church numerals

GSucc, GPred - successor and presecessor

GIs0, GEq, GLEq, GGr - is zero, equal, less or equal, and greater

``````let g3 = GAdd << G1 << G2 |> evald0
let g8 = GPow << G2 << G3 |> evald0
let g7 = GPred << g8
leg gfalse = GIs0 << G1 |> evald0
let gtrue = GLEq << G1 << G3 |> evald0
let gfalse = GGr << G1 << G2 |> evald0
``````

#### goa |> pairs

The library defines Pairs algebra (GPair, GFst, GSnd, GPhi).
The phi combinator takes a pair (_, Gn) and returns (Gn, Gn+1).

``````let pair = GPair << G1 << G2
let g1 = GFst << pair
let g2 = GSnd << pair
let g2a = GFst << GPhi << pair
let g3 = GSnd << GPhi << pair

``````

## simplee |> goa

Project which implements lambda calculus parser, and interpreter.

#### goa |> ast

Contains the definitions of the lambda calculus grammar. Here is an example of the lambda terms:

``````type GIdentifier = string

type GExpression =
| GVar      of GIdentifier
| GApp      of GExpression * GExpression
| GLambda   of GIdentifier * GExpression
``````

#### goa |> ofstr

Parses strings and converts them to lambda expressions. The implementation is using the FParse library.
Here are several examples of valid strings which are parsed into lambda expressions.
In the following example, we get a lambda expression from a given string.

``````"""\x -> (x y)""" |> gexpr
"""\a b -> b""" |> gexpr
``````

The results of parsing these strings are equivalent to the following lambda expressions built using the provided infix operators:

``````"x" .>> ("x" .<<. "y")
"a" .>> ("b" .>> ("b" |> gvar))
``````

#### goa |> combinators

The library provides the standard lambda combinators: S, K, I, M, KI, C, B, Th, B1, V, Y

``````let sum = "f" .>> ("n" .>> (GIs0 <<. "n" << G0 << ("n" .<< GSucc << ("f" .<< (GPred <<. "n")))))
let g6 = Y << sum << G3
``````

#### goa |> eval

The library implements normalization function for lambda expression using beta reduction.
There are several convenience variations for such evaluation function where you can pass
a logging function, the depth of the evaluation, and a lookup function to replace variables.

``````// Function with complete list of arguments: logger, depth, lookup
GAnd << GTrue << GTrue |> evalLR logr 100 (fun _ -> None)

// Slim function where the logger is skipped and the depth is set by default to 1000.
// In this example the lookup will replace the 'myID' variable with the ID combinator.
GAnd << GTrue << GTrue |> evald0 (fun s -> if s = "myID" then I |> Some else None)
``````

#### goa |> bool

The library defines Boolean algebra (GTrue, GFalse, GNot, GOr, GAnd, GBeq)

``````let gfalse = GNot << GTrue |> evald0
let gfalse1 = GAnd << GTrue << GFalse |> evald0
``````

#### goa |> numerals

The library defines Numerals algebra:

G0, G1, G2, ... - Church numerals

GSucc, GPred - successor and presecessor

GIs0, GEq, GLEq, GGr - is zero, equal, less or equal, and greater

``````let g3 = GAdd << G1 << G2 |> evald0
let g8 = GPow << G2 << G3 |> evald0
let g7 = GPred << g8
leg gfalse = GIs0 << G1 |> evald0
let gtrue = GLEq << G1 << G3 |> evald0
let gfalse = GGr << G1 << G2 |> evald0
``````

#### goa |> pairs

The library defines Pairs algebra (GPair, GFst, GSnd, GPhi).
The phi combinator takes a pair (_, Gn) and returns (Gn, Gn+1).

``````let pair = GPair << G1 << G2
let g1 = GFst << pair
let g2 = GSnd << pair
let g2a = GFst << GPhi << pair
let g3 = GSnd << GPhi << pair

``````

## Release Notes

Added Y-combinator and the GSum << Gn which uses the Y-combinator.

## GitHub Usage

This package is not used by any popular GitHub repositories.