# The procedures
---
## What is the procedure?
In terms of the TAAL procedure is the synonym to the function in other languages.
It has four basic elements:
* name
* argument(s)
* body
* return value
Where the body means some actions to get the result of calculus _(return value)_.
----
The procedure may return a value of any type _(also procedure)_. The arguments may be any type too.
The procedure may have or not the name _(in case of the name is absent we call that procedure anonymous)_.
---
## The Syntax for the procedures.
We use the same word as for the variables -- **define**. But with some differences.
```lisp
(define (<proc-name> [<arg> ...])
<some actions>
<return value>
)
```
It is a _'syntactic sugar'_ but it is very useful.
**Return value** is the last line of procedure -- always!
----
For example, we may create a simple procedure
```lisp=
(define (duplicator x)
(+ x x)
)
```
The procedure contains only one string inside so it is an action and a return value altogether.
----
```lisp=
(define (duplicator x)
(+ x x)
)
```
Here we have:
* name: <span style="color:#00c;">**duplicator**</span>
* argument(s): <span style="color:#00c;">**x**</span>
* body: <span style="color:#00c;">**(+ x x)**</span>
* return value: <span style="color:#00c;">**(+ x x)**</span> _(because it is a last line)_
----
The full syntax for the procedure definition _(without sugar)_
```lisp
(define <proc-name>
(lambda <list-of-arguments>
<some actions>
<return value>
)
)
```
Where ==\<list-of-arguments\>== may be <span style="color:#00c;">**named**</span>, <span style="color:#00c;">**empty**</span> or <span style="color:#00c;">**unnamed**</span> list.
The <span style="color:#900;">**lambda**</span> is the anonymous procedure -- clear action. Here we have defined bound to name procedure.
----
### Named arguments list
Used for an unknown number of arguments.
```lisp
(define <proc-name>
(lambda <args-list-name>
<some actions>
<return value>
)
)
```
```lisp=
(define plus
(lambda args
(if (every number? args)
(apply + args)
(null)
)
)
)
```
----
### Empty arguments list
Just for procedures without any arguments.
```lisp
(define <proc-name>
(lambda ()
<some actions>
<return value>
)
)
```
```lisp=
(define say-hello
(lambda ()
(display "Hello")
)
)
```
----
### Unnamed list of arguments
Used for a strongly defined number of arguments.
```lisp
(define <proc-name>
(lambda (<arg> [<arg> ...])
<some actions>
<return value>
)
)
```
```lisp=
(define hypo
(lambda (a b)
(sqrt (+ (sqr a) (sqr b)))
)
)
```
---
## More complicated example
Try to solve quadratic equation with own self written procedure.
$$a \cdot x^2 + b \cdot x + c = 0$$
We may get one, two, or zero roots as an answer _(where zero stands for complex roots)_. So we just will work with real numbers for simplification of our task.
----
### The sequence of embedded IF-s
```lisp=
(define (solve a b c)
(define D (- (* b b) (* 4 a c)))
(define (z d!) (/ (+ (- 0 b) d!) (* 2 a)))
(if (= a 0)
(/ (- 0 c) b)
(if (< D 0)
"complex"
(if (= D 0)
(z 0)
(list (z (sqrt D)) (z (- 0 (sqrt D))))
)
)
)
)
```
----
### Using COND
```lisp=
(define (solve a b c)
(define D (- (* b b) (* 4 a c)))
(define (z d!) (/ (+ (- 0 b) d!) (* 2 a)))
(cond
((= a 0) (/ (- 0 c) b))
((< D 0) "complex")
((= D 0) (z 0))
(else
(list (z (sqrt D)) (z (- 0 (sqrt D))))
)
)
)
```
---
## What about the lambdas?
As you have seen before we may use the full syntax for binding the procedure with a name. It points to us that we also may use procedures without naming.
----
**Lambda-syntax** allows us to work with procedures when we do not want to use the procedure more than once. So it is special for one-time actions.
----
### Where do we use lambdas?
We have a class of procedures that have to use the procedure as an argument. E.g. map, filter-map, apply, etc.
Also, we may use lambda-notation in some cases to unify our procedures.
----
## Unification
Let's take a look at an example.
```lisp=
(define (all-positives lst)
(map
(lambda (item)
(abs item)
)
lst
)
)
```
How does the procedure work?
----
We need to call it with a list of numbers as an argument.
```lisp
taali> (all-positives (list 2 3 -6 2 -1 0 -5))
(2 3 6 2 1 0 5)
```
----
What happens if we use the lambda-syntax definition? But with some changes.
```lisp=
(define all-positives
(lambda lst
(map
(lambda (item)
(abs item)
)
lst
)
)
)
```
----
Now we can call the procedure with any number of arguments, and without boxing them into a list.
```lisp
taali> (all-positives 2 3 -6 2 -1 0 -5)
(2 3 6 2 1 0 5)
```
And it is not the end!
----
What about this?
```lisp
taali> (apply all-positives (list 2 3 -6 2 -1 0 -5))
(2 3 6 2 1 0 5)
```
Now we have the unified procedure for using with any number of arguments, and applicable to any length list.
----
Look at the difference between the use cases.
```lisp
taali> (all-positives (list 2 3 -6 2 -1 0 -5))
(2 3 6 2 1 0 5)
```
```lisp
taali> (all-positives 2 3 -6 2 -1 0 -5)
(2 3 6 2 1 0 5)
```
```lisp
taali> (apply all-positives (list 2 3 -6 2 -1 0 -5))
(2 3 6 2 1 0 5)
```
---
## Control task
### Population standard deviation
$$\sigma = \sqrt{ \frac{1}{n} \cdot \sum_{i=1}^{n}{\left( x_i - \bar{x} \right)^2} }$$
Some additional conditions. Use a list of values as an argument of your procedure.
$$\left( 2, 4, 4, 4, 5, 5, 7, 9\right)$$
----
## Answer
$$\sigma = 2$$
## Hint for beginners
Work decomposition is the key to success!
----
* Look at the task and find what kind of procedure may to use for each part of the work?
* Understand what type of data you will use?
* What is the order of calculations?
* What kind of helper procedures do you need to write?
---
## Recursion
### In order to understand recursion, you must first understand recursion.
_Of course, it is a joke but very close to be the truth._
----
Here we have a very simple example of the recursive procedure.
```lisp=
(define (remainder dividend divisor)
(if (< dividend 0)
(+ dividend divisor)
(remainder (- dividend divisor) divisor)
)
)
```
----
### What's going on here?
Imagine we need to know how to calculate a remainder of the division. We just need to do some actions one-by-one to receive the solution.
For example, we have two numbers: **9** and **4**.
----
Do some math!
$$9 \mod 4 = 1$$
It means we try to divide **9** by **4** but have the remainder **1**. Because
$$\begin{align}
9 & = 4 \cdot 2 + 1 \\
9 & = 4 + 4 + 1 \\
9 - 4 & = 4 + 1 \\
9 - 4 - 4 & = 1
\end{align}
$$
----
So what is the division? It is just multiple subtractions!
To find an algorithm for our procedure we need to use a simple math operation. We need to subtract the second number from the first again and again till receiving a negative number as an answer.
----
When the result is negative, we have to undo our previous iteration and restore the result.
$$\begin{align}
9 - 4 & = 5 \\
5 - 4 & = 1 \\
1 - 4 & = -3 \\
-3 + 4 & = 1
\end{align}
$$
So we have an algorithm and the right answer.
----
Take a look at our procedure again.
```lisp=
(define (remainder dividend divisor)
(if (< dividend 0)
(+ dividend divisor)
(remainder (- dividend divisor) divisor)
)
)
```
==The first rule of finite recursion is knowing where to stop!==
----
At line \#2, we follow this simple and very important rule!
In other words, we have a condition with two possibilities: return the value or do one more operation.
At line \#4 we just call the procedure with a new set of data.
----
When we will try to solve our example, for the interpreter, it looks like this:
```lisp
(remainder 9 4)
(remainder 5 4)
(remainder 1 4)
;; I need to stop this!
1
```
Maybe without comments, but very similar to the steps above...
----
## More complicated example of the recursive procedure.
```lisp=
(define (deep-find item plst)
(define (df-iter inp out)
(if (null? inp)
out
(if (member? item inp)
(begin
(define tail (cdr (member item inp)))
(df-iter tail (list-add out (car tail)))
)
(df-iter (null) out)
)
)
)
(df-iter (list-flatten plst) (list))
)
```
----
This procedure finds the key in all lists recursively and returns a list of values.
```
taali> (deep-find 'a (list 'c 3 'b 2 'a 2 'd 4 'e (list 'b 3 'a 7 'c 6 'd (list 'b 4 'a 8 'c 6))))
(2 7 8)
```
---
# The end.
{"metaMigratedAt":"2023-06-15T15:50:18.032Z","metaMigratedFrom":"Content","title":"The procedures","breaks":true,"contributors":"[{\"id\":\"50e50a49-9bd5-469a-bb18-7a083a8b3cc0\",\"add\":10318,\"del\":1142}]"}