m4_lambda

[Eric Blake]

A recent post on the m4-discuss list mentioned a Y-combinator implemented in M4 
[1], which had me digging up memories about functional meta-programming stuff 
better left for college classes [2] ;)  But as a net result, I realized that 
anonymous m4 macros (aka the classic lambda construct which is fundamental to 
Lisp dialects) deserves a place in m4sugar right alongside m4_curry.  I will 
probably apply the following patch soon (or you can try it now, with 'git fetch 
git://repo.or.cz/autoconf/ericb.git m4-lambda').

[1] http://uszla.me.uk/space/essays/m4Y

[2] http://rayfd.wordpress.com/2007/05/06/y-combinator-for-dysfunctional-non-
schemers/ has the perfect quote summarizing its exposition of how to write a Y-
combinator in JavaScript:

"What’s in it for me beyond the “oh, neat” factor? Er. Frankly, I’m not sure. 
In the real world, if I need to write a recursive function, I will just give it 
a bloody name."




Meanwhile, I'm wondering if it is worth trying to add some syntactic sugar to 
make anonymous macros easier to use.  My initial thoughts (but only lightly 
tested) is that something like this would make it easier to write macro 
definitions which in turn define other (possibly anonymous) macros:

# m4_defer(string)
# ----------------
# Output STRING, but with all repeating sequences of `][' within STRING
# shortened by one `][' pair.  The intent is that strings like `[$][1]'
# can be used to mean the first parameter of a deferred macro definition,
# rather than the first parameter of the current macro, regardless of how
# many layers of nested quoting contains it, while `[$][][1]' still
# results in a literal $1 in the deferred macro's expansion.
m4_define([m4_defer], [m4_bpatsubst([[$1]],
  m4_changequote`'_m4_defn(`_m4_defer')m4_changequote([,]), [\1])])
m4_define([_m4_defer],
  m4_changequote`\]\[\(\]\[\)*'m4_changequote([,]))

[The M5 language would make this task easier: in a macro definition, $1 is the 
first parameter, but $$1 expands to "$1" rather than it "$"<first parameter>, 
and $$$1 to "$$1", making it much easier to write macros that define macros.]

Note the difference:
m4_define([a], [m4_lambda([[$1 $][1 $][][1]])])dnl
m4_define([b], [m4_lambda(m4_defer([[$1 $][1 $][][1]]))])dnl
a(2)(3)
=> 2 $1 $1
b(2)(3)
=> 2 3 $1

In fact, now that I think about it, maybe m4_lambda should be defined as pushdef
(tmp,m4_defer([$1])) rather than the following patch's pushdef(tmp,[$1]) (hmm, 
maybe m4_undefer is a better name - the macro is all about removing a layer of 
deferral, not adding one; the opposite action would be replacing the 
regex "[[$]" with "\1][" to add a layer of deferral).  Also, my next foray into 
functional meta-programming will probably be a Y-combinator in m4sugar, which 
works with m4_lambda to allow recursion over an anonymous macro.




From: Eric Blake <address@hidden>
Date: Fri, 16 Jan 2009 10:56:33 -0700
Subject: [PATCH] Add m4_lambda.

* lib/m4sugar/m4sugar.m4 (m4_lambda, _m4_lambda): New macros.
* doc/autoconf.texi (Looping constructs) <m4_map_args>: Mention
use of m4_lambda.
(Set manipulation Macros) <m4_set_map>: Likewise.
(Evaluation Macros) <m4_lambda>: Document new macro.
* NEWS: Likewise.
* tests/m4sugar.at (m4@&address@hidden, m4@&address@hidden, and
m4@&address@hidden): Test it.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog              |   12 ++++++++
 NEWS                   |    9 +++---
 doc/autoconf.texi      |   69 ++++++++++++++++++++++++++++++++++++++++++-----
 lib/m4sugar/m4sugar.m4 |   28 ++++++++++++++++---
 tests/m4sugar.at       |   35 ++++++++++++++++-------
 5 files changed, 126 insertions(+), 27 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 20cc56e..dc5fb47 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,15 @@
+2009-01-16  Eric Blake  <address@hidden>
+
+       Add m4_lambda.
+       * lib/m4sugar/m4sugar.m4 (m4_lambda, _m4_lambda): New macros.
+       * doc/autoconf.texi (Looping constructs) <m4_map_args>: Mention
+       use of m4_lambda.
+       (Set manipulation Macros) <m4_set_map>: Likewise.
+       (Evaluation Macros) <m4_lambda>: Document new macro.
+       * NEWS: Likewise.
+       * tests/m4sugar.at (m4@&address@hidden, m4@&address@hidden, and
+       m4@&address@hidden): Test it.
+
 2009-01-14  Ralf Wildenhues  <address@hidden>
 
        Ignore `set -e'-related failure of NetBSD sh.
diff --git a/NEWS b/NEWS
index 7eff140..c744c8a 100644
--- a/NEWS
+++ b/NEWS
@@ -26,9 +26,9 @@ GNU Autoconf NEWS - User visible changes.
    `autoreconf -I dir' option.
 
 ** The following documented m4sugar macros are new:
-   m4_chomp  m4_curry  m4_default_quoted  m4_esyscmd_s  m4_map_args
-   m4_map_args_pair  m4_map_args_sep  m4_map_args_w  m4_set_map
-   m4_set_map_sep  m4_stack_foreach  m4_stack_foreach_lifo
+   m4_chomp  m4_curry  m4_default_quoted  m4_esyscmd_s  m4_lambda
+   m4_map_args  m4_map_args_pair  m4_map_args_sep  m4_map_args_w
+   m4_set_map  m4_set_map_sep  m4_stack_foreach  m4_stack_foreach_lifo
    m4_stack_foreach_sep  m4_stack_foreach_sep_lifo
 
 ** The following m4sugar macros are documented now, but in some cases
@@ -1808,7 +1808,8 @@ Various bug fixes.
 -----
 
 Copyright (C) 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001, 2002,
-2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation,
+Inc.
 
 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
diff --git a/doc/autoconf.texi b/doc/autoconf.texi
index d619578..21c6d8b 100644
--- a/doc/autoconf.texi
+++ b/doc/autoconf.texi
@@ -183,7 +183,8 @@
 templates and an M4 macro package.
 
 Copyright @copyright{} 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000,
-2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software
+Foundation, Inc.
 
 @quotation
 Permission is granted to copy, distribute and/or modify this document
@@ -11179,7 +11180,8 @@ Looping constructs
 @end example
 
 In cases where it is useful to operate on additional parameters besides
-the list elements, the macro @code{m4_curry} can be used in @var{macro}
+the list elements, the macros @code{m4_curry} or @code{m4_lambda} can be
+used in @var{macro}
 to supply the argument currying necessary to generate the desired
 argument list.  In the following example, @code{list_add_n} is more
 efficient than @code{list_add_x}.  On the other hand, using
@@ -11187,7 +11189,7 @@ Looping constructs
 
 @example
 m4_define([list], [[1], [2], [3]])dnl
-m4_define([add], [m4_eval(([$1]) + ([$2]))])dnl
+m4_define([add], [m4_eval([($1) + ($2)])])dnl
 dnl list_add_n(N, ARG...)
 dnl Output a list consisting of each ARG added to N
 m4_define([list_add_n],
@@ -11201,6 +11203,8 @@ Looping constructs
   [,add([$1],m4_defn([var]))]))])dnl
 list_add_x([1], list)
 @result{}2,3,4
+m4_shift(m4_map_args([,m4_lambda([add([$1], [$1])])], list))
address@hidden,4,6
 @end example
 @end defmac
 
@@ -11270,8 +11274,9 @@ Looping constructs
 @code{m4_stack_foreach_lifo} starts with the current definition.
 @var{action} should not push or pop definitions of @var{macro}, nor is
 there any guarantee that the current definition of @var{macro} matches
-the argument that was passed to @var{action}.  The macro @code{m4_curry}
-can be used if @var{action} needs more than one argument, although in
+the argument that was passed to @var{action}.  The macros @code{m4_curry}
+or @code{m4_lambda} can be used if @var{action} needs more than one
+argument, although in
 that case it is more efficient to use @var{m4_stack_foreach_sep}.
 
 Due to technical limitations, there are a few low-level m4sugar
@@ -11337,15 +11342,25 @@ Evaluation Macros
 @defmac m4_curry (@var{macro}, @address@hidden)
 @msindex{curry}
 This macro performs argument currying.  The expansion of this macro is
-another macro name that expects exactly one argument; that argument is
+an anonymous macro that expects exactly one argument; that argument is
 then appended to the @var{arg} list, and then @var{macro} is expanded
-with the resulting argument list.
+with the resulting argument list.  If the argument is needed more than
+once, or in a position other than the final argument, then
address@hidden is a better choice.
 
 @example
 m4_curry([m4_curry], [m4_reverse], [1])([2])([3])
 @result{}3, 2, 1
 @end example
 
+Note that the implementation of @code{m4_curry} is more efficient than
+the following meta-programming construct, but has the same effect.
+
address@hidden
+m4_define([my_curry],
+[m4_lambda([$1(m4_shift($@@,)]m4_dquote([$][1])[)])])
address@hidden example
+
 Unfortunately, due to a limitation in M4 1.4.x, it is not possible to
 pass the definition of a builtin macro as the argument to the output of
 @code{m4_curry}; the empty string is used instead of the builtin token.
@@ -11468,6 +11483,43 @@ Evaluation Macros
 serve the same purpose, although it is less readable.
 @end defmac
 
address@hidden m4_lambda (@var{defn})
address@hidden
+The expansion of this macro is an anonymous macro whose definition is
address@hidden, ready for an argument list to be supplied for expansion.
+This macro is primarily useful in higher-order functional programming
+(since generally, a named macro is easier to use than an anonymous
+macro).  Note that the anonymous macro will always be passed at least
+one argument.  When using an anonymous macro inside the definition of
+another macro, care must be taken to distiguish between parameter
+expansion of the named macro and parameter expansion of the anonymous
+macro; @code{m4_dquote} can be helpful.
+
address@hidden
+m4_lambda([m4_eval([$1 + $2])])([3], [4])
address@hidden
+m4_define([add_five],
+  [m4_lambda([m4_eval(5+(]m4_dquote([$][1])[))])($@@)])dnl
+m4_define([add_n],
+  [m4_lambda([m4_eval([($1)]+(]m4_dquote([$][1])[))])])dnl
+add_five([1])
address@hidden
+add_five([2])
address@hidden
+add_n([4])([3])
address@hidden
address@hidden example
+
+Note that it is more efficient to use @code{m4_curry} than
address@hidden when creating an anonymous macro that performs argument
+currying.
+
+Unfortunately, due to a limitation in M4 1.4.x, it is not possible to
+pass the definition of a builtin macro as the argument to the output of
address@hidden; the empty string is used instead of the builtin token.
+This behavior is rectified by using M4 1.6 or newer.
address@hidden defmac
+
 @defmac m4_make_list (@var{arg}, @dots{})
 @msindex{make_list}
 This macro exists to aid debugging of M4sugar algorithms.  Its net
@@ -12141,7 +12193,8 @@ Set manipulation Macros
 @code{m4_map_args(address@hidden(address@hidden))} or
 @code{m4_set_foreach(address@hidden, [var],
 address@hidden(m4_defn([var]))])}.  It is possible to use @code{m4_curry}
-if more than one argument is needed for @var{action}, although it is
+or @code{m4_lambda} if more than one argument is needed for
address@hidden, although it is
 more efficient to use @code{m4_set_map_sep} in that case.
 @end defmac
 
diff --git a/lib/m4sugar/m4sugar.m4 b/lib/m4sugar/m4sugar.m4
index 556969f..f4525dd 100644
--- a/lib/m4sugar/m4sugar.m4
+++ b/lib/m4sugar/m4sugar.m4
@@ -4,7 +4,7 @@ divert(-1)#                                                  -*-
 Autoconf -*-
 # Requires GNU M4.
 #
 # Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
-# 2008 Free Software Foundation, Inc.
+# 2008, 2009 Free Software Foundation, Inc.
 #
 # This program is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -789,9 +789,13 @@ m4_define([m4_count], [$#])
 # original ARG list, then invokes MACRO.  For example:
 #   m4_curry([m4_curry], [m4_reverse], [1])([2])([3]) => 3, 2, 1
 # Not quite as practical as m4_incr, but you could also do:
-#   m4_define([add], [m4_eval(([$1]) + ([$2]))])
-#   m4_define([add_one], [m4_curry([add], [1])])
-#   add_one()([2]) => 3
+#   m4_define([add], [m4_eval([($1) + ($2)])])
+#   m4_define([add_one], [m4_curry([add], [1])($@)])
+#   add_one([2]) => 3
+#
+# Note that we could also use the slower definition:
+#   m4_define([m4_curry],
+#     [m4_lambda([$1(m4_shift($@,)]m4_dquote([$][1])[)])])
 m4_define([m4_curry], [$1(m4_shift($@,)_$0])
 m4_define([_m4_curry],               [[$1])])
 
@@ -894,6 +898,22 @@ m4_define([_m4_expand_],
 m4_define([m4_ignore])
 
 
+# m4_lambda(DEFN)
+# ---------------
+# Create a one-shot anonymous macro with definition DEFN.  The
+# expansion of this macro takes another argument list.  Note that DEFN
+# will always have at least one argument.  For example:
+#   m4_map_args([m4_lambda([:m4_eval([$1], [8])])],
+#               [7], [8], [9]) => :7:10:11
+# Not quite as practical as m4_incr, but you could also do:
+#   m4_define([add], [m4_eval([($1) + ($2)])])
+#   m4_define([add_one], [m4_lambda([add(]m4_dquote(
+#     [$][1])[, [1])])($@)])
+#   add_one([2]) => 3
+m4_define([m4_lambda], [m4_pushdef([$0], [$1])$0(_m4_popdef([$0])_m4_lambda])
+m4_define([_m4_lambda],                                         [$@)])
+
+
 # m4_make_list(ARGS)
 # ------------------
 # Similar to m4_dquote, this creates a quoted list of quoted ARGS.  This
diff --git a/tests/m4sugar.at b/tests/m4sugar.at
index 0d90ca2..008d0e0 100644
--- a/tests/m4sugar.at
+++ b/tests/m4sugar.at
@@ -2,8 +2,8 @@
 
 AT_BANNER([M4sugar.])
 
-# Copyright (C) 2000, 2001, 2002, 2005, 2006, 2007, 2008 Free Software
-# Foundation, Inc.
+# Copyright (C) 2000, 2001, 2002, 2005, 2006, 2007, 2008, 2009 Free
+# Software Foundation, Inc.
 #
 # This program is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -1228,11 +1228,11 @@ hi
 AT_CLEANUP
 
 
-## --------------------------------------- ##
-## m4_map_args{,_sep,_pair} and m4_curry.  ##
-## --------------------------------------- ##
+## --------------------------------------------------- ##
+## m4_map_args{,_sep,_pair}, m4_curry, and m4_lambda.  ##
+## --------------------------------------------------- ##
 
-AT_SETUP([m4@&address@hidden and m4@&address@hidden)
+AT_SETUP([m4@&address@hidden, m4@&address@hidden, and m4@&address@hidden)
 AT_KEYWORDS([m4@&address@hidden m4@&address@hidden m4@&address@hidden
 m4@&address@hidden)
 
@@ -1240,13 +1240,19 @@ dnl First, make sure we can curry in isolation.
 AT_CHECK_M4SUGAR_TEXT(
 [[m4_curry([m4_echo])([1])
 m4_curry([m4_curry], [m4_reverse], [1])([2])([3])
-m4_define([add], [m4_eval(([$1]) + ([$2]))])dnl
-m4_define([add_one], [m4_curry([add], [1])])dnl
-add_one()([4])
+m4_define([add], [m4_eval([($1) + ($2)])])dnl
+m4_define([add_one], [m4_curry([add], [1])($@)])dnl
+add_one([4])
+m4_lambda([m4_eval([($1) + ($2)])])([3], [4])
+m4_define([double], [m4_lambda([add(]m4_dquote([$][1])[,]m4_dquote(
+  [$][1])[)])($@)])dnl
+double([3]) double([4])
 ]],
 [[1
 3, 2, 1
 5
+7
+6 8
 ]])
 
 dnl Now, check that we can map a list of arguments.
@@ -1284,17 +1290,24 @@ plain active
 
 dnl Finally, put the two concepts together, to show the real power of the API.
 AT_CHECK_M4SUGAR_TEXT(
-[[m4_define([add], [m4_eval(([$1]) + ([$2]))])dnl
+[[m4_define([add], [m4_eval([($1) + ($2)])])dnl
 m4_define([list], [[-1], [0], [1]])dnl
+
 dnl list_add_n(value, arg...)
 dnl add VALUE to each ARG and output the resulting list
 m4_define([list_add_n],
-  [m4_shift(m4_map_args([,m4_curry([add], [$1])], m4_shift($@)))])
+  [m4_shift(m4_map_args([,m4_curry([add], [$1])], m4_shift($@)))])dnl
+list_add_n([1], list)
+list_add_n([2], list)
+m4_define([list_add_n], [m4_shift(m4_map_args(
+  [,m4_lambda([add([$1], ]m4_dquote([$][1])[)])], m4_shift($@)))])dnl
 list_add_n([1], list)
 list_add_n([2], list)
 ]], [[
 0,1,2
 1,2,3
+0,1,2
+1,2,3
 ]])
 
 AT_CLEANUP
-- 
1.6.0.4