jra's thoughts

Back to school

—

by

jra
in

I was sick last week, and in my drug- and virus-induced haze of incoherence, the idea that I should write a Scheme interpreter in assembly language came to mind. I cannot explain from where, but there it was. So I started looking into it, wondering if I still had it in me to dig into a computer problem and get it done. I’ve been feeling a bit burned out on different aspects of the IT world, and I was thinking maybe that getting back to the basics of computer science might help. The course that I remember mostly vividly (not fondly: vividly, like in nightmares) was my Programming Languages class, where I wrote a Scheme interpreter in (wait for it, wait for it…) Scheme. It was hard, really hard. But I was also young and stupid. I don’t think it would be so hard now.

I suspect another idea was floating in my mind, which came from this article. Functional Programming is part of the solution to the multi-core problem, which is the most pressing problem facing computer science to ensure continued growth in computer capabilities. Things written the functional way self-decompose into parallelizable threads of execution, which is good in a future where lots of small processors are available instead of a few huge ones.  It’s an open question if “continued growth in computer capabilities” is really a useful thing. My work with Entuura argues, “no, smaller embedded devices will deliver more social good”. But better to plant mango stones in all types of soil anyway.

So I started looking into what it would take write a Scheme interpreter in assembly and ran across An Incremental Approach to Compiler Construction [PDF]. Which is something else entirely, a guided tour into the world of compilers, where you write a compiler for Scheme in Scheme, resulting in native x86 code that evaluates Scheme expressions. Since I never actually did a compiler class, this was even better. It would scratch my itch to get back into functional programming, as well as taking me on a guided dip into the waters of assembly, but letting me program my assembly in Scheme, which I prefer anyway.

I’ve completed chapters 1 and 2 of the tutorial. This is my way of publically stating that I’ll make it through the rest of the chapters. Feel free to poke me later and ask how it went!

Comments

2 responses to “Back to school”

  1. snout.org-openid Avatar
    snout.org-openid

    Well, it’s been… seven hours. Are you done yet? I’ve got a bunch of code monkeys here who need to write a Facebook app in Scheme before the inauguration tomorrow. 🙂

    Reply
  2. jra Avatar
    jra

    As long as you only need immediates, unary operators, and if/and/or, I’ve got you covered. God help you if you need primitives that take more than one arg, statically defined constants, or lambdas.

    This is why I love Scheme… (and a b) is defined in Scheme as “if a then b else #f”. The definition scales up and down from 0 to n arguments. So, if you have “if” implemented in your compiler, you are one subroutine away from having “and” implemented. The subroutine takes as input the expression with and at the front, and creates as output a new expression using the definition of “and”. The output expression now starts with “if”, and has no and’s in it anymore. Then you pass that expression to your existing compiler for if-expressions, and you’re done.

    To whit:

    (define (transform-and expr)
    (cond
    ; basis cases: (and) => #t, (and test) => test
    [ (null? (cdr expr)) #t ]
    [ (null? (cddr expr)) (cadr expr) ]
    ; recursion case: reduce (and a b…) to (if a b #f)
    [ else (let ([test (cadr expr)] [test-rest (cddr expr)])
    (list ‘if test (transform-and (cons ‘and test-rest)) #f)) ]))

    One of the things I forgot about functional programming is that it’s frustrating until you get it and then it’s a very intense “I got it” feeling. What’s interesting about recursive programs is that they are completely wrong until they are completely right, and when they are right, they are really, really right.

    Another interesting thing I’m learning is about the emotional side of programming and how test-driven coding works with the built-in behavior of our minds. As an intensely mental activity, programming productivity and work enjoyment is all about saying in the flow. If you can manage your emotional state well, you can keep the flow up. Test-driven coding does that, because when you get the recursive algorithm right, not just the first test starts passing, but they all start passing! That’s a huge ego-stroke, and it gives you the energy to go take on the next ones.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *