~technomancy/fennel

4 2

Fennel 0.2.1

Details
Message ID
<87imyfwbos.fsf@hagelb.org>
Sender timestamp
1548262867
DKIM signature
missing
Download raw message
Hey folks.

Yesterday Calvin just pushed out version 0.2.1 of Fennel, which fixed a
few bugs we found right after the 0.2.0 release:

* Add not= as an alias for ~=
* Fix a bug with in-scope? which caused pattern matching outer unification to fail
* Fix a bug with variadic ~= comparisons
* Improve error reporting for mismatched delimiters

Happy hacking!

-Phil

Optimizations in Lua code generation

Details
Message ID
<20190128024946.GA30978@calvin-p51.localdomain>
In-Reply-To
<87imyfwbos.fsf@hagelb.org> (view parent)
Sender timestamp
1548643786
DKIM signature
pass
Download raw message
Hi Everyone,

This is a heads up on some changes I have been working on for Fennel
having to do with code generation. Some discussion on IRC has been about
how the Fennel compiler (0.2.1) was generating anonymous functions that
are immediately called (IIFE, or Imediately Invoked Function Expression)
in many cases, even when not strictly necessary. There will probably
always be some need for these IIFEs, but they do result in slower, more
obtuse Lua, especially when this happens in a tight loop. The latest
Fennel has eliminated many of these IIFEs, and generates better quality
Lua.

As an example, we can look at some old code generated by Fennel for the
fennelview.fnl module, the module included with fennel for
pretty-printing data structures.

A clear example of IIFE removal is the generated code for the function
`get-nonsequential-keys` in fennelview.fnl.

The old generated Lua (commit 9dc6da3):

    local function get_nonsequential_keys(t)
      local keys = {}
      local sequence_length = get_sequence_length(t)
      for k in pairs(t) do
        local function _2_()
          if not sequence_key_3f(k, sequence_length) then
            return table.insert(keys, k)
          end
        end
        _2_()
      end
      table.sort(keys, sort_keys)
      return keys, sequence_length
    end

We can see an IIFE, _2_, that is called immediately inside a loop. We
can also see that it really doesn't need to be there.

The new generated Lua (commit cd2fc7c):

    local function get_nonsequential_keys(t)
      local keys = {}
      local sequence_length = get_sequence_length(t)
      for k in pairs(t) do
        if not sequence_key_3f(k, sequence_length) then
          table.insert(keys, k)
        end
      end
      table.sort(keys, sort_keys)
      return keys, sequence_length
    end

We can see that the IIFE has been removed, and the code is functionality
equivalent. There are actually many IIFE removals in fennelview.fnl when
comparing these 2 commits, several of them inside loops.

I'm posting this on the mailing list because I think it's cool, but also
because this changes code generation very significantly. I want to let
people know about it in case projects break when people pull the latest
version of fennel (not that they should). This also make hacks like
inserting 'break' and 'return' into fennel code easier, as there are
fewer anonymous functions to get in the way.

