New Logo Interpreter [Help Required]

Hi,

This is my first post to the group, I am a keen fan of LOGO (and a
student, I used LOGO for a short while at school which inspired me to
start my latest project) I am making a new LOGO Interpreter, I
invisage a new LOGO implementation for 2008 and beyond, because LOGO
is stil a fantastic language for newcomers and also advanced users...
It can teach recursion, functions, fractals, simple building blocks
building up to huge possibilities etc

I have currently made the main interpreter in Visual Basic 6 (So the
interpreter is Windows only at the moment) I only used VB6 as it is
currently available to me at home and college so I have more time to
program the interpreter.

I plan to re-program the main interpreter in Python and Turtle
Graphics in PyGame to make the code portable, with the possibility of
a TkInter GUI to help with usability. I hope to re-implement the
project when I study Computer Science at university, hopefully
starting a new faster, better version of the interpreter then.

The following URL shows a quick screenshot of the interpreter:
http://img178.imageshack.us/img178/5...nterprezo8.png

At the moment I have the main [probably simple] problems with the
interpreter:
- You cannot define functions with text
string PRINT statements
- Function definitions don't work well
[Can't use functions inside REPEAT's etc]
- You cannot have nested loops [I know I
need to use recursion here, I just don't know /how/ to use recursion
here]
+ Lots of small little bugs/problems...

So, I am asking anyone who has had any experience in writing a LOGO
Interpreter for help, I possibly need the source to a small basic LOGO
implementation to get the basics of how a nested loop would work etc,
I am willing to share the source for my project if anyone is willing
to either join me on the project or would simply like to help.

Comments on my progress so far or just any general comments are also
welcome.

Thanks , Alex.

On Apr 10, 8:56 pm, alexmcn...@googlemail.com wrote:
> Hi,
>
> This is my first post to the group, I am a keen fan of LOGO (and a
> student, I used LOGO for a short while at school which inspired me to
> start my latest project) I am making a new LOGO Interpreter, I
> invisage a new LOGO implementation for 2008 and beyond, because LOGO
> is stil a fantastic language for newcomers and also advanced users...
> It can teach recursion, functions, fractals, simple building blocks
> building up to huge possibilities etc
>
> I have currently made the main interpreter in Visual Basic 6 (So the
> interpreter is Windows only at the moment) I only used VB6 as it is
> currently available to me at home and college so I have more time to
> program the interpreter.
>
> I plan to re-program the main interpreter in Python and Turtle
> Graphics in PyGame to make the code portable, with the possibility of
> a TkInter GUI to help with usability. I hope to re-implement the
> project when I study Computer Science at university, hopefully
> starting a new faster, better version of the interpreter then.
>
> The following URL shows a quick screenshot of the interpreter:http://img178.imageshack.us/img178/5...nterprezo8.png
>
> At the moment I have the main [probably simple] problems with the
> interpreter:
> - You cannot define functions with text
> string PRINT statements
> - Function definitions don't work well
> [Can't use functions inside REPEAT's etc]
> - You cannot have nested loops [I know I
> need to use recursion here, I just don't know /how/ to use recursion
> here]
> + Lots of small little bugs/problems...
>
> So, I am asking anyone who has had any experience in writing a LOGO
> Interpreter for help, I possibly need the source to a small basic LOGO
> implementation to get the basics of how a nested loop would work etc,
> I am willing to share the source for my project if anyone is willing
> to either join me on the project or would simply like to help.
>
> Comments on my progress so far or just any general comments are also
> welcome.
>
> Thanks , Alex.

Hi, Sorry the URL was incorrect, the screenshot URL can be accessed
below:
http://img178.imageshack.us/img178/5...nterprezo8.png

Thanks, Alex.

Hi, welcome to the group!

I was confused about what level of expertise to pitch an answer at until I
finally worked out that you live in a part of the world where "college" and
"university" aren't synonyms. :-)

