Learning happens when the attention is focussed.

If you don't have a good theory of learning, then help yourself focus by removing interference.

Now let's begin by defining what is computer science.

Computer Science is perhaps the wrong name for the field, it is neither about science nor computers (electrical engineering is the study of machines). Programming is more like engineering where the building takes majority of the time, so software engineering would've been a more suited term. However, software engineering has already been taken to represent a whole philosophy of other things. In software engineering there are two areas you should build your understanding in:

• complexity engineering, control of complexity
• programming paradigms (e.g. functional programming)

It helps to answer the question: why is there more than one programming language? Different languages have different design principles; for example, in scheme everything is first class, in another language it could be that everything is efficiently compile-able.

Being able to implement compact computer programs is an important part of computer literacy. There are three parts to computer literacy:

• access literacy, or reading code
• creative literacy, or writing code
• genre literacy, or adapting to different literatures

Why is the idea of function important?

Firstly, functions are well understood by theoreticians, and it is easier to do reasonings about a computer software system that is built functional.

Computers can do more than one task at a time, this is even truer these days because there are multi-core processors on one chip. If your program is entirely made of functions, the function is by definition unaffected by the behaviour of the rest of the program. The program can be run in parallelism, which is why most people care about functional programming.

You can also compose composition functions without having lots of parameter variables lying around. In Pascal, you can use function as input to another function, but not as return value. It is an arbitrary restriction, because relatively hard for compilers to allow functions as return values.

Terminologies

A function takes some inputs and gives some outputs, and it will always deterministically give you the same outputs given the same inputs. If a function depends on some external variable, then it is not a function because you won't always get the same outputs. The domain of a function is the kinds of things the function takes as arguments, and the range is what it returns as results.

A predicate is a function that returns true or false, in other words, a predicate is a function whose range is boolean.

A procedure is a sequence of steps for computing a function; same function can have different procedures. Inside the computer, there are only procedures.

A procedure is functional if it always creates new values and change nothing about inputs, that new values may or may not point to the same memory as inputs.

For a function f(x) (* x x)

• x is the formal parameter, a name for the placeholders of arguments in a function, which will later be substituted with actual argument expression or actual argument value
• (* x x) is the function, a prefix notation of multiplication

Calling the function can look like: f (+ 2 3), where the expression in bracket is called the actual argument expression. The actual argument value is 5 which is invisible.

When we say input or argument of a function, it can mean any of the three: formal parameter, actual argument expression, or actual argument value.

Special Form

Special Form is a primitive function where not all its arguments are evaluated, it has its evaluation rules following variable bindings.

Recursion is an example of special form, the first recursion cannot be fully evaluated, otherwise end up in an infinite loop of running the recursive call in the condition statement. The conditional statement has its own evaluation rule and terminates once it finds a base case. As a side note, the base case should always come before the recursive call, otherwise you won't ever find out if it has hit the base case.

Other examples of special form are the if-then-else conditional statement, and defining a function. So a special form is really a special expression with a predefined language keyword as the name.

There are two types of evaluation based on the order:

Applicative Order Evaluation： evaluate the arguments and then apply

Evaluate all the argument sub-expressions to turn all the actual argument expressions into actual argument values. Then pass the actual argument values to procedures, by substituting the formal parameters in the body of the procedures. This is illustrated in the example above.

Normal Order Evaluation： fully expand and then reduce

Take the actual argument expressions and substitute them in the function body. Nothing gets evaluated until a primitive is called.

Why does order matter?
When you have a non-functional argument where you'd get a different output each time e.g. a random integer, the normal order evaluation will give you different answers each time. Functional programming protects you to having think about what's going on and where inside the computer.

Function as Data: Generalising Patterns

In everyday language, we categorise words into nouns, verbs, etc. In programming by metaphor, data is the noun and procedures are the verbs. However, this is not how it works in programming, the line between data and function is blurred.

Higher order procedures either take a procedure as an argument or returns a procedure. A higher order procedure represents a higher order function, it does that in order to generalise patterns.

Taking function as an argument in another function, the argument does get evaluated in an applicative order, but evaluating is not the same as invoking. Evaluating recognises the argument is a function with certain name, invoking runs the nested function with arguments.

In other words, treat functions as data, i.e. first class data types. Function names are no different than variable names, with their values being the lambda expression with formal parameters and body. You can use procedures as data to build any control mechanism you want.

A data type is first class in a language if things of that type can be value of a variable (i.e. assigning a procedure in this case), or can be anonymous (a lambda function, procedure without name). A first class data type can be a member of an aggregate e.g. an array. Here's a list of capabilities for a first class type in no particular order:

• the value of a variable
• anonymous
• argument to a procedure
• value returned by a procedure
• a member of an aggregate

In every language, numbers are first class. Characters in a string are first class in some languages, but not all (e.g. C). Data aggregates are rarely first class, but pointers to the aggregates are. Hardly any language gives procedures as first class, but that's changing e.g. Python has lambda, Java has anonymous class.

A powerful programming language should not only provide means to instruct computers to do tasks, but also serve as a framework within which you can organise your ideas about procedures. This is achieve through three things: primitive expressions, means of combining and abstracting elements.

---

Credit to Berkeley The Structure and Interpretation of Computer Programs lectures.