Transcript As we leave Lisp

Important Concepts from Clojure
28-Mar-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?
user=> (in-range? 101)
false
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
user=> (hundred-times 3)
300
Function composition is combining two or more
functions into a new function


user=> (def third (comp first rest rest))
#'user/third
user=> (third [1 2 3 4 5])
3
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