Memoization: Lisp vs. Ruby

All implementations of memoization below use lexical closures.

Lisp

Common Lisp

Based on Paul Graham's code for memoize (search for memoize) from the book On Lisp, here is a version that also handles functions that return multiple values:

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              (values-list val)
              (let ((val (setf (gethash args cache)
                               (multiple-value-list (apply fn args)))))
                (values-list val)))))))

This works by keeping all the values returned by the function call in a list created using multiple-value-list, inside the cache hash table. The conversion from the stored list to multiple values is done by values-list.

Arc - a new dialect of Lisp

Memoization in Arc by Paul Graham:

(def memo (f)
  (let cache (table)
    (fn args
      (or (cache args)
          (= (cache args) (apply f args))))))

As you can see, it is significantly shorter than the Common Lisp one.
Please note, however, that in this case, function calls returning nil are not retrievable from cache, since (cache args) would appear to fail. There is a workaround, involving the use of the *fail* variable: Arc search functions return the value of *fail* upon failure. However, the author assumes that the case of a function call that is computationally intensive only to return nil in the end is so rare that this implementation deliberatly ignores this case and evaluates the function call normally. Thinking about programs that deal with automated theorem proving, program verification or other scientific apps, this assumption may or may not hold a lot of liquid for your purposes. I, for one, would be content with an increase of 1 or 2 in the line count of memoize's definition so that I can forget about this quirk in the implementation that restricts the return value of functions and have it cache everything properly, thereby getting a clean abstraction, just like in the Ruby code below.
But, as always, YMMV.

Ruby

And now for something completely similar, in Ruby-speak:

def memoize(fn)
    cache = {}
    lambda {|*args|
        return cache[args] if cache.has_key?(args)
        cache[args] = fn.call(*args)
    }
end

It is worth noting that in Ruby, there is no difference between multiple values and Arrays, so no conversion between the two is necessary for storing and retrieving them. This is one reason for which the Ruby version is surprisingly shorter.
Please note that there is an even more elegant (while very similar) implementation of memoize that can optionally cache on disk too, by Daniel J. Berger.

The birth of recursion from self-application in lambda calculus

Reading Many faces of the fixed-point combinator and Y overriding self-application by Oleg Kislyov (oleg-at-pobox.com), I came to understand how to express recursive functions in lambda calculus in an elegant way. Oleg's code was written in Scheme, but it was clear that it was easily translated in pure lambda calculus. I used the Lambda calculator by Carl Burch to do this for the (recursive) factorial function:

(λf.f f) (λf.λn.if (= n 0) 1 (* n (f f (- n 1))))
Example: ((λf.f f) (λf.λn.if (= n 0) 1 (* n (f f (- n 1)))) 5) 

Afterwards, I found on the CLiki Factorial page a Common Lisp translation of the above:

((lambda (f) #'(lambda (n) (funcall f f n)))
 #'(lambda (f n) (if (= n 0) 1 (* n (funcall f f (- n 1))))))

This would probably look much better in Scheme, and I am beginning to understand why Scheme is regarded as a "better Lisp" than Lisp.

Just when I was contemplating "porting" the lambda expression to Ruby, here it is... well, almost. Actually, the Y combinator is used here, instead of the U combinator used by Oleg in the above articles. So, here is the true Ruby translation (actually a sample call of it):

p lambda { |f|
    f.call(f)
}.call(
    lambda { |recurse|
        lambda { |n|
            if n == 0 then
                1
            else
                n * recurse.call(recurse).call(n-1)
            end
        }
    }).call(5)

YALQ - Yet Another Lisp Quine

Here is a format-based Lisp quine:

(let ((p "(let ((p ") (s "(format t \"~A~S) (s ~S)) ~A)\" p p s s)")) (format t "~A~S) (s ~S)) ~A)" p p s s))

Please note that the above code should be written on a single line, and there should be a space before the last ~A, before the end of the string.

While I thought it was pretty original at the time it was written, I now discovered the quine by Dave Seaman (ags@seaman.cc.purdue.tom.edu MINUS cat) on the Lisp section of the Quine Page:

(let ((p "(let ((p ~s)) (format t p p))")) (format t p p))

This one is smarter and shorter, since p is used as a format-string for printing itself, without needing both a prefix and a suffix, but it is clearly in the same vein.

Mapcar in Ruby

A Ruby version of Lisp's mapcar function:

require 'generator'
# One mapcar to rule all Enumerables.
def mapcar(*enums)
 generators = enums.collect {|e| Generator.new(e)}
 result = []
 while true
     begin
         params = generators.collect {|g| g.current; g.next}
         rescue EOFError
             return result
     end
     result << yield(*params)
 end
end

Sample usage:

qSorters = arrays.collect {QSort.new}
threads = mapcar(qSorters, arrays) {|q, a| Thread.new {q.quicksort(a)}}

This creates an Array of Threads that use the objects in qSorters to sort each element of arrays.
Please note that the QSort class is user-defined and omitted here for brevity (and sanity).
The above mapcar is based on recipe 7.9, pages 256-257 of the Ruby Cookbook, specifically the interosculate function.