On Sun, May 18, 2025 at 08:05:21AM -0400, Nikolaos Chatzikonstantinou wrote:
> > And speaking of Turing complete, Doug McIlroy has an interesting demo
> > at how not only is m4 Turing complete with all of its builtins, but if
> > you strip it down to JUST the define macro, it is still Turing
> > complete:
> >
> > https://www.tuhs.org/mailman3/hyperkitty/list/t...@tuhs.org/thread/7ZRYUMZ2QNKE24QWUFT7MRK74COT7BIQ/
>
> I only briefly skimmed over it, it has some cool techniques. They
> definitely went the academic route to prove this by creating a model
> for arithmetic. I prefer the hand-wavy route: m4 is turing complete
> merely by supporting syscmd(). I want to share my own m4 code that I
> wrote when I studied m4 to fix issues with Guile's Autotools macros
> (haven't gotten around to that yet) Once I managed to implement lambda
> functions in a language that didn't originally support them I was
> pretty convinced of its coolness. I also managed to cram in currying,
> in a way completing a challenge mentioned by Kenneth J. Turner in
> "Exploiting the m4 Macro Language":
>
> > Unfortunately a single Curry macro cannot be defined since the number of
> > parameters to be fixed must be known.
>
> I amused the author by e-mailing him my solution. M4 has enough
> syntactic manipulation power that you can implement a lot of
> functional programming in it, like foldr and so on. I actually think
> it's a good tool to teach syntactic manipulation to talented students,
> *especially* if we can get an IDE (debugger?) around it, that shows
> all the steps of expansion. Of course debugmode() can do this, but
> it's a bit more technical than I'd like it to be.
>
> --- m4 source, cut here ---
>
> define(apply,`ifelse($1,`',`',$1(shift($@)))')
I don't see "apply" used in the rest of your example. Why is it here,
and does it even do what you thing it should?
If you meant for apply(`foo', 1, 2, 3) to expand to foo(1) foo(2)
foo(3), then it should probably be:
define(`apply', `ifelse(`$2',,,
`$1(`$2')`'apply(`$1', shift(shift($@)))')')
>
> define(id, $@)
> define(
> peel,
> `ifelse(eval($1 == 0),1,`id(``$2'')',eval($1 ==
> 1),1,`id(`$2')',`peel(decr($1),$2)')')
Slightly more efficient to drop the evals, and declare this as:
define(`peel', `ifelse($1, 0, `id(``$2'')',
$1, 1, `id(`$2')', `peel(decr($1),$2)')')
>
> define(
> randhex,
> `esyscmd(`od -N$1 -An -tx1 /dev/urandom | tr -d " \n"')')
This depends on GNU m4. Why is an incrementing counter not good
enough that you need to risk arbitrary collisions with a pseudo-random
string instead? And if you really need random macro characters with
just POSIX m4 (rather than depending on the GNU extension of esyscmd),
you can (ab)use mkstemp() for that purpose, along the lines of:
# randalnum() - produce 6 bytes of psuedo-random alphanumerics
define(`randalnum', `_randalnum(mkstemp(`m4XXXXXX'))')
define(`_randalnum', `syscmd(`rm -f $1')substr(`$1', 2)')
>
> define(
> lambda__aux,
> `define($1,$2)`$1'')
>
> define(
> lambda,
> `peel(3,``lambda__aux('lambda_``''`randhex(5), ``$1'')'')')
Couldn't this also be written with just peel(2) and one less layer of
inner quoting:
define(`lambda', `peel(2, `lambda__aux('lambda_``''`randhex(5), ``$1'')')')
>
> # curry(f,arg1,...,argn)
> # Partially applies arg1, ..., argn to f.
> # Note that there must be at least one argument, i.e. n >= 1.
> define(
> curry,
> `lambda(`$1(shift($@),'$`'@`)')')
Here's how the m4 manual declared a version of curry:
divert(`-1')
# curry(macro, args)
# Expand to a macro call that takes one argument, then invoke
# macro(args, extra).
define(`curry', `$1(shift($@,)_$0')
define(`_curry', ``$1')')
divert`'dnl
Writing curry() in m4 is relatively easy. Writing a truly generic
lambda() that can define an anonymous m4 macro is much tougher,
because of the inability to easily generate '$1' and friends into the
macro body without having it be prematurely expanded. In the
literature, I have seen reference to the "M5" language, where writing
lambda functions was easier because that language specifically treats
"$$1" in a macro body as expanding to literal "$1" (so writing macros
to write other macros gets a whole lot easier), unlike m4 where it is
a literal "$" followed by the immediate expansion of "$1". One of my
vague ideas on branch-2.0 was to implement the ability for GNU m4 to
implement the M5 language (although I'd have to actually research if
there are any publicly accessible implementations of M5 to compare
against, more than just the vague reference in that document I read).
--
Eric Blake, Principal Software Engineer
Red Hat, Inc.
Virtualization: qemu.org | libguestfs.org
