Pattern matching and tail recursion in Emacs Lisp

https://arnesonium.com/2022/11/pattern-matching-tail-recursion-emacs-lisp

by nemoniac • 4 years ago

99 40 4 years ago

gigatexal• 4 years ago

I want to get my head wrapped around lisp but I just see code like this and my head hurts

Highly recommend Clojure(Script) as a nice introduction to Lisps. It has slightly more syntax (square and squiggly brackets) to avoid having to use an army of parens to denote destructuring, binding etc.

medo-bear7• 4 years ago

i think common lisp has much better learning material. although it has been a while since i last looked, there isnt really anything beginner friendly for clojure

beginners would do well to look at COMMON LISP: A Gentle Introduction to Symbolic Computation. it's easy going and i think everything you learn can quite easily translate to other lisps

coutego• 4 years ago

I'd say that Racket makes for an easier introduction to Lisps, at least for people not familiar with the functional paradigm.

The reason for this is that Clojure intentionally discourages many common imperative idioms by not making any effort to support them. That forces you to learn how to do things "the Clojure way". Once you know it, you realise it makes sense and it's a better way to do thing in that context, but when you are coming from outside, it can be very hard to get things.

At least it was for me, after some 20 years of programming experience. Racket? Sure, I was able to do (simple) programs without too many problems in a matter of hours. Clojure? Lots of "huh?" moments for months until the "aha" moment when things makes complete sense.

I'm quite a big fan of Clojure, for full context.

agumonkey• 4 years ago

it's mostly just induction over trees with a few old idioms for matching

jdale27• 4 years ago

I wouldn't call this everyday Lisp code for beginners. Try Practical Common Lisp: https://gigamonkeys.com/book/.

medo-bear7• 4 years ago

common lisp gentle introduction - begginer programmer

practical common lisp - intermediate programmer

paradigms of artifical intelligence programming - advanced programmer; also one of the best books on software engineering ever written even if you dont care much for lisp

all free. the latter has a new markdown edition

Archelaos• 4 years ago

I would like to give Common Lisp a try. What setup/frameworks are best for a beginner targeting Win10 GUI apps (ideally self-contained in a single exe) that need to access a MariaDB server over the Internet?

tetris112• 4 years ago

I think there's an inherent beauty to Lisp, but when I see backquote/comma expansion commas it upsets this idea for me. I wish they chose other symbols for this

abecedarius• 4 years ago

Do you have an alternative design you like?

(Not a gotcha. I have my own Lisp dialect and I'm willing to mess with the syntax.)

lispm• 4 years ago

It's unfamiliar to the beginner and could take also some "unlearning" of expectations how a program looks like and how to program.

But there are reasons for the syntax: it allows relatively easy language extensions. The mentioned PCASE macro extends the language with a pattern matching construct. Every user can write theses things. Directly in Lisp, without modifying the language itself - because it is already extensible.

The source for PCASE is here: https://github.com/emacs-mirror/emacs/blob/master/lisp/emacs...

Emacs Lisp has some well written extensions. I find the coding style of something like the PCASE extension to be quite readable, for me as a Lisp user. ;-)

medo-bear7• 4 years ago

this is not beginner code, lisp or otherwise. you are looking at macros. macros are a very powerful programming feature, and no other programming language excells at writing macros to lisp level. moreover writing macros might not be very elegant compared to other code. however writing macros in lisp certainly is much more elegant compared to what you need to do to achieve the same result in other languages. the point of writing macros is to make calling them elegant

neilv• 4 years ago

Don't get intimidated. This article doesn't much get into explanation.

Understanding `match`-like syntax takes some explanation, and then the syntax can sometimes still look intimidating, especially if they added in lots of conveniences. But once you read through the docs, it's usually trivial, and can eliminate a lot of bulky and error-prone code.

Named-`let` in Scheme (which is what I suspect inspired this Emacs `named-let`) looks confusing until you know it. As you try to write Scheme code without mutating variables (setting variables to new values after they already had one) as a stylistic choice, named-`let` and properly-implemented tail calls get very useful. And once you've used it a little, it's simple, and tail recursion will usually be easy to follow (easier than trying to follow code setting flag variables, having premature exits, etc.).

These are actually two very-very different kinds of constructs. `match` ends up being a kind of mini-language with some syntactic sugar thrown in, but named-`let` is more a fundamental construct.

hddqsb4• 4 years ago

