Tail call elimination

classic Classic list List threaded Threaded
83 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

Tail call elimination

Pete Dietl
What do you all think about me attempting to implementing tail call elimination for recursive make functions? This combined with the proposed (let) construct would be rather powerful.

I did the first 10 exercises in Advent of Code 2019 in Make. but ran into problems with blowing the stack from recursion.
Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Daniel Herring-2
Hi Pete,

I like your enthusiasm and understand the benefit.  If this can be
done cleanly, then why not?

However, I am still vaguely uneasy about the idea.  I don't think Make
will ever be a first-class programming language.  Prolog was a better
general-purpose language, but more people use Make because it is a
domain-specific tool.  Traditional Make has a certain simplicity that
makes it fairly easy to read and to machine generate.  As Make becomes
Turing-complete, it may loose these properties and grow in complexity.

How would you debug this?  Do parallel builds?  Do distributed builds?
Optimize build times?  etc.


Maybe it would be more useful to develop a protocol for invoking external
programs and including their results in the build rules?  Something like
the support for generating build dependencies, with cleaner semantics and
a direct way to run multiple times in a build.  For example, when a code
generator like Qt's moc or uic is run, it could also generate a rule
update that causes Make to compile and link the results.

This might give full general semantics (invoke your language of choice)
while preserving simplicity (communicate simple Make rules).

If we do want Make to be Turing-complete, then it may be better to link in
an embedded language (Guile, Lua, Python, ...), rather than building a new
ad-hoc language.

- Daniel


On Mon, 11 May 2020, Pete Dietl wrote:

> What do you all think about me attempting to implementing tail call elimination for recursive make functions? This combined with the proposed (let) construct would be rather powerful.
>
> I did the first 10 exercises in Advent of Code 2019 in Make. but ran into problems with blowing the stack from recursion.
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Tim Murphy-4
Yes we do want make to be a first class language and have had to put up with it being a b*** a*** to do computations and impossibly slow to use $shell.

Regards,

Tim

On Mon, 11 May 2020, 20:47 Daniel Herring, <[hidden email]> wrote:
Hi Pete,

I like your enthusiasm and understand the benefit.  If this can be
done cleanly, then why not?

However, I am still vaguely uneasy about the idea.  I don't think Make
will ever be a first-class programming language.  Prolog was a better
general-purpose language, but more people use Make because it is a
domain-specific tool.  Traditional Make has a certain simplicity that
makes it fairly easy to read and to machine generate.  As Make becomes
Turing-complete, it may loose these properties and grow in complexity.

How would you debug this?  Do parallel builds?  Do distributed builds?
Optimize build times?  etc.


Maybe it would be more useful to develop a protocol for invoking external
programs and including their results in the build rules?  Something like
the support for generating build dependencies, with cleaner semantics and
a direct way to run multiple times in a build.  For example, when a code
generator like Qt's moc or uic is run, it could also generate a rule
update that causes Make to compile and link the results.

This might give full general semantics (invoke your language of choice)
while preserving simplicity (communicate simple Make rules).

If we do want Make to be Turing-complete, then it may be better to link in
an embedded language (Guile, Lua, Python, ...), rather than building a new
ad-hoc language.

- Daniel


On Mon, 11 May 2020, Pete Dietl wrote:

> What do you all think about me attempting to implementing tail call elimination for recursive make functions? This combined with the proposed (let) construct would be rather powerful.
>
> I did the first 10 exercises in Advent of Code 2019 in Make. but ran into problems with blowing the stack from recursion.
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Paul Smith-20
In reply to this post by Pete Dietl
On Mon, 2020-05-11 at 14:01 -0500, Pete Dietl wrote:
> What do you all think about me attempting to implementing tail call
> elimination for recursive make functions? This combined with the
> proposed (let) construct would be rather powerful.

If it's straightforward it doesn't bother me.  I'd have to see the code
involved.  It seems likely that it would be sufficient to require
copyright assignment.

As mentioned by Daniel I'm uneasy about, basically, inventing a
completely new, fully functional language in make.  We already have
plenty of those.

I suspect it's not what Tim has in mind :) but for what it's worth, GNU
make has supported using Guile as an extension language since GNU make
4.0 (2013).  Making simple enhancements and performance improvements to
make's language is fine but if people REALLY need a full language I
think an extension for an existing language is a better bet.


Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
Indeed I understand these concerns.
So the consensus seems to be that I may go ahead and attempt to implement this.

Other than the (let) and tail call optimization, I would like to know your thoughts about
adding something like $(expr ) to evaluate integer expressions and comparisons.
Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
And I swear that's the last thing I want. :)
Reply | Threaded
Open this post in threaded view
|

Dependencies from moc (was Re: Tail call elimination)

Edward Welbourne-3
In reply to this post by Daniel Herring-2
Daniel Herring (11 May 2020 21:46) wrote, inter alia,
> For example, when a code generator like Qt's moc or uic is run, it
> could also generate a rule update that causes Make to compile and link
> the results.

