TinyLogo

© 1999 Timothy Lipetz

Advanced Information

Topics on this page: TinyLogo Tokens and Data Types, TinyLogo Recursion and Tail Recursion, Advanced Logo Features not in TinyLogo, Space and Speed Limitations, Known Problems, Possible Future Extensions

See also: TinyLogo Main, Beginners Guide, Advanced Information, Built-in Procedures, Samples

The information on this page assumes that you have some background in programming and about Logo in general. (For beginners, see Logo web sites, Beginners Guide )

TinyLogo Tokens and Data Types

TinyLogo has a rigid set of data types. It is more rigid than most other Logo implementations. Here are the rules…

TinyLogo Recursion and Tail Recursion

Recursion

TinyLogo supports Recursion, which is a procedure that calls itself. As a quick guide to recursion, here are four rules that allow a recursive procedure to stop on its own:

  1. To be recursive, the procedure must contain a call to itself
  2. The procedure must take an argument.
  3. There must be a test (if, ifelse) against that argument, and for at least one value, the procedure goes through a path that does not recurse.
  4. When the procedure does recurse, it must change the value of its argument

As an alternative, you can write a procedure that does "runaway" recursion and just stop it yourself by pressing and holding the "Scroll Down" button.

Tail Recursion

There is one problem with ordinary recursion. TinyLogo must keep track of all the levels of the procedure as it calls itself. This consumes program memory referred to as the "call stack." After about 20 to 50 levels (depending on conditions), TinyLogo runs out of memory and will halt with a PocketC message saying, "ByteCode: #### Stack overflow -- out of memory." You can do a lot with 20 to 50 levels of recursion, but for some procedures it is not enough.

TinyLogo supports a special kind of recursion called, Tail Recursion, that avoids this problem. However, tail recursion can only be used if the recursive call is the last procedure call made in the procedure. Note: this is not the same as the last call listed in the procedure. So, for example, this procedure does tail recursion even though sum is listed after tailrecurse :

to tailrecurse :i print :i tailrecurse sum :i 2 end

TinyLogo automatically detects when tail recursion can be applied. You can tell when TinyLogo will be using tail recursion by listing the procedure with printprocedure or pp. TinyLogo will add an extra two spaces in the listing just before the tail recursive call.

With a procedure doing tail recursion, TinyLogo can run indefinitely. I have tested it for several thousand calls.

Mutual Recursion and Forward References

Sometimes a program needs two procedures each of which calls the other. This type of regular recursion is called Mutual Recursion or Indirect Recursion. TinyLogo can handle mutual recursion, however, there is a little trick to entering the procedures. Because TinyLogo expects to know all procedures (and the number of arguments they take) before you call them, we need to fool TinyLogo into accepting a "forward reference."

Say you want to enter procedure "A" which calls and is called by procedure "B."

Note: if you want to save "A" and "B" you must do a saveprocedure after each of the three steps above.

Advanced Logo Features not in TinyLogo

Certain design choices were made in the development of TinyLogo. Most of these choices were made to improve the performance during parsing or evaluation. Some of the choices have resulted in subtle differences between TinyLogo and some other Logos. Most of the differences are unimportant to beginning programmers, but for the more advanced user, I list them here.

Space and Speed Limitations

Speed

TinyLogo is roughly as fast as the old Apple and Texas Instruments versions of Logo. By modern standards that may seem slow, but you can still do a lot with that. In particular, watching the Turtle draw line by line can be more educational than not seeing the steps. In any case, if I can find ways to make it faster I will, but don't expect it to behave like a Pentium III :-}.

Nodes and Garbage Collection

TinyLogo, like most other Logos, manages memory using a technique called Garbage Collection which means recovering memory that is no longer being used. Memory is divided into chunks called Nodes. TinyLogo has 1800 nodes available. These nodes are used both to hold procedure definitions and to support processing. After each command (in interactive mode) TinyLogo reports how many nodes are still available.

When TinyLogo starts to run out of nodes, it finds a safe time to interrupt the current processing and do garbage collection. During the garbage collection, which can take several seconds, unused nodes are recovered and made available. When the garbage collection is done, the processing continues.

If you are in Turtle Mode when TinyLogo does garbage collection, you will see a "gc" in the lower left corner. Otherwise, you will see "<gc" at the beginning of the collection and the closing ">" at the end.

Any procedures defined or loaded into TinyLogo consume nodes which are not garbage collected. Obviously, loading procedures that use all 1800 nodes will leave none for doing the processing.

Other Space Limits

There are other memory space considerations when using TinyLogo.

As mentioned above, excess recursion can overrun the call stack.

Also, TinyLogo words use PocketC strings which use memory from the Palm OS. It is possible to run out of space because of many long words. (Note: I have yet to make this happen, but it is possible.)

Known Problems

  1. Attempting to manipulate a list containing procedure calls (by using first etc.) can confuse TinyLogo. This is not a supported feature and should be avoided.
  2. When redefining a procedure that is already defined, TinyLogo can fail to detect an opportunity for tail recursion and uses ordinary recursion instead. This is fixed by saving the procedure, restarting TinyLogo, and reloading the procedure.
  3. There is no value returned from ifelse, which means that print ifelse :logicvalue["a]["b] must be written as ifelse :logicvalue[print "a][print "b].

Possible Future Extensions

I share these tentative plans because if they are completed I will be using more keywords for the built-in procedures. I make no guarantees about future development, but for now you may want to avoid using the following symbols:

edit, debug, trace, continue, cont, depth, bye, verbose, fput, lput, quote, q, unload, uld, log, readchar, rc, readcharfast, rcf, char, setc, getc, sentence3, se3, sentence4, se4, textattr, second, scd, tick, time, date, user, clear, launch, reset

See also: TinyLogo Main, Beginners Guide, Advanced Information, Built-in Procedures, Samples