The very best thing would be if you can dig up a copy of _Logo Works:
Challenging Programs in Logo_ (Solomon, Minsky, Harvey, eds., McGraw-Hill,
1986), because it includes a Logo interpreter written in Logo, which would
definitely help you understand the structure of an interpreter.

If I'm understanding your message correctly, one thing that's making it hard
for you is that you're representing a Logo instruction as a character string,
which has no structure beyond the individual characters. What you really want
is to represent an instruction as something like a Logo list:

? make "instruction [repeat 4 [fd 100 rt 90]]
? print count :instruction
3
? print first :instruction
fd
? print last :instruction
fd 100 rt 90
? print first (last :instruction)
fd

I don't know what VB gives you in the way of data structures, but I hope you
can achieve something at least roughly like this.

Then you want to write a procedure that can evaluate a single instruction
or expression. (An instruction is something like
print count :instruction
that takes an action; an expression is something like
count :instruction
that outputs a value.) This EVAL procedure has to handle special cases such
as numbers (just return the number itself), quoted words (return the word
without the initial quotation mark), etc. Otherwise, it's a procedure call.
The first thing in a procedure call is the name of a procedure. You have to
look up that name in a table of procedures, to find out how many inputs it
takes. Then call EVAL recursively that many times to get the input values,
and then call the procedure itself.

Procedure calls inside repeats shouldn't be different from procedure calls
anywhere else, since you'll just EVAL the second input to REPEAT repeatedly.

To call a user-defined procedure, you have to set up a table associating
the names of the inputs (from the procedure's title line) with the actual
input values (from the recursive EVAL calls), then just EVAL the body of
the procedure!

That may be too abstract for you -- maybe if you ask more specific questions?

On Apr 11, 5:22 am, b...@cs.berkeley.edu (Brian Harvey) wrote:
> Hi, welcome to the group!
>
> I was confused about what level of expertise to pitch an answer at until I
> finally worked out that you live in a part of the world where "college" and
> "university" aren't synonyms. :-)
>
> The very best thing would be if you can dig up a copy of _Logo Works:
> Challenging Programs in Logo_ (Solomon, Minsky, Harvey, eds., McGraw-Hill,
> 1986), because it includes a Logo interpreter written in Logo, which would
> definitely help you understand the structure of an interpreter.
>
> If I'm understanding your message correctly, one thing that's making it hard
> for you is that you're representing a Logo instruction as a character string,
> which has no structure beyond the individual characters. What you really want
> is to represent an instruction as something like a Logo list:
>
> ? make "instruction [repeat 4 [fd 100 rt 90]]
> ? print count :instruction
> 3
> ? print first :instruction
> fd
> ? print last :instruction
> fd 100 rt 90
> ? print first (last :instruction)
> fd
>
> I don't know what VB gives you in the way of data structures, but I hope you
> can achieve something at least roughly like this.
>
> Then you want to write a procedure that can evaluate a single instruction
> or expression. (An instruction is something like
> print count :instruction
> that takes an action; an expression is something like
> count :instruction
> that outputs a value.) This EVAL procedure has to handle special cases such
> as numbers (just return the number itself), quoted words (return the word
> without the initial quotation mark), etc. Otherwise, it's a procedure call.
> The first thing in a procedure call is the name of a procedure. You have to
> look up that name in a table of procedures, to find out how many inputs it
> takes. Then call EVAL recursively that many times to get the input values,
> and then call the procedure itself.
>
> Procedure calls inside repeats shouldn't be different from procedure calls
> anywhere else, since you'll just EVAL the second input to REPEAT repeatedly.
>
> To call a user-defined procedure, you have to set up a table associating
> the names of the inputs (from the procedure's title line) with the actual
> input values (from the recursive EVAL calls), then just EVAL the body of
> the procedure!
>
> That may be too abstract for you -- maybe if you ask more specific questions?

Hi Brian,

Wow, Cool to talk to you... :-)... And thanks for your help...
Firstly, Yeah I live in the UK, currently doing just an A-Level in
Computing at college (College is from ages 16-18 in the UK) but i'm
off to study CS at degree level in September... (I probably shouldn't
be writing an interpreter at this age, its just one of those things
i've allways wanted to do, so, I thought I would... and if it wasn't
LOGO it would be BASIC or Lisp I think (of course LOGO is lisp so I
get two challenges in one))

I looked for the book you mentioned... I can find it on Amazon UK but
its like £30 :-( And i'd have to order it from the US... Is there a
free ebook or electronic version online anywhere? I'd like to read it,
I just don't know whether I have the time to wait for the shipping
from the US.

Also, I think I should give a few specifics on how its working
allready so that you can possibly better help me, at the moment the
interpreter first splits the whole string of commands into an array,
it splits on a " " whitespace (ASCII code 32) character... once it has
done this there is a main procedure that the commands are passed
through, they are all evaluated at strings like you say which is
probably where my problems lie. The one problem I have with your
suggestion is that, it would mean essentially programming a lisp or
list orientated language... Is this needed for LOGO? I know it is
essentially LISP based but I was hoping just to store multiple repeats
in the same array string and just evaluate by first going to the
middle repeat E.g. REPEAT 30 [ REPEAT 20 [ REPEAT 10 [ ] ] ] and
working backwards <<< (outwards) until I got to the last REPEAT...
That is where my idea for recursion came from... The idea that you can
drill down into a function and then go back and back etc etc Hope that
makes sense, i'm usually bad at explaining stuff...

Maybe if I were to go down the route you suggested python would be a
bettr language... As it has more list orientated data structure (List,
Tuple) that would help in that regard (whereas VB just has Array &
Collection, You pretty much have to program a data structure if you
want it)

Anyway, Thanks for your help so far... One final point, If I won't be
able to get that book, is there a chance I could find something
similar that could teach me the basics? (preferably available for free
in electronic form)

Thanks again, Alex. :-)

alexmcneil@googlemail.com writes:
>off to study CS at degree level in September... (I probably shouldn't
>be writing an interpreter at this age, its just one of those things
>i've allways wanted to do [...]

There's no "should" about it -- the worst that'll happen is that it won't
be a perfect interpreter! :-)

>I just don't know whether I have the time to wait for the shipping
>from the US.

Sigh, okay, look in
http://www.cs.berkeley.edu/~bh/logoworks
and you'll find 21 jpegs of the relevant pages. They're not perfect, since
the book isn't bound in a way that allows for laying it flat on the scanner,
but it'll do. (Also, if I were more computer literate I'd have figured out
how to eliminate all the greyscale stuff so the files would be smaller!)

> The one problem I have with your
>suggestion is that, it would mean essentially programming a lisp or
>list orientated language... Is this needed for LOGO? I know it is
>essentially LISP based but I was hoping just to store multiple repeats
>in the same array string and just evaluate by first going to the
>middle repeat E.g. REPEAT 30 [ REPEAT 20 [ REPEAT 10 [ ] ] ] and
>working backwards <<< (outwards) until I got to the last REPEAT...

You can implement lists in pretty much any language that lets you manipulate
pointers. But I agree that VB isn't my implementation language of choice.
It'd be much easier if you did it in Lisp! That way you could focus your
attention on the interesting parts instead of having to invent basic data
structures.

Why are you so focused on REPEAT as a special case? For one thing, IF and
IFELSE and TEST and RUN all use the same kind of instruction list input as
REPEAT. But, more importantly, even without any of those, when you say

forward sum 20 30

the EVAL of that instruction requires an EVAL of the subexpression

sum 20 30

If you use infix arithmetic, it's just that much harder to find the right
subexpression to evaluate next.

>Anyway, Thanks for your help so far... One final point, If I won't be
>able to get that book, is there a chance I could find something
>similar that could teach me the basics? (preferably available for free
>in electronic form)