If your code does break with the newest Fennel, it may very well be a
new bug in the compiler, so feel free to report the bug and berate me on
IRC (unless you were relying on a strange hack, in which case you should
still let us know but don't create a new issue on GitHub.)

- Calvin

P.S. - Perhaps a more lispy/functional way to think about 
these IIFEs is as thunks, especially considering that they really
aren't a single expression.

Re: Optimizations in Lua code generation

Details
Message ID
<8736pciuiz.fsf@hagelb.org>
In-Reply-To
<20190128024946.GA30978@calvin-p51.localdomain> (view parent)
Sender timestamp
1548695028
DKIM signature
missing
Download raw message
Calvin Rose <calsrose@gmail.com> writes:

> This is a heads up on some changes I have been working on for Fennel
> having to do with code generation. Some discussion on IRC has been about
> how the Fennel compiler (0.2.1) was generating anonymous functions that
> are immediately called (IIFE, or Imediately Invoked Function Expression)
> in many cases, even when not strictly necessary.

Nice work! I only find the need to look at the compiled output
increasingly rarely, but "too many IIFEs" was basically my only
complaint about the readability when I did need to.

I loaded the new version into EXO_encounter-667, which is my largest
Fennel codebase. It removed all but 3 unnecessary IIFEs (at least, those
3 seemed unnecessary to me; maybe they in fact are needed.) But there
was one bug I found:

    (fn abc []
      (xyz (if (and c1 c2)
               true-value
               false-value)
           52))

^ This compiles to this:

    local function abc()
      if (c1 and c2) then
      else
      end
      return xyz(nil, 52)
    end
    return abc

Note that if you remove the 52 from the call to xyz, the bug goes
away. I haven't had time to look into the details yet, but I thought you
might find that helpful.

Thanks for making this change.

-Phil

Re: Optimizations in Lua code generation

Details
Message ID
<871s4wilwh.fsf@hagelb.org>
In-Reply-To
<8736pciuiz.fsf@hagelb.org> (view parent)
Sender timestamp
1548706206
DKIM signature
missing
Download raw message
Phil Hagelberg <phil@hagelb.org> writes:

> I loaded the new version into EXO_encounter-667, which is my largest
> Fennel codebase. It removed all but 3 unnecessary IIFEs (at least, those
> 3 seemed unnecessary to me; maybe they in fact are needed.)

Here are the IIFEs I saw; turns out there's 3:

    (let [layer (: map :addCustomLayer "player" 8)]
      (set layer.sprites [(unpack state.rovers)])
      (tset layer.sprites 0 state.probe)
      (set layer.draw (partial draw.player world state)))

    ;; local function _0_(...)
    ;;   local layer = map:addCustomLayer("player", 8)
    ;;   layer.sprites = {unpack(state.rovers)}
    ;;   layer.sprites[0] = state.probe
    ;;   local function _1_(...)
    ;;     return draw.player(world, state, ...)
    ;;   end
    ;;   layer.draw = _1_
    ;;   return nil
    ;; end
    ;; _0_(...)

The _1_ one is a partial; it looks like an IIFE but it's actually not;
just a generated function which is not immediately evaluated. It would
be nice to see this emitted instead:

    layer.draw = function(...) return draw.player(world, state, ...) end

But probably there's an implementation detail I'm missing that makes
this difficult. Also this is purely a readability concern and has no
effect on the actual runtime.

On the other hand, the outer _0_ IIFE above seems unnecessary because
the final form in the `let' body is a side-effect. Maybe we're not yet
to the point where we distinguish between those two, but it seems to me
that there's an opportunity to improve that in the future.

    (rover-forward set-mode state.selected
                   (if (love.keyboard.isDown "up") dt (- dt)))

    ;; local function _3_()
    ;;   if love.keyboard.isDown("up") then
    ;;     return dt
    ;;   else
    ;;     return ( - dt)
    ;;   end
    ;; end
    ;; return rover_forward(set_mode, state.selected, _3_())

In this case we are using IIFE in order to turn an `if' from a statement
into an expression. It could ideally be compiled into code like this:

    local _3_
    if love.keyboard.isDown("up") then
      _3_ = dt
    else
      _3_ = ( - dt)
    end
    return rover_forward(set_mode, state.selected, _3_)

But I'm not sure if that strategy is as generally-applicable as IIFE; I
haven't thought thru all the implications. The only other option I can
think of is to compile into a chain of and/or expressions, which I think
would be much less readable.

    (set state.laser (and (love.keyboard.isDown "space" "lctrl"
                                                "rctrl" "capslock")
                          (let [(x y w h) (: world :getRect state.probe)]
                            (laser.fire (+ x (/ w 2))
                                        (+ y (/ h 2) -6)
                                        state.probe.theta state world map
                                        [] [state.probe] 64))))

    ;; local function _4_()
    ;;   local x, y, w, h = world:getRect(state.probe)
    ;;   return laser.fire((x + (w / 2)), (y + (h / 2) + -6),
    ;;          state.probe.theta, state, world, map, {}, {state.probe}, 64)
    ;; end
    ;; state.laser = (love.keyboard.isDown("space", "lctrl", "rctrl",
    ;;   "capslock") and _4_())

This one is similar to the first case, except the body of the `let' is a
function call, so the compiler can't tell if it's a value or a
side-effect. In this case I think if the strategy from the previous case
can't be applied that an IIFE is pretty reasonable.

If you point me in the right direction I might be able to take a swing
at some of these.

-Phil

Re: Optimizations in Lua code generation

Details
Message ID
<20190128215346.GA1268@calvin-p51.localdomain>
In-Reply-To
<871s4wilwh.fsf@hagelb.org> (view parent)
Sender timestamp
1548712426
DKIM signature
pass
Download raw message
On Mon, Jan 28, 2019 at 12:10:06PM -0800, Phil Hagelberg wrote:
> Phil Hagelberg <phil@hagelb.org> writes:
> 
> > I loaded the new version into EXO_encounter-667, which is my largest
> > Fennel codebase. It removed all but 3 unnecessary IIFEs (at least, those
> > 3 seemed unnecessary to me; maybe they in fact are needed.)
> 

Thanks for the feedback, Phil.

Addressing the IIFEs you presented, the hard part about some of these
situations is that the compiler doesn't look inside functions before
compiling them (it is purely top down). For all cases, although your
intent is to return either nothing or a single value, imagine you were
returning multiple values. 

Your rover example:
>     (rover-forward set-mode state.selected
>                    (if (love.keyboard.isDown "up") dt (- dt)))
> 
>     ;; local function _3_()
>     ;;   if love.keyboard.isDown("up") then
>     ;;     return dt
>     ;;   else
>     ;;     return ( - dt)
>     ;;   end
>     ;; end
>     ;; return rover_forward(set_mode, state.selected, _3_())

The nicer code:
>     local _3_
>     if love.keyboard.isDown("up") then
>       _3_ = dt
>     else
>       _3_ = ( - dt)
>     end
>     return rover_forward(set_mode, state.selected, _3_)

What if (- dt) was replaced by (values (- dt) 100), or even (unpack
a-large-table)? Your proposed code would not work in those cases, while
the IIFE handles them quite nicely, albeit inefficiently. Since the
compiler doesn't yet look inside a function (does not backtrack), it
doesn't know that if returns at most 1 value  until the if has already
been compiled!  If the if statement was the first argument to
rover-forward, then opts.nval = 1 and no IIFE would be generated
(although perhaps the bug you found would be triggered).

As for addressing these issues, getting rid of the IIFEs is mostly a
matter of getting the special forms to properly detect and optimize
emission for various `opts`, and also making sure that forms recursively
compile sub forms with the best possible `opts` for optimizations.

The forms that have proved trickiest are the `if` special, which needs
to be turned into a statement in Lua from an expression in Fennel, and
all of the destructuring forms (let, set, local), which are used in many
places so should emit good code all the time. These are the two places
that were modified in the last commit, and I would be willing to bet are
the root of bugs but have potential for more optimizations.

The options that a special form can take are as follows.

- opts.tail - indicates a form is in tail position (can immediately
  return). This means in some circumstances we can just return without
  assigning to a local and return a "dud expression" ({returned =
  true}) to indicate that we have returned and the compiler doesn't need
  to emit a return statement. If we return a normal expression, the
  compiler will emit the return statement for us.

- opts.target - this indicates that the value we are compiling is the
  rvalue to some assignment (lvalue = rvalue). Similar to a tail, we can
  emit code to assign to target (a string) and return a dud expression. Note that target can
  be a multiple values, like "a, b, _2_, abc.def". If we return an expr
  object, the compiler will make the assignment for us.

- opts.nval - this an option dealing with multiple return values. It
  indicates how many of the returned expressions will be used (specials
  can return a sequence of expressions, as well as the usual single
  expression). If nval is a constant like 1, we know we can return a single
  expression and drop extras. If nval is 0, we can ignore all return
  values and return nothing. If we return the wrong number of return
  expressions, that's fine and the compiler will handle that as well.

Bugs pop up most often when special optimize these options incorrectly,
usually not emitting the required code when returning the "dud
expression".

Below are some invariants that are probably not held through the
compiler that I will look for after writing this email, but make sense
to me and should probably be enforced by compile1.

- if opts.tail is true, then no other options should be set.
- if opts.nval is 0, then no other options should be set.
- if opts.target is set, then opts.nval should be > 0.

For good code generation, the most common specials may need to optimize many
of these combinations. Unfortunately, this can be error prone.

A good place to start is probably the places I touched in the most
recent commits, namely the 'if' special and the destructure function.

- Calvin