Pattern matching and tail recursion in Emacs Lisp
arnesonium.com
arnesonium.com
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))
...))
(eval `(funcall ,fn ,@args))
------------
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]
------------
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.)
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.
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.
This information is not current, they moved it out of the global namespace in Python 3.
> 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.
I've been using Emacs for ... I dunno, at least a decade. I've never read seq.el, and if I've heard of it before I brushed it off as irrelevant. Hopefully I didn't need to know about it.
There are far to many functions in Emacs for it to be reasonable to expect someone to know any particular family. At least without some efforts at teaching it to them. Now I assume from context that someone who spends a lot of time programming in ELisp is going to run in to this family, but it is unclear why anyone would walk in and think "of I need a seq library!" unless they already happened to be immersed in the functional programming world.
Which is to say, unless someone already knows what reduce means, they are not going to look it up in seq.el.
> It also implements lot of Common Lisp anyway under the `cl-` namespace (incidentally there is also `cl-reduce`)
It includes cl- because Elisp is funky and there are a large contingent of programmers - myself included - who don't want to have to learn a funky lisp to get good results out of our text editor. I'm happy to spend weekends reading up on Common Lisp; that language is awesome.
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.
Some of those functions are named `<action>-sequence`. Some of them are named `seq-<action>`. Some of them are just `<action>`.
Some of them overlap (`seq-length`/`length`; `sequencep`/`seqp`; `sort`/`seq-sort`; `seq-contains-p`/`memberp`), and it's not always clear what the difference is.
Some come with caveats for specific sequences (`sort`: "Note that this function doesn’t work for all sequences; it may be used only for lists and vectors."; `length`: "If you need to compute the width of a string on display, you should use `string-width` (see Size of Displayed Text), not length, since length only counts the number of characters").
No language or library is perfect, but this kind of inconsistency is undeniably a hurdle when trying to write a program.
> The seq.el library provides the following additional sequence manipulation macros and functions, prefixed with seq-. To use them, you must first load the seq library.
> All functions defined in this library are free of side-effects; i.e., they do not modify any sequence (list, vector, or string) that you pass as an argument. Unless otherwise stated, the result is a sequence of the same type as the input. For those functions that take a predicate, this should be a function of one argument.
> The seq.el library can be extended to work with additional types of sequential data-structures. For that purpose, all functions are defined using cl-defgeneric. See Generic Functions, for more details about using cl-defgeneric for adding extensions.
That statement occurs before the various `seq-` functions are listed and described so it's hard for me understand the claim that "it's not always clear what the difference is" when it's stated so clearly before the functions themselves. And when you get into them, like with `seq-length`, you get a statement like this:
> For built-in sequence types, seq-length behaves like length.
I really don't see how they could present this more clearly, what's your suggestion? Should they put flashing lights around the text?
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.
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...)
[1]: https://www.gnu.org/software/emacs/manual/html_node/elisp/Lo...
[2]: https://www.gnu.org/software/emacs/manual/html_mono/cl.html#...
like which ones?
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
How about Brave Clojure?
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.
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
LispWorks is expensive so try the free version for a long time to make sure it is right for you.
For macOS and Linux, the open source SBCL is excellent and there are libraries to use TK or web apps as GUI interfaces.
As far as being self-contained it's at least easy enough to get everything within a single project directory, and one should be able to load pretty much everything (other than if you rely on tcl or something external like that) into the image and save it as an .exe with sb-ext:save-lisp-and-die.
If you don't like Tk, there's a few alternatives like IUP or Qtools.
Of course if you'd prefer you could grab Armed Bear, use Java libraries, and export a JAR. In that case you can use Swing and JDBC.
(Not a gotcha. I have my own Lisp dialect and I'm willing to mess with the syntax.)
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. ;-)
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.