I have been programming now in R for at least 7 years and never once have I needed to resort to a for-loop. In fact I also never resort to while or until loops

I have always managed to avoid it with the apply family of functions.

Then today, I was defining a function with two variables where one of them has to be a regex. Instead, of calling it from the outside and passing these, I “curried” it and I felt good about it.

Now, if you know what I meant by that, then you are a functional programmer who will very likely be happy with R, but if you don’t see what I mean, I can see why you will pooh-pooh R, I get it, it is not for you.

This is the last part of my notes on recursion. I am reminded that these techniques are only possible in a language that is supportive of the functional style of programming. Fixpoint is a mathematics concept which has been migrated to computer science.

In mathematics, a fixpoint refers to a function. Well, what a surprise, we are talking about functional programming after all! Here is a quick way of explaining a fixpoint of a function. Given a function $y = f(x)$, the fixpoint of this function is that value of $x$ for which this equation holds $x = f(x)$. We illustrate it below. The fixpoints of the function below are 0 and 1.

In $\lambda$ Calculus and in functional programming this is called the Y-Combinator. This was discovered by the American computer scientist Haskell Curry. For those who are into this calculus, it is stated below like this:

$Y = \lambda f.(\lambda x.f\ (x\ x)) \ (\lambda x.f\ (x\ x))$

Fixpoint programming allows you to effect a recursion without doing an actual recursion. It relieves you of complexities that come with recursion.

In Scheme, it is so close to the above and gives you an almost one to one correspondence:

Watch how this is directly translatable to R:

This is why I have so much fun with R. It looks so like Scheme!

Now let us do the Fibonacci Sequence without Tail Recursion! This version is what comes naturally – it is recursion but it is not tail recursion by definition. It is because the last thing it does is not call the function, instead, it adds two results.

We now pass this function to our Y-Combinator and voila! It works!

You can keep this R Y-Combinator function in your pocket, you can carry it with you anywhere and bring it up when you need to use it. It is forever done and should always work.

For now, this ends my rambling on recursive programming in R.

Last time I wrote some notes to self on the use of Tail Recursion in R. What I gave in the previous post (look at the one before this) was actually the accumulator passing style to do a tail call. Today I will do the same, this time the so called CPS. Again, I will illustrate using the Fibonacci Sequences.

Continuous Passing Style of recursion is a type of recursion where you look at computation in two senses. Past Tense – the part of computation that have already been completed and that part that is still yet to do. In CPS, on the latter part the programmer passes this as a complete parameter that needs to be executed. This parameter is called the continuation, semantically – you are saying do some more.

This is where the concept of the lambda function, I think becomes very handy. The so called anonymous function – or function on the fly is the way to go. Did you know that R – follows closely the syntax of the λ calculus? See the examples below:

The function command in R is the lambda operator. We can translate the above this way:

$(\lambda x . x + 1)(2)$ ⇒ 3

$(\lambda x y. x + y)(2,3)$ ⇒ 5

Anyway, as I was saying, we get the same now w/ CPS + tail call with the help from $\lambda$ and we get this (refer to the previous post!)

Notice now we have an extra parameter – which we conveniently call continuation (which could have been any name we wished) but note! It is equal to the identity function found in R. The identity function returns the same thing we pass to it. See line 21 and 25. Note that in line 30, the text I underlined in green stands for the continuation work that needs to be done – a bit requiring some reflection because it is a curried function.

Note another idea – I am calling the recursive function deep again inside it. Here is the result

You might say – hmm, that code looks wild, it looks like voodoo to me. We can re-write it a bit better so here is another version:

In line 46-47, I re-arranged the code so it can be better analyzed. The we now have a name for the lambda.

I marked with a red arrow the continuation command for deeper thought. Here is the result of execution…It works!

So note, again, we are indeed doing tail recursion here because, the last thing we are doing is we cleanly call back ourselves.

Functional programming is not popular because it seems to suggest you need to learn a few more conventions on top of the language but for me, it does wind up more elegant in the end.

