Learning Scheme

by Jochem Kossen in articles

At work, we talked our first-year students into participating in the Advent of Code 2020. It’s quite the challenge for them, but quite a few had a lot of fun solving the puzzles together. They mostly utilize PHP and JavaScript.

As a fun project I thought I’d participate as well and use the occasion to learn a different way of programming as an extra challenge. Ever since rediscovering Emacs I’ve been wanting to understand elisp better. Up to now I just considered LISP to be an annoying collection of parentheses containing bits of code. LISP code looks a bit like it was written by aliens. After considering a few options (Emacs with elisp, Common Lisp, Racket, Scheme). I picked the GNU Guile Scheme implementation.

Scheme is considered a minimal Lisp variant which made me think it’d be one of the easier options to start with. While not strictly required in Scheme, one of my personal goals was diving into functional programming, recursion and avoiding side-effects. Which meant I could not use iteration (for, foreach, while) and I was not allowed to mutate variables (change their values).

When telling my students they wondered if it was at all possible to write working code this way. We’ve only been teaching them imperative coding styles with some Object Orientated Programming up to now.

Challenging

For me, it did turn out to be quite the challenge. It does not help that there are multiple implementations of Scheme such as Guile, Chez, and Chicken Scheme. Each implement Scheme in slightly different ways. So when finding documentation online, you have to keep in mind the code will need adjustments in order to work in the specific Scheme implementation that you use. The documentation of Guile itself is lacking in giving examples.

Still, when writing this post, I’ve solved everything up to day 5, and I feel I am getting better thinking in recursive functions.

Here’s my solution to day 1, my very first Scheme code. It works but is still full of newborn-schemer-ugliness.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

(define (do-num lst-a lst-b i)
  (define l (car lst-a))
  (define r (car lst-b))
  (define sum (+ l r))
  (if (= sum 2020)
      (format #t "\nFOUND: ~d+~d=~d\nSolution: ~d\n" l r sum (* l r)))
  (if (> (length lst-a) (+ i 1))
      (do-num lst-a (cdr lst-b) (+ i 1))
      (if (> (length lst-a) 2)
          (do-num (cdr lst-a) (cdr (cdr lst-a)) 1))))

(do-num lst (cdr lst) 1)

After programming with it a few more days, it gets better though. Day 5 looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

(use-modules (srfi srfi-9) (ice-9 format) (ice-9 regex) (ice-9 match) (ice-9 rdelim))

(define (parse-row chars res lower-char upper-char start end)
  ;;(format #t "start: ~a end: ~a\n" start end)
  (if (= (length chars) 0)
      res
      (let ((char (car chars)))
        (cond ((equal? lower-char char)
               (parse-row (cdr chars)
                          start lower-char upper-char start
                          (floor (+ start (/ (- end start 1) 2)))))
              ((equal? upper-char char)
               (parse-row (cdr chars)
                          end lower-char upper-char
                          (ceiling (+ start (/ (- end start) 2)))
                          end))))))

(define (get-seat-id pass)
  (let* ((row (string-drop-right pass 3))
         (col (string-drop pass 7))
         (rowl (string->list row))
         (coll (string->list col))
         (res-row (parse-row rowl 0 #\F #\B 0 127))
         (res-col (parse-row coll 0 #\L #\R 0 7)))
    (+ (* res-row 8) res-col)))

(define (get-pass-list port pass-list)
  (let ((line (read-line port)))
    (if (eof-object? line)
        (sort pass-list <)
        (let ((seat-id (get-seat-id line)))
          (get-pass-list port (cons seat-id pass-list))))))

;; find missing pass in _sorted_ list
(define (get-missing pass-list)
  (if (not (= (cadr pass-list) (+ (car pass-list) 1)))
      (+ (car pass-list) 1)
      (get-missing (cdr pass-list))))

;; Correct solution: 739
(define file (open-input-file "aoc5_input.txt"))
(define missing (get-missing (get-pass-list file (list))))
(format #t "Solution: ~a\n" missing)
(close-input-port file)

Want to see more? Check my Git repository

Gains

Aside from that, Scheme re-peeked my interest in programming languages. I’ve been looking into Haskell which looks super nice and Rust which is currently hyped everywhere. Both are completely different beasts from Scheme but very interesting nonetheless.

Lasting code

Another aside, looking into Scheme and LISP made me think about writing long(er) lasting code. Scheme has been around for 40 years. Scheme code still looks about the same as it did back then. You can still use Scheme (and LISP) to write modern software.

One of the things annoying me at writing code is that most code will stop running once a newer version of the it’s mostly the frameworks (Laravel, Spring MVC, ASP.net, etc.) which don’t seem to care about keeping code working.

If you’d want to write code which will still compile and run a hundred years from now, which programming language / environment would you use?

Want to dive into Scheme as well?

If you want to dive into Scheme as well, here are a few resources which helped me along the way: