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.

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.