Jun 122013
 

I’ve been a huge fan of LISP and related programming languages (scheme, racket, etc.) for a very long time. I’ve been evangelizing the utility of learning how the language works and understanding functional concepts among my friends for almost as long, and recently a friend of mine finally caved and read McCarthy’s original paper. Once he realized how important it was, he decided to learn while solving the L-99, a list of 99 problems for LISP (based on Haskell’s list of 99 problems), except we use Scheme/Racket for our implementations, because of the excellent Dr. Racket environment on both Windows and Linux.

The purpose of the L-99 was to provide a series of challenges that would force someone to learn about the language, its syntax and structure, standard paradigms, etc., which something I think it accomplishes very well. But I think it also provides a great backdrop for discussing algorithms regardless of the language they are written in. L-99 therefore provides two opportunities: the first is learning how to do something in LISP, and the second is learning how to do it “the best way”—the one with the lowest time and/or memory complexities. An example I’d like to mention is the list reversal problem, #5, because it is easy to understand and has two easy solutions with very different characteristics. My friend’s solution (in Racket), which works correctly, is given below:

(define (list-reverse x)
  (cond
    [(null? (cdr x)) x]
    [else (append (list-reverse (cdr x)) (list (car x)))]))

As I mentioned above, his solution works correctly (aside from a little bit of parameter validation that is missing), but a close reading reveals that its time complexity is O(n^2). This is because the append function is O(n), and it is called once per item in the list to reverse. In another language, with another library (say, C++ with STL containers), appending to a list is a constant time operation, which is likely why he didn’t think much of using append here. That said, an opaque list structure can be made (in LISP) that offers constant time append operations, but this isn’t how a chain of cons cells works. For comparison, here is my solution to the problem, which uses a helper function to reverse the list in O(n) time:

(define (list-reverse-linear x)
  (define (lr-inner xa xr)
    (cond
      [(empty? (cdr xa)) (cons (car xa) xr)]
      [else (lr-inner (cdr xa) (cons (car xa) xr))]))
  (cond
    [(not (pair? x)) x]
    [(empty? (cdr x)) x]
    [else (lr-inner (cdr x) (cons (car x) null))]))

I suppose it is obvious to most people that faster asymptotic complexity is always better, but just for the sake of argument, let’s look at the time required for reversing a list with 10,000 elements in it:

; Input
(define (gen-list n)
  (cond
    [(= n 0) null]
    [else (cons n (gen-list (- n 1)))]))
(define tl (gen-list 10000))
(time-apply list-reverse (cons tl null))
(time-apply list-reverse-linear (cons tl null))

; Result is, in milliseconds (cpu real gc)
(3432 3427 2293)
(0 1 0)

A stark contrast—based on a measurement with time-apply, it takes nearly 3.5 seconds to reverse the list using the O(n^2) algorithm, but less than one millisecond to do so with the O(n) algorithm. A big part of this, of course, also comes from the garbage collection time, which accounts for nearly 2/3 of the run time in the slower algorithm, due to how many intermediate lists are generated and discarded, while the linear algorithm does not allocate any unused items. Another important difference is that my solution is tail-recursive, which enables significant optimizations (ones that Dr. Racket is capable of doing, too), compared to my friend’s solution.

I think that the L-99 has a wonderful secondary purpose. Not only can it be used to introduce someone to the standard idioms, tools, and techniques of functional programming, but it can also be used to introduce and discuss analysis of algorithms, as the problems can generally be solved in multiple ways, with different time and space complexity requirements. It even provides a platform to discuss different implementation strategies (such tail-recursion vs. not) and experiment with their effects on performance, all with problems and solutions that are very simple to state and understand. This is a great aspect of LISP as a tool for learning in general—it frees you as a programmer from worrying about necessary but conceptually irrelevant implementation details, to focus on understanding what you’re doing, why you’re doing it, and how you’re doing it, on an algorithmic level. Mastering the relevant skills translates readily into using other languages, where it helps separate the problems—algorithms, memory management, program structure, inheritance organization, the list goes on—out in your mind, allowing you to solve each individually.

Normally I’d write another 3+ pages, at minimum, trying to beat this to death, but I think this is a pretty self-defending position. Instead, I’d like to ask you a few questions to think about and maybe take with you as you do or learn about programming. Have you ever looked at the L-99? Can you solve all the problems, even if you don’t take the time to write out complete solutions? Are your solutions optimal in their asymptotic complexities? I’d also love to hear about any particularly clever solutions people have created.

Nov 152012
 

While discussing game scripting languages with a friend, I asserted that a Lisp-based language such as Scheme or Racket would form a very effective in-game scripting language due to its expressive power and flexibility, as well as the efficiency with which modern, JIT-capable implementations execute code. One of the most widely used scripting languages for this purpose appears to be Lua which is pretty small and designed to be embedded in C programs. I glanced over the feature list on Wikipedia and saw that it was basically a subset of Scheme with some omissions and a few additions. In particular, I really liked the idea of a metatable, which effectively automatically handled function memoization.

