functional language purpose
- general programming
- symbolic programming
first class functions
function are values, they can be passed as arguments and returned from functions
datastructures
treated holistically rather than element by element
functional features in mainstream languages
- closures/anonymous functions/lambdas
- first class functions
variable
a symbol or name that refer to a memory location
expression
a combination of variables, operators, etc that describe a computation
value
an instance of a datatype
parameters
the variables in the function definition
sometimes called formal parameters
arguments
the values passed when calling a function
sometimes called actual parameters
declaration
where we indicate a symbol is a variable, often also has a type declaration
definition
the first time we give a variable a value
mostly refers to functions, initialisation used for non-functions
call by value
values of the argument expressions are passed into the function call
e.g. f(x+y, x-y) would pass the resuts of the expressions
call by reference
a reference to a variable is passed rather than the value
call by name
the expressions in the call are substituted into the function body and are then evalauted. they are passed in and then evaluated rather than evaluated and then passed in as in call by value
call by need
like call by name that only evaluates a given argument once to get closer to the efficiency of call by value. this is done by memoising the argument evaluations
laziness
- used in many languages
- called short circuit evaluation
- often logical operators are lazy
e.g. if x = 0 then in (x == 0 || 1/x == 0) the 1/x == 0 is never evaluated because it won’t change the outcome of the condition, this is a useful feature as if x ==0 and 1/x is still evaluted then it will likely throw an error
combinator
a higher order function
program in combinatory logic
a variable-free composition of functions
reduction
evaluating an expression by simplifying it according to formal rules
moves the data around inside the expression
SKI combinators
all operations in lambda calculus can be encoded via abstraction elimination into the SKI calculus as binary trees whose leaves are one of the three symbols S, K, and I
super combinators
program specific combinators are synthesised from the program itself, larger instructions and more efficient encoding
haskell is an example of this
