REBOL Technologies

Is REBOL a Pure Functional Language?

Carl Sassenrath, CTO
REBOL Technologies
14-Sep-2005 18:15 GMT

Article #0206
Main page || Index || Prior Article [0205] || Next Article [0207] || Post Comments || Send feedback

In the realm of computer science, there is the concept of functional languages or functional programming. It is sometimes debated whether REBOL falls into that category. As the designer of REBOL, I think I can help clarify the debate: REBOL is not a pure functional language (PFL). And, to be precise: it was not intended to be.

If you are not familiar with the concepts of functional languages, the paradigm has been around for 50 years and is described in many places. You can read a quick summary from the wikipedia entry on that topic:

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. It is more heavily used in academia than in industry. The strength of a functional paradigm is the removal of side-effects during computation.

I do not consider REBOL to be a PFL for two main reasons:

  1. REBOL does not automatically "copy" data references that are to be modified. (See the discussion below.)

  2. A number of REBOL functions allow side effects on purpose.

The Copy Principle

The issue regarding copying of data is obvious in REBOL in several ways. Here is an example of a function that shows a well known case:

indent: func ["Increment indentation" amount /local str] [
    str: ""
    head insert/dup tail str " " amount
]

The str string is statically allocated and reused with each call to the indent function. This behavior of data causes the results of the function to become dependent on prior calls to the function. In PFL terms, the function is said to not be referentially transparent (RT). In the above case, although the side effect is used in a positive way, it violates the RT rule of functional programming.

At the root of the problem here is the fact that the indent function above embodies and depends on a prior state. In other words, the essential problem is at a high level, in the actual definition of the function. (By the way, you can get into a really interesting debate about whether the concepts of variable assignment found in any language create the same problem. But, we won't get into that now.)

If you were to rewrite the function to be:

indent: func ["Increment indentation" amount /local str] [
    str: copy ""
    head insert/dup tail str " " amount
]

the function would cease to work as you intended it. Although it would meet the definition of RT, it would always return the same result (given the same argument) regardless of how many times it was called.

Regardless of how you rework this function, there is no way to make it RT, because the issue is in the definition of the function itself. The definition implies a state, and that state changes with each invocation.

This gets a lot deeper and a lot more interesting when you consider the concepts of REBOL data in general. For example, if you define the block:

person: [
    name "John Smith"
    email john@example.org
    site http://www.example.org
]

Now, if you write a function that modifies that block or its data without first deep copying all of the data that is to be modified then any such function will not be RT. A violation of PFL rules.

If you stop to consider how often you might use data (and code) blocks such as the one shown above, you can easily see why I do not consider REBOL to be a PFL.

The Side Effect Principle

With the RT issue now fully exposed, we can address the second bullet noted above. If we do not pretend that REBOL is PFL, then why not allow some REBOL internal functions to have side effects?

If you look at the newest REBOL Word Browser, you will see a category for modify functions. These are functions that were designed to have side effects and we make no bones about that fact. They include:

alter
append
change
clear
detab
entab
insert
lowercase
remove
remove-each
replace
reverse
sort
trim
uppercase

Let's look deeper at an example. Pick the uppercase function for instance:

str: "example"
str2: uppercase str
?? str
str: "EXAMPLE"

It has the side effect that it modified its original argument. Of course, in REBOL you can also explicitly force the copy:

str: "example"
str2: uppercase copy str
?? str
str: "example"

You may ask yourself, do all these REBOL functions really need to have side effects? The answer of course is no. Functions like lowercase could easily be RT. But, although it is possible, we should always ask: is it a good idea? For example, if you have a 100KB string, and you want to capitalize the first character of it, to be RT, you need to copy the entire string (or the equivalent, depending on internals) then change that single character. In other words it always becomes this:

str2: uppercase/part copy str1 1

There is never an option to do just this:

str2: uppercase/part str1 1

(Modify the data directly, side-effecting all references to the data as well.)

Now, imagine what the essential REBOL series functions like insert, change, and remove would be like if they were purely functional? They would almost always force an automatic copy of their data. They would never be allowed to modify the data itself (as long as there were any other references to the data).

These issues and effects of PFL get a lot deeper really fast. They propagate throughout a language and can be seen in the way a language defines functions, objects, modules, threading, continuations, and more.

You may find it very interesting to note that REBOL/core 1.0 was PFL. That fact made REBOL's implementation very complex, but more importantly it made its execution 30 times slower than REBOL/core 2.0 that followed it.

Which is better? You will need to decide that for yourself. It depends on what properties of languages you find the most important for the applications you are implementing. REBOL does a lot of things differently. After all, it is called REBOL for a good reason.

But, at the very least, I think it is a good thing that we put this entire issue of REBOL as a PFL to rest. It is not. Nor, was it intended to be that way.

I'm sure that I'm going to get a pile of feedback on this topic. Someday I would like to add an additional article: "Is functional programming natural? (e.g "natural" being the basis for the concept of object-oriented programming.) But, that topic is really going to get some developers foaming... so best to do that at another time.

Post Comments

Updated 29-Aug-2014   -   Copyright Carl Sassenrath   -   WWW.REBOL.COM   -   Edit   -   Blogger Source Code