Calcolo Lambda tramite C# (9) Avvolgimento di numeri di chiesa e aritmetica

Calcolo Lambda tramite C# (9) Avvolgimento di numeri di chiesa e aritmetica

[LINQ tramite serie C#]

[Calcolo Lambda tramite serie C#]

Ultima versione:https://weblogs.asp.net/dixin/lambda-calculus-via-csharp-3-numeral-arithmetic-and-predicate

Nella parte precedente, la funzione Diminuisci era una Func, T>>, Numeral>:

// Decrease = n => f => x => n(g => h => h(g(f)))(_ => x)(_ => _)
public static Numeral<T> Decrease<T>
    (this Numeral<Func<Func<T, T>, T>> numeral) => 
            f => x => numeral(g => h => h(g(f)))(_ => x)(_ => _);

Questo va bene perché nella definizione di Numeral:

public delegate Func<T, T> Numeral<T>(Func<T, T> f);

T può essere qualsiasi cosa. Ma d'altra parte, Diminuisci può essere più utile, se il suo parametro e il valore restituito sono esattamente dello stesso tipo. Questo può essere fatto se nella definizione di Numeral, il parametro type può essere nascosto, in modo che Decrease possa essere qualcosa come un Func.

Wrapper non generico per Numeral e Aumenta

Una possibile soluzione (ispirata a forall in Haskell) è creare una classe wrapper non generica senza parametro di tipo e avere Numeral sul membro di quella classe:

public partial class _Numeral
{
    public virtual Numeral<T> Numeral<T>()
    {
        …
    }
}

Ancora una volta, un carattere di sottolineatura antepone il nome della classe per indicare che si tratta di un imbroglio, perché la classe esiste in C# ma non nel calcolo lambda.

Ma come può essere implementata questa classe? Ricorda:

Increase2 := λn.λf.f ∘ (n f)

Quindi la classe _Numeral può essere implementata dal suo precedente numero della Chiesa:

public partial class _Numeral
{
    public _Numeral(_Numeral predecessor)
    {
        this.Predecessor = predecessor;
    }

    protected virtual _Numeral Predecessor { get; set; }

    public virtual Numeral<T> Numeral<T>
        () => 
            f => f.o(this.Predecessor.Numeral<T>()(f));
}

Quindi un _Numerale aumentato viene costruito utilizzando _Numero corrente come predecessore:

public partial class _Numeral
{
    public _Numeral Increase
        () => new _Numeral(this);
}

Come caso speciale, 0 non si applica affatto a f. Può essere implementato come una sottoclasse di _Numeral in modo che il comportamento possa essere ignorato:

public partial class _Numeral
{
    private _Numeral()
    {
    }

    private class _ZeroNumeral : _Numeral
    {
        protected override _Numeral Predecessor { get { return this; } set { } }

        public override Numeral<T> Numeral<T>
            () => 
                f => x => x;
    }

    public static _Numeral Zero { get; } = new _ZeroNumeral();
}

E questo è tutto. L'inquinamento OOP per i numeri della Chiesa (del calcolo lambda) non andrà oltre. L'avviso 0 non ha un numero della Chiesa precedente, quindi il suo predecessore è se stesso. Una parte successiva implementerà i numeri di chiesa firmati.

Aggiungi

Anche gli altri operatori nella parte precedente devono essere rifattorizzato. Naturalmente, Add sarà:

public static partial class _NumeralExtensions
{
    // Increase = n => n.Increase()
    private static _Numeral Increase
        (_Numeral numeral) => numeral.Increase();

    // Add = a => b => a(Increase)(b)
    public static _Numeral Add
        (this _Numeral a, _Numeral b) => a.Numeral<_Numeral>()(Increase)(b);
}

Diminuisci e sottrai

Infine, Diminuisci e Sottrai può essere fatto bene, perché ora Diminuisci è un Func<_Numeral, _Numeral>:

public static partial class _NumeralExtensions
{
    public static _Numeral Zero { get; } = _Numeral.Zero;

    public static _Numeral One { get; } = _Numeral.Zero.Increase();

    // ...

    // Decrease = n => f => x => n(g => h => h(g(f)))(_ => x)(_ => _)
    public static _Numeral Decrease
        (this _Numeral numeral) =>
            new Numeral<_Numeral>(f => x =>
                numeral.Numeral<Func<Func<_Numeral, _Numeral>, _Numeral>>()(g => h => h(g(f)))(_ => x)(_ => _))
                (Increase)(Zero);

    // Subtract = a => b => b(Decrease)(a)
    public static _Numeral Subtract
        (this _Numeral a, _Numeral b) => b.Numeral<_Numeral>()(Decrease)(a);
}

Moltiplica e Pow

Simile ad Aggiungi e Sottrai, Moltiplica e Potenza possono essere definiti come:

Multiply := λa.λb.a (λx.Add b x) 0
Pow := λm.λe.e (λx.Multiply m x) 1

(Moltiplicare a b) significa semplicemente fare "aggiungere b" a volte sopra 0. (Potenza m e) significa fare "moltiplicare m" e volte a partire da 1.

public static partial class _NumeralExtensions
{
    // Multiply = a => b => a(x => b.Add(x))(Zero)
    public static _Numeral Multiply
            (this _Numeral a, _Numeral b) => a.Numeral<_Numeral>()(b.Add)(Zero);

    // Power = m => e => e(x => m.Multiply(x))(1)
    public static _Numeral Pow
        (this _Numeral mantissa, _Numeral exponent) => exponent.Numeral<_Numeral>()(mantissa.Multiply)(One);  
}

Dividi?

Divide verrà implementato in un'altra parte, dopo aver implementato i predicati. E una versione migliore sarà implementata dopo l'introduzione del combinatore Y.