Let me know if you have any suggestions or any topic you would like me to tackle next time.

I have been reflecting on recursion lately and as far as I know, tail recursion is the best kind of recursion and is the way to go in R. However, I heard R’s interpreter does not optimize recursion, which is sad. At least, it does help you not to blow up your call stack. There are several ways of handling this:

• By using Trampolines. However, this is not straight forward and can be messy for some. It is not intuitive.
• By using type of continuation passing function definition. There is a gist of this in here by a great R author Thomas Mailund who wrote the book Functional Programming in R.-

In this post, I shall follow Mailund’s recommendation of how to do tail recursion in R, but I will do this using the Fibonacci Sequence rather than the usual Factorial example to illustrate recursion.

Mathematically, the Fibonacci Sequence is formulated this way:

$F_0 = 0, F_1 = 1$ and $F_n = F_{n - 1} + F_{n - 2}$

Here are a few leading sequences $0, 1, 1, 2, 3, 5, 8, 13, 21, 34$ etc.

Following the mathematical form, we get this R code which reminds you of the C syntax:

The definition of tail recursion is that the last thing your recursion should do is to do nothing else except to call the function again. Although this follows neatly the mathematical form, this is not doing tail recursion.

The reason is that it is not simply calling the function, it does something more. It does call the function but it is adding the result of the calls. By definition, this is not tail recursion, it does not simply call the function. Non-tail recursion can blow up your call stack heap. So, you could be lucky or not so lucky as you do not know what $n$ might be when your function is called.

Below is the same version but legally does a tail recursion

Few things to observe. Notice now that we do not simply pass $n$ to the function. There are more arguments. $a, b$ are what is called accumulators. I know, it is not natural and it needs a bit more mental work than the non functional style. Note the {,}. I placed them there because for some reason the R version 4.0.3 will give me the error below if I do not put them there although legally it is not required by the syntax. Here is what I get if I don’t :

However, there is a certain cuteness in this code. Observe that the $a$ position is acting as $F_{n - 1}$, and the $b$ position is acting as $F_n$.

In Lisp/Scheme programming parlance this is the concept of call by continuous passing.

Unlike in Scheme where tail recursion is so supported in the language, it is not so with R due to its dynamic nature. Maitlund has the tailr package that translates your tail recursion internally however, I won’t get into that here. My objective is the need to have lateral thinking when making your recursive call, tail recursive by the use of accumulators – it requires some creativity and some challenge, but it looks elegant to me in the end.

HT:

An opinion piece in the usual debate…

Why R and not Python for Data Science

Python is a great programming language to learn if you are starting off in coding, but is this where you should end?

This is an interesting opinion on the usual debate…

Why Python is not the Programming Language of the Future

I know why Python is becoming more popular than R. The syntax can be grasp by kids. Whereas R needs a professional computer scientist’s mind to appreciate it. It is functional programming friendly and that demands thinking out of what is obvious box.

Also, I get that the switch to Python promises a hopeful career to the IT professional.

However, for old folks like me who is no longer after a career uplift, I will stick to R if not professionally at least privately because it is the RIGHT language to use.

Here is a study why R is not likely going to disappear so soon, at least those who are doing real data science – those in the health sciences.

https://www.datasciencecentral.com/profiles/blogs/which-one-is-faster-in-multiprocessing-r-or-python

UPDATED

All over the internet and in ML/AI forums, we see the constant debate. I must admit, there are slightly more Python fans than R.  I know why people are switching – it is for jobs! For economic reasons. I get that. But for an old timer like me, I am more after fun and enjoyment not just income. Anyway, who likes to change every couple of years whenever a new thing comes along – I get tired with this.

Python’s syntax is easier to deal with, I get that too. I admit R takes some time to deal with but it is not the syntax, it is the functional paradigm that it exposes the new comer of which she has no inkling of what the functional programming paradigm happens to be. Due to its fan base, a lot of myths are being propagated by their proponents. I for one, will not be switching anytime soon. Because I believe I got what I need in R. Here are some examples of the myths, and most who believe these myths have very little knowledge of computing theory.

