wiki:BigIdeas/Procedures

Procedures

Procedures, like enzymes, are the basic building blocks along with data-structures (proteins made from a set of 20 base amino acids). Enzymes are proteins.

The great mantra is All you need is Lambda.

In good old times every named block of code used to be called a procedure. In Common Lisp we still have PROGN and friends. Nowadays we used to call a procedure either a functions which produce only side effects, such as for-each.

Remember, that function is a block of code which maps input to output without having any side-effects - same input - same out. Always.

Here is the identity procedure in its full glory (in-place definition within an application)

((lambda (x) x) (lambda (x) x))

applied to itself.

And even more esoteric list procedure

((lambda x x))

which returns '()

(define add (lambda (x)
                (lambda (y)
                    (+ x y))))

Now when we call this procedure with one argument

(add 3)
#[compound-procedure 13]

We would get back a closure - a procedure of one argument to be called with a second value.

((add 3) 4)
7

We could explicitly bind and then call that returned closure

(let ((add3 (add 3)))
   (add3 4))
7

What we have here is the notion of procedures of exactly one argument - no more, no less - which could be nested to "capture" more than one argument.

We could generalize this notion of currying as a procedure

(define (curry f)
   (lambda (x)
      (lambda (y)
          (f x y))))
;Value: curry

(map ((curry +) 10) '(1 2 3))
; Value 13: (11 12 13)

and "parametrize" it for our needs, like this:

(define (curry2 f x)
    (lambda (y) 
        (f x y)))
;Value: curry2

(map (curry2 + 10) '(1 2 3))
;Value 14: (11 12 13)

While in Haskell currying is implicit

map (+ 10) [1,2,3]
[11,12,13]

Calling (+ 10) produces a closure.

In Haskell this is a default behavior

We could define the add procedure "explicitly" as two nested (curried) procedures.

let add = \x -> \y -> x + y
:t add
add :: Num a => a -> a -> a

While Haskell has syntactic sugar for this

let add x y = x + y
:t add
add :: Num a => a -> a -> a

What looks like procedure of two arguments would be rewritten (transformed into) "nested lambdas" form \x -> \y -> x + y which also called a Curried Procedure, In the same way, function application has its own syntactic sugar,

When we define a procedure "of three arguments" we are using syntactic sugar.

let mult x y z = x*y*z
:t mult
mult :: Num a => a -> a -> a -> a

Which is really

let mult = \x -> \y -> \z -> x*y*z

When we call it, instead of explicitly expressing nested procedure application

((mult 5) 3) 2
30

we just write

mult 5 3 2
30

Now we could see, that without all this syntactic sugar Haskell is a lot like Scheme

let mult = \x -> \y -> \z -> x*y*z

is almost exactly

(define mult (lambda (x) (lambda (y) (lambda (z) (* x y z)))))

while

((mult 5) 3) 2
30

is exactly

(((mult 5) 3) 2)
30

The crucial difference is that because curried function application in Haskell is left-associative, so the parenthesis are optional:

mult 5 3 2
30

While in Scheme parenthesis denote an application of a procedure and are mandatory.

There is another "similarity". In Haskell lists (essential lists, without nonsense) are constructed the same way

> 1:(2:(3:[]))
[1,2,3]

like in Scheme

> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)

and because function applications in Haskell are right-associative (goes from right to left) we don't have to write parenthesis.

> 1:2:3:[]
[1,2,3]

Sections in Haskell

In Scheme we gave only prefix notation for function application, so we write (+ 1 2) instead of 1 + 2.

In Haskell there are inflix operators, like + which takes exactly two arguments, and could be nested in an expression like x + y + z (which should be read as x + (y + z) because of right-associativeness).

There is another syntactic sugar, based on currying which gives us partial application.

When we evaluate (+) it is an abbreviation for \x -> \y -> x+y

so we could say

(+) 1 2

which is nothing, but

((+) 1) 2

or explicit application of a curried function.

Thus we could give "one side" to the binary operator or partially apply it.

(1+)

is abbreviation for

\x -> 1+x

and

(+2)

is abbreviation for

\x -> x+2

So, now we understand how and why this works:

>map (1+) [1,2,3]
[2,3,4]
> map (+2) [1,2,3]
[3,4,5]

because, like in Math parenthesis define precedence, and + or 1+ or +2 are partial applications - with zero or one argument.

Beautiful.

Last modified 2 years ago Last modified on Dec 20, 2017, 1:27:41 PM
Note: See TracWiki for help on using the wiki.