A nice turtle reduction
I've been poking away at my Logo Interpreter for the past week. A whole bunch of changes went in - it now supports 64 built-in procedures (25 Turtle Graphics, 25 arithmetic/logical/comparisons, plus flow control, etc.), infix expressions (+-*/%^, etc.), and attempts to adhere to the UCBLogo and Apple II Logo "standards" where possible. (They are only "standards" as every Logo interpreter has its own quirks; it's a far less standardized language than BASIC.) To wrap up the tinkering today, I decided to tackle a "weird" bit of syntax - calling a procedure within parenthesis.
In most programming languages, () are grouping characters around expressions. This is true in Logo as well so you can do FORWARD (1+2)*3. But Logo also supports a convention for calling functions that may consume an unlimited number of arguments - e.g. (SUM 1 2 3 4). This required adding two new bits of logic - the syntax handling, and the function handling.
First, a special case for the ( operator so that if the first atom inside is an identifier, don't simply evaluate the contents but instead create a list from the following expressions. So (SUM 1 2 + 3 4) prepares a list [ 1 5 4 ] to hand off.
Second, the handling. I started looking in dread at the functions - how do I make SUM handle 2 (in a non-list context) or a list of arguments? I started off special-casing the function and caller to pass in "multi" mode. That was lame, when you need to do it for some large fraction of the 64 functions (SUM, PRODUCT, AND, OR, WORD, ...). An alternative would be to specify the "arity" as metadata for each function - so the evaluator would know before calling that SUM would consume two inputs in a sequence like PRODUCT 2 SUM 3 MINUS 12 and take care of the evaluation. This scales (and is probably the standard implementation technique).... but still wasn't elegant enough.
Instead, after staring at the functions, I decided to use a reduce (or fold) heuristic. So SUM only ever consumes two inputs from the input list. But when called in a parenthetical context, it keeps getting called until there are no inputs left in the list, e.g.
The nice thing is that for the built-in procedures like PRODUCT, SUM, WORD, AND, OR, etc. this does exactly what you'd expect.
What's neat though is that this instantly - with no other changes to the code - you can apply this to user defined functions. So you can do:
To avoid locking up when you call a function that consumes no inputs like (HIDETURTLE) I put in a check so that if no arguments are consumed the reduction terminates.
In most programming languages, () are grouping characters around expressions. This is true in Logo as well so you can do FORWARD (1+2)*3. But Logo also supports a convention for calling functions that may consume an unlimited number of arguments - e.g. (SUM 1 2 3 4). This required adding two new bits of logic - the syntax handling, and the function handling.
First, a special case for the ( operator so that if the first atom inside is an identifier, don't simply evaluate the contents but instead create a list from the following expressions. So (SUM 1 2 + 3 4) prepares a list [ 1 5 4 ] to hand off.
Second, the handling. I started looking in dread at the functions - how do I make SUM handle 2 (in a non-list context) or a list of arguments? I started off special-casing the function and caller to pass in "multi" mode. That was lame, when you need to do it for some large fraction of the 64 functions (SUM, PRODUCT, AND, OR, WORD, ...). An alternative would be to specify the "arity" as metadata for each function - so the evaluator would know before calling that SUM would consume two inputs in a sequence like PRODUCT 2 SUM 3 MINUS 12 and take care of the evaluation. This scales (and is probably the standard implementation technique).... but still wasn't elegant enough.
Instead, after staring at the functions, I decided to use a reduce (or fold) heuristic. So SUM only ever consumes two inputs from the input list. But when called in a parenthetical context, it keeps getting called until there are no inputs left in the list, e.g.
(SUM 1 2 3 4) turns into: procedure SUM, arguments [ 1 2 3 4 ]
call SUM with [ 1 2 3 4 ], yielding 3 and leaving [ 3 4 ]
push 3 onto the front of the list
call SUM with [ 3 3 4 ], yielding 6 and leaving [ 4 ]
push 6 onto the front of the list
call SUM with [ 6 4 ], yielding 10 and leaving []
the input list is empty, so return 10This is called folding or reducing over a function - in some languages, you can call reduce( myfunctions, inputs ... ) and it basically does this same thing, calling the function repeatedly until you run out.
The nice thing is that for the built-in procedures like PRODUCT, SUM, WORD, AND, OR, etc. this does exactly what you'd expect.
What's neat though is that this instantly - with no other changes to the code - you can apply this to user defined functions. So you can do:
to rect :l :h repeat 2 [ fd :l rt 90 fd :h rt 90 ] sum :l :h endThat's a fairly lame example - anything better?
(rect 20 30 40 50 60)
To avoid locking up when you call a function that consumes no inputs like (HIDETURTLE) I put in a check so that if no arguments are consumed the reduction terminates.
Comments
Post a Comment