Borges, Haskell, Euler

In one of my favorite Borges stories, he describes the imaginary people of Tlön who speak a language that has no nouns.  They have only impersonal verbs, adverbs, and prepositions.  Instead of saying, 'The moon rose above the river,' they would say something like, 'Upward, behind the onstreaming it mooned.'  The story explores the ways in which language shapes what we do and how we think.  Borges writes, 'For the people of Tlön, the world is not an amalgam of objects in space; it is a heterogeneous series of independent acts.'  This raises the question: how would your life be different if you didn't have a word for 'you' or 'I'?

You don't have to merely ponder this if you learn a functional language like Haskell (named after mathematician Haskell Curry).  I've taken a deep dive into Haskell, though I still feel like one of the early explorers trying to understand Tlön.  If you're used to thinking in terms of 'objects in space'--that is, if you mostly work in object-oriented languages--Haskell is very weird at first.  You'll have to start thinking in terms of functions.  Even basic units, like the number 5, are really functions that return the value 5 and which can then be passed to other functions.

Check out this implementation of the Quicksort algorithm, taken from Miran Lipovača's awesomely-named book Learn You a Haskell for Great Good!:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

This code declares a function quicksort, which takes a list and returns a list of things that can be ordered.  It recursively calls itself, so the base case is an empty list.  It grabs the first item from the list and uses it as the pivot to generate two other lists of all items greater and smaller that it.  Then it concatenates and returns the sorted sublists.  Voila!

You might wonder why it's useful to learn a language like Haskell.  I personally haven't seen any production Haskell code, though you can find some cases of it.  I wanted to learn Haskell because it is a purely functional language, and I thought it would help me better understand some of the ways functional programming is creeping into OOP.  For example, Java 8 will have closures, the Clojure language is gaining popularity, and C# makes heavy use of lambdas and extension methods in LINQ.

I have also heard that learning Haskell will make you a better programmer.  I do think it's hard to really know any language unless you know what else is out there, just like I think it's a bad idea to maintain a belief in something if you don't consider other beliefs, whether it's politics, religion, or anything else where reasonable people disagree.  However, I'm not sure what Haskell or other functional languages teach besides recursion.  You really have to be comfortable with recursion to do any amount of functional programming.  For example, you could write a function to check if a list or string of characters is a palindrome in the following way:

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome ([]) = True
isPalindrome ([x]) = True
isPalindrome (x:y) = 
    if x == z && isPalindrome w then True else False
    where z = last y
          w = init y

Haskell is great for problems where you can break a task into a series of mathematical equivalences.  It's hard for me to imagine trying to solve Project Euler problems without Haskell.  I've done about 25 of these for practice, and I highly recommend poking around in them.  Problem 20, for example, asks you to sum the digits of 100!.  This can be done in one line of Haskell.  Problem 9, which asks you to find a Pythagorean triangle where a + b + c = 1000, can also be done in one line.  First you generate three lists of numbers (a, b, and c) from 1 to 500 or so.  Then you get a list where a² + b² = c².  Then you get a list where a + b + c = 1000.  Finally, you filter out all the items where a < b < c to get a unique tuple. 

I've written before that you have to be careful with functional languages because they abstract away the implementation from the code.  In the Pythagorean example above, for example, you do not have to write a series of for loops.  It's easy to write code that will take days or years to finish in Haskell.  I speak from experience.  (For fun, try running last [1..]).   But this kind of abstraction can be beneficial, as the logical nature of Haskell highlights the logic of your thought process.  One of the most important things I've learned in working with Haskell, especially on problems dealing with huge numbers, is just how important it is to have a good algorithm.  Because Haskell programming is nothing but functional logic, it's easy to concentrate on the essentials.

Gödel, Kuhn, and Human/Computer Co-evolution

Kurt Gödel showed that all formal systems are incomplete, meaning that there are truths that can be stated within a system that cannot be demonstrated within it. This means that truth cannot be reducible to axiomatic principles and, therefore, that there is no single system to which all truths could be reduced, whether it be physics, mathematics, logic, or any other system of abstraction.

These principles have become widely accepted within mathematical and scientific communities. After Thomas Kuhn's Structure of Scientific Revolutions, it has become common to think of domains of knowledge as paradigms which are never proven or disproven but which are eventually abandoned in favor of new, more helpful, or more interesting paradigms. What makes a paradigm valuable cannot be shown within the paradigm itself but by the problems it helps solve or the vistas it allows.

I've been trying to think through the implications of these insights for technology ever since reading Douglas Hofstadter's Gödel, Escher, Bach. As I understand it, the book's main point is that any attempts to create artificially intelligent systems that are grounded solely in deductive logic are doomed to failure. Human thought involves deduction, but it involves much more. As Hofstadter writes in his introduction to Ernest Nagel and James Newman's Gödel's Proof, the goal of AI research should be to devise systems "guided by visual imagery, the associative patterns linking concepts, and the intuitive processes of guesswork, analogy, and esthetic choice that every [person] uses."

The kind of AI we are most familiar with is Google. It is probably a stretch to say that the Google engine thinks, but it is certain that the algorithms it uses to filter and aggregate trillions of bits of information are guided by analogies and associations if not esthetic choice. Google gets feedback from users in the form of click-throughs, so it can better predict what sites to show in the future. Feedback loops like this are at the center of thought and learning. The more the Google engine can modify itself instead of relying on engineers to tweak algorithms, the more it can be said to think.

But the computer side of this loop is only one half of the picture. Just as computer systems learn from us, we learn from the systems. It's a dynamic, co-evolutionary process, and we need to think about the kinds of choices that computers make available to us. Eli Parser has coined the term 'filter bubbles' to describe the ways that applications like Google and Facebook filter information for us and thus structure the choices we make. This is not necessarily a bad thing, since we desperately need ways of filtering out information that is not relevant to our purposes. However, it will be a co-evolution that requires careful attention, for, unlike the bee and the flower, we can control our collective destiny.

This brings me back to Kuhn, since he suggests that the terms we currently use to think about our co-evolution are not necessarily the best for the job. One of the interesting things about computing is the way its concepts and language have been used to understand other things. Metaphors from other walks of life permeate computing, like 'the cloud', 'friend', or 'stream', but computing has also shaped the ways we understand each other and the world. It's not simply a matter of words like 'Google', 'text', and 'filter' becoming commonplace, because everything is either a computer or something to be computed today. For example, it's hard not to think of human minds (or 'wetware') along computational lines now. Not only do we 'process data' and 'filter out noise', but we act on information that has been computed so that we can better operate computers. Commercials tell us that our very personhood is threatened if our personal data are lost.

I wonder if we're seeing the waning of a paradigm, or the waxing of a new one. Will the next years of computing see more of the same, only faster? Or will we come to understand thought, action, art, ethics, and even humanity in an entirely different, techno-saturated vein? Are computers just machines (with which have have been long familiar--we are eating machines, sex machines, and poop machines). Or are they something different?

Links:
-Jaron Lanier's You Are Not A Gadget