{"id":354,"date":"2007-03-20T17:00:02","date_gmt":"2007-03-20T17:00:02","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/03\/20\/backuss-idea-of-functional-programming\/"},"modified":"2007-03-20T17:00:02","modified_gmt":"2007-03-20T17:00:02","slug":"backuss-idea-of-functional-programming","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/03\/20\/backuss-idea-of-functional-programming\/","title":{"rendered":"Backus's Idea of Functional Programming"},"content":{"rendered":"

In my earlier post about John Backus, I promised to write something about his later work on
\nfunctional programming languages. While I was in a doctors office getting treated for an awful
\ncough, I re-read his 1977 Turing Award Lecture<\/a>. Even 30 years later, it remains a fascinating read,
\nand far from being dated, it’s positively astonishingly to see both how far-sighted Backus was, and how little progress we’ve actually made.<\/p>\n

<\/p>\n

Backus started from a pretty solid perspective. Almost all of the common programming
\nlanguages that we see – ranging from Backus’s own 1950s version of Fortran, to the most modern languages we see widely used today (Java\/C\/C++), to the various languages that have been proposed as alternatives to those (Modula-3, Oberon, Ada), even to most of the supposedly functional programming languages (Lisp, ML) – all of them are ultimately based quite strongly on the von Neumann model of computing.<\/p>\n

The von Neumann model of the computer consists of two parts: a processing unit,
\nand a state, connected by a tube. The processing unit can do all sorts of mathematical operations on little piece of data. But the data lives in the state on the other end of the tube. Computations occur by having the processor pull little pieces of data from the state through the tube, do something to them, and then push them back through the tube, updating the state. If you know how modern computer hardware works, that should sound pretty familiar to you: our computers are basically von Neumann machines: there’s a CPU, and a bunch of memory, and they’re connected by a data channel called a bus. The computation works by fetching things from memory into the CPU, where the CPU does some arithmetic operations on it, and then storing the results back into memory. In terms of programming, von Neumann computing is basically programming in a system with assignment statements.<\/p>\n

According to Backus (and many other people), the problem with assignment statements is
\nthat they divide the programming language into two distinct worlds: the world of functions and algebra; and the world of assignments. That’s the world on the right-hand side of an assignment statement, and everything else<\/em>.<\/p>\n

That division stinks<\/em> for a lot of reasons. Just for a start, it can rob a system of a lot of its clarity; make code far more complex and hard to read; make code far harder to reuse; and make it much harder to build generic code for gluing together computations.<\/p>\n

Backus correctly pointed out that that basic division of code into two universes – statements and expressions – was a source of incredibly complexity in programming languages. What’s sad to realize is that Backus talked – with awe – about the idea of programming languages whose complete specification reached 500 pages. And today, we have programming language standards documents that exceed 2,000 pages.<\/p>\n

The alternative Backus proposed was to adopt a kind of function-oriented programming. In a Backus-style functional language, there are no variables<\/em>. None<\/em>. In fact, in
\nBackus-style functional code, there is no way<\/em> to even name a piece of data. Everything is built from a set of primitive functions, which are put together using a variety of extremely flexible combinators.<\/p>\n

Let’s take a look at a bit of Backus-style FP code, to get a bit o a sense of what that means.<\/p>\n

Suppose we want to compute the inner product (otherwise known as the scalar product) of two vectors.\tHere’s how we’d write that in Python in classical imperative (von-Neumann) style (and without error checks to ensure that the two vectors have matching lengths):<\/p>\n

\ndef innerProduct(a,b):\nsum = 0\nfor i in range(len(a)):\nsum += a[i]*b[i]\nreturn sum\n<\/pre>\n
 The thing that bugged Backus about that is that the real key to what’s going on in an inner product is obscured – the looping, the figuring out the lengths of the arrays, the division of
\nstuff a sequentially iterated assignment statement to generate a result – it really hides the fundamentals of what’s going on.<\/p>\n
 In Backus’s FP, inner product would be written:<\/p>\n
\nDef<\/b> InnerProduct ≡ (\/+)º(α×)ºTranspose\n<\/pre>\n
 The Backus FP implementation is built from the following building blocks:<\/p>\n
    \n
  1.  A function that transposes the two lists, transforming a pair of lists into a list of pairs; so [[1,2,3],[6,5,4]] would become [[1,6],[2,5],[3,4]].<\/li>\n
  2.  A function “+” that adds two integers.<\/li>\n
  3.  A function “×” that multiplies two integers.<\/li>\n
  4.  A combinator “α”, which applies a function to every member of a list. So α×([[1,6],[2,5],[3,4]]) is equivalent to [1×6, 2×5, 3×4]<\/li>\n
  5.  A combinator “\/”, which inserts a binary function between all of the elements of a list. So “\/+([1,2,3,4,5])” is equivalent to “(1+(2+(3+(4+5))))”.<\/li>\n
  6.  A binary combinator º that composes the functions on its left and right. So fºg(x) = f(g(x)).<\/li>\n<\/ol>\n
     What it actually means is: the inner product is the result of adding up the products of corresponding pairs of two vectors. If you carefully look at the FP code, that’s exactly what it says: “Transpose” is a function that returns a list of corresponding pairs; that’s composed with “α×” which will apply × to each pair; so “(α×)ºTranspose” gives a list of the pairwise products of the elements of two lists; and “\/+” will compute the sum of a list of values, so composing that in will give you the sum of the products of the corresponding pairs of two vectors. <\/p>\n
     The problem with FP is that it’s just totally illegible in textual form. People stink<\/em> at thinking about these kinds of function composition. or example, here’s matrix multiply – which is really a pretty simple piece of code – written in FP:<\/p>\n
    \nDef<\/b> MatrixMultiply ≡ (ααInnerProduct)º(αdistl)ºdistr;º[1,Transposeº2]\n<\/pre>\n
     That’s mostly elements from that I’ve already explained. The pieces that are new are:<\/p>\n
      \n
    1.  “distl” is an operation that does a distribution of an operator from left to right; “distr” distributes from right to left.<\/li>\n
    2.  “1” and “2” are primitive functions that select the 1st and 2nd elements from a list.<\/li>\n
    3. “[]” is a combinator which turns two separate functions into a single function that returns a list of two elements.<\/li>\n<\/ol>\n
       So now you’ve seen all the building blocks that make it up. And it’s a short program. Can you
      \nfigure out how it works by looking at it? It took me a while to work my way through it, and figure
      \nout how to it works. It’s not<\/em> easy. It took me far longer to understand that than
      \nit would take me to figure out a matrix multiple in, say, Fortran.<\/p>\n
       As you can probably see, I’m very skeptical of whether this kind of ultra-pure functional programming is really a good idea. The only thing that makes me think that there might be something to this kind of function stuff is looking at people who program in APL<\/a> and it’s successor, J<\/a>  A huge amount of programming in APL and J are in a style very much like this – and while there’s a hard learning curve, people who program in APL and\/or J are incredibly<\/em> productive.<\/p>\n
       Anyway – from the primitive FP, Backus goes on to propose something called an applicative state transition system<\/em>, or AST. An AST is a system which defines a state, consisting of
      \na set of bindings of names to values. A computation is written in AST as the application of
      \na function to the state; and the result of the application replaces the old state. So a computation becomes a sequence<\/em> of state-to-state function applications.<\/p>\n
       If you’ve been reading my Haskell tutorial, that ought to sound extremely<\/em> familiar. A AST is essentially the same thing as a State monad; an AST with IO is a combined monad – the result of applying the IO monad transformer to the State monad. 30 years ago, Backus basically told us what the solution to the problems of IO and State in a functional language would be! And 20 years after he told us the solution, someone went to a lot of trouble to independently reinvent what Backus told us.<\/p>\n
       If you’re interested in trying it out, there’s are implementation of Backus’s FP here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
      In my earlier post about John Backus, I promised to write something about his later work on functional programming languages. While I was in a doctors office getting treated for an awful cough, I re-read his 1977 Turing Award Lecture. Even 30 years later, it remains a fascinating read, and far from being dated, it’s […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[54],"tags":[],"class_list":["post-354","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-5I","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/354","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=354"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/354\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=354"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}