As others have said, this article is not beginner-friendly. The book "Structure and Interpretation of Computer Programs" (SICP) is a classic introduction to Lisp (specifically Scheme), the full text is available online: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...

medo-bear7• 4 years ago

great book but not an introduction to lisp

throwaway815232• 4 years ago

This is nice, I didn't know about named-let being usable for tail recursion. I have always liked the idea of a Emacs Lisp back end for Purescript and having tail recursion makes it easier. Purescript is a typed functional language that is sort of a modernized Haskell with strict evaluation, originally written to give a typed language that compiles to Javascript, but now it has more backends while Typescript seems to have occupied the "typed JS" niche that Purescript had hoped to fill. (www.purescript.org for more info). Anyway, it would be cool to generate Emacs Lisp code from Purescript and get rid of a lot of wrong-type-arguments errors at runtime.

medo-bear7• 4 years ago

and get rid of a lot of wrong-type-arguments errors at runtime

like which ones?

throwaway815232• 4 years ago

If you have used Emacs for any length of time you will have run into them now and then. The usual sort is when something is expected to be a value but instead it is nil, the equivalent of a null pointer exception. It's hard to give examples because if there was a reproducible one that happened often enough to remember, it would go through the bug fix process. Instead it just happens enough to be annoying. I guess gnus.el is a common subsystem where it happens a lot, say if a remote server is down.

kazinator2• 4 years ago

That ela/apply function is actually reduce.

You cannot call the function multiple calls with funcall to implement apply; there has to be only one call to funcall.

Basically you have to ways:

