MCIPFE - Cálculo Lambda

Nathan Branco Caracho — Tue, 17 May 2022 03:05:52 +0000

Saga MCIPFE

O Manual Completamente Incompleto de Programação Funcional com Elixir é uma série de postagens bem pequenas para explicar um pouco de programação funcional.

Cálculo lambda

"No início eram apenas funções"

O cálculo lambda é a abstração de um sistema formal da matemática lógica baseado na substituição e mapeamento de valores, sendo a base do conceito de funções puras que temos hoje.

Usando símbolo λ (lambda), seguido do nome do parâmetro e por fim a expressão.

Uma soma:

\lambda x.\;x + 1 \newline (\lambda x.\;x + 1)2 \newline 2+1 =3

add_one = fn(x) -> x+1 end
add_one(2)
#3

No caso acima temos uma função simples que recebe um valor como parâmetro (x) e retorna a soma do parâmetro mais (+) 1, ou seja, substitui (x) por um valor e mapeia para expressão de (+1).

O poder de uma função

Com o conceito simples de mapeamento e substituição é possível construir qualquer coisa inclusive a lógica booleana.

Lógica booleana de forma extremamente resumida é ideia que no universo só existem dois estados Verdadeiro ou Falso, contendo operadores como E, OU e NÃO.

Vamos criar a lógica de Verdadeiro , Falso e o operador Negação.
O conceito de Negação é basicamente a inversão do valor booleano, dessa forma NÃO Falso é igual à Verdadeiro.

\lambda x.\lambda y. \;x \newline false = \lambda x.\lambda y. \;y \newline (\lambda b. \;b \;false \;true) true \newline (true\;false\;true) = false \newline (\lambda b.\; b \;false\; true) false \newline (false\;false\;true) = true

lambda_true = fn(x, _) -> x end 
lambda_false = fn(_, y) -> y end 

lambda_not = fn(bool) -> 
   bool.(lambda_false,lambda_true) end

print = fn(bool) -> 
    IO.puts(bool.("true","false")) end

print.(lambda_not.(lambda_true)) #false
print.(lambda_not.(lambda_false)) #true

Já no exemplo acima criamos duas funções true e false que recebem dois parâmetros x e y , a função true retorna somente o parâmetro x e a função false retorna somente o parâmetro y .
Para a negação precisamos criar uma outra função que mapeie uma função booleana, true ou false, em outra função booleana invertida.

Conclusão

Mas qual a função do cálculo lambda no dia à dia? O cálculo lambda é a base do que conhecemos hoje como uma função, entender esse conceito, mesmo que de forma mais superficial, é a porta de entrada para entender outros conceitos de programação funcional.

Bibliográfia

ÁLGEBRA BOOLEANA
Lambda calculus wikipedia
Lambda Calculus - Computerphile Assistam é incrível
Learn You a Haskell for Great Good!

Lambda Saga - Currying

Nathan Branco Caracho — Mon, 23 Nov 2020 19:43:03 +0000

Introduction

If you need share a specific behaviour with functional programming, Currying is the answer. Created by Haskell Curry currying basically is a technique to transform a multiple arguments or n-tuple argument function in a chain of single arguments functions.
f:( x ∗ y ) → z to ( f ):x → ( y → z )

Function signature

Let understanding what is → , ( x ∗ y ), Domain and Range. The tuple or ( x ∗ y ) is a product of two types or a composing between two types, arrow function or → is used to indicate a map of a set into another set, in other words indicate the argument and return, Domain is the argument of a function and Range is a result of a function.

Look below the example:

f: x → y

The function above has x as Domain and y as Range and that is read as from x to y , so the function f has x as argument and y as result. Now look another example with a tuple as Domain:

f: ( x ∗ y ) → z

Symbol/Name	Means
→	returns
Domain	argument type
Range	result type
( x ∗ y )	Tuple

Look the same examples with F#:

multiply: int → int

let multiply a b = a * b
multiply 5 3

multiply: ( int ∗ int ) → int