It depends what you mean by "basics." What you /really/ should read is the
best computer science book ever written, _Structure and Interpretation of
Computer Programs_ by Abelson and Sussman and Sussman, which will teach you
the hidden mysteries of interpreters. But it's not an easy read. But it
/is/ available free online:

http://mitpress.mit.edu/sicp/full-text/book/book.html

P.S. Be sure to come to the Eurologo conference next summer (2009) in Paris!

On Apr 12, 5:06*am, b...@cs.berkeley.edu (Brian Harvey) wrote:
> alexmcn...@googlemail.com writes:
> >off to study CS at degree level in September... (I probably shouldn't
> >be writing an interpreter at this age, its just one of those things
> >i've allways wanted to do [...]
>
> There's no "should" about it -- the worst that'll happen is that it won't
> be a perfect interpreter! :-)
>
> >I just don't know whether I have the time to wait for the shipping
> >from the US.
>
> Sigh, okay, look in
> * * * *http://www.cs.berkeley.edu/~bh/logoworks
> and you'll find 21 jpegs of the relevant pages. *They're not perfect, since
> the book isn't bound in a way that allows for laying it flat on the scanner,
> but it'll do. *(Also, if I were more computer literate I'd have figured out
> how to eliminate all the greyscale stuff so the files would be smaller!)
>
> > The one problem I have with your
> >suggestion is that, it would mean essentially programming a lisp or
> >list orientated language... Is this needed for LOGO? I know it is
> >essentially LISP based but I was hoping just to store multiple repeats
> >in the same array string and just evaluate by first going to the
> >middle repeat E.g. REPEAT 30 [ REPEAT 20 [ REPEAT 10 [ ] ] ] and
> >working backwards <<< (outwards) until I got to the last REPEAT...
>
> You can implement lists in pretty much any language that lets you manipulate
> pointers. *But I agree that VB isn't my implementation language of choice.
> It'd be much easier if you did it in Lisp! *That way you could focus your
> attention on the interesting parts instead of having to invent basic data
> structures.
>
> Why are you so focused on REPEAT as a special case? *For one thing, IF and
> IFELSE and TEST and RUN all use the same kind of instruction list input as
> REPEAT. *But, more importantly, even without any of those, when you say
>
> * * * * forward sum 20 30
>
> the EVAL of that instruction requires an EVAL of the subexpression
>
> * * * * sum 20 30
>
> If you use infix arithmetic, it's just that much harder to find the right
> subexpression to evaluate next.
>
> >Anyway, Thanks for your help so far... One final point, If I won't be
> >able to get that book, is there a chance I could find something
> >similar that could teach me the basics? (preferably available for free
> >in electronic form)
>
> It depends what you mean by "basics." *What you /really/ should read is the
> best computer science book ever written, _Structure and Interpretation of
> Computer Programs_ by Abelson and Sussman and Sussman, which will teach you
> the hidden mysteries of interpreters. *But it's not an easy read. *Butit
> /is/ available free online:
>
> * * * *http://mitpress.mit.edu/sicp/full-text/book/book.html
>
> P.S. *Be sure to come to the Eurologo conference next summer (2009) in Paris!

Hi Brian,

First of all, thanks for uploading the pages of the book, they have
given me a whole different insign into how a "real" interpreter works
(I was basically just going of guesswork)... I realise now each
function (e.g. FD) needs a set amount of inputs defined for it, so
when I have time I'm going to re-implement the interpreter using this
method.

The one problem I still have is the idea of control loops though, my
specific problem is still the same, if I have a statement such as the
one below:

repeat 360 [ repeat 4[fd 50 rt 90] rt 1 ]

I can understand how the interpreter understands the first section, it
gets the command "repeat", gets its input (360) and starts repeating
the functions inside, on the first iteration of this it sees the new
repeat, gets its input (4) and repeats the code inside that loop...
But how does it then know to return to the previous loop and more
importantly, when it returns to the previous loop start at the end to
execute "rt 1"?

