25 January 2012

Yep, Programming Is Borked

I recently read “I want to fix programming”, which touches on one of the fundamental problems with programming as we know it. I agree with the author, but I think many of the commenters failed to understand the issue, so I’d like to present it in another way.

I’ve been programming for a long time, mostly because I’m addicted to solving puzzles. I’m very much into programming languages, partly because as a programmer I’m surrounded by them, but also because language is an important part of what makes us human.

So while programming is a craft I enjoy, and I love having the power to create awesome stuff practically ex nihilo, I too am disappointed in what we have to work with. Here’s why.

Process-Oriented versus Result-Oriented Programming

Concatenative, functional, object-oriented, logic—whatever paradigm you choose, they all have the same issue: they require that you describe the how rather than the what. In any language you can name, a program is a description of the process by which you compute what you want, when it could be just a description of what you want. Sure, some languages are more declarative than others, but this is orthogonal to the issue of “declarative versus imperative”—a language that expresses a process declaratively is still process-oriented, not result-oriented.

That’s the real issue. As programmers, we solve problems using code. Even a fun problem like “a game like this should exist but doesn’t” is valid. So we should be able to express our code in terms of its intended result, not the process by which that result is attained.

The author proposes a style of programming based on constraint satisfaction. From a set of constraints, it’s possible to derive an algorithm that meets them. Of course, we naturally worry about the properties of the algorithm the compiler will derive; is it Θ(n!) when it could be Θ(n log n)? But while that is a reasonable worry, it is not—strictly speaking—relevant.

See, there are many equivalent sets of constraints that define a particular algorithm, and by selecting intelligently from those, we can be confident that the compiler will derive what we intend. Our job should be to intelligently express requirements as formal constraints for the compiler to satisfy.

I know that sounds boring, and I was initially skeptical that useful programs could be made this way. But think about it: every non-trivial program already is implemented this way, just in a slow, error-prone, manual fashion. A programmer takes some requirements, formalises them, then painstakingly translates them into a suitable process. We can avoid one of those steps.

A Realistic Example

Say you’re writing a game. The first thing on your to-do list is to be able to move a character around the screen with the arrow keys. In just about any existing language, you have to construct a bunch of unrelated infrastructure to make this happen:
  • Transforming continuous physics into a discrete representation
  • Dealing with issues of frame rates, rendering, and collision
  • Managing the state and resources of living and dead objects
All of this crap is unrelated to just making something that works.

Often, much of this work has already been done for you by a library author, but the fact remains that someone had to do the busywork. Functional reactive programming, in contrast, gets this right. You can say precisely what you mean:
  • The character consists of:
    • Acceleration of ( ax , ay )
    • Velocity of ( vx , vy )
    • Position at ( x, y )
    • Sprite of size ( w, h )
  • When an arrow key is pressed, change the acceleration:
    • Left: ( ‒1, 0 )
    • Right: ( +1, 0 )
    • Up: ( 0, ‒1 )
    • Down: ( 0, +1 )
  • Integrate over time:
    • Velocity from acceleration
    • Position from velocity
  • The colour of a pixel at ( px , py ) is:
    • If ( px , py ) is within the sprite ( x, y, x + w, y + h ):
      • The colour of the pixel at ( pxx, pyy ) in the sprite
    • Otherwise:
      • The background colour

This is a complete, fully declarative, fully result-oriented description of the program. It contains only those details that are relevant to the problem at hand, and every detail is expressed as a constraint that can be plugged directly into an FRP system—which is really a simple constraint solver—to derive the runtime behaviour.

And Whither Hence?

Prolog serves as an example of constraint-based programming, and Haskell FRP libraries are nice, but these are basically just toys compared to what we can do.

There is no reason we cannot make a better, more result-oriented language, or even just make existing process-oriented languages look more result-oriented to get some momentum for the paradigm. Take a look at Swym (“Say What You Mean”), where the etc keyword lets you do things like this:

