Why lambda?

In an functional programming it is not sufficient to define small trivial functions for lower level operations, rather these functions can be used as an argument. The most convenient way to define a function to associate a variable to a particular operation without bounding to a particular identifier is to use lambda.

                                 A lambda expression evaluates to a procedure. The environment in effect when the lambda expression is evaluated is remembered as part of the procedure; it is called the closing environment. When the procedure is later called with some arguments, the closing environment is extended by binding the variables in the formal parameter list to fresh locations, and the locations are filled with the arguments according to rules about to be given. The new environment created by this process is referred to as the invocation environment.

One way to accomplish this is to use an auxiliary procedure to bind the local variables:

(define (f x y)

  (define (f-helper a b)

    (+ (* x (square a))

       (* y b)

       (* a b)))

  (f-helper (+ 1 (* x y)) 

            (- 1 y)))

 By using lambda for the example then the body of f becomes a single call to the procedure.

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

The lambda is also known as an anonymous functions since it doesn't spoil the name space by unnecessary definition of named functions.  

Functional Programming

Functional programming(FP) is one of the programming paradigm, paradigm means which describes various concepts and ideas. Functional programming was the new way to abstract and compose the structure and to avoid mutation. Functions are the basic structures that leads to higher procedural abstractions. Functions in FP are first class citizens that can be
:: defined anywhere inside or outside the functions
:: can be passed as arguments

Popular functional programming languages are
:: Lisp
:: Scala
:: Scheme
:: Racket
:: Clojure
:: Small Talk
:: Ruby

Functions are the powerful ways of abstracting operations and lower order formulas in order to modularize each part of programming construct and segregate to form a higher order construct using basic functions. Functions that  can manipulate functions are known as higher order functions. These powerful way of abstraction will increase the expressive power of our language.

Glueing  functions together

Glue enables simple functions to be glued together to make more complex ones. It can be illustrated with a simple list- processing problem - adding up the elements of a list. We define lists by

listof X ::= nil | cons X (listof X)

which means that a list of Xs (whatever X is) is either nil, representing a list
with no elements, or it is a cons of an X and another list of Xs. A cons represents
a list whose first element is the X and whose second and subsequent elements
are the elements of the other list of Xs.
[]            means     nil
[1]          means     cons 1 nil
[1,2,3]    means     cons 1 (cons 2 (cons 3 nil))

Our ability to decompose a problem into parts depends directly on our ability to glue solutions together. To assist modular programming, a language must provide good glue.

Functional programming languages provide two new kinds of glue - higher-order
functions and lazy evaluation. Using these glues one can modularise programs
in new and exciting ways, and as small snippets explained earlier.

Difference between if and customized if as new-if

Suppose we wanted to define a function new-if which acts just like if; for instance,

(if (< 2 3) 4 5) => 4

and likewise

(new-if (< 2 3) 4 5) => 4

This is not too hard to write:

(define new-if
  (lambda (test then-exp else-exp)
    (cond [test then-exp]
          [else else-exp])))

This even seems to work. But there is something deeply wrong with this definition. Try stepping through (fact 4) for the following definition of fact:

(define fact
  (lambda (x)
    (new-if (< x 3)
           x
           (* n (fact (- n 1))))))

No application of fact ever halts--the function keeps calling itself recursively forever.

The problem is that functions (such as new-if) always evaluate all their arguments, while special forms (such as if and cond) may only evaluate some of their arguments, leaving others as expressions rather than values. We can't use the ordinary part of Scheme to write new special forms, only new functions.


Theory behind the new-if is the explanation regarding tail recursion which was explained in previous blog post.

                                           ......Thank You......

Tail recursions

Tail recursion is the act of making a tail recursive call. We can understand that term in parts. A call is just application of a function. A recursive call occurs when a function invokes itself. A tail call occurs when a function's result is just the value of another function call. In other words, in order to determine the value of function f, we call g, and return whatever g did, without modification.

Why to use tail calls?

 For a non-tail call, Scheme must remember that after the current function application, it is responsible for doing something else (in this case, adding 1 to the result); and there may be many such things to do. For a tail call, Scheme doesn't have to remember anything, because there is nothing more to do: after it is done with the current function call, it is really done.
                    
                                               Non-tail calls force Scheme to remember future actions (that couldn't be performed before), but tail calls don't. Non-tail calls require more space (because there is more to remember), so they are not as efficient as tail calls. Tail calls also permit us to forget the values of function parameters and local variables, because we never do any more work in the calling function, but a non-tail call forces us to remember such values, which might be used when we return to the calling function.

(define foo
  (lambda (x)
    (if (even? x)
      (+ 1 (foo (/ x 2)))
      (bar x))))

(define bar
  (lambda (y)
    (* y 3)))

                          The definition of foo contains a recursive call to foo (it's recursive because foo is the procedure in which the call to foo appears) and a tail call to bar. The call to bar is a tail call because, if the parameter x is even, then the value of the call of foo is just whatever bar returns.