Artful Code

A suggested that it would be helpful to have a short primer on the basics of functional programming for the imperative programmer coming to newLISP (although this also applies to other Lisps).

What is functional programming?

Functional programming is a programming technique based on lambda calculus that stresses application of functions to data (or other functions) and side-effect-free programming style. This contrasts with imperative programming, the style used in C, Java, PHP, Python (well, sometimes) and others, which emphasizes declarations that change the state of data (known as destructive functions in functional programming).

Immutable state

In an imperative program, a variable is declared, and then the value of that variable is modified to produce the changes desired. For example, in PHP:

$x = 0;
$x++; // x is now equal to 1
$x++; // x is now equal to 1

In this example, $x is a variable, = is an assignment operator (meaning a sort of function that changes the state of the left-hand-side expression, which typically must be a variable of some sort), and ++ is the postfix increment operator (an operator that increases the value of variable by one).

In strict functional programming, the value assigned to x would be immutable. Attempting to change it would cause an error. The only way to represent a value that is based on the value of x would be to use a function that accepts x as a parameter. For example, using Erlang:

n_plus_two(N) -> N + 2.
X = 0.
Y = n_plus_two(X).

Although a bit contrived, this example shows how a new variable must be created if the incremented value of X is to be stored. However, in many cases, storing a variable is not necessary. Often, temporary storage inside a local variable (such as a let expression or function scope) is all that is necessary.

Application of functions

Functional languages are often expression-based. This means that everything is an expression, as opposed to imperative languages in which expressions are typically permitted only on the right-hand side of an operator. In functional programming, functions are applied to their arguments. For example, the following expressions produce the same result in newLISP:

(+ 1 2 3 4 5) ; => 15
(apply + '(1 2 3 4 5) ; => 15

In fact, what apply is actually doing is breaking down the list into smaller chunks and applying the function, +, to each set:

(+ (+ (+ (+ 1 2) 3) 4) 5)

Another useful function is map. Map applies a function to all elements in a list. Lambdas are extremely helpful when mapping to a list. For example:

(map (fn (n) (+ 1 n)) '(1 2 3 4 5)) ; => '(2 3 4 5 6)

Applicative programming is helpful for collecting and filtering from lists as well. The newLISP function filter removes all elements from a list for which the passed function does not evaluate non-nil.

(filter (fn (n) (string? n)) '(1 2 "three" "four" 5)) ; => ("three" "four")

Currying / partial applications

Another handy technique common to functional languages is currying. Curry is a function that returns a function (or a higher order function, as it is known in functional languages). In many functional languages, currying is built in. Here is an example in OCaml:

let add_numbers x y = x + y;;
let increment_by_ten = add_numbers 10;;
let x = increment_by_ten 5;; (* => 15 *)

In this example, the function add_numbers takes two numeric arguments (in OCaml, they must specifically be integers). increment_by_ten takes the function, add_numbers, and associates the first argument with 10. The function returned by this currying operation looks like this:

let increment_by_ten 10 y = 10 + y;;

This is called implicit currying, or partial application. In languages like newLISP, currying is a function:

(define (add-numbers x y) (+ x y))
(set 'increment-by-ten (curry add-numbers 10))

Recursion

Recursion is another technique commonly used in functional programming. A recursive function calls itself. This is the equivalent of a loop in an imperative language (arguments about efficiency aside). To add a series of numbers using imperative syntax, iteration would be necessary. For example, in Python:

def sum(*args):
  n = 0
  for x in args:
    n = n + x
  return n
sum(1,2,3,4,5) # => 15

Here is an example in newLISP of a sum function that uses recursion to add a list of arguments:

(define (sum list-of-ints)
  (cond
    ((null? list-of-ints) 0)
    (true (+ (first list-of-ints) (sum (rest list-of-ints))))))
(sum '(1 2 3 4 5)) ; => 15

The important thing to remember with recursion is that each application of the function must test its arguments. For example, if a function applies itself to every argument in a list, it needs to test the list for length with every recursion (the cond, (null? list-of-ints), in the example). This is called the base case. The base case stops the function from an infinite loop by defining the conditions under which the function stops. Recursion is a powerful and elegant technique that can seriously reduce the amount of code it takes to create an outcome.

To get a better hold on these concepts, here are some concrete examples. First, we will show the imperative solution, then we will show how to implement the same result using functional techniques.

Growing a string

This is a common task in scripting languages, especially web programming and database operations. Let’s build a simple SQL query using the global constant, ‘table’ and a list of strings, ‘fields’.

PHP:

$table = "address_book";
$fields = array("id", "first_name", "last_name", "phone", "email");
$sql = "SELECT";
foreach ($fields as $i => $field)
{
  $sql = $sql . "`$table`.`$field`";
  if ($i < count($fields))
  {
    $sql = $sql . ", ";
  }
}
$sql = $sql . " FROM $table";

newLISP:
<

(let ((table "address_book")
   (fields '("id" "first_name" "last_name" "phone" "email")))
  (format "SELECT %s FROM %s"
    (join (map (fn (field) (format "`%s`.`%s`" table field)) fields) ", ")
    table))

Formatted output from a list

We want to build an HTML table from the results of the query we just formed. We have the data in an array (using mysql_fetch_array() in PHP, for example), $results.

PHP:

echo "";foreach($fieldsas$field){echo"";}echo"";foreach($resultsas$row){echo"";foreach($rowas$value){echo"";}}echo"

   

   
$field

 
   

   

     
  
     
{$value}
  

 
";

newLISP:

(let ((row-format (curry format "%s"))
      (field-format (curry format "%s"))
      (value-format (curry format "%s")))
     (println (format
       "%s%s"
       (row-format (join (map field-format fields)))
       (join
         (map row-format
           (map join
             (map (curry map value-format) results)))))))

Notice the currying of map to the already-curried value-format in the second example.

Common pitfalls

Infinite recursion

Always remember the base case in recursive functions. There has to be a stopping point!

Efficiency

In functional languages, functions are first class objects that can be manipulated, curried, returned from other functions and passed as arguments to other functions. Because calling a user-defined function incurs a certain amount of overhead, using a lambda with a function such as map can create efficiency issues. The cost of applying a first class object over and over is typically higher than that of an imperative loop.

Different languages have different solutions to this. Many functional languages (in particular, Schemes and MLs) optimize tail recursion (this is recursion where the final action of a function is the recursive call) by converting it into a loop in the lower level language. newLISP does not do this. Instead, it offers iterative expressions (such as for, while, dolist, et al) that avoid the problem altogether, since imperative loops can be used in almost all tail recursions.

Expressiveness

Map is a very expressive function.
(map println '("Hello" "world")) is certainly more expressive than foreach ($words as $word) { echo $word . "\n"; }. However, in deeply nested lists, mapping a function deeply can create difficult-to-read code. In these situations, it is better to create either locally curried function definitions or use an imperative control structure instead.

Remember the mantra: expressive, efficient, elegant, then idiomatic.