List.byPairs: [[.1st, .2nd], [.3rd, .4th], etc];
byPairs[1..10] == [[1,2],[3,4],[5,6],[7,8],[9,10]];

Which even does something sane when you give it a different number of arguments:

[1,2,3].byPairs == [[1,2]];
[1,2].byPairs == [[1,2]];
[1].byPairs == [];

This is really exciting stuff, but it shouldn’t have to be, and we can do even better. The implementation of a few “magic” operators like etc and each could make even an imperative language look much more result-oriented.

For a while, I was working on a language called Prog. It was to be an imperative language for generic programming, with dependent typing. Many of the magic was implemented with “radioactive types”, unstable types that could exist only during evaluation, which decayed into ordinary types thereafter. These were used, for instance, to implement various query operators on iterable structures:

which (1..10) > 5 == (6, 7, 8, 9, 10);
every (1..5) ** 2 == (1, 4, 9, 16, 25);
every (1..3) * every (1..3) == ((1,2,3), (2,4,6), (3,6,9));

After reading that article and the comments, I’m inspired to work on Prog again, if I can find the time. Expect to see more blarticles about it. A project in the same vein that’s consuming a lot of my energy right now is a tool to help non-programmers make professional-quality interactive media. If you don’t know how to program, you have limited means of creating games and other media applications. All the authoring software that’s out there falls into two categories:
  • Tragically underpowered
  • Needlessly complicated
So, using research into how people best solve problems, I’m making a tool that helps people solve the problem of having an idea and not being able to make it a reality. At the end of the day, that’s a frustration that a lot of programmers face. If as a programmer you feel inspired to contribute, please contact me at evincarofautumn@gmail.com, and I’ll let you know how you can get involved.

