Transcript Clojure 9
Important Concepts from Clojure 11-Apr-16 Abstract syntax trees Compilers turn source code into ASTs (Abstract Syntax Trees) This is a major first step in virtually all compilers and interpreters Lisp/Clojure syntax is an AST Basic functional programming Functions are values (“first-class objects”) Functions have no side effects May be passed as parameters to other functions May be returned as the result of a function call May be stored in variables or data structures Given the same parameters, a function returns the same result Referential transparency: The result of a function call may be substituted for the function call Data is immutable and persistent Immutable data makes concurrency much easier Persistent means that structure is shared Recursion Loops and recursion are equivalent in power If a function is tail-recursive, it can be automatically turned into a loop (thus saving stack frames) Anything that can be done with a loop can be done recursively, and vice versa Tail recursion is when the recursion is the last thing done in every branch of the function Loops are less useful when data is immutable Loops are used primarily to modify data When data is immutable, the substitution rule applies: Any variable or function call may be replaced by its value The substitution rule simplifies reasoning about programs Tail call elimination Recursive functions can often be rewritten to be tail recursive This is done by creating a helper function that takes an additional “accumulator” parameter Non-tail recursive function to find the factorial: (defn factorial-1 [n] (if (= n 1) 1 (* n (factorial-1 (dec n))) ) Tail recursive function to find the factorial: (defn factorial-2 ([n] (factorial-2 1 n)) ([acc n] (if (= n 1) acc (recur (* n acc) (dec n)) ) ) ) Higher-order functions add expressiveness A higher-order function is a function that takes a function as an argument, returns a function as its vallue, or both Of course, higher-order functions do not increase the number of things that can be computed Any Turing complete language can compute anything that can be computed It doesn’t take much for a language to be Turing complete Higher-order functions can take the place of explicit recursions (or explicit loops) Using higher-order functions typically makes code shorter and clearer Common higher-order functions Almost every functional languages has these features and functions: Anonymous (literal) functions, so a function doesn’t have to be defined independently, but can be placed directly as an argument to a higher-order function (map function sequence) applies the function to each element of the sequence, yielding a sequence of the results (filter predicate sequence) applies the predicate to each element of the sequence, yielding a sequence of the elements that satisfy the predicate (reduce initial-value binary-function sequence) applies the binaryfunction to each pair of elements of the sequence, starting with aninitialvalue , and yielding a single value List comprehensions combine and may simplify the above user=> (for [x (take 10 (iterate inc 1))] (* x x)) (1 4 9 16 25 36 49 64 81 100) Closures When a function definition uses variables that are not parameters or local variables, those variables are “closed over” and retained by the function The function uses those variables, not the value the variables had when the function was created user=> (defn rangechecker [min max] (fn [num] (and (>= num min) (<= num max))) ) #'user/rangechecker Notice that the function being returned gets the values of min and max from the environment, not as parameters user=> (def in-range? (rangechecker 0 100)) #'user/in-range? Currying and function composition Currying is absorbing a parameter into a function to make a new function user=> (def hundred-times (partial * 100)) #'user/hundred-times Function composition is combining two or more functions into a new function user=> (def third (comp first rest rest)) #'user/third Persistence and laziness A persistent data structure is one that is itself immutable, but can be modified to create a “new” data structure The original and the new data structure share structure to minimize copying time and wasted storage A lazy data structure is one where parts of it do not exist until they are accessed They are implemented (by Clojure) as functions that return elements of a sequence only when requested This allows you to have “infinite” data structures Macros, metaprogramming, homoiconicity A macro is like a function whose result is code Metaprogramming is using programs to write programs Arguments to a macro are not evaluated Macro calls are evaluated at compile time The return value of a macro should be executable code This is the primary use of macros in Clojure Macros are used to implement DSLs (Domain Specific Languages) Homoiconicity is when there is no distinction between code and data Homoiconicity greatly simplifies metaprogramming The End