Understanding Closures, Lambda Functions, and Higher-Order Functions in Programming
In programming, closures bind functions and lexical environments, while lambda functions are nameless and used by higher-order functions. Higher-order functions operate by applying other functions, such as map and fold functions. Example implementations in LISP demonstrate how these concepts are utilized in practice.
Uploaded on Oct 05, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Closure Closure binds a first-class function and a lexical environment together This is a complex topic, so we will build up our understanding of it we must understand higher-order functions to support higher-order functions, we must understand the notion of returning a function or in using a pointer to a function we then must define first-class functions first-class functions are nested functions so we have to understand nested functions we must understand binding of variables within a scope optionally, we should probably understand lambda functions we have already discussed at least briefly several of these topics, now we put them all together
Lambda Functions A nameless or anonymous function the function is not bound to a name (identifier) the function is utilized by a higher-order function First used in programming languages by LISP where its called a Lambda Expression the syntax in LISP is (lambda (params) ) where are one or more function calls example to add 1 to x (lambda (x) (+ x 1)) example to compare two data and return the largest (lambda (x y) (cond ((> x y) x) (t y))) Lambda expressions are nested inside of other functions such as the define function to define and name a function, and mapcar
Higher-order Functions A function which either takes a function as one of its parameters and/or returns a function as its result Basically, a higher-order function operate by applying other functions Types of higher-order functions map take a list of data and apply the parameter function to the list, returning a list fold take a recursive data structure (e.g., a tree) and a function which combines elements of the data structure, returning a reduced structure or a single value example: sum up the elements of a linked list or tuple or array sort if the sort function itself applies some type of compareTo function integration function which computes area under a curve by adding the results of applying the function to each point on the curve
Example: LISPs mapcar A map function which is defined as follows (defun mapcar (func lis) (if (null lis) nil (cons (func (car lis)) (mapcar func (cdr lis))))) Take each element of the lis (a list) and pass it to func (a function), returning as a list all of the return values from func assume func adds 1 to its parameter, then passing mapcar func and the list (1 3 6 8) causes mapcar to return (2 4 7 9) The function passed to mapcar is typically a lambda function example: (mapcar # (lambda (x) (+ x 1)) (1 3 6 8))
Example: Building an Add All Function in C An addall function normally receives a list of values and adds them together in this case, we want to receive the list of values and a function f to apply each value to, add all of the results and return this result (this is a fold type higher order function) int addAll(int (*f)(int), int data[], int size) { int sum=0, i; for(i=0;i<size;i++) sum+=f(data[i]); return sum; } receives a pointer to function f, and a list of data in an int array (along with the number of ints), returns an int it is computing the summation of all data as applied to f(data[i]) f could be just about any function say one that returns the square of data[i] so that addAll would compute the summation of all the squares in data, or abs(data[i]), etc
Returning a Function in F# We define outer to receive two parameters, both are functions outer defines the function inner which receives one parameter inner applies its parameter to the two functions which are outer s two parameters , that is, it performs op1(op2(x)) outer returns the function inner (not a computed value) outer is a function is defined let outer op1 op2 = let inner x = op1 (op2 x) inner We now define a couple of functions, for instance let x a = a + 1 let y b = b * 2 Next, we assign a variable to store the function returned from outer (inner) as let temp = outer x y // temp is now the function x(y( )) temp 5 passes 5 to temp, which was what outer returned (inner), temp 5 returns 11
First-class Functions In a language, a first-class citizen is any construct which can be treated like the other first-class citizens of the language If a language has first-class functions, it means the functions are treated like data types, variables, values, etc in this case, we mean that the function can be passed as a parameter to a subroutine returned from a subroutine as a return value assigned to a variable (or stored in some type of data structure) modified dynamically (in this case, its not the function that is modified but the variable referencing the function) All first-class functions are higher-order functions but higher-order functions are not necessarily first-class functions as it may not contain all of the functionality as listed above (e.g., being treated as a value or variable)
Storing Functions in a Data Structure in F# First, we define two functions let square x = x * x let cube x = x * x * x Now we can place square and cube in different types of data structures let myTuple = (square, cube) let myList = [ square, cube ] We can pass myTuple or myList to a function and utilize the two functions let f1 x y = let a1 = (fst x) y let a2 = (snd x) y x + y f1 myTuple 5 will compute and return 5 * 5 + 5 * 5 * 5
Languages With and Without First-Class Functions LISP if using static scoping (but not if using dynamic scoping) Functional languages like ML, Haskell, F# Scripting languages like Perl, PHP, Python, Lua, JavaScript OOP: Java (starting with Java 8) and C# (starting with 2.0), Swift/Objective-C (starting with 2.0) Languages without first-class functions include Pascal, Algol functions can be passed as parameters but not returned from functions C/C++ - not garbage collected and since C/C++ does not support nested subroutines, the usefulness of having first- class functions is limited, for instance closures would not be available
Closure Now we can tackle the concept of closure A closure is a first-class function which is bound with lexically scoped variables that is, the function has access to variables whose scope is strictly determinable at compile time and thus the function can know its values we will refer to variables not defined within the function itself as free variables we need to have a means to determine this scope one way to implement this is to use static scoping rules of nested subroutines as introduced in Algol if free variables are not lexically (or statically) scoped then it can lead to two issues poor run-time efficiency as we have to locate the variables on the run-time stack impact from side effects in that if a variable can be altered by another entity, then the function, when passed the same parameter, could produce different results
Example of Using a Closure We want to take an array and create an HTML table out of its items we have a first-class function, render, which is passed the current item and renders it in the way we want we could pass a different render function if we want a different form of rendering render is passed to this function so that we control how we render based on which function we pass for instance, maybe we want to render all numbers to be real numbers by adding a decimal point if they don t have one, or maybe we want to render all content to be exactly 5 characters wide, each render function can differ now let s assume that the render function might want to access other local variables of the outer function this is possible with a closure without a closure, we have to pass to the render function local variables as parameters but some render functions may be designed to accept such parameters and others may not so for this functionality, we need closure
Example Implemented in JavaScript function renderArrayAsHtmlTable (array, renderer) { var table = "<table>"; var row = 0; for (var idx in array) { var object = array[idx]; row++; table += "<tr><td>" + renderer(object) + "</td></tr>"; } table += "</table>"; return table; } Notice that row is a local variable but not passed to renderer If we have closure, then renderer has access to row and this may be useful (e.g., renderer needs the row number to determine if the row is even or odd to alternate the background color of this row of the table being produced
Can We Avoid Closure? Yes In the previous example, we could pass row to renderer but this requires that all renderer functions receive that as a parameter even if there is no need for it if there are a lot of local variables, then any renderer function would have to receive all of them! Or we could pass row to renderer and require that all renderer functions receive optional parameters that they can use or ignore Neither solution is as elegant as making the outer function a closure
Example of Closure in C# public int outer(int y) { int notInFunctionScope = 1; Func<int> add = (int param) => { return notInFunctionScope + param; } Console.WriteLine(add(y)); } Here, we have a nested inner function, add add receives a parameter, param, but also has access to a variable not specifically in its scope the reason notInFunctionScope is accessible in add is because of the closure available in that add is defined in outer and called from within outer imagine that after x = add(y); we have notInFunctionScope++; followed by another Console.WriteLine(add(y)); instruction we get two different results, y+1 and y+2
Example of Closure in F# Here we see a similar illustration in which the result changes because the local variable s value has changed let example = let str = old value let closureFunction() = sprintf %s str let str = new value printfn %s %s (closureFunction()) str Note that sprintf is like printfn except that it returns the value being printed (this is required because the function must return a value to be used in printfn) the output is: old value new value
In Conclusion Closure is a complex concept, why is it important? we see that it provides a shortcut in utilizing higher-order functions whereby the local environment (outside of the passed function) is accessible it can be used in libraries for instance, we might define a sort where the compareTo function is passed to the sort method the compareTo can access things available in sort closures use lazy evaluation which can improve efficiency a collection of closures can be defined which share variables thus providing an alternative means of accessing shared data which would otherwise be private or inaccessible C/C++ does not have closures no nested functions and there s no way to define the scope needed you can simulate closures by defining a struct in which one struct member is a pointer to the function you are going to pass and other members are the variables whose scope should be accessible in that function