Also when the full procedure has executed, how does the interpreter
know to go forward and not get in an endless loop of looking for the
"repeat"?

I hope that makes sense... I'm not sure if a nested loop like this
would be possible in VB... And yeah I think I am a little bit obsessed
with the REPEAT statement, I think I just don't get how you you can
iterate through a loop and then jump back to the previous position in
the sense of a interpreter.

Sorry if I seem like I am repeating myself... I did read your previous
post thoroughly and understand that the evaluation needs to be more
dynamic and less static, as in what if I had "sum 20 30 40 50 60"...
in my current interpreter it just looks for two values, when really it
needs to look for N values until a new command is found (In the new
version I will make a list of all current commands that will be
iterated through for that purpose) (recursion would also need to be
used to get all inputs)

Also thankyou for the link to the computer science book, looks really
interesting... If a little advanced... I can't wait to do the
interpreter and compilers module @ University...

Also do you have some more details about the EuroLOGO Conference, What
is it? I did a google search but I couldn't find anything about a
conference in 2009... Maybe i'm a little early though.

alexmcneil@googlemail.com writes:
> repeat 360 [ repeat 4[fd 50 rt 90] rt 1 ]
>
>I can understand how the interpreter understands the first section, it
>gets the command "repeat", gets its input (360) and starts repeating
>the functions inside, on the first iteration of this it sees the new
>repeat, gets its input (4) and repeats the code inside that loop...
>But how does it then know to return to the previous loop and more
>importantly, when it returns to the previous loop start at the end to
>execute "rt 1"?

REPEAT takes /two/ inputs, not one: a number and a list. Its job is to
call EVAL, repeatedly, with repeat's second input as eval's input.

If there's another REPEAT inside the first one, then it's like any recursive
invocation -- each invocation has its own local variables, including in this
case the number of repetitions left.

You're imagining one invocation of EVAL scanning back and forth through the
text, but that's not what happens; the text is scanned only once, and all
the stuff in brackets is just data (as always when things are in brackets!)
given to REPEAT as its input. The situation is sort of like what happens
when you call a user-defined procedure: the procedure's body is used as input
to another EVAL call.

>Sorry if I seem like I am repeating myself... I did read your previous
>post thoroughly and understand that the evaluation needs to be more
>dynamic and less static, as in what if I had "sum 20 30 40 50 60"...
>in my current interpreter it just looks for two values, when really it
>needs to look for N values until a new command is found (In the new
>version I will make a list of all current commands that will be
>iterated through for that purpose) (recursion would also need to be
>used to get all inputs)

No, for

print sum 20 30 40 50 60

what you get is

50
You don't say what to do with 40

It's if you say

print (sum 20 30 40 50 60)

that you have to collect more inputs. Every procedure has a minimum, a
default, and a maximum number of inputs. For most procedures the three
values are equal, but for SUM they're 0, 2, and infinity.

>Also thankyou for the link to the computer science book, looks really
>interesting... If a little advanced... I can't wait to do the
>interpreter and compilers module @ University...

Unless you're really lucky, they won't give you SICP as a textbook, so you
should read it on your own!

>Also do you have some more details about the EuroLOGO Conference, What
>is it? I did a google search but I couldn't find anything about a
>conference in 2009... Maybe i'm a little early though.

Yes, it's early for 2009. Look up Eurologo 2007 in Bratislava and you'll
get the idea of what Eurologo is like.

