Scheme - gregorymorrison/euler1 GitHub Wiki
Scheme is a variant of lisp designed for academic purity which debuted in 1975. Whereas Lisps usually include all sorts of libraries to make them more generally useful, Scheme is stripped down for elegance. At first upon exploring this language, I was horrified that it was missing so much basic functionality. I thought that I would hate this language. Instead though, I found myself fascinated by a language so simple that you could learn the basics in one sitting.
What users of Scheme do is build up their own libraries, functions, and utilities to get things done - it's a Lego language. I found the exercise of having to write operations like sum and filter to be not tedious, but academically interesting, since they're not just magic routines that you call. Rather, writing them imparts a deep understanding of how the language functions. And you can find most operations that you'd want already written on the 'net.
For this exercise, I've chosen Gnu's implementation of Scheme, Guile. To write Euler1 in Scheme, here is the set of utility functions I started off with. The last function, mod-3-5, is specific to our problem.
; util.scm
(use-modules (srfi srfi-1))
(define (id obj) obj)
(define (flip func) (lambda (x y) (func y x)))
(define (curry func x) (lambda (y) (func x y)))
(define (compose f g) (lambda (arg) (f (g arg))))
(define (foldr func end lst)
(if (null? lst)
end
(func (car lst) (foldr func end (cdr lst)))))
(define (foldl func accum lst)
(if (null? lst)
accum
(foldl func (func accum (car lst)) (cdr lst))))
(define fold foldl)
(define reduce fold)
(define (unfold func init pred)
(if (pred init)
(list init)
(cons init (unfold func (func init) pred))))
(define (sum . lst) (fold + 0 lst))
(define (product . lst) (fold * 1 lst))
(define (range low high)
(cond
((> low high) '())
(else (cons low (range (+ low 1) high)))))
(define (slice lst start end)
(drop (take lst end) start))
(define (mod-3-5 x)
(or (= (modulo x 3) 0) (= (modulo x 5) 0)))
Now, let's get to work. Here's our first example of Euler1. It's a straight application of map, then filter, then fold. Map here is admittedly stupid - it takes a number and returns itself; it's included only for illustration. My code blew out the stack - I thought Scheme was supposed to be optimized to prevent that? Luckily, Guile lets you increase the stack size:
; Euler1 in Scheme
(load "util.scm")
(debug-set! stack 100000)
(define (euler1 x)
(reduce + 0
(filter mod-3-5
(map (lambda (x) x)
(range 0 x)))))
(display (euler1 999))(newline)
Notice that we are not maintaining any state to solve our problem. No loops, no variables, no mutable state. We simply call map, filter, and fold, and get the solution. This is an important part of the solution of the concurrency problem - how do you keep threads from stepping on each other's states? By eliminating mutable state!
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.
; Euler1 in Scheme
(load "util.scm")
(define (euler n acc)
(if (= n 0)
acc
(if (mod-3-5 n)
(euler (- n 1) (+ acc n))
(euler (- n 1) acc))))
(define (euler1 x)
(euler x 0))
(display (euler1 999))(newline)
Although Scheme is a functional language, and that last version is idiomatic of functional languages like Standard ML – no mutability, it’s not really idiomatic of a 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:
; Euler1 in Scheme
(load "util.scm")
(debug-set! stack 100000)
(define (mod-3-5-n n)
(if (mod-3-5 n) n 0))
(define (euler lst acc)
(if (null? lst)
acc
(euler (cdr lst) (+ acc (mod-3-5-n (car lst))))))
(define (euler1 n)
(euler (range 0 n) 0))
(display (euler1 999))(newline)
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:
; Euler1 in Scheme
(load "util.scm")
(debug-set! stack 100000)
(define (mod-3-5-n n)
(if (mod-3-5 n) n 0))
(define (euler lst)
(if (null? lst)
0 ; return 0
; else find the midpoint of the list
(let ((pivot (ceiling (/ (length lst) 2))))
(+
; return a value for the middle element
(mod-3-5-n (list-ref lst (- pivot 1)))
; plus euler on the first half of the list
(euler (slice lst 0 (- pivot 1)))
; plus euler on the last half of the list
(euler (slice lst pivot (length lst)))))))
(define (euler1 n)
(euler (range 0 n)))
(display (euler1 999))(newline)
Here’s a version in which I define my own map/filter/reduce functions using lambdas, and then simply apply them using Scheme's built-in function composition. Map’s only purpose here obviously is for illustration, since it returns itself:
; Euler1 in Scheme
(load "util.scm")
(debug-set! stack 100000)
(define (myMap lst)
(map (lambda (x) x) lst))
(define (myFilter lst)
(filter mod-3-5 lst))
(define (myFold lst)
(fold + 0 lst))
(define (euler1 x)
((compose myFold (compose myFilter myMap)) (range 0 x)))
(display (euler1 999))(newline)
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, Scheme doesn’t have anything like that, but don’t despair – Scheme lets you roll your own! The macro stage takes source tokens as input, transforms it, and then returns syntax that replaces the original tokens. Here I've defined two different versions of lcomp - one that takes a filter and one that does not. I'm only using the second one but am including both to illustrate overloading of a macro definition by wildcard. I’ve colored the function parameters and arguments passed in for ease of illustration. Notice we do nothing with the tokens for, in, and conditional - they exist merely as part of our list comprehension’s grammar:
; Euler1 in Scheme
(load "util.scm")
(use-syntax (ice-9 syncase))
(debug-set! stack 100000)
(define-syntax lcomp
(syntax-rules ()
((lcomp expression for var in mylist)
(map (lambda(var) expression) mylist))
((lcomp expression for var in mylist conditional test)
(map (lambda (var) expression)
(filter (lambda (expression) test) mylist)))))
(display
(fold + 0
(lcomp x for x in (range 0 999) if (mod-3-5 x))))
(newline)
Finally, here’s 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. Scheme sucks at making long math expressions legible outside of an IDE, so I’ve attempted to clarify it with indentation:
; Euler1 in Scheme
(load "util.scm")
(define (mySum n size)
(* n
(floor
(/
(+
(expt (floor (/ size n)) 2)
(floor (/ size n)))
2))))
(define (euler1 size)
(- (+ (mySum 3 size) (mySum 5 size)) (mySum 15 size)))
(display (euler1 999))(newline)
To install on Fedora, use yum to install guile. Then, to execute, just pass your program as an argument to Guile:
$ guile euler1.scm
233168
$