let multiply (a,b) = a * b
multiply (5,3)

Explaining Currying

The ideia is share the sum behavior, so we will create two functions. First the sum function, that function will receive two int type, first and second, as arguments and return a int type value, first + second. Last we will create addOne function, that function will receive just one int argument calledsecond and add 1 to this argument. That way we will share the sum behavior to addOne function.

Regular sum function

sum: ( int ∗ int ) → int

let sum (first , second) = first + second

let addOne second = sum (1, second)

addOne 2    
|> printf "regular function result: %d"

That is a regular function with a tuple as argument and it only can applied with both values.

Curried sum function

sum: int → int → int or sum: int → (int → int)

let sum first = //main function
    let subFunction second = first + second
    subFunction

let addOne = sum 1 // int -> int

addOne 2
|> printf "curried sum result: %d"

What we did

We created two functions, the main function, int → (int → int) , has one int type argument called first and return sub-function, that function, int → int , has one int type argument called second and in your body has the arguments sum.

How this works

The main function receive a value as parameter and "hold it" in your inner scope, this main function return a single parameter sub-function and that sub-function sum main function parameter with your own parameter. That is only possible because the sub-function is inside main function inner scope, that way it can access all main function variables, that is called closure.

Basically when you create a function all your environment is stored too, it works look like a lexical/static scope if scope is a part of code lexical/static scope is a free or bounded variable scope access range. See an example below:

let lexicalExample =
    let a = 2 // <- lexical scope start 
    let multiply b = a * b
    let a = 3 // <- lexical scope end
    multiply 5
lexicalExample

The example above when variable a is created a lexical/static scope is created too and the function multiply is created inside that lexical/static scope, that way the multiply function can use the a value. When a variable is recreated another lexical/static scope is create but this not change the a value used by multiply function because this function was created inside last lexical/static scope.

Now when we talk about lexical closure the concept is the same, but with one difference the scope is created when the function is created, so the all function arguments is accessible for anything inside function scope.

Currying on FSharp

Use currying with FSharp is easy because all multi arguments functions is curried by default, so not is necessary create it manually. Look it below:

let sum first second = first + second

let addOne = sum 1 // int -> int

addOne 2
|> printf "implicit curried sum result: %d"

The result is the same than first function and we can simplify this further. Look it:

let addOne = (+) 1 // int -> int

addOne 2
|> printf "simplify curried sum result: %d"

The sum operator is a infix notation and a multi argument too so is by default curried.

(+): int → int → int

The use of currying

With currying we are able to partial apply a function, in others words we fix the first of N arguments of a function and reuse the resulted function. That technique possibility us to share a behavior without create a new function and with lightweight syntax. A good examples of curried function is Seq.reduce and |>, look it below:

[1;2;3;4]
|> Seq.reduce (+)
|> printf "sum of all list itens: %d"

Explaining the expression

First we need understanding what is the operator |> or forward pipe operator. Basically the forward pipe operator is a infix notation where the operator apply left value to right function.

f: a → (a → b) → b

let (|>) a b = b a

The Seq.reduce function have two arguments, first (int → int → int) and last a seq\<int\> . If you are a good observer can see the signature int → int → int is the same signature than (+) operator, so we partial apply (+) operator to Seq.reduce and after apply [1;2;3;4] to Seq.reduce (+).

The same expression can be write with a different way look it below:

let sumAll = Seq.reduce (+) // seq<int> -> int

sumAll [1;2;3;4]
|> printf "sum of all of integer list : %d"

This is the same of last expression but creating a new function sumAll: seq<int> → int partially applying (+) to Seq.reduce. That way we can share the behavior of sum all itens of a list.

Conclusion

The currying is a great technique to share behavior, basically transform a n-tuple argument function to a chain of functions with one argument using lexical closure. Use currying in Fsharp is easy because all multi arguments is curried by default.

References

Ending

If you wanna read this post with a cool way visit my repository on github tower-of-windsock and if you see any error, typo or have any question just write here I'll happy to answer you.

DEV Community: Nathan Branco Caracho