dunny

Hi all,

I've been recently reliving my youth by writing a logo interpreter - using
only turtle graphics though. While I can interpret very complex expressions and
produce nice drawings, I am thinking about extending the vocabulary. I've read
about UCBLogo, and it seems to be the Logo I'd like to use as a model.

Is there a spec for this language version anywhere? I'd prefer to get my
hands on a BNF spec - I realise that there is no standard spec for Logo (been
googling for a few days now), so I thought I might have more success finding a
spec for one of the more mainstream implementations.

Anyone?

--
Paul Dunn AKA Dunny
ICQ: 284648388 - AIM: ZXDunny - Y!: Dunny291073
http://homepage.ntlworld.com/paul.dunn4/

bh

"Dunny" <paul.dunn4@ntlworld.com> writes:


Nope, sorry. There's a reference manual, at
http://www.cs.berkeley.edu/~bh/usermanual
and if you download the complete ucblogo distribution from
http://www.cs.berkeley.edu/~bh/logo.html
it includes a file called plm (in the source directory) with a Program Logic
Manual about the evaluator. That's it for do***entation, unless you count
Chapter 5 of _Structure and Interpretation of Computer Programs_, from which
I stole the overall design.

It'd be hard to do a really helpful BNF, anyway. It would have to include
things like

<proc call> ::= <name-of-proc-with-0-default-inputs> |
<name-of-proc-with-1-default-input> <expr> |
<name-of-proc-with-2-default-inputs> <expr> <expr> |
<name-of-proc-with-3-default-inputs> <expr> <expr> <expr> |
... |
( <name-of-proc-that-can-take-0-inputs> ) |
( <name-of-proc-that-can-take-1-input> <expr> ) |
( <name-of-proc-that-can-take-2-inputs> <expr> <expr> ) |
( <name-of-proc-that-can-take-3-inputs> <expr> <expr> <expr> ) |
...

If you just said <proc-name> <expr>* that wouldn't help you parse things like
foo baz 1 2 3 4 5
for which you need to know the arity of foo and baz.

ian bicking

I think there's a lack of spec in part because it would be such a boring
spec. I believe the UCBLogo manual describes the tokenizing procedure,
including some of the compromises it makes.

Once you have a list of tokens, the parsing stage is highly minimal.
[]'s are used to create nested lists, just like you'd expect, and
there's the TO form. Maybe the BNF is:

object := list | word | evaluation
list := "[" objects* "]"
evaluation := "(" word objects* ")"
to := "TO" word signature "\n" objects* "\n" "END"
signature := variable* | variable* integer
variable := ":" word | word

