Lisp - gregorymorrison/euler1 GitHub Wiki

Lisp, introduced in 1958, is one of the oldest programming languages still in common use. It's a functional language, and if you've never explored functional languages before, I would highly encourage you to. They use a completely different computational model than the standard Von Neumann model used by imperative and object-oriented languages - they use Church's Lambda calculus instead. Instead of Von Neumann's model of writing a list of discrete steps for the machine to follow, in Lambda calculus you write your program more as theoretical formulas. Here is a version of Euler1 in Lisp using Lisp's variant of list comprehensions:

#!/usr/bin/clisp
; Euler1 in Lisp

(defun euler1 (x)
    (reduce #'+
        (loop for y from 0 to x
            if (or (= (mod y 3) 0) (= (mod y 5) 0))
            collect y)))

(print (euler1 999))

Not the shortest version of our program, but not too bad. Yes, it's prefix notation with lots of parens, but suck it up, sweet pea, it's good for you. There is a compelling reason for this, which will slowly become apparent as you begin to explore the language (hint - read up on s-expressions).

Here’s a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic – it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation – there are instead only functions which return values. The other main point is that this recursion uses tail call optimization – it’s written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

#!/usr/bin/clisp
; Euler1 in lisp

(defun euler (n acc)
    (if (= n 0)
        acc
        (if (or (= (mod n 3) 0) (= (mod n 5) 0))
            (euler (1- n) (+ acc n))
            (euler (1- n) acc))))

(defun euler1 (n)
    (euler n 0))

(print (euler1 999))

Although Lisp is a functional language, and that last version is idiomatic of functional languages like Standard ML - no mutability, it's not really idiomatic of Lisp. Lisp is all about lists. Here's a more idiomatic version in which we pass around a list generated up front, peeling off and using the first value in each recursive call. It also shows the use of optional parameters. You'd think Lisp would have a built-in range function, but I couldn't find one:

#!/usr/bin/clisp
; Euler1 in lisp

(defun _range (m n)
    (loop for i from m to n collect i))
(defun range (m &optional (n 0))
    (if (= 0 n)
    	(_range 0 m)
    	(_range m n)))

(defun mod-3-5 (n)
    (if (or (= (mod n 3) 0) (= (mod n 5) 0)) n 0))

(defun Euler (lst acc)
    (if lst
        (Euler (cdr lst) (+ acc (mod-3-5 (car lst))))
        acc))

(defun Euler1 (lst)
    (Euler lst 0))

(print (Euler1 (range 999)))

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, Euler1() returns Euler1() calculated on the half of the list before the pivot element, Euler1() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:

#!/usr/bin/clisp
; Euler1 in Lisp

(defun range (n m)
    (loop for i from n to m collect i))

(defun mod-3-5 (n)
    (if (or (= (mod n 3) 0) (= (mod n 5) 0)) n 0))

(defun Euler1 (lst)
    (if lst
        ; find the midpoint of the list
        (let ((pivot (ceiling (/ (length lst) 2))))
            (+
                ; return a value for the middle element
                (mod-3-5 (nth (1- pivot) lst)) 
                ; plus Euler1 on the first half of the list
                (Euler1 (subseq lst 0 (1- pivot)))
                ; plus Euler1 on the last half of the list
                (Euler1 (subseq lst pivot))))
        0 ; else return 0
    )
)

(print (Euler1 (range 1 999)))

Here's a version in which I define my own map/filter/reduce functions using lambdas, and then simply apply them. Map's only purpose here is for illustration, since it returns itself. Note that there is no recursion or looping involved (except for the initial range generation):

#!/usr/bin/clisp
; Euler1 in lisp

(defun myMap (lst)
    (mapcar (lambda (x) x) lst))

(defun myFilter (lst)
    (remove-if-not
        (lambda (n) (or (= (mod n 3) 0) (= (mod n 5) 0)))
        lst))

