;;; Fennel for Advent
;
; This file is a Fennel program; you can run it with:
;   fennel thispost.txt
;
;; Advent (of Code)
;
; Advent of Code is a yearly programming / CS / math contest. Each day from
; December 1 to December 25, there's a new puzzle with two parts, and there
; is a global leaderboard of who finished the parts more quickly. I don't
; generally go for the leaderboard, but I still try to do the puzzles as they
; come out. You can read more at https://adventofcode.com :)
;
;; Fennel
;
; Fennel is a Lisp that compiles into Lua. You can read more about it at
; https://fennel-lang.org.
;
; Here are a few example examples of how Fennel looks in use. Notice that you
; don't directly iterate over tables - instead, you use either ipairs or pairs,
; which iterate over the contiguous integer keys or all keys respectively. This
; is because of a quirk of Lua's design: tables are a combination of integer-
; indexed vector and scalar-indexed map, and which part of that combination you
; are using can vary. This can sometimes be pretty useful.
;
; Here's an example: we take in a list and use ipairs to walk its vector part,
; accumulating the intermediate values into s by repeatedly evaluating (+ s e).
; The _ in [s 0 _ e (ipairs list)] is actually used to bind the (integer) index
; of e in the table, but because we don't need it here we use _ to ignore it.

(fn sum [list]
  (accumulate [s 0 _ e (ipairs list)]
    (+ s e)))

; This function demonstrates two of Fennel's features: one of the arguments is
; destructured, and then we use match to case on the direction. In fact, match
; has a lot more capability than we're using here - it can destructure and
; match parts of the value, which came in handy quite a few times.

(fn move [[x y] dir]
  (match dir
    :up     [x (- y 1)]
    :down   [x (+ y 1)]
    :left   [(- x 1) y]
    :right  [(+ x 1) y]
    _       (error "puzzling dir " dir)))

; This function relies on the fact that in Lua, nil cannot appear as a value in
; tables, because it used to mark non-presence in the vector part and to delete
; values in the map part. That means that, for example, the common filter
; function from Lisp can be expressed like this, using icollect:

(fn filter [list f]
  (icollect [_ v (ipairs list)]
    (if (f v) v nil)))

; And the familiar map function also looks very similar:

(fn map [list f]
  (icollect [_ v (ipairs list)]
    (f v)))

; Fennel also has a composition mechanism, in the form of -> and the related
; operators. This is *syntactic* composition, so it has some limitations that
; we'll get into later, but it can be quite useful. Fennel also has a shorthand
; syntax for anonymous functions: #(...) produces a lambda with arguments bound
; to $1, $2, and so on. This is very convenient but relies on another limitation
; of Fennel that I'll talk about below as well - namely that functions have no
; definite arity, like in shell. The fact that -> does syntactic splicing means
; that some argument orders for functions are "better" than others because they
; are more amenable to splicing with -> or ->>.

