This cycle of articles is my small (or huge) experiment. I’ll try to get back to the basics and learn a something new.
I chosed “Structure and Interpritation of Computer Program”, because a lot of cool programmers (my idols) think that the book is the greatest! So I’ll check it! But I’ll use Clojure instead of Scheme, I think it’s more efficient and popular in our time.
In first part, author writes a lot about syntax of Scheme (analog for Clojure here and here) and describes some base concepts.
Recursion is an abstract model, where an object is part of itself. For instance, a picture with some picture inside or function, which call itself.
(defn sum [x]
(if (= x 0)
0
(+ x (sum (dec x)))))
It’s example of linear recursion. If we call this procedure (sum 5), the interpreter will first create a chain (line) (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0))))) and then calculate it.
Similarly, we can create tree recursion:
(defn fib [n]
(cond
(= n 0) 0
(= n 1) 1
:else (+ (fib (- n 1))
(fin (- n 2)))))
In general, a recursive process is characterized by the accumulation of actions and their further execution. There is also an iterative process. It immediately performs the action, and accumulates the result of these actions. For instance:
(defn sum [x]
(let [iter [i result]
(if (= i 0)
result
(recur (dec i) (+ i result)))]
(iter x 0)))
Author give us many examples of high-order function (HOF) and first-class elements. HOF is a function (procedure), which can manipulate others functions: consume, produce, call. In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first-class elements are:
- They may be named by variables.
- They may be passed as arguments to procedures.
- They may be returned as the results of procedures.
- They may be included in data structures
You can see some examples and solutions of exercise in this repo