Switch on different argument list lengths, to one of many funcall expressions that has a matching arity:

  (pcase args
    (() (funcall fn))
    (`(,a1) (funcall fn a1))
    (`(,a1 ,a2) (funcall fn a1 a2))
    (`(,a1 ,a2 ,a3) (funcall fn a1 a2 a3))
    ...))

Or build the funcall dynamically and eval it:

  (eval `(funcall ,fn ,@args))

Lisp newbiews who don't know about apply sometimes end up simulating it like this.

hddqsb4• 4 years ago

I was about to post a similar comment. My version might be easier to understand, so here it is.

------------

The author confuses "apply" and "reduce" (aka "fold").

- `apply` calls a function once, passing it all the specified args. It is very similar to `funcall`, except the last argument of `apply` is a list of args.

- `reduce` repeatedly calls a function on an accumulator and each element of a list.

Examples:

    (vector 1 2 3 4)
    => [1 2 3 4]

    (funcall 'vector 1 2 3 4)
    => [1 2 3 4]

    (apply 'vector 1 2 (list 3 4))
    => [1 2 3 4]

    (seq-reduce 'vector (list 1 2 3 4) 0)
    => [[[[0 1] 2] 3] 4]

The author's confusion is probably because `+` in Lisp is variadic, so `(apply '+ nums)` and `(seq-reduce '+ nums 0)` happen to produce the same result.

------------

Also, the way the author's implementation guesses the initial value is awful. The standard practice is to either ask the caller to explicitly provide the initial value (which is what `seq-reduce` does), or to use the first element of the list as the initial value.

(The latter has the advantage of being simpler to use, since the programmer doesn't need to find the correct identity element that needs to be passed as the initial value (e.g. for + the identity is 0, but for * the identity is 1). The disadvantage is that it fails on empty lists. Also, in statically-typed languages it can only supports binary operators, so it is not as powerful as the version that takes an explicit initial value.)

roenxi2• 4 years ago

That ela/apply function is actually reduce.

I feel it is fair to call out ELisp as the problem here; there are a lot of operations (reduce is a good example) where it is unclear how the programmer is meant to discover the name they want. It is unusual to see a good resource that explains how programmers are meant to use lists, and if someone comes in from an imperative language then the need to find a resource on transforming lists is unclear.

Emacs is particularly bad because they have that weird dialect of lisp that didn't catch on anywhere, so you can't use generic tutorials and nobody teaches it. And as I recall there is no neat introductory resource explaining "how to manipulate lists in Elisp".

So it is true that he has reinvented a bad reduce, but also true that this is a celebration of a programmer stumbling over an important concept despite a so-so learning experience.

natrys• 4 years ago

I am not sure that's fair, either generally or specifically. The `reduce` function is well known, it's covered in pretty much every mainstream language's standard library - not just lisps or fringe "functional" languages. I mean Python is imperative, and it always had reduce.

On the other hand, Python's reduce is in global namespace so you pretty much need to know its name. While Emacs doesn't have actual modules or namespaces, if the end goal is organisation and discoverability, I think that's still accomplished by the convention of prefixing function names with a unique and descriptive string. So, seq.el implements many list/sequence related functions. If you type "seq-" and hit tab, the autocompletion menu would show all list related functions, you can just browse for reduce there.

As for how to know about seq.el (or dash.el) in first place, imo these are not that obscure to be hidden from google search. But you can also take any list function that you know about from elsewhere (let's say `count`, or `reduce` itself), then you just need to use the internal search system like `M-x apropos count`, and from `seq-count` result you can deduce that `seq-` is the interesting namespace.

In any case I would contest that Elisp is particularly weird. It also implements lot of Common Lisp anyway under the `cl-` namespace (incidentally there is also `cl-reduce`). As for the matter of it not catching on anywhere, it's still the most popular Lisp used in the world today, a fact that imo makes up for lack of generic tutorials with a lot of Elisp specific tutorials out in the wild.

Jtsummers2• 4 years ago

Emacs Lisp has an entire manual, and it's even included in emacs.

https://www.gnu.org/software/emacs/manual/elisp.html

Here is a list of sequence functions (lists are sequences): https://www.gnu.org/software/emacs/manual/html_node/elisp/Se....

As I said in another discussion the other day, no language can be fully intuited. That's why we have documentation and training material. Emacs Lisp has pretty good documentation which is searchable from within the environment it's meant to be used in, and can be obtained online.

kazinator2• 4 years ago

The author obviously knows left fold from having done functional programming outside of a Lisp context, but is not familiar with apply. I'm guessing that he saw examples of apply usage somewhere which looked like reduce, e.g. (apply '+ 1 2 3) -> 6 and formed the belief that Lisp uses the term "apply" to denote "left fold", and is not aware of the "reduce" terminology.

However, apply is very central in classical Lisp; it's used in the so-called "Maxwell's Equations".

It's possible that the author explored static functional languages and didn't encounter anything like apply. Static functional languages tend not to support variadic functions in any straightforward way, let alone dynamic calls to them.

apply relies on dynamic typing. The number of arguments a function takes is part of its type: a three-parameter function is of a different type from a four-parameter function, right? We don't even have to look at the parameter types to know that the function types are not compatible. Now lists can be of different lengths (even in a static language). E.g. in Haskell or what have you, a list of three integers isn't a different type from a list of four integers. (Probably if you work at it, you can have that arranged; or use a tuple or whatever).

So when you think about what apply is doing, it requires a dynamic check: a list that could have any number of items it known only at run-time is being turned into a function call, which must be correctly typed. If a four-argument list is applied to a three-argument function, an error must be signaled.

The functional argument of apply cannot be type checked as a specific function type; it takes any function type whatsoever, and possibly non-function objects that are funcallable. This is more dynamic than funcall, because we can infer the arity of the argument of funcall from the number of arguments being passed. (funcall 'cons 1 2 3) can, in principle, be diagnosed at compile time as misuse of cons. (apply 'cons arglist) cannot be diagnosed, unless arglist is a lexical variable provably initialized with with a list of other than two arguments, with no possibility of a rescuing assignment.

djaouen• 4 years ago

Now this is the kind of content I come to HN for! Edit: sorry for the spammy comment, I just really felt the need to express my gratitude after the tidal wave of crypto posts recently.

hddqsb4• 4 years ago

First time I'm hearing about `named-let` and tail call optimisation in Emacs, thanks for sharing!

A clarification: Tail call optimisation in Emacs is not tied specifically to `named-let`, but it is tied to `cl-labels` (which `named-let` uses internally). Normal functions declared using `defun` don't currently support tail call optimisation.

(The tail call optimisation was only added to `cl-labels` recently, in Emacs 28.1: https://github.com/emacs-mirror/emacs/commit/29c7f8c915c3889...)

hddqsb4• 4 years ago

Edit: The documentation of `named-let`[1] explicitly mentions that it supports tail call optimisation, but the documentation of `cl-labels`[2] doesn't. So maybe the optimisation should be viewed as being tied specifically to `named-let` (or maybe the documentation of `cl-labels` should be updated to mention that it also supports the optimisation).

[1] https://www.gnu.org/software/emacs/manual/html_node/elisp/Lo...

[2] https://www.gnu.org/software/emacs/manual/html_mono/cl.html#...

Pattern matching and tail recursion in Emacs Lisp

Related Stories