The example given on Wikipedia is a metatable-based function to calculate the nth Fibonacci number, a classic example of a simple recursive expression that has exponential time complexity for a naïve implementation, but can be improved to linear time (or, depending on the usage scenario, amortized constant time, for sufficient reuse) with a memoization table. The Lua for this is given (available under the Creative Commons Attribution-ShareAlike license from Wikipedia) as:

fibs = { 1, 1 }
setmetatable(fibs, {
  __index = function(name, n)
    name[n] = name[n - 1] + name[n - 2]
    return name[n]
  end
})

I didn’t recall seeing a Scheme or Racket built-in to provide the same functionality, but I was confident that it would be easy to implement such a language feature using standard Racket built-ins, such as the hash table. So, I started with a simple function that would check if a value for ‘arg’ existed in a given hash table, and if so, return that value, otherwise compute a value by applying the given function, storing the result, and then returning:

(define (memo-or-call ht fun arg)
  (if (hash-has-key? ht arg)
      (hash-ref ht arg)
      (let ((result (fun arg)))
        (hash-set! ht arg result)
        result)))

With this, I was able to define a hash table on my own, set up the default values, and then create an index function, which was pretty effective and enabled me to compute any Fibonacci number that I wanted almost instantly:

(define fibtable (make-hash))
(hash-set! fibtable 0 1)
(hash-set! fibtable 1 1)

(define (fib n)
  (memo-or-call fibtable
                (lambda (k) (+ (fib (- k 1)) (fib (- k 2))))
                n))

This is great, but it felt like it required too much template-like rewriting of code for each function that I wanted to provide table memoization for. I’d have to create a new hash table, add default values, and then use the “internal” function memo-or-call to create my memoization-capable function. To resolve this, I wrote another function that would take a lambda expression and wrap it with a hash table and call to the memoization function:

(define (mt-store-defaults tbl defaults)
  (cond
    [(empty? defaults) tbl]
    [else (hash-set! tbl (caar defaults) (cadar defaults))
          (mt-store-defaults tbl (cdr defaults))]))

(define (make-metatable fun defaults)
  (let ((tbl (mt-store-defaults (make-hash) defaults)))
    (lambda (k)
      (memo-or-call tbl fun k))))

This reduced the complexity of creating a new memorized function considerably, which brought me to functionality that was effectively equivalent to what was possible in Lua. It’s worth noting that I’m strictly dealing with the case where a table is used to memorize computation; not the other usage cases, such as implementing classes or objects, although it would be possible to modify the idea here to include support for the __call magic function in Lua, and it is already possible to store functions in a hash table, as they are still first class objects. Scheme code implementing the now-table-based Fibonacci calculator

(define fib2
  (make-metatable
   (lambda (k) (+ (fib2 (- k 1)) (fib2 (- k 2))))
   '((0 1) (1 1))))

Therefore, in summary, a reasonable implementation of automatic memoization with “metatables” can be achieved with just a few lines of Scheme/Racket, allowing for concise definitions of memorized functions in user code. Note that this is just some example code and not really robust, but feel free to use it as a starting point.

#lang racket

(define (memo-or-call ht fun arg)
  (if (hash-has-key? ht arg)
      (hash-ref ht arg)
      (let ((result (fun arg)))
        (hash-set! ht arg result)
        result)))

(define (mt-store-defaults tbl defaults)
  (cond
    [(empty? defaults) tbl]
    [else (hash-set! tbl (caar defaults) (cadar defaults))
          (mt-store-defaults tbl (cdr defaults))]))

(define (make-metatable fun defaults)
  (let ((tbl (mt-store-defaults (make-hash) defaults)))
    (lambda (k)
      (memo-or-call tbl fun k))))
Aug 312012
 

Earlier this week, I stumbled across McCarthy’s original paper describing LISP, and I felt a motivation to write my own LISP interpreter. I know there are plenty of good ones out there already, but this isn’t really about making one that is better or different from the others. Mostly, I am interested in exploring my own understanding of what LISP programs really mean and, as a part of that, testing my ability as a C programmer to implement a LISP interpreter. I’ve talked with a friend that I will be collaborating with on this project, and we hope to get a basic interpreter up and running over the weekend.

We don’t have a definitive feature list, although we do plan on supporting everything in the original paper, as well as basic garbage collection and an external function interface to define symbols that provide additional functionality to the LISP environment. This is primarily an investigation into what we’re able to do, and, as a part of that, how hard it is to write a functional LISP interpreter, so we’re not planning on too many language features; the focus is mostly on things that are necessary to run the engine itself. If we wanted the kind of functionality found in PLT Scheme/Racket, then we’d just use that to run our programs, but we don’t want to stop with something that can’t be used to do anything useful, either.

We’ve thrown around the idea of making a stand-alone compiler as well, but for now we’re simply going to focus on implementing a REPL and on executing LISP scripts as an interpreter. I know that technically this counts as compilation (in some sense, based on the semantics of the paper), but we’ve also considered making a standalone compiler that will take a script and produce a binary that does not need to re-parse the script every time it is executed.

If you want to follow our progress, we’ve created a public github repository: https://github.com/gmalysa/cs-lisp where you can see all of the code.