21 comments:

  1. The examples given of prog remind me quite a bit of lisp's map and filter functionalities.

    The first example is a filter with the predicate > 5 while the last two are maps (mapcar ...).

    I'm not saying lisp is as declarative as prog I'm just wondering if you could provide more examples to illustrate the differences.

    Cheers,
    green7ea

    ReplyDelete
    Replies
    1. Well, declarativeness is not the point. It’s about intent and results, as opposed to process. Filters, maps, folds, and such are all standard functional programming tools that are available in any functional language. They are very descriptive because they closely match a lot of problems.

      This is largely unrelated to the contents of the article, but the main difference between the Prog examples and their Lisp or Haskell equivalents is that they work on any iterable structure, not just lists. In general, “Predicate(where Iterable)” evaluates to a structure of the same type as “Iterable”, containing only those elements “Element” of “Iterable” for which “Predicate(Element)” returns “true”. And this filtering is lazy, so there is O(1) space overhead unless you copy the result. The case of “where Iterable > 5” is just a generalisation where “>” is treated as a function.

      I’ll be adding more information about further development of Prog in future posts, so be sure to bookmark me if you’re interested. :)

      Delete
    2. You underestimate Haskell. map, foldr, filter - these work on lists by historical accident and convenience. They all have generalized versions which operate on any data structure satisfying their laws - fmap and the Functor typeclass, foldr and Foldable, mfilter and MonadPlus, etc.

      Delete
    3. As gwern alludes to, what you are thinking about has been thought about for a long time and quite deeply in Programming Language research. That research has been waiting for computers to become powerful enough that problems become deep enough that production programmers want that research.
      Here's an implementation of your 'which' and 'every' in Racket Scheme. See also their "Comprehensions" library. BTW, I can make it more infixy, and add precedence, but this version has the advantage of actually being usable [as opposed to ones that people only wish they had because they haven't had the time to write the parser] in a full-featured language with a rich set of libraries.

      #lang racket

      ; Print that shows streams as lists.
      (define (show a) (displayln (if (stream? a) (stream->list a) a)))

      ; Range stream that's inclusive of end value.
      (define (.. m M) (in-range m (+ M 1)))

      ; Implementation of 'which'.
      ; The "..." is NOT missing code: it's like "etc" mentioned above.
      (define-syntax-rule (which «stream» «f» «arg» ...)
      (let ([constant-args (list «arg» ...)])
      (stream-filter (λ (e) (apply «f» e constant-args)) «stream»)))

      ; Displays: (6 8 10).
      (show (which (which (.. 1 10) > 5) even?))

      ; Implementation of an 'every' ---exact semantics to be decided.
      (define-syntax every
      (syntax-rules ()
      [(every «stream»)
      (stream->list «stream»)]
      [(every «stream» «op» «arg/list»)
      (let ([arg/list «arg/list»])
      (stream-map
      (if (list? arg/list)
      (λ (e) (map (λ (arg) («op» e arg)) arg/list))
      (λ (e) («op» e arg/list)))
      «stream»))]))

      (define ** expt)
      (show (every (.. 1 5) ** 2)) ; (1 4 9 16 25)
      (show (every (.. 1 3) * (every (.. 1 3)))) ; ((1 2 3) (2 4 6) (3 6 9))

      Delete
  2. "Blarticles"... that one word alone almost completely destroys the impression the rest of your well-written and intelligent post created.

    ReplyDelete
    Replies
    1. I’m one of those seemingly urbane, sophisticated, no-nonsense writers who also just enjoys fucking with people.

      Delete
    2. What is it with these aneologist fuckleberries?

      "Waily, waily wail! You made up a word and created a context for its use. I don't understand or like this so therefore you must be wrong."

      Personally I liked your blarticle and have been discussing similar ideas with a mate of mine in the context of creating a graphically structured programming language that can be used with a white-board and webcam.

      Delete
  3. Bookmarked. I look forward to future posts.

    ReplyDelete
  4. "The first thing on your to-do list is to be able to move a character around the screen with the arrow keys"

    From where did come these: acceleration, velocity, position. What the hell is sprite? Integrate over time? Pixels?! Pixels in sprite??!! Background of what???!!! Didn't we just want to move our character around the screen?

    It is not programming that is broken but we - programmers. Instead of ruling machines we are becoming ones - unable to switch between different contexts of abstraction.

    This is how typical chat bot "thinks":

    "-Stop changing subject!
    -I thought our love was special.
    -Stop changing subject!
    -I'm not changing the subject.
    -You are! I'm trying to talk about Your inability to understand what we are talking about.
    -No its not even close. my favorite beatles song is across the universe. what is yours?"

    And no - fancy new language won't cut it.

    ReplyDelete
    Replies
    1. Surely you’re being intentionally obtuse. In the game example, those terms are a minimal set of components within the problem domain—the entity of “character” necessarily has a position, velocity, acceleration, and image, because that is literally what we mean when we say it “moves around on the screen”. No more, no less. “Background colour” is also obvious—the screen must have a colour wherever our character is not.

      It’s not at a different level of abstraction at all, and that’s the point: we should be able to compose programs in terms of meaningful behaviours, because that is a level of abstraction that works well for people. We should not have to become machines.

      Delete
  5. Is there a fundamental difference between a sufficiently high-level language, and a declarative description of a program?

    Most of the systems I've worked on, once you get to a certain level of abstraction (and especially if you're working in a language with some kind of syntactic abstraction, like Lisp/Ruby/Tcl), you end up writing code that looks pretty much like a description of the desired solution, even though you didn't necessarily set out to write it in such terms.

    For example, take your simple game example. If you were writing this in assembly in 1985, it would take all month, and your head would be full of bytes and pixels. If you were writing it in C in 1995, it'd be a lot simpler, but still largely procedural. If you were writing it in Javascript on a web browser in 2005, most of the concepts you have are already built-in and invisible to the programmer (e.g., objects that know their position and how to composite themselves on screen). You still need to handle the motion, but there are libraries that do this, too.

    ReplyDelete
    Replies
    1. You could look at it that way. There are a couple of problems with building your way up to high-level abstractions within an existing language. First, you have to do it every time; second, you’re out of luck when those abstractions leak. With a higher-level language, there are some abstractions you can rely on. I’m reluctant to say “declarative” because a high-level language is not necessarily so, and at that point all you’re saying is that high-level languages make for high-level programs, which is true by definition.

      Delete
  6. Aye, but then the algorithm lives: it lurks not in the program itself, but in the compiler or interpreter.

    "What is the tortoise standing on?"
    "It's turtles all the way down."

    ReplyDelete
    Replies
    1. However, the difference is in placing the burden in the compiler/interpreter writers instead of the (larger) set of compiler/interpreter users.

      As a programmer, it's a very appealing idea. My more practical side, though, thinks it's very much like cooking: you can sharpen your knife as much as possible, but you can never avoid chopping.

      Then again, vegetables can't process millions of instructions per second. Yes, as a programmer, it's a very appealing idea.

      Delete
  7. For what it's worth, I thought 'blarticles' was funny. But I also think that you are way off as to why programming is broken. I think the problem is that it's not concrete enough, not that it's too abstract. There is no correct abstraction. There are only systems of abstractions which have different properties, that compete for the same problem space. It is much like the number of coordinate systems a physicist must choose from before attempting to solve a problem.

    ReplyDelete
  8. While fun to think about, I keep hearing this complaint from programmers both experienced and new, every few years. It boggles my mind that you want to feed in a desired result and expect the machine to "just do it". The problem is frustrating. After all, we can just "do" things. The problem inherent in that thought though is this, Humans learn processes. After we learn the processes, they become mindless tasks that we can do without really thinking about.

    Keep in mind, that it took you several years to do virtually everything that you do - from learning to grasp objects, to walking, talking, reading, eventually to get to a point where you are programming a computer.

    While I made this comment on the original inspiration to this post, the inherent problem is that many programmers don't tend to realize that THEY are the fastest computer known (the human brain) In many cases, prior to getting into a career of programming, they've (on average) spent some 20+ years learning and mastering all concepts they know. However, the computer has zero intelligence and is less capable than a newborn baby. Would you expect your newborn kid to be able understand even basic concepts such as "mom" or "dad" let alone being able to just tell the kid to "go grab a bottle from the fridge and feed yourself"

    As extreme as this example may be, it's 100% true. You're expecting to tell a computer "move this character on the screen" you have to first introduce concepts such as moving, characters, screens, etc. Only then will you be able to tell it to do that. Libraries help lay a foundation, however, someone, somewhere, had to introduce this to the computer at some point, otherwise you're doing the exceptionally hard work of actually creating those libraries.

    Only once we have a machine capable of true learning will we be able to tell the machine "get me a beer" and will it be able to translate that to:

    Check fridge
    if (!beer) {
    go_to_beer_purveyor();
    purchase_beer();
    } else {
    grab_beer();
    deliver_beer();
    }

    of course this is simplified and assumes that you have the methods figured out and well documented. But to say that we humans don't think in procedures is to not understand how humans think. We just think very fast and it takes effort to break down our actions into a clear and formally documented procedure.

    ReplyDelete
    Replies
    1. The reason that you keep hearing it may be just that you want to, because I certainly haven’t said it. Sure, I think the way we do programming could be improved, but I don’t expect computers to “just do it”. In this very article I say nothing whatever to suggest we should be able to say “make my character move on the screen”—instead, I offer a solution in an existing paradigm (FRP) that lets us closely model the problem by combining primitive behaviours: positions, rendering, input, and changes over time. All I want is more of that, so my programs look like what they mean.

      Delete
    2. Unfortunately, "combining primitive behaviors" is deus ex machina. In your example you've invented a domain-specific environment that automatically takes care of all the ugly details, and that's what makes it clear. It's pseudo-code. How you specify details may make an order of magnitude difference in effort. What you have to specify dwarfs that.

      For example, here's imperative pseudo-code that uses the same kind of environment:

      mychar = {
          Imaginary accel;
          Imaginary velocity;
          Imaginary position;
          Sprite sprite;
      }

      accelVect = {
          Left => [-1, 0],
          Right => [+1, 0],
          Up => [0,-1],
          Down => [0,+1]
      }

      while (event = NextEvent()) {
          if exists accelVect{event.action} {
              mychar.accel = accelVect{event.action};
              mychar.velocity.integrate(mychar.accel, event.time);
              mychar.position.integrate(mychar.velocity, event.time);
          }

          for (ScreenCoord p in Screen.rect) {
              if p.within(mychar.sprite.globalRect)
                  Screen[p].color = mychar.sprite[p].color;
              else
                  Screen[p].color = BackgroundColor;
          }
      }

      I don't see that as any more complex than what you described. If, on the other hand, the "When" event was not "arrow key is pressed", but "USB communications event", then both FRP and pure procedural would be very, very painful to specify. I suspect the procedural code would be simpler, since the USB protocol has a lot of states.

      Delete
  9. methinks you want something similar to an (automatic) proof assistant (like Coq e.g.)... where you provide a type/specification and the programming environment helps you find a programm/proof that satisfies it.

    is that something along your lines of thought?

    ReplyDelete
  10. I look forward to more blarticles about Prog as it reminds me somewhat of Flapjax:

    http://www.flapjax-lang.org/

    Good luck!

    ReplyDelete
  11. Hmm. the "results-oriented program" you wrote is too detailed and in fact in error. Simply right the program as "move the character in response to the press of an arrow according to the laws of physics under constant acceleration in the direction of the arrow". done. Just write use cases (which specify the what) and your all done. No need for that silly syntax that only a mother can love (but ceratinly not read).

    Of coure, telling it to integrate over time is insufficient- in 0.1 second, 2 second or 10 minute time intervals? Or is the compiler of your pseudo-code to infer something and guess at the context? Integration is done over a singled state of combiner position/velocity via an equation of motion that describes the physics and an integrator of low or high fidelity (you didn't specify -- again is the computer to infer this?) Doing it as you suggest (with too much implementation detail) will probably accumlate error over time and have poor performance (assuming I understand the context of what you want to do correctly).

    Now the interesting part: you haven't specified what happens if two or three arrows are pressed at one time. And did you mean to say "when an arrow key is pressed" or "while an arrow key is pressed". big difference in behavior there actually!

    I am not trying to be facetious here. Software development is more than just programming, it is understanding the intended use of the product, making changes based on continual feedback (in an Agile environment ;-) ), This can be done through more formal requirements or Use Cases or TDD -- so the specification of what really should happen and if you don't do this as a programmer via an imperative language (as you define it), you aren't doing things right. And when you take the (small) amount of time to do this work as in integral part of development, you find your programs are simpler and more understandable. Now can the what and the how be integrated together into one language (like Zed - ack!!) with a smart enough and experienced enough system to infer all the hidden contexts and intentions of the porgrammer and handle all the hidden off-nominal cases? Perhaps, but I have to believe that is just too far away. (Links to show me wrong here would be appreciated!!!!)

    The example you give is also far far too simple an example of a linear progression of logic. It's like showing someone how easy it is to build a 6 inch bridge out of Popsicle sticks and as the question "How hard could it be to build those suspension bridges?". Software involves making engineering/architectural decisions at the start and over the cycle of development. And if you write something to make those decisions for you, I suspect you will be having to make those decisions at a different level or in a different arena, but then you're just pushing the problem around and not solving it.

    Another thought: the more we try to make computers "smarter" by mimicking humans in terms of learning behavior and context to develop "programs", are we making things more error-prone or less? Humans have a profound ability to miscommunicate and misunderstand and yet we muddle through.

    ReplyDelete