Python is more powerful than R? Like, you can write algorithms that you cannot write in R. Huh? Both Python and R are Turing Complete (TC) languages! TC means any algorithm you can think of you  can express it in either languages. You are just limited by your imagination. In fact, you can even do it low verbosity in R than in Python, because R is applicative programming (functional). So if you are looping in R using the for or while loop then you are doing it wrong. In R, you recur, you apply, you filter, you reduce.

I admit, to the non-professional programmer Python is easy – for after all it is like BASIC language of many many years ago.  Between the two, Python is context sensitive while R is context free (it is after all inspired by Scheme which came from LISP).  What does that mean? It means with Python, the programmer has to be conscious of the use of white spaces. For example the Python coder has to pay attention on his indentation each time he places a line specially if she is doing a code block. This is not true in R. The {} marks a code block and when you see that, that is immediately a signal you got a set of code to be treated as a unit. In context free, the white spaces are non events, but in context sensitive languages, that white space is bad trouble.

With Python, you do not need to comment code? This is another fake news. Once you read a Python code without comments and that code is using libraries from all over the place, good luck to you when you are asked to modify or debug that code. I hope you stay safe and not break any piece there.  You also won’t be working for me if you love no comments. It is extreme folly to think the code is the comment. This is another hype made out by fans which normally do not come from computer science back ground.

Why I am staying put with R? Python started out as a general purpose language which moved into ML. Yet, R which started in statistics is actually now moving to being general purpose as well. It is a matter of facilities.

Can you write command line app in R? Yes.

Can you write a desk app in R? Yes.

Can you write data manipulation, data cleaning, etc in R? Yes, without resorting to PERL.

Can you write web scrapers in R? Yes.

Can you write a web apps in R? Yes.

Can you consume or expose web services in R? Yes.

Can you write job control apps in R? Yes.

Have I left off anything? Yes.

Can you write games in it? Believe me – yes.

If not, then it is good for everything then.

Somewhere somehow, when something is new, it must be good or better than the one that came before. I don’t believe it.  Hype  makes  the  world  go  round. People feed on this. Frankly, I have no more appetite to learn another programming language.

What they put in to enhance a programming language, they learned it from Lisp.

They don’t like its syntax because it is tracking close to its inspiration, the Lambda Calculus of Alonso Church. But that is why it is so elegant and concise.

In functional capable languages, if you are doing loops and not doing apply, recursion, map, reduce, you are doing it wrong. I was saying to an inquirer asking me about R (which came from Scheme), if you are looping, and not recurring or applying, then you are not using the power of the language, those facilities make your code smaller than necessary and so much easier to debug.

This is one language I believe every software engineer should go for before they pass on to the …

Now please do not get upset. I am using the word “intelligent” the way computer scientists used the word some 60 decades ago. According to the late John McCarthy, the man who coined the words “artificial intelligence”, something is intelligent if the ‘thing’ has common sense.

We shall therefore say that a program has common sense if it automatically deduces for itself a sufficiently wide class of immediate consequences of anything of anything it is told and what it already know — John McCarthy.

The fact that in statistics we have to get a sample of size $n$ and it has to be large as large as we can afford with our resources, makes Statistics not so intelligent, if we follow McCarthy’s definition. The Central Limit Theorem(CTL) is the saving grace of Statistics, at least the classical one. In classical statisics, before we proceed to use it, we must first go behind the probability distribution $f(X)$ that governs the values of our random variable $X$ under study. This is not usually known, but CTL says, don’t lose hope, forget $X$ just get a lot of samples and consider $\bar{X}$, just get lots and lots of examples of $X$ and form its $\bar{X}$, at least $n >30$ because we know that $\bar{X}$ is going to be Normal. However, when someone has common sense, you do not have to give it tons and tons of data for it to know what you are saying, so by computer science standard, Statistics is not intelligent 😉