For reference, Qt6's moc (the Qt project's current dev branch) supports
dependency generation:

    .../path/to/moc --output-dep-file ../function-with-attributes.h -o test.moc

creates test.moc as generated source and test.moc.d containing the line

    test.moc: ../function-with-attributes.h

there's also --dep-file-path and --dep-file-rule-name to control the
output path and the rule name

        Eddy.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Jouke Witteveen
In reply to this post by Pete Dietl
On Mon, May 11, 2020 at 11:33 PM Pete Dietl <[hidden email]> wrote:
>
> Indeed I understand these concerns.
> So the consensus seems to be that I may go ahead and attempt to implement this.
>
> Other than the (let) and tail call optimization, I would like to know your thoughts about
> adding something like $(expr ) to evaluate integer expressions and comparisons.

Not that my opinion should carry any weight, but I do not like the
idea of adding an arithmetic context to make. It should not be
necessary for the use-cases of make. Bash has an arithmetic context,
and while it works (and is useful), it sort of sticks out like a sore
thumb design-wise [1].

I did not understand the concerns regarding Turing completeness.
Unless I am overlooking something, make has been Turing complete at
least as long as it has $(call).

Regards,
- Jouke

[1] It's weirder than you may think:
https://mywiki.wooledge.org/ArithmeticExpression

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
> It should not be necessary for the use-cases of make

I assert that arithmetic functionality does have use-cases in Make.
Beyond building, I use Make for packaging my software and running tests.
I often find that it would be useful to perform version comparisons
and other simple packaging things.

I sometimes get into scenarios in more complex Makefiles where I want
to perform sanity checks on versions that users pass in via
environmental variables and the like.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Tim Murphy-4
I have often wanted to auto generate targets with progressive numbers to ensure uniqueness or count the number of times a particular macro is used and most especially to compare two numbers to see if they are numerically greater, less or equal.

Example: generating rules from potentially very long lists of targets - you can end up with a list that is longer than even the generous limit for command lines on Linux and much too long for Windows so if you can do arithmetic you can chop the list into sizes that can be dealt with.   Doing it with 'x' es to represent numbers as in the GMSL was gross.

Regards,

Tim

On Mon, 18 May 2020, 18:57 Pete Dietl, <[hidden email]> wrote:
> It should not be necessary for the use-cases of make

I assert that arithmetic functionality does have use-cases in Make.
Beyond building, I use Make for packaging my software and running tests.
I often find that it would be useful to perform version comparisons
and other simple packaging things.

I sometimes get into scenarios in more complex Makefiles where I want
to perform sanity checks on versions that users pass in via
environmental variables and the like.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
Yeah I was thinking something like:

VERSION     := 1.3.0
OLD_VERSION := 1.2.0

EMPTY :=
SPACE := $(EMPTY) $(EMPTY)

ver_is_less_than = $(strip \
    $(let \
        ( \
            (major1 $(word 1,$(subst .,$(SPACE),$1))) \
            (minor1 $(word 2, ...)) ... \
        ) \
        $(if $(expr $(major1) <= $(major2) \
            1, \
            $(if $(expr $(minor1) < $(minor2) ...))))))

ifneq ($(call ver_is_less,$(VERSION),$(OLD_VERSION)),)
    ...
endif

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Paul Smith-20
In reply to this post by Pete Dietl
On Mon, 2020-05-11 at 16:32 -0500, Pete Dietl wrote:
> I would like to know your thoughts about adding something like $(expr
> ) to evaluate integer expressions and comparisons.

I have no problem with some basic math facilities.  We already have
functions like $(word ...), $(words ...), and $(wordlist ...), which
sort of need math to be fully useful.

Adding in some simple comparison operators seems reasonable to me.