On Apr 16, 3:20 pm, b...@cs.berkeley.edu (Brian Harvey) wrote:
> alexmcn...@googlemail.com writes:
> > repeat 360 [ repeat 4[fd 50 rt 90] rt 1 ]
>
> >I can understand how the interpreter understands the first section, it
> >gets the command "repeat", gets its input (360) and starts repeating
> >the functions inside, on the first iteration of this it sees the new
> >repeat, gets its input (4) and repeats the code inside that loop...
> >But how does it then know to return to the previous loop and more
> >importantly, when it returns to the previous loop start at the end to
> >execute "rt 1"?
>
> REPEAT takes /two/ inputs, not one: a number and a list. Its job is to
> call EVAL, repeatedly, with repeat's second input as eval's input.
>
> If there's another REPEAT inside the first one, then it's like any recursive
> invocation -- each invocation has its own local variables, including in this
> case the number of repetitions left.
>
> You're imagining one invocation of EVAL scanning back and forth through the
> text, but that's not what happens; the text is scanned only once, and all
> the stuff in brackets is just data (as always when things are in brackets!)
> given to REPEAT as its input. The situation is sort of like what happens
> when you call a user-defined procedure: the procedure's body is used as input
> to another EVAL call.
>
> >Sorry if I seem like I am repeating myself... I did read your previous
> >post thoroughly and understand that the evaluation needs to be more
> >dynamic and less static, as in what if I had "sum 20 30 40 50 60"...
> >in my current interpreter it just looks for two values, when really it
> >needs to look for N values until a new command is found (In the new
> >version I will make a list of all current commands that will be
> >iterated through for that purpose) (recursion would also need to be
> >used to get all inputs)
>
> No, for
>
> print sum 20 30 40 50 60
>
> what you get is
>
> 50
> You don't say what to do with 40
>
> It's if you say
>
> print (sum 20 30 40 50 60)
>
> that you have to collect more inputs. Every procedure has a minimum, a
> default, and a maximum number of inputs. For most procedures the three
> values are equal, but for SUM they're 0, 2, and infinity.
>
> >Also thankyou for the link to the computer science book, looks really
> >interesting... If a little advanced... I can't wait to do the
> >interpreter and compilers module @ University...
>
> Unless you're really lucky, they won't give you SICP as a textbook, so you
> should read it on your own!
>
> >Also do you have some more details about the EuroLOGO Conference, What
> >is it? I did a google search but I couldn't find anything about a
> >conference in 2009... Maybe i'm a little early though.
>
> Yes, it's early for 2009. Look up Eurologo 2007 in Bratislava and you'll
> get the idea of what Eurologo is like.

Ok, Thanks for the explanation again, I'm going to read your books on
logo again until I properly understand what every bit of logo does/
should do...

One final question (hopefully :-) ), I'm having trouble parsing nested
[ ] square brackets (And this is a fundamental part of a logo
interpreter...) I've tried doing the the old fashioned way with for-
loops and substrings, and also the modern way with regular
expressions, both won't work... the problem is with the nesting...
Apparently it's semi-impossible to do this with just regular
expressions... and it seems impossible with for-loops and substrings
too.

I just wondered how UCBLogo does this? Does it implement a engine for
lists in-between square brackets [ ] before it starts parsing? Maybe I
should just look at the source code but I imagine its huge...

Thanks, Alex.

alexmcneil@googlemail.com writes:
>One final question (hopefully :-) ), I'm having trouble parsing nested
>[ ] square brackets (And this is a fundamental part of a logo
>interpreter...) I've tried doing the the old fashioned way with for-
>loops and substrings, and also the modern way with regular
>expressions, both won't work... the problem is with the nesting...
>Apparently it's semi-impossible to do this with just regular
>expressions... and it seems impossible with for-loops and substrings
>too.

It's not just semi-impossible; it /is/ impossible with regular expressions
to parse unlimited-depth nestings. Regular expressions have the same power
as finite state machines, and you'd need a state for every possible depth
of nesting to do it. (See chapter 1 of CSLS vol 3. :-)

You can do it in a loop, if you have a variable containing the current depth
in brackets. That's what UCBLogo does to count brackets when inside a
comment or something where it doesn't have to make sense of them.

But the natural way is with recursion! A list is a recursive data structure,
because its elements can include lists. If you want to see how UCBLogo parses
lists, look at the recursive call to parser_iterate inside parser_iterate
on line 480 of parse.c.