I think that actually describes UCBLogo fairly completely, and other
Logos are close though they might have a few more special forms, or
allow for a little more generality (e.g.,
((procedure.producing.procedure) args) -- i.e., second-order functions,
which I don't believe are supported in UCBLogo).

The infix operators are a little fuzzy, and in my experience cause
problems parsing -- does setxy 10 -12 mean move to 10, -12, or does it
mean move to -2, and the second argument is missing? I chose the
second; maybe by tokenizing "-12" as a single (negative) number you
could achieve the first (so "-12" and "- 12" would be semantically
different).


In the end there's two kinds of parsing -- you can parse according to
that BNF, but then there's a sort of parsing that can only happen at the
interpretion phase. This is where infix operators come into play, as
well as the separation of the stream of tokens into specific procudure
calls, e.g. "FD 10 RT 90" is turned into (FD 10) (RT 90) -- but until
you know that FD takes one argument, you don't know how to parse that.

The Logo interpreter I wrote (PyLogo: pylogo.org) is a pretty
easy-to-read interpreter, I think. Much easier to read than something
implemented in C, at least. You might find that helpful to look at.

Ian


LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum

bh

Ian Bicking <Use-Author-Address-Header@[127.1]> writes:

UCBLogo, at least, doesn't do syntax parsing (as opposed to tokenizing)
at all until the instruction is run for the first time, because of the
procedure-arity problem. So there isn't a first phase of BNF-ish parsing
and a second phase of arity resolution; it happens all at once. (And the
resulting parse tree is saved, so repeated invocations of a procedure
don't have to reparse each time.)

dunny

In news:9B5E6C54-89DD-11D8-8E99-00039340E3F8@colorstudy.com,
Ian Bicking <Use-Author-Address-Header@[127.1]> typed:


Thanks for that - it makes sense. I was aware that there was a large amount of
"other" language/ability underlying the turtle of my youth, but I was a little
baffled as to what "sense" it should make.

For example, my old logo would allow

Repeat 36 [PenUp]

but not

Repeat 36 PenUp

Both of which, to me, are logically identical. Okay, you'd not actually *do*
that operation, but it illustrates the point - Repeat takes a numerical
expression and a thing to do; if you want to repeat more than one thing, then
use a list. Correct?


I use my own method of converting infix to postfix using float "stacks" and only
stop interpreting when I hit a symbol that can't be part of an expression, so I
guess I'm using the second type too :-)

I was wondering how well an RPN Logo would work... Kind of like a "ForthLOGO" if
you will. It'd remove the infix->postfix conversions, that's for certain.

As I only parse while interpreting, I find that mine works by calling the FD
handler, which calls the "getexpression" handler which stops when it encounters
RT (which can't be part of an expression) and then performs the FD before
returning to the interpreter main loop which continues with the RT. I may look
at p-code later when I understand the language more.

Thanks, that will indeed be very useful. Although I now code in x86 asm and
Borland Delphi (I know, I know...) the only really high level language I have
experience with is Sinclair BASIC - and LOGO is nothing like that. It's taking
time to get my head around how damned intricate it can be :-)

Thanks for your help,
D.

bh

"Dunny" <paul.dunn4@ntlworld.com> writes:

No, it's not just a matter of more than one thing.

Unlike many languages, which have a dozen different statement types, in
Logo there is really only one: the procedure call. So there's no
"repeat statement"; rather, REPEAT is a procedure, the same as FORWARD
is a procedure and + is a procedure.

In Logo, as in most languages, arguments to procedures are evaluated
before the procedure is called. So if you say
forward 3+2
then what the FORWARD procedure sees is the value 5, not the expression
that gave rise to that value.

Well, the same is true of REPEAT: Its arguments are evaluated before
the procedure is called. So the instruction
repeat 36 penup
tells Logo to evaluate the expression 36 (which is trivial; its value
is 36), *evaluate the expression PENUP*, and then call the REPEAT
procedure with those two values as inputs. But evaluating the
expression PENUP doesn't give rise to a value; it performs an action.
So the result will be that the pen is raised, once; then you get the
error message
PENUP didn't output to REPEAT
meaning that REPEAT was expecting PENUP to return a value, but it
didn't.

The point of putting the PENUP in square brackets isn't just that the
result is a list, but also that it's a *literal* list -- the things
inside the brackets are not themselves evaluated. In this case, the
list contains the five-letter word PENUP, not the result of calling
a procedure named PENUP.

ian bicking

On Apr 9, 2004, at 11:58 PM, (Brian Harvey) <bh@cs.berkeley.edu>:


Another way of thinking of this is that these expressions are
equivalent:

REPEAT 36 [FD 10 RT 10]
REPEAT 36 (LIST "FD 10 "RT 10)
REPEAT 36 (LIST "FD "10 "RT "10)
REPEAT 36 SE (LIST "FD 10) (LIST "RT 10)

And at least UCBLogo I believe would allow:

REPEAT 36 "PENUP

Since evaluating a single word is like evaluating a list with that word
as the only member.

Then lastly, it's important to realize that REPEAT is not a
specially-defined procedure, just something like:

TO REPEAT :num :block
WHILE [:num > 0] [RUN :block MAKE :num :num - 1]
END

--
Ian Bicking | ianb@colorstudy.com | http://blog.ianbicking.org

LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum

ian bicking

On Apr 9, 2004, at 11:57 PM, (Brian Harvey) <bh@cs.berkeley.edu>.


I'd say it's vague what the difference between tokenizing and syntax
parsing is. To me it's parsing when [[nested]] produces a list that
contains a list that contains "nested. If it was *just* tokenizing,
the result would be a list containing "[, "[, "nested, "], "]. So I
consider producing nested structures to be a kind of simple parsing.

I have thought about saving the "full" parsing -- or doing the full
parsing immediately (as Logo->Scheme does), but I wonder why it's
really necessary? Does it actually lead to any performance
improvement?

If you stick to straight interpretation, the expensive parts aren't
related to the parsing. Really, Logo is like a backwards Forth (as
Paul alluded to), except with slightly more formalism since procedure
objects have ******** arity. Forth never had performance problems
because you couldn't decompose the program into discrete expressions.
In the same way, once you have a procedure and you know how many inputs
it takes, is it really burdensome to grab that many values from forward
expressions?

I suppose once you've parsed it into expressions, you make available
all sorts of conventional optimizations that are targeted at languages
which are structured like that. This was no doubt important to
ObjectLogo, where they were building on their Lisp experience. But
does this mean anything for most of the other Logo implementations,
where they aren't performing any of these complex optimizations (nor
are they likely to)?

Or at least, I expect there's other optimizations that would provide a
more immediate benefit.

--
Ian Bicking | ianb@colorstudy.com | http://blog.ianbicking.org

LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum

gordon elliott

Of course the issue goes even beyond the strict language concept of the
"repeat" requiring a list the argument (wherein the list is really the
statement being repeated).

There is a bit of question about whether that argument might be
interpreted
as part of the parameters to the "repeat" statement to be executed
immediately. One could consceivably allow for repeat to take a second
argument as a quoted statement to be executed or define the language so
that
the statement was the remainder of the line. For example consider:


Repeat :a - correction [PenUp]

Where "correction" is a routine that returns some value decremented
from the
variable to determine the repeat count.

If the repeated statement could be just the remainder of the line, as
opposed specifically the second argument (as a statement) to "repeat",
we


Repeat :a - correction PenUp

Now we have a problem reading that statement. Just looking (without
preliminary knowledge) one would need considerable context of the
function
"correction" to determine which is the first argument, and which is the
remainder of the line. The "-" might be a unary value prefixing a
function
"correction" that takes an argument, and that could only be discovered
as
incorrect by then realizing that there is no usage of the returned value
from the unary '-'.

(e.g. was the statement really meant to say:

repeat :a [- correction [PenUp]]

or was it meant to say

repeat (:a - correction) [PenUp]
?)

The former interpretation has to have a return value from the unary '-'
and
thus cannot be legal.

But it is not so simple to just say that the rest of the line contains
the
statement to be repeated.

Of course it could literally be unambiguously parsed. There is a legal
parsing of

:a - correction

so it could be declared that parsing continues until there are no infix
or
otherwise unresolved arguments, and the unambiguous second
interpretation is
always arrived at. The probelm is that the statement more easily
becomes unr
eadable. The list format gives punctuation. And even though LOGO
attempts to
remove some of the distracting punctuation as compared to either LISP
(where
practically all punctuation is in the parentheses), or C wherein there
are
lots of details of punctuation (and thus BNF grammar specification
becomes
useful for understanding (and compiling)).

(I did that on purpose, by the way).


ON BNF:

Remember that LISP and LOGO more or less use a concept of a "reader"
that
parses the line at the first level for tokens. That is turned into a
list,
in the vary language that processes lists. That list is then
interpreted,
and LISP actually has less syntax that LOGO, in that LOGO has to parse
the
infix notation. Lisp (using parentheses as the list delimiter) simply
uses
the argument position exclusively. Rather far from "context free"
grammar
concepts. But of course the original "reader" is almost completely
context
free, since it knows absolutely nothing about the further intracacies
of the
language that will follow (in either LISP or LOGO).

-- Gordon

LogoForum messages are archived at:
http://groups.yahoo.com/group/LogoForum

bh

Ian Bicking <Use-Author-Address-Header@[127.1]> writes:


Well, of course it's just a constant factor speedup, and I've never tried to
measure it, but I know that the way a procedure speeds up the second time you
call it is noticeable in UCBLogo. Not if you just have one recursive
procedure, but if you have a big program with many procedures calling one
another.