#598 QUEUE and DEQUEUE don't work with some variable names

[Vilim]

> make "queue []
> queue "queue "item
< lput doesn't like queue as input in queue
> make "item []
> queue "item "abc
< lput doesn't like abc as input in queue

Proposed solution: edit queue.lgo and deque.lgo in logolib:

to queue :logolib.queue.queue :logolib.queue.item
make :logolib.queue.queue lput :logolib.queue.item thing :logolib.queue.queue
end

to dequeue :logolib.dequeue.queue
local "result
make "result first thing :logolib.dequeue.queue
make :logolib.dequeue.queue butfirst thing :logolib.dequeue.queue
output :result
end

I also attempted a more robust solution using macros:

.macro queue :queue :item
op (list "make (word "" :queue) "lput (quoted :item) "thing (word "" :queue))
end

.macro dequeue :queue
op (list "invoke (list "make (word "" :queue) "butfirst "thing (word "" :queue) "?) "first "thing (word "" :queue))
end

While this works for QUEUE, DEQUEUE seems to still execute its output instructionlist within its own context, but only when used as an argument to a procedure:

> make "queue [abc]
> show dequeue "queue
< q
> show :queue
< [abc]
> dequeue "queue
< You don't say what to do with abc in invoke
< [.maybeoutput apply :function :inputs]
> show :queue
< []

I assume this is a bug in the FMSLogo core.
While testing I once even encountered a strange behavior where the template (where the MAKE call is) was executed in the outer context even though the arguments to INVOKE were evaluated in the inner context:

> make "queue [abc]
> show dequeue "queue
< q
> show :queue
< []

But I couldn't reproduce it again.

[David Costanzo]

Good bug! "queue is a reasonable name for a queue, so it should work. Your first proposed solution is similar to what UCBLogo does: make the parameter names less likely to shadow the queue name.

I like your approach with the macro because it would make QUEUE/DEQUEUE work regardless of the queue's name. You code looks correct, so I agree that there's probably some deeper bug that prevents it from working.

[David Costanzo]

I opened Bug #599 to cover the bug in .MACRO that prevents DEQUEUE from being written as a macro.

[David Costanzo]

There's a similar problem in NAME, except that its parameter names were selected to be unlikely to shadow a programmer's names. If QUEUE/DEQUEUE is rewritten to be a marco, it makes sense that NAME should also be rewritten.

to name :name.value.input :name.variable.input
make :name.variable.input :name.value.input
end

[David Costanzo]

I have updated QUEUE and DEQUEUE to use the same parameter names used in UCBLogo in [r6112]. This does not fix the bug, but it mitigates the bug by making a conflict less likely. It also makes it so that a logo program that works in UCBLogo won't fail in FMSLogo and vice-versa. Even less likely parameter names could have been chosen, such as ones that include a space in their name, but I think there's value in have the same bug as UCBLogo until the bug is fixed.

I had hoped to fix this completely, but it looks unlikely that I'll fix the macro bug that prevents a complete fix before the next release of FMSLogo and I wanted to enable queues named "queue" in the next release (even if queues name "the.queue.name" now won't work).

[David Costanzo]

I fixed the macro bug, which enabled me to use Vilim's suggestion of converting QUEUE and DEQUEUE into macros to avoid the naming conflict. This is implemented in [r6130]. It will be available in FMSLogo 8.5.0.

When I used pure macros as Vilim provided, the procedures became much slower. I worked out a hybrid solution, similar in spirit to what the .MACRO documentation recommends. The general macros are only used when there's a naming conflict. Otherwise, the code looks a lot like it did before.

My performance test:

To PerfTest
  Local [q before]

  Make "before TimeMilli
  Repeat 100 [ Make "q [] Repeat 1000 [ Queue "q RepCount ] ]
  Print (Sentence [Total Queue Time] TimeMilli - :before [ms])

  Make "before TimeMilli
  Repeat 100 [ Make "q [1 2 3 4 5 6 7 8 9 10] Repeat 10 [ Ignore Dequeue "q ] ]
  Print (Sentence [Total Dequeue Time] TimeMilli - :before [ms])
End

As functions (the way FMSLogo used to do it)

Total Queue Time 1641 ms
Total Dequeue Time 13 ms

As simple macros

Total Queue Time 6355 ms
Total Dequeue Time 74 ms

As macros that do something simpler when there's no name conflict:

Total Queue Time 1753 ms
Total Dequeue Time 15 ms

This is still a little slower, even when people don't have conflicting queue names, but it's the cost of having procedures that work in every case. This makes me wonder if Brian Harvey knew about the bug and chose not to fix it for performance reasons.

[Vilim]

I spotted an interesting idiom in the new dequeue implementation! Is [first [x]] the most efficient way to construct a value that evaluates to x when fed into run regardless of the type of x? Better than using quoted?

[David Costanzo]

Vilim asks

Is [first [x]] the most efficient way to construct a value that evaluates to x when fed into run regardless of the type of x? Better than using quoted?

By my measurements, yes, it's faster. The outer list is necessary, so the difference is really between (FIRST (LIST :x)) and (QUOTED :x). Since FIRST and LIST are primitives, they're faster.

Here's an updated PerfTest that's more sensitive to DEQUEUE's performance. It uses non-words in the queue so that QUOTED does less computation.

To PerfTest
  Local [q original before]

  Make "before TimeMilli
  Repeat 100 [ Make "q [] Repeat 1000 [ Queue "q RepCount ] ]
  Print (Sentence [Total Queue Time] TimeMilli - :before [ms])

  Make "original []
  Repeat 100 [ Queue "original [] ]

  Make "before TimeMilli
  Repeat 1000 [ Make "q :original Repeat 100 [ Ignore Dequeue "q ] ]
  Print (Sentence [Total Dequeue Time] TimeMilli - :before [ms])
End

I ran the new PerfTest with the what I had committed in [r6130].

Total Queue Time 1383 ms
Total Dequeue Time 964 ms

Then I changed the last line of DEQUEUE to use QUOTED as:

  output (list quoted :the.item.value)

and got execution times like:

Total Queue Time 1389 ms
Total Dequeue Time 1234 ms

That said, I'm open to suggestions. I can attach a pre-release executable that has the macro bug fixed if you want to experiment yourself.

[Vilim]

If quoted was a primitive, it could just call maybe_quote...
If backtick was a primitive, making performant macros would be so much easier...

[David Costanzo]

Vilim writes:

If quoted was a primitive, it could just call maybe_quote...
If backtick was a primitive, making performant macros would be so much easier...

Both those statements are true. Similarly, I could have fixed this bug by making QUEUE and DEQUEUE primitives instead of macros. However, I try to avoid adding new primitives due to the compatibility risk. Any existing program which defines a procedure with the same name as the new primitive won't run on the new FMSLogo. This is a small risk, but I prefer no risk to a small risk.

The main reason I was concerned about performance of the new QUEUE and DEQUEUE is not because I wanted the procedures to run faster but because I didn't want them to run significantly slower than before. Performance degradation is also a compatibility risk.

[David Costanzo]

[r6141] fixes NAME using a similar strategy that I used for QUEUE and DEQUEUE. This will also be available in FMSLogo 8.5.0.