Functional Programming on a TI NSpire CX CAS

Functional programming is cool. I like functional programming. I can write out programs as equations and somehow my computer makes sense of it. Some people call some programming executable mathematics, which makes me feel like I'm doing complicated number processing.

Unfortunately, you can't always use your favourite tool all the time. In exams, you'd probably get more than a few frowns for taking GHC or MIT/GNU Scheme to your cardboard-walled cell for nearly two hours. Therefore, it'd be much nicer to get the really important features of your favourite language on the calculator. These are map and filter for me, but you might disagree. It's very easy to write equations and functions the way you would on your favourite REPL after defining a few primitives in an alien language.

This post targets the TI-Nspire CX CAS, but any calculator with conditionals and function definitions will suffice. I'll also show Scheme and Haskell equivalents of any interesting functions used.

The CAS for Functional Programmers

The CAS, unsurprisingly, is designed to make defining functions and using them as math-y as possible. Here's a definition of a function:
f(x) = x × x
Should a function need to span several lines, the end result becomes terrible:
Define f(x) = Func
If evenp(x) Then
  Return x/2
Else
  Return 2 × x + 1
EndIf
EndFunc
This approach screams BASIC to me. (At least I don't need MathJax to typeset it, nonetheless.)

Here's an application:
f(5) (→ 25)
A few typographic conventions will be seen in this document. Variables will be in italics , user-defined functions will be in bold , results will be in gray with parentheses, and all CAS definitions will be in blocks with serif text:
love(fire) = building(on, fire) (→ 1977.2)
Being able to join lists is important in functional programming. Haskell uses a : b , where the item a is being placed in front of the list b. Scheme uses (cons a b) . The CAS does not expose its lists as linked, so we must resort to slow list joins, like [a] ++ b and (append (list a) b) . This is written as:
augment({a}, b)

apply

The first important function is apply , which can be defined as:
apply(f, x) = f(x)
If only that would work on my calculator. It doesn't support first-class functions, where you can pass a definition as a variable. There is a hack to achieve what we want though, which is using expr(). It's not pretty, but it does work. Here's the function in action:
apply(f, x) = expr(f)
The function (f) has to be passed in as a string in terms of x, such as "x / 3" which works well enough. x is bound to our variable, so x is substituted automagically. We won't need to touch this function very much after defining the higher order functions.

first

Our "first" function will return the first of a list, and will be equivalent to Haskell's head function, and Scheme's car (1) function. This is the simplest function to write, and is defined as:
first(l) = l[1]
This only works for lists, which are written as {item1, item2, item3, ...} in the CAS. Matrix support is an excercise to the reader, or can be examined further with the downloadable CAS file at the end of this document.

(1) The odd names car and cdr are supposedly remnants of the IBM mainframes Lisps were originally written on. Scheme should have adopted the first/rest notation usable in Common Lisp, and presented here.

rest

The other function necessary for recursion is "rest". This returns the rest of a list, and is equivalent to Haskell's tail , and Scheme's cdr . This needs some more work to implement, as lists are presented as a whole entity, and not linked items. The CAS uses a similar solution to Python's list comprehensions:
rest(l) = seq(l[x], x, 2, dim(l))
seq tells the CAS to evaluate the first argument (l[x]) for each value of the second argument (x) bound from the third (2) to the fourth (dim(l)). dim gets the length of a list. The CAS is one-indexed, by the way.

nullp

nullp checks if a list is empty, like Haskell's null or Scheme's null? . (The CAS doesn't support question marks in names, so we settle for "nullp" like the Common Lisp function.) We've already seen dim in action, and we can use it to check emptiness.
nullp(l) = (dim(l) = 0)

map

Finally, a worthwhile function! The canonical way to write map in Haskell is:

map' f [] = []
map' f (x:xs) = f x : map' f xs

The Scheme way may be more familiar: 
(define (map* f x)
  (cond
    ((null? x) '())
    (else       (cons (f (car x)) (map* f (cdr x))))))
This can be read as "if the list is null, return an empty list, otherwise join the first item passed through the function with the mapping of the rest of the list."

Our map will be our first function with conditionals. Here goes.
Define map(f,l)=
Func
If nullp(l) Then
  Return l
Else
  Return augment({apply(f,first(l))}, map(f, rest(l)))
EndIf
EndFunc
Welcome to CAS programming. It's awful.

This is a simple recursive function. It can be run like:
map("3 × x", {1, 2, 3}) (→ {3, 6, 9})
Let's step through this. The first thing the CAS does is check if our list is empty. It's not, so let's move to the Else clause:
Return augment({apply(f, first(l))}, map(f, rest(l)))
Yuck. Let's start with the first argument to augment. We're making a list from the result of applying f to the first item of l. Let's substitute that in.
Return augment({apply("3 × x", 1)}, map(f, rest(l)))
Using our logic for apply, we can also evaluate that side.
Return augment({3}, map(f, rest(l)))
The second argument is simpler.
Return augment({3}, map("3 × x", {2, 3}))
Now, we can continue with the rest of the applications, remembering when the list is empty.
Return augment({3}, augment({6}, map("3 × x", {3})))

Return augment({3}, augment({6}, augment({9}, map("3 × x", {}))))

Return augment({3}, augment({6}, augment({9}, {})))

Return {3,6,9}
Almost all functional programming can be analysed through this method. Our function's only weakness is its many calls to augment and itself. The CAS only supports 256 recursive calls, so presumably it will fail after 254 items have been processed.

filter

filter works similarly to map, but checks all its items against a "predicate" function. Only truthy items are returned. In Haskell, its application looks like:

filter even [1, 2, 3, 4] (→ [2, 4])

This is similar in Scheme:

(filter even? '(1 2 3 4) (→ (2 4))

This has the same messiness as map when written in CAS speak, unfortunately:
Define filter(p, l)=
Func
If nullp(l) Then
  Return l
ElseIf apply(p, first(l)) Then
  Return augment({first(l)}, filter(p, rest(l)))
Else
  Return filter(p, rest(l))
EndIf
EndFunc
This function doesn't return the applied values, and doesn't add items to the list when the predicate is false. You should be able to analyse a call like this now:
filter("mod(x,2)", {1, 2, 3, 4})