Expand string patterns in Elisp

Question

I need to expand logical patterns to list of strings.

For example I have the following definition:

(expand-pattern '(and "xy"
 (or "1" "2")
 (or (and "ab0"
 (or "1" "2" "3"))
 "cd01")))

Which evaluates to the following list of strings:

("xy1ab01" "xy2ab01" "xy1ab02" "xy2ab02" "xy1ab03" "xy2ab03" "xy1cd01" "xy2cd01")

I wrote the following code:

(defun expand-pattern (pattern)
 (defun expat (parents expr)
 (pcase expr
 ((or (pred stringp)
 (pred numberp)) (mapcar (lambda (parent)
 (cons expr parent))
 parents))
 (`(and ,first) (expat parents first))
 (`(and ,first . ,rest) (expat (expat parents first)
 (cons 'and rest)))
 (`(or . ,args) (apply #'append 
 (mapcar (lambda (arg)
 (expat parents arg))
 args)))
 (_ (error "unknown %S" expr))))
 (mapcar (lambda (tokens)
 (mapconcat (lambda (token)
 (format "%s" token))
 (reverse tokens)
 ""))
 (expat '(()) pattern)))

I am new to Emacs Lisp and would like to know, if this is a reasonable way to solve the problem in Elisp or if it can be optimized, to simplify the code.

Answer 1

Scoping

In Emacs Lisp a nesting a defun inside another defun does not create a lexically scoped function. The symbol for the 'nested' function is still interned at in the current objarray. The behavior is unlike that of Scheme.

In Emacs Lisp let ((f (lambda (x) (body))))...(funcall f some-value) is the general structure for a 'local' function.

Formatting

The formatting of the code within the call to pcase is difficult to read. When the condition and consequent cannot be listed on the same line, it is probably more common to place the consequent below the conditional.

Suggested Alternative Format

(defun expand-pattern (pattern)
 (mapcar (lambda (tokens)
 (mapconcat (lambda (token)
 (format "%s" token))
 (reverse tokens)
 ""))
 (expat '(()) pattern)))
(defun expat (parents expr)
 "Utility function for expand pattern."
 (pcase expr
 ((or (pred stringp)
 (pred numberp))
 (mapcar (lambda (parent)
 (cons expr parent))
 parents))
 (`(and ,first)
 (expat parents first))
 (`(and ,first . ,rest)
 (expat (expat parents first)
 (cons 'and rest)))
 (`(or . ,args)
 (apply #'append 
 (mapcar (lambda (arg)
 (expat parents arg))
 args)))
 (_ (error "unknown %S" expr))))

Other Remarks

Because expat throws an error, it might make sense to have expand-pattern invoke expat within a try...catch block. Alternatively, expat could return nil when no match is found. If nil is a possible return value from processing the pattern, then a "Lispy" thing to do is to return two values, the first being the result of processing the expression and the second being either nil or t to indicate an error or no error.

• ceving: expat is an internal helper function, I did not want to export. So letrec is the only way to define something within the lexical scope?
• Vatine: @ceving You can also use cl-labelsand cl-flet, depending on if you have a need to call functions bound in the same form or not (anything defined in cl-flet is "non-shadowing", whereas cl-labels "shadows" function definitions).
• ben rudgers: @ceving I've edited my answer to show the let...funcall syntax for creating 'local' functions in Emacs Lisp. The Emacs Lisp Manual is a bit short in this regard unfortunately. I've sent a documentation suggestion.

Answer 2

It's unusual to defun within a function. If you just want expat available while executing expand-pattern, you should use use letrec:

(defun expand-pattern (pattern)
 (letrec ((expat (lambda (parents expr)
 (pcase expr
 ((or (pred stringp)
 (pred numberp)) (mapcar (lambda (parent)
 (cons expr parent))
 parents))
 (`(and ,first) (funcall expat parents first))
 (`(and ,first . ,rest) (funcall expat (funcall expat parents first)
 (cons 'and rest)))
 (`(or . ,args) (apply #'append 
 (mapcar (lambda (arg)
 (funcall expat parents arg))
 args)))
 (_ (error "unknown %S" expr))))))
 (mapcar (lambda (tokens)
 (mapconcat (lambda (token)
 (format "%s" token))
 (reverse tokens)
 ""))
 (funcall expat '(()) pattern))))

This way, the binding of expat doesn't live beyond the function.

It looks like what you're doing is a 'reduce' type of operation - you may find it worthwhile to look into cl-reduce and related functions.

• ceving: But the funcalls do not make it more readable.
• ben rudgers: Emacs Lisp does not have letrec or an equivalent. In Common Lisp the equivalent is labels. (require 'cl) will provide access to labels in Emacs Lisp, however a function defined with labels in Emacs Lisp still requires funcall for invocation. I believe this is because symbols in a let type structure are not interned, but I may be mistaken.
• Toby Speight: @ben: letrec is a Lisp macro in 'subr.el'. Can you explain how it is different to letrec in other Lisp implementations? The only languages I know from this family are Emacs Lisp and standard Scheme, so perhaps I've missed some subtlety. Certainly the code I wrote in this answer produces the expected results for the example in the question.
• ben rudgers: Thanks for pointing out the availability of letrec. The source code comments say it is only useful in lexical-binding mode. It does not show up in the Emacs Lisp Manual. I'd say the big difference with Scheme is that a function defined with letrec` in Emacs Lisp requires invocation via funcall whereas Scheme does not. Common Lisp provides labels to allow invocation without funcall.