(fn sum-of-even-squares [list]
  (-> list
      (map #(* $1 $1))
      (filter #(= (% $1 2) 0))
      sum))

;; Fennel for Advent of Code
;
; Alright, enough Fennel examples - let's get into what's good and bad about it
; as an Advent of Code language specifically, and then into what I like and
; dislike about Fennel.
;
;; Good things for Advent of Code:
;
; * Fennel is extremely flexible so it's a superb language for quick
;   prototyping and iteration
; * Tables are pretty powerful and you can often fit your data into the right
;   shape to use one
; * Mutation is available, which is sometimes indispensable for efficient
;   solutions
; * The usual dynamic typing advantages: good runtime reflection, debuggability,
;   etc
; * Lua's string library, while tiny, is quite powerful and was totally fine for
;   all the parsing I needed to do
;
;; Bad things for Advent of Code, most of which are inherited from Lua:
;
; * Lua's math stack, when numbers exceed somewhere around 2**46, falls back to
;   IEEE754 doubles instead of to slower bignums. This can cause silent loss of
;   precision, and in particular useful arithmetic properties like, say,
;   x + 1 > x can suddenly stop holding without any warning. That's a logical
;   result of using floating-point math like this but for Advent of Code having
;   bignums instead would be a way better default.
; * Lua tables are combination vector/maps, and in particular they *don't* have
;   the O(1) head-removal behavior you might be used to from other Lisps. That
;   makes them quite slow if you try to use them for BFS queues, which I did.
; * Lua tables don't allow composite keys - the key always has to be a single
;   scalar. For Advent this is very annoying, since you very often want to make
;   tables that are keyed on a 2-tuple or 3-tuple of integers; Lua's use of
;   scalar keys forces you to either find an integer encoding scheme that works
;   for the specific problem (bearing in mind the lurking loss of precision)
;   or serialize all your keys into strings, which is pricey. You can work
;   around this by giving a table custom indexing behavior, at the cost of
;   putting some Lua code on the hot path of every index into the involved
;   table - and your custom indexing function still has to do one of the same
;   hacks, just in a way that is invisible to you.
; * Fennel's error messages can be pretty sparse; in particular, assertion
;   failures don't tell you which assertion failed (although you do get a
;   line number) and other problems like nil dereferences only sometimes
;   tell you which thing was being dereferenced. This can make debugging more
;   of a pain than it has to be.
;
;; General Fennel Thoughts
;
; Fennel is now one of my favorite languages, and I've started using it for
; other non-Advent fun programming. It feels great to work in and I like a lot
; of its aesthetic choices. There are a couple of quirks of it that I don't
; like, but overall I am super pleased with it and plan to keep writing a bunch
; of it :)
;
; The quirks I don't like are:
;
; * When I say that -> is syntactic composition, what I mean is that this:
;     (-> foo (bar 1) (baz :z) quxx)
;   is rewritten syntactically into this:
;     (quxx (baz (bar foo 1) :z))
;   That is, each form is spliced in as the first function argument of the
;   following form. That means that you can't do this, for example:
;     (-> foo ... #(+ $1 $2) ...)
;   because the -> macro tries to splice the previous form into the #(...),
;   which breaks it. If -> instead meant *semantic* composition, that should
;   work fine.
;
; * Functions have no arity. Even very dynamically typed languages usually do
;   arity-checking, because a) it's easy and b) it catches a lot of mistakes.
;   Scheme, Python, and a bunch of other very dynamic languages still check
;   function arity. In Fennel, this checking isn't done; arguments the called
;   function doesn't want are simply ignored, and missing arguments are filled
;   in with nils. This can create hard-to-debug problems where a function is
;   called without an argument, then a nil is passed several layers down the
;   stack before being dereferenced as a table. Ouch. It *does* mean that it's
;   very easy to do optional arguments in Fennel, though, and I developed a
;   pattern like:

(fn dostuff [needed1 needed2 optional1 optional2]
  (assert needed1)
  (assert needed2)
  (var optional1 (or optional1 :default))
  (var optional2 (or optional2 :default)))

; * There's no way to constrain a table's keys to a fixed set - read references
;   to a missing key return nil, and write references just create a new key. It
;   is possible to deal with this by adding a metamethod on the table to
;   override key accesses, but again you pay in execution time for adding some
;   Lua code to the hot path for every table access. It would be nice if there
;   were a way in the runtime to freeze the set of a table's keys and have
;   attempted accesses to other keys cause errors.
;
; * Strings are a little bit table-like, in that the '#' function works on
;   them, but not enough table-like, in that the 'ipairs' function doesn't work
;   on them. I'm not sure why.
;
; * You have to use mutation to handle large data structures efficiently. The
;   compiler and interpreter don't have any notion of copying a table, which
;   means that a) you have to open-code copies and, more annoyingly, b) the
;   interpreter can't tell that you are copying something whose last reference
;   is going away immediately after and elide the expensive copy. For example,
;   consider this functional update function:

(fn update [table index f]
  (icollect [i v (ipairs table)]
    (if (= i index)
        (f v)
	v)))

; There's no way for the compiler to "know" that I'm creating a mostly
; identical copy of the input table and reuse the old one instead, which means
; that if I write, say:

(fn double-even-indexes [table]
  (var t table)
  (for [i 2 (# table) 2]
    (set t (update t i #(* $1 2))))
  t)

; That function ends up having to create a whole bunch of intermediate copies
; of the table as I progressively insert new elements into it. That cost makes
; functional updates like this very painful, so instead efficient Fennel code
; has to use mutation.
;
; That said, all of those are pretty minor annoyances, all things considered,
; and Fennel has a few huge virtues in my book:
; * Destructuring
; * Pattern matching
; * Small size & portability because of targeting Lua
; * Reasonable performance with LuaJIT
;
; So I'll definitely be using Fennel again, and I'll probably use it for Advent
; next year too :D
;
; As always, thanks for reading!

(local testresults [
  (= 20 (sum [2 4 6 8]))
  (let [p (move [0 0] :up)]
    (and (= 0 (. p 1)) (= -1 (. p 2))))
  (= 3 (# (filter [1 2 3 4 5 6] #(= (% $1 2) 0))))
  (= 20 (sum-of-even-squares [1 2 3 4]))
  (= 16 (sum (double-even-indexes [1 2 3 4])))
])

(each [i r (ipairs testresults)]
  (assert r i))
(print (.. (# testresults) " tests ok"))