(defun myReduce (lst)
    (reduce #'+ lst))

(defun range (n m)
    (loop for i from n to m collect i))

(defun Euler1(lst)
    (myReduce (myFilter (myMap lst))))

(print (Euler1 (range 1 999)))

Functions in Lisp are first-class, meaning they are as easy to manipulate as data. Let's build off the previous example, but this time we'll store our map/filter/reduce functions in a list. We'll pass the functions and the integers into Euler1(), and recursively apply the first function to the integers until the function list is empty:

#!/usr/bin/clisp
; Euler1 in lisp

(defun range (n m)
    (loop for i from n to m collect i))

(defun myMap (lst)
    (mapcar (lambda (x) x) lst))

(defun myFilter (lst)
    (remove-if-not
        (lambda (n) (or (= (mod n 3) 0) (= (mod n 5) 0)))
        lst))

(defun myReduce (lst)
    (reduce #'+ lst))

(defun Euler1 (fns data)
    (if fns
        (Euler1 (cdr fns) (funcall (car fns) data))
        data))

(print (Euler1 '(myMap myFilter myReduce) (range 1 999)))

Here’s one more - an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation. Lisp seems to suck at making long math expressions legible, so I've attempted to clarify it with indentation:

#!/usr/bin/clisp
; Euler1 in lisp

(defun mySum (n size)
  (* n 
    (floor 
      (/
        (+ 
          (expt (floor (/ size n)) 2) 
          (floor (/ size n)))
        2))))

(defun euler1 (size)
  (- (+ (mySum 3 size) (mySum 5 size)) (mySum 15 size)))

(print (euler1 999))

One of Lisp's greatest claims to fame is its regular syntax. It may appear illegible at first, but Lisp is not designed for human-readability - it's designed for machine-readability. Unlike other languages where your code is written as a bunch of text, Lisp is written as collection of syntax symbols having a regular grammar. Lisp also has a precompilation stage called macros which generate and substitute code using user-defined routines, allowing you to extend the language arbitrarily. What does all this mean? Since I'm a macro novice myself, I'll borrow some material from this StackOverflow answer. Let's say you're fond of the Python lisp comprehension syntax:

    S = [x for x in range(1000) if x%3==0 or x%5==0]

Well, Lisp doesn't have anything like that, but don't despair - Lisp lets you roll your own! The macro stage takes source tokens as input, transforms it, and then returns syntax that replaces the original tokens. Notice we do nothing with the tokens for and in - they exist merely as part of our list comprehension's grammar:

#!/usr/bin/clisp
; Euler1 in lisp 

(defmacro lcomp (expression for var in list conditional conditional-test)
  ;; create a unique variable name for the result
  (let ((result (gensym)))
    ;; the arguments are really code so we can substitute them 
    ;; store nil in the unique variable name generated above
    `(let ((,result nil))
       ;; var is a variable name
       ;; list is the list literal we are suppose to iterate over
       (loop for ,var in ,list
            ;; conditional is if or unless
            ;; conditional-test is (= (mod x 2) 0) in our examples
            ,conditional ,conditional-test
            ;; and this is the action from the earlier lisp example
            ;; result = result + [x] in python
            do (setq ,result (append ,result (list ,expression))))
       ;; return the result 
       ,result)))

(defun range (n m)
    (loop for i from n to m collect i))

(defun mod-3-5 (n)
    (or (= (mod n 3) 0) (= (mod n 5) 0)))

(print (reduce #'+ (lcomp x for x in (range 1 999) if (mod-3-5 x))))

The following code is what is generated in my environment, returned by the macro and substituted for the original tokens:

(LET ((#:G2909 NIL))
 (LOOP FOR X IN (RANGE 1 999) IF (MOD-3-5 X) DO
  (SETQ #:G2909 (APPEND #:G2909 (LIST X))))
 #:G2909)

Lisp also has other claims to fame, such as introducing the world to the fantastic concepts of the REPL and garbage collection. My belated thanks to John McCarthy for giving us such a well-designed and elegant language.

There are a lot of lisp variants; I chose to use GNU CLisp. Simply add the shebang to the top of your file and execute it:

$ ./euler1.lsp
233168
$