>         $(if $(expr $(major1) <= $(major2) \

I assume the missing ")," at the end of this was an oversight?



Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
Yes
Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Jouke Witteveen
In reply to this post by Paul Smith-20
On Mon, May 18, 2020 at 8:50 PM Paul Smith <[hidden email]> wrote:
>
> On Mon, 2020-05-11 at 16:32 -0500, Pete Dietl wrote:
> > I would like to know your thoughts about adding something like $(expr
> > ) to evaluate integer expressions and comparisons.
>
> I have no problem with some basic math facilities.  We already have
> functions like $(word ...), $(words ...), and $(wordlist ...), which
> sort of need math to be fully useful.

Each of these has an obvious 'output', which is not the case for
something like a comparison operator. This is also an objection
against $(eq) and $(not), which are hidden behind the EXPERIMENTAL
compilation flag.

> Adding in some simple comparison operators seems reasonable to me.
>
> >         $(if $(expr $(major1) <= $(major2) \
>
> I assume the missing ")," at the end of this was an oversight?

Note that version comparison can quickly get rather non-trivial. For
that reason, I would advise against implementing it in make. Instead,
simply use a dedicated program via $(shell). On my Arch Linux system,
I have a vercmp program tailored to this exact use case. Note that the
return value of a call to $(shell) is available in $(.SHELLSTATUS).

Otherwise, POSIX prescribes an expr command, so with:
expr = $(shell expr '$1')
you can already do $(call expr,2 * 3 + 5).

Regards,
- Jouke

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
> Each of these has an obvious 'output', which is not the case for
> something like a comparison operator. This is also an objection
> against $(eq) and $(not), which are hidden behind the EXPERIMENTAL
> compilation flag.

I think the convection is that an empty string is false while a
non-empty string is true.

> Otherwise, POSIX prescribes an expr command, so with:
> expr = $(shell expr '$1')
> you can already do $(call expr,2 * 3 + 5).

Ooh I didn't know about that.
That seems like a good alternative.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
Speaking of

> return value of a call to $(shell) is available in $(.SHELLSTATUS).

I think it would be a nice addition to have some global setting where
any failed $(shell )
command automatically fails Make.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Pete Dietl
Also, I think an advantage of an $(expr) command is that we can have
it return an empty string on false,
whereas with shell we have to transform the output conditionally based
on whether we are performing arithmetic
or comparison...

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Tim Murphy-4
In reply to this post by Pete Dietl
$(shell) causes severe parse performance problems in large makefiles unless you use it extremely sparingly.

[insert strong expression of frustration at make's deficiencies being treated as blessed] :-)

Regards,

Tim




On Mon, 18 May 2020 at 19:18, Pete Dietl <[hidden email]> wrote:
> Each of these has an obvious 'output', which is not the case for
> something like a comparison operator. This is also an objection
> against $(eq) and $(not), which are hidden behind the EXPERIMENTAL
> compilation flag.

I think the convection is that an empty string is false while a
non-empty string is true.

> Otherwise, POSIX prescribes an expr command, so with:
> expr = $(shell expr '$1')
> you can already do $(call expr,2 * 3 + 5).

Ooh I didn't know about that.
That seems like a good alternative.

Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Paul Smith-20
In reply to this post by Jouke Witteveen
On Mon, 2020-05-18 at 21:05 +0200, Jouke Witteveen wrote:

> On Mon, May 18, 2020 at 8:50 PM Paul Smith <[hidden email]> wrote:
> >
> > On Mon, 2020-05-11 at 16:32 -0500, Pete Dietl wrote:
> > > I would like to know your thoughts about adding something like
> > > $(expr
> > > ) to evaluate integer expressions and comparisons.
> >
> > I have no problem with some basic math facilities.  We already have
> > functions like $(word ...), $(words ...), and $(wordlist ...),
> > which sort of need math to be fully useful.
>
> Each of these has an obvious 'output', which is not the case for
> something like a comparison operator.

We should be sure to not talk past each other.  There are at least 3
different sets of functionality I think people are referring to:

* Math operators (+ - * / %)
* Integer comparison (< > == != >= <=)
* String comparison (eq ne le ge gt lt)

Then there are specialized operations such as semver-based version
comparison operators etc.

I was talking specifically about math functions in the above paragraph:
the word* functions resolve to integers or take integers as arguments:
this behavior naturally leads one to expect that there is a way to
manipulate integers in GNU make functions... which there is not (fancy
tricks notwithstanding).

> This is also an objection against $(eq) and $(not), which are hidden
> behind the EXPERIMENTAL compilation flag.

It doesn't matter what the output is, IMO.  Boolean expressions in GNU
make are quite trivial: empty string is false, anything else is true.

So any comparison operator simply has to expand to the empty string for
false any any non-empty value for true.  That could be a pre-defined
value like "t" (for lispy folks) or "true" or we could arbitrarily
choose one of the operands or whatever.

For integer comparison this is quite simple.

String comparisons are much harder because you run into issues like
locale (would it just be UTF-8 comparison), dealing with whitespace
(GNU make doesn't interpret quote characters: do we just say we don't
support comparing strings containing whitespace?), etc. etc.

And of course version comparison is a whole other level given all the
different ways it can be done.

I don't think we should discuss built-in string or version comparison,
and should restrict ourselves to discussing math, and possibly integer
comparisons.


Reply | Threaded
Open this post in threaded view
|

Re: Tail call elimination

Paul Smith-20
In reply to this post by Jouke Witteveen
On Mon, 2020-05-18 at 21:05 +0200, Jouke Witteveen wrote:
> Otherwise, POSIX prescribes an expr command, so with:
> expr = $(shell expr '$1')
> you can already do $(call expr,2 * 3 + 5).

Please remember not every user of GNU make has access to a POSIX
environment.

I'm not suggesting we re-implement POSIX shell, coreutils, etc. inside
GNU make.  But, there may be a way to get a lot of bang for relatively
little buck, portability-wise.

It's at least worth discussing.


12345