CS 61A     Programming project #4:  A Logo Interpreter


Partner declaration (1 point): due Friday July 29th at 11:59 pm


Part 1: due Saturday August 6th at 11:59 pm

Part 2: due Monday August 8th at 11:59 pm  (MUCH longer than Part 1)

Part 2 due:

In Chapter 4 we study a Scheme interpreter written in Scheme, the metacircular evaluator.  In this project we modify that evaluator to turn it into an interpreter for a different programming language. This project is valuable for several reasons:  First, it will make you more familiar with the structure of the metacircular evaluator because you'll have to understand which procedure to modify in order to change some aspect of its operation.  Second, working with another language may help overcome some of the confusion students often have about talking to two different versions of Scheme at once.  In this project, it'll be quite obvious when you're talking to Scheme and when you're talking to Logo.  Third, this project will encourage you to think about the design of a programming language.  Why did Scheme's designers and Logo's designers make different choices?

As in the adventure game project, you'll have a group of two people, person A and person B.  Within each part of the project you will do some of the work separately and then meet together for the final steps. After the first week you should be able to enter instructions using
primitive procedures with constant arguments.  In the second part you
will add variables and user-defined procedures.

Before you begin working on the project, you have to know something about the Logo programming language.  The Logo-in-Scheme interpreter is structured like the metacircular evaluator, so to run it you say

        % stk
        > (load "~cs61a/lib/obj.scm")
        > (load "~cs61a/lib/logo.scm")
        > (load "~cs61a/lib/logo-meta.scm")
        > (initialize-logo)

and the question-mark prompt means that you're talking to Logo.  (The versions in the library are incomplete; you'll have to do the project before you can really run it!)  Errors in your Logo instructions can cause the interpreter to get a Scheme error message and return you to the Scheme prompt.  If this happens, type (driver-loop) to return to Logo.  You should only use (initialize-logo) once, or else you will lose any Logo variables or procedures you've defined.

>>> NOTE TO MACINTOSH GAMBIT USERS:  Before running this project you must tell Gambit to read a line, not a Scheme expression, in response to the ENTER key.  To do this, look in the Edit menu and select Window Styles.  Near the bottom right corner of the window that will appear are three check boxes; the middle one is labelled "Enter = Send Line".  Check that box (so that you see an X in the box), then click OK.

>>> NOTE TO WINDOWS-NATIVE STK USERS:  We don't think there's any way to tell the Windows version of STk to read a line rather than an expression.  You must either do the project on the lab machine with ssh, or else install the Unix version of STk on your machine under a Unix simulator such as cygwin.

If you want to experiment with a *real* Logo interpreter, to see how it's supposed to work, just say

        % logo

to the shell.  You exit Logo by saying BYE.  (You can download Berkeley Logo for your home computer at http://www.cs.berkeley.edu/~bh/logo.html )

Logo is essentially a dialect of Lisp.  That makes it a good choice for this project, both because it'll be easy to teach you the language and because the modifications to the evaluator are not as severe as they would be for an unrelated language.  However, Logo was designed for educational use, particularly with younger children.  Many design decisions in Logo are meant
to make the language more comfortable for a beginner.  For example, most Logo procedures are invoked in prefix form (first the procedure name, then the arguments) as in Lisp, but the common arithmetic operators are also provided in the customary infix form:

        ? print sum 2 3
        ? print 2+3

(Note: As you work with the Logo-in-Scheme interpreter, you probably won't be impressed by its comfort.  That's because our interpreter has a lot of rough edges.  The most important is in its error handling.  A real Logo interpreter would not dump you into Scheme with a cryptic message whenever you make a spelling mistake!  Bear in mind that this is only a partial implementation.  Another rough edge is that THERE IS NO PRECEDENCE AMONG INFIX OPERATORS, unlike real Logo, in which (as in most languages) multiplication is done before addition.  In this interpreter, infix operators are carried out from left to right, so 3+4*5 is 7*5 or 35, not 3+20.)

Even in the trivial example above, adding two numbers, you can see several differences between Scheme and Logo.  The most profound, in terms of the structure of the interpreter, is that expressions and their subexpressions are not enclosed in parentheses.  (That is, each expression is not a list by itself.)  In the metacircular evaluator, EVAL is given one complete
expression as an argument.  In the Logo interpreter, part of EVAL's job will be to figure out where each expression begins and ends, by knowing how many arguments are needed by each procedure, for example:

        ? print sentence word "now "here last [the invisible man]

Logo must understand that WORD requires two arguments (the quoted words that follow it) while LAST requires one, and that the values returned by WORD and LAST are the two required arguments to SENTENCE.  (Also, PRINT requires one argument.)

Another important difference between Scheme and Logo is that in the latter you must explicitly say PRINT to print something:

        ? print 2+1
        ? 2+1
        You don't say what to do with 3

An expression that produces an unused value causes an error message. Unlike Scheme, in which every procedure returns a value, Logo makes a distinction between OPERATIONS that return a value and COMMANDS that are used for effect.  PRINT is a command; SUM is an operation.  This distinction means that Logo has less of a commitment to functional programming style, and it makes the interpreter a little more complicated because we have to keep track of whether we have a value or not.  But in some ways it's easier for the user; we don't keep saying things like "set! returns some value or other, but the value is unspecified and  you're not supposed to rely on it in your programs."  Also, Logo users don't see the annoying extra values that Scheme programs sometimes print because some procedure that was called for effect happens to return () or #F or OKAY as a value that gets printed.

One implication for the interpreter is that instead of Scheme's read-eval-print loop

        (define (driver-loop)
          (display "> ")
          (print (eval (read) the-global-environment))

Logo just has a read-eval loop without the print.

In Scheme something like 2+3 would be considered a single symbol, not a request to add two numbers.  The plus sign does not have special status as a delimiter of expressions; only spaces and parentheses separate expressions. Logo is more like most other programming languages in that several characters are always considered as one-character symbols even if not surrounded by spaces.  These include arithmetic operators, relational operators, and parentheses:

        + - * / = < > ( )

Remember that in Scheme, parentheses are used to indicate list structure and are not actually part of the internal representation of the structure. (In other words, there are no parentheses visible in the box-and-pointer diagram for a list.)  In this Logo interpreter, parentheses are special
symbols, just like a plus sign, and are part of the internal representation of an instruction line.  Square brackets, however, play a role somewhat like that of parentheses in Scheme, delimiting lists and sublists.  One difference is that a list in square brackets is automatically quoted,
so [...] in Logo is like '(...) in Scheme:

        ? print [hi there]

Logo uses the double quotation mark (") to quote a word, so "foo in Logo is like 'foo in Scheme.  Don't get confused -- these quotation marks are not used in pairs, as in Scheme string constants ("error message"); a single one is used before a word to be quoted.

        ? print "hello

Just as the Scheme procedure READ reads an expression from the keyboard and deals with parentheses, spaces, and quotation marks, you are given a LOGO-READ procedure that handles the special punctuation in Logo lines. One important difference is that a Scheme expression is delimited by parentheses and can be several lines long; LOGO-READ reads a single line and turns it into a list.  If you want to play with it from Scheme, first get out of Logo (if you're in it) by typing ^C twice, then type the invocation (logo-read) and the Logo stuff you want read all on the same line:

        > (logo-read)print 2+(3*4)
        (print 2 + ( 3 * 4 ))
        > (logo-read)print se "this [is a [deep] list]
        (print se "this (is a (deep) list))

Remember that the results printed in these examples are Scheme's print representation for Logo data structures!  Don't think, for example, "LOGO-READ turns square brackets into parentheses."  What really happens is that LOGO-READ turns square brackets into box-and-pointer lists, and Scheme's print procedure displays that structure using parentheses.  Note:  In the first of these two examples, the inner parentheses in the returned value are *not* the boundaries of a sublist!  They are parenthesis symbols. What logo-read returned was a sentence with eight words:
        print, 2, +, (, 3, *, 4, and ).
This makes it a little tricky to be sure what you're seeing.

If you want to include one of Logo's special characters in a Logo word, you can use backslash before it:

        ?print "a\+b

Also, as a special case, a special character other than square bracket is considered automatically backslashed if it's immediately after a quotation mark:

        ?print "+

All of this is handled by LOGO-READ, a fairly complicated procedure. You are not required to write this, or even to understand its algorithm, but you'll need to understand the results in order to work on EVAL.

Procedures and variables:  Here is a Scheme procedure and an example of defining and using the corresponding Logo procedure:

        (define (factorial n)
          (if (= n 0)
              (* n (factorial (- n 1))) ))

        ? to factorial :n
        -> if :n=0 [output 1]
        -> output :n * factorial :n-1
        -> end
        ? print factorial 5

There are several noteworthy points here.  First, a procedure definition takes several lines.  The procedure name and formal parameters are part of the first instruction line, headed by the TO special form.  (This is the only special form in Logo.)  The procedure body is entered on lines
in response to a special -> prompt.  These instruction lines are not evaluated, as they would be if entered at a ? prompt, but are stored as part of the procedure text.  The special keyword END on a line by itself indicates the end of the body.  (In real Logo, the special prompt is just > but we use -> to avoid confusion with the Scheme prompt.)

Unlike Scheme, Logo does not have first-class procedures.  Among other things, this means that a procedure name is not just a variable name that happens to be bound to a procedure.  Rather, procedures and variables are looked up in separate data structures, so that there can be a procedure and a variable with the same name.  (This is sometimes handy for names like LIST and WORD, which are primitive procedures but are also convenient formal parameter names.  In Scheme we resort to things like L or LST to avoid losing access to the LIST procedure.)  Variable names are part of a Scheme-like environment structure (but with dynamic rather than lexical scope); procedure names are always globally accessible.  To distinguish a procedure invocation from a variable reference, the rule is that a word FOO without punctuation is an invocation of the procedure named FOO, while the same word with a colon in front (:FOO) is a request for the value of the variable with that name.

A Logo procedure can be either a command (done for effect) or an operation (returning a value).  In this example we are writing an operation, and we have to say so by using the OUTPUT command to specify the return value. Once an OUTPUT instruction has been carried out, the procedure is finished; in this example, if the IF in the first line of the body outputs 1, the second line of the body is not evaluated.

The file ~cs61a/lib/test.logo contains definitions of several Logo procedures that you can examine and test to become more familiar with the language.  You can load these definitions into your Logo interpreter by copying it to your directory and then using Logo's LOAD command:

        ? load "test.logo

(Notice that if you want to use a filename including slashes you have to backslash them to make them part of the quoted word.)

Unlike Scheme's IF, Logo's IF is not a special form.  You probably remember a homework exercise that proved that it had to be, but instead Logo takes advantage of the fact that square brackets quote the list that they delimit.  The first argument to IF must be the word TRUE or the word FALSE.  (Predicate functions in Logo always return one of these two words. Logo does not accept any non-FALSE value as true; anything other than these two specific words is an error.)  The second argument is a list containing instructions that should be run conditionally.  Because the list is enclosed in square brackets, the instructions are not evaluated before IF is invoked. In general, anything that shouldn't be evaluated in Logo must be indicated by explicit quotation, with "xxx or [xxx].  The only special form is TO, in which the procedure name and formal parameter names are not evaluated.

The procedures first, butfirst, etc. that we've been using to manipulate words and sentences were invented in Logo.  The Scheme versions don't quite work as smoothly as the real Logo versions, because Scheme has four distinct data types for numbers, symbols, strings, and characters; all of these are a single type (words) in Logo.  If you evaluate (bf 104) in Scheme you get "04", not just 04, because the result has to be a Scheme string in order not to lose the initial zero.  Our Logo interpreter does manage to handle this:

        ? print bf 104
        ? print bf bf 104

The interpreter represents 04 internally as a Scheme symbol, not as a number. We can nevertheless do arithmetic on it

        ? print 7+bf 104

because all the Logo arithmetic functions have been written to convert symbols-full-of-digits into regular numbers before invoking the actual Scheme arithmetic procedure.  (This is the job of MAKE-LOGO-ARITH.)

If you used Logo as a kid, what you probably remember is not doing text processing, but drawing pictures.  Our Logo-in-Scheme includes the turtle graphics primitives FORWARD, BACK, LEFT, RIGHT, CLEARSCREEN, HOME, PENUP, PENDOWN, PENERASE, SHOWTURTLE, HIDETURTLE, SETXY, XCOR, YCOR, POS, HEADING, SETHEADING, SETPENCOLOR, PENCOLOR, SETBACKGROUND, and their abbreviations.

Okay, time for the actual project.  You will need these files:

        ~cs61a/lib/obj.scm                object-oriented tools
        ~cs61a/lib/logo.scm                various stuff Logo needs
        ~cs61a/lib/logo-meta.scm        modified metacircular evaluator

These files (or your modified versions of the last two) must be loaded into Scheme in this order; each one depends on the one before it.  Much of the work has already been done for you.  (The names logo-eval and logo-apply are used so as not to conflict with Scheme's built-in eval and apply functions.)

For reference, ~cs61a/lib/mceval.scm is the metacircular evaluator without the modifications for Logo.

Start by examining logo-eval.  It has two parts: eval-prefix, which is comparable to the version of eval in the text, handles expressions with prefix operations similar to Scheme's syntax.  The result of evaluating such an expression is then given as an argument to handle-infix, which checks for a possible infix operator following the expression.  For now, we'll ignore handle-infix, which you'll write later in the project, and concentrate on eval-prefix.  Compare it with the version of eval in the text.  The Scheme version has a COND clause for each of several special forms.  (And the real Scheme has even more special forms than the version in the book.)  Logo has only one special form, used for procedure definition, but to make up for it, eval-prefix has a lot of complexity concerning parentheses.  An ordinary application (handled by the else clause) is somewhat more complicated than in Scheme because we must figure out the number of arguments required before we can collect the arguments.  Finally, an important subtle point is that the Logo version uses LET in several places to enforce a left-to-right order of evaluation.  In Scheme the order of evaluation is unspecified, but in Logo we don't know where the second argument expression starts, for example, until we've finished collecting and evaluating the first argument expression.

Part 1

PART I.  These six problems (two per person, two together) are due Monday. The ones done separately must be completed before you'll be able to run the Logo interpreter at all.


A1.  As explained above, EVAL can't be given a single complete expression
as its argument, because expressions need not be delimited by parentheses
and so it's hard to tell where an expression ends.  Instead, EVAL must
read through the line, one element at a time, to figure out how to group
things.  LOGO-READ, you'll recall, gives us a Logo instruction line in the
form of a list.  Each element of the list is a "token" (a symbol, a number,
a punctuation character, etc.) and EVAL reads them one by one.  You might
imagine that EVAL would accept this list as its argument and would get to
the next token by CDRing down, like this:

        (define (eval-prefix line-list env)
          (let ((token (car line-list)))
            (set! line-list (cdr line-list))

but in fact this won't quite work because of the recursive invocation of
eval-prefix to evaluate subexpressions.  Consider a line like

        print sum (product 2 3) 4

One invocation of eval-prefix would be given the list

        (sum ( product 2 3 ) 4)

as argument.  It would cheerfully cdr down its local line-list variable,
until it got to the word "product"; at that point, another invocation of
eval-prefix would be given the ENTIRE REMAINING LIST as its argument (since
we don't know in advance how much of that list is part of the subexpression).
When the inner eval-prefix finishes, the outer one still needs to read another
argument expression, but it has no way of knowing how much of the list was
read by the inner one.

Our solution is to invent a LINE-OBJECT data type.  This object will be used
as the argument to logo-eval, which in turn uses it as argument to
eval-prefix; the line-object will remember, in its local state, how much of
the line has been read.  The very same line-object will be the argument to
the inner eval-prefix.  When that finishes, the line object (still available
to the outer invocation of eval-prefix) has already dispensed some tokens and
knows which tokens remain to be processed.

Your job is to define the LINE-OBJECT class.  It has one instantiation
variable, a list containing the text of a line.  Objects in the class should
accept these messages:

        (ask line-obj 'empty?)                should return #T if there is nothing
                                        left to read in the line-list, #F if
                                        there are still tokens unread.

        (ask line-obj 'next)                should return the next token waiting
                                        to be read in the line, and remove
                                        that token from the list.

        (ask line-obj 'put-back token)        should stick the given token at the
                                        front of the line-list, so that the
                                        next NEXT message will return it.
                                        This is used when EVAL has to read
                                        past the end of an expression to be
                                        sure that it really is the end, but
                                        then wants to un-read the extra

There are several places in logo-meta.scm that send these messages to the
objects you'll create, so you can see examples of their use.  You'll get
ASK from obj.scm and should use its syntax conventions.

Also write a short procedure (make-line-obj text) that creates and returns
a line object instance with the given text.  This procedure is invoked in
several places within the Logo interpreter.

A2.  We need to be able to print the results of Logo computations.  Logo
provides three primitive procedures for this purpose:

        ? print [a [b c] d]                ; don't show outermost brackets
        a [b c] d
        ? show [a [b c] d]                ; do show outermost brackets
        [a [b c] d]
        ? type [a [b c] d]                ; don't start new line after printing
        a [b c] d?

PRINT and SHOW can be defined in terms of TYPE, and we have done so in the
procedures logo-print and logo-show (defined in logo.scm).  Your job is to
write logo-type.  It will take a word or list as argument, and print its
contents, putting square brackets around any sublists but not around the
entire argument.  You should use the Scheme primitive DISPLAY to print the
individual words.  DISPLAY is described in the Scheme reference
manual in your course reader.  Hint: (display " ") will print a space.

**** When you've finished these two steps, you must combine your work with
**** that of person B.  When you've done that, you should be able to run
**** the interpreter and carry out instructions involving only primitive
**** procedures and constant (quoted or self-evaluating) data.  (You
**** aren't yet ready for variables, conditionals, or defining procedures,
**** and you can only use prefix arithmetic operators.)

(There are some suggestions for things to test at the end of person B's
problems for this week.)


B1.  A Logo line can contain more than one instruction:

        ? print "a print "b

This capability is important when an instruction line is given as an
argument to something else:

        ? to repeat :num :instr
        -> if :num=0 [stop]
        -> run :instr
        -> repeat :num-1 :instr
        -> end
        ? repeat 3 [print "hi print "bye]

On the other hand, an instruction line used as argument to something might
not contain any complete instructions at all, but rather an expression that
provides a value to a larger computation:

        ? print ifelse 2=3 [5*6] [8*9]

In this example, when the IFELSE procedure is invoked, it will turn the
list [8*9] into an instruction line for evaluation.  (Note:  This example
is here to explain to you why you need to handle an "instruction line"
without a complete instruction.  You can't actually type this into your
Logo interpreter yet; you haven't invented infix notation or predicates.)

Logo-eval's job is to evaluate one instruction or expression and return
its value.  (An instruction, in which a command is applied to arguments,
has no return value.  In our interpreter this is indicated by logo-eval
returning the symbol =NO-VALUE= instead of a value.)  We need another
procedure that evaluates an entire line, possibly containing several
instructions, by repeatedly invoking logo-eval until either the line is
empty (in which case =NO-VALUE= should be returned) or logo-eval returns
a value (i.e., a value other than =NO-VALUE=), in which case that value
should be returned.  You will write this procedure, called eval-line,
like this:

        (define (eval-line line-obj env)

You'll find several invocations of eval-line in the interpreter, most
importantly in driver-loop where each line you type after a ? prompt
is evaluated.

B2.  Conditionals.  The Logo primitives IF and IFELSE require as argument
the word TRUE or the word FALSE.  Of course our implementation of the Logo
predicates will use Scheme predicates, which return #T and #F instead.

Your job is to write the higher-order function LOGO-PRED whose argument is
a Scheme predicate and whose return value is a Logo predicate, i.e., a
function that returns TRUE instead of #T and FALSE instead of #F.  This
higher-order function is used in the table of primitives like this:

        (add-prim 'emptyp 1 (logo-pred empty?))

That is, the Scheme predicate EMPTY? becomes the Logo predicate EMPTYP.
(The "P" at the end of the name stands for "Predicate," by the way.  Some
versions of Logo use this convention, while others use ? at the end the way
Scheme does.  The educational merits of the two conventions are hotly
debated in the Logo community.)

The spiffiest way to do this is to create a LOGO-PRED that works for
predicate functions of any number of arguments.  To do that you have
to know how to create a Scheme function that accepts any number of arguments.
You do it with (lambda args (blah blah)).  That is, the formal parameter
name ARGS is not enclosed in parentheses.  When the procedure is called,
it will accept any number of actual arguments and they will all be put in a
list to which ARGS is bound.  (This is discussed in exercise 2.20.)

Alternatively, I'll accept two procedures LOGO-PRED-1 for predicate functions
of one argument and LOGO-PRED-2 for functions of two arguments, but then
you'll have to fix the add-prim invocations accordingly.

By the way, IF and IFELSE won't work until your group does problem 3
below.  Meanwhile, you should just be able to PRINT the values
returned by the predicates, once you've combined the work of your two
people so far.

**** When you've finished these two steps, you must combine your work with
**** that of person A.  When you've done that, you should be able to run
**** the interpreter and carry out instructions involving only primitive
**** procedures and constant (quoted or self-evaluating) data.  (You
**** aren't yet ready for variables, conditionals, or defining procedures,
**** and you can only use prefix arithmetic operators.)

Try these examples and others:

        ? print 3
        ? print sum product 3 4 8
        ? print [this is [a nested] list]
        this is [a nested] list
        ? print 3 print 4
        ? print equalp 4 6

Now come the two problems you'll do together:

3.  Ordinarily, each Logo procedure accepts a certain fixed number of
arguments.  There are two exceptions to this rule.  First, some primitive
procedures (but only primitives) can accept variable numbers of arguments,
just as in Scheme.  In Logo, such a procedure has a "default" number of
arguments -- this is the number that logo-eval will ordinarily look for.  If
you want to use a different number of arguments, you must enclose the entire
expression in parentheses as you would in Scheme:

        ? print sum 2 3
        ? print sum 2 3 4                        ; this is an error
        You don't say what to do with 4
        ? print (sum 2 3 4)

Second, certain primitive procedures need access to the current
environment in order to do their job.  For example, MAKE, which is Logo's
equivalent to SET!, takes two arguments, a variable name and a new value,
but the procedure that implements it requires a third argument, the current
environment, since the job is done by modifying that environment.  In the
Scheme metacircular evaluator, this problem is less noticeable because SET!
is a special form anyway -- its first argument isn't evaluated -- and so it
is handled directly by eval itself.  In Logo we have no special forms except
for TO, so MAKE is an ordinary procedure handled by logo-apply, but we still
need to indicate that it needs the environment as an extra "hidden" argument.

In this interpreter a procedure is represented as a four-element list:

        (name type-flag arg-count text)

NAME is the procedure's name.  (Unlike Scheme's first-class procedures which
can be created by lambda without a name, every Logo procedure must have a
name in order to exist at all.)

TYPE-FLAG is a symbol, either PRIMITIVE or COMPOUND.  The former means that
the procedure is written in Scheme (or is a Scheme primitive); the latter
means that the procedure was defined in Logo, using TO.

ARG-COUNT is the number of arguments that the procedure expects.  For most
procedures, this is a straightforward nonnegative integer.  In this part of
the project, we are going to deal with the exceptions discussed above.  For
a procedure that accepts variable numbers of arguments, ARG-COUNT will be a
negative integer, the negative of the default number of arguments.  For a
procedure that requires the environment as an extra argument, ARG-COUNT will
be a list whose only element is the number of visible arguments, before the
environment is added.  (No procedure is in both categories.)  Examples:

        (list 'type 'primitive 1 logo-type)        ;ordinary case
        (list 'word 'primitive -2 word)                ;variable # of args
        (list 'make 'primitive '(2) make)        ;2 visible args plus env

These lists are generated by the add-prim procedure that you can see in
logo-meta.scm along with entries for all the existing primitives.

TEXT is either a Scheme procedure, for a primitive, or a list whose first
element is a list of formal parameters and whose remaining elements are
instruction lines making up the body of the procedure, for a user-defined
Logo procedure.

The actual collection of argument values, corresponding to list-of-values
in the metacircular evaluator, is called collect-n-args in the Logo
interpreter.  It has an extra argument, n, which is the number of arguments
to be collected from the line-object.  If that argument is negative, then
collect-n-args will keep evaluating argument expressions until it sees a
right parenthesis.  (Remember that we allow a variable number of arguments
only if the expression is in parentheses.)

Your job is to modify the invocation of collect-n-args to handle both of
the special cases described here.  If the arg-count in the procedure is
a list, call collect-n-args with its car as the number, and cons the current
environment onto the front of the resulting argument list.  If the arg-count
is negative, you should use its absolute value as the number unless this
invocation is inside parentheses.  (There is a local variable paren-flag
that will be #T in this situation, #F otherwise.)

Once you've done this, modify the primitive table entries for sum,
product, word, sentence, and list so that they can accept variable
numbers of arguments.

****  Then test your work:

        ? ifelse equalp 2 3 [print "yes] [print "no]
        ? ifelse equalp 3 3 [print "yes] [print "no]
        ? print ifelse equalp 2 3 [product 5 6] [product 8 9]
        ? print (sum 4 5 6 7 8)
        ? print (word "a "b "c)
        ? print (sum 4 5 product 6 7 8)

4.  We are going to invent variables.  Most of the work has already been
done, because the environment structure is exactly like that of the Scheme
metacircular evaluator.  There are two things left for you to handle:
First, eval-prefix uses data abstraction procedures VARIABLE? and
VARIABLE-NAME to detect and process a variable reference.  In Scheme, any
symbol is a variable reference, since procedure names are variables too.  In
Logo, a variable reference is a symbol whose first character is a colon (:)
and the actual variable name is all but the first character of that symbol.
Write the necessary procedures.

Second, Scheme provides two different special forms, DEFINE and SET!, for
creating a new variable binding and for changing an existing binding.  In
Logo there is one procedure, MAKE, that serves both purposes.  If there is
already a binding for the given name in the current environment, then MAKE
acts like SET!.  If not, then MAKE creates a new binding in the global
environment.  (Note, this is not necessarily the current frame.)  Make
the MAKE procedure in logo.scm call the right logo-meta.scm procedures to
accomplish this, modifying those procedures if necessary.

**** Test your work:

        ? make "foo 27
        ? print :foo

(Why the quotation mark?  Remember, MAKE isn't a special form.  The VALUE
OF its first actual argument expression has to be the name we want to bind.)

Note:  You can't fully test this yet, because you won't know if it does
the right thing for local variables until we can define and invoke
procedures.  For now, just test that it works for global variables.

**** Turn in a transcript showing your interpreter at work.


PART II.  These five problems (one per person and three common ones)
are due Monday at 11:59 PM.  When you're done with them, the Logo interpreter
will be complete.

Note:  There is a point partway through this part when you have to combine
results with your partner, in order to be able to do another separate part,
following which comes yet another common part.  


A5.  Infix arithmetic.  Logo-eval calls eval-prefix to find a Scheme-style
expression and evaluate it.  Then it calls

        (handle-infix value line-obj env)

We have provided a "stub" version of handle-infix that doesn't actually
handle infix, but merely returns the value you give it.  Your task is to
write a version that really works.  The situation is this.  We are dealing
with the instruction line

        ? print 3 + 2

We are inside the logo-eval that's preparing to invoke PRINT.  It knows
that PRINT requires one argument, so it recursively called logo-eval.
(Actually logo-eval calls eval-prefix, which calls collect-n-args, which
calls logo-eval.)  The inner logo-eval called eval-prefix, which
found the expression 3, whose value is 3.  But the argument to PRINT isn't
really just 3; it's 3 + 2.

The job of handle-infix is to notice that the next token on the line is
an infix operator (one of + - * / = < >), find the corresponding procedure,
and apply it to the already-found value (in this case, 3) and the value of
the expression after the infix operator (in this case, 2).  Remember that
this following expression need not be a single token; you have to evaluate
it using eval-prefix.  If the next token isn't an infix operator, you must
put it back into the line and just return the already-found value.  Remember
that there may be another infix operator after you deal with the first one,
as in the instruction

        ? print 3 * 4 + 5

We've provided a procedure called de-infix that takes an infix operator as
argument and returns the name of the corresponding Logo primitive procedure.

To further your understanding of this problem, answer the following
question:  What difference would it make if your handle-infix invoked
logo-eval instead of eval-prefix as suggested above?  Show a sample
instruction for which this change would give a different result.

By the way, don't forget that we are not asking you to handle the precedence
of multiplication over addition correctly.  Your handle-infix will do all
infix operations from left to right, unless parentheses are used.  (You
don't have to deal with parentheses in handle-infix.  Logo-eval already
knows about them.)

**** Now skip over person B's problem to get to common problems 6 and 7.
**** You must merge the results of A5 and B5 before you can solve
**** those problems.


B5.  Time to define procedures!  You are going to write eval-definition,
a procedure that accepts a line-obj as argument.  (The corresponding
feature in the metacircular evaluator also needs the environment as an
argument, but recall that in Logo procedures are not part of the environment;
they go in a separate, global list.)  The line-obj has just given out the
token TO, and is ready to provide the procedure name and formal parameters.
Your job is to read those, then enter into an interactive loop in which you
read Logo lines and store them in a list, the procedure body.  You keep doing
this until you see a line that contains only the word END.  You put together
a procedure representation in the form

        (list name 'compound arg-count (cons formals body))

and you prepend this to the procedure list in the (Scheme) variable
the-procedures.  The arg-count is the number of formal parameters you found.
Formals is a list of the formal parameters, without the colons.  Body is the
list of instruction lines, not including the END line.  Don't turn the lines
into line-objects; that'll happen when the procedure is invoked.

To print the prompt, say (prompt "-> ").

It's going to be a little hard to test the results of your work until you
can invoke user-defined procedures, which requires one more step.  Meanwhile
you could leave Logo, and ask Scheme to look at the first element of
the-procedures to see if you've done it right.

**** You must merge the results of A5 and B5 before
**** you can solve common problems 6 and 7.


6.  Evaluating procedure bodies.  In the metacircular evaluator, APPLY sets up an
environment and uses eval-sequence to evaluate each expression in the
procedure body.  The Logo interpreter does the same, except that the job
of eval-sequence is different.  Its argument is a list of instruction
lists.  Each of those lists must be turned into a line-object before it can
be evaluated.  Also, we must take into account the fact that instructions
are different from expressions; the instruction lines in the procedure body
should generally return =NO-VALUE= when evaluated.  If not, eval-sequence
must signal the error "You don't say what to do with" the value.

The exceptions are the two primitive commands that can end a procedure
invocation early, STOP (for commands) and OUTPUT (for operations).  If
STOP is invoked, it will return the symbol =STOP=; if OUTPUT is invoked,
it will return a pair whose car is =OUTPUT= and whose cdr is the desired
return value:

        (add-prim 'stop 0 (lambda () '=stop=))
        (add-prim 'output 1 (lambda (x) (cons '=output= x)))

If eval-sequence evaluates a STOP, it should immediately return =NO-VALUE=.
If it gets an OUTPUT, it should immediately return the value provided (the
cdr of that pair).

7.  Dynamic scope.  In the metacircular evaluator, MC-APPLY handles
compound (user-defined) procedures by setting up an environment and
evaluating the procedure body (using eval-sequence) in that environment.
LOGO-APPLY must do the same thing, but instead of Scheme's lexical scope,
in which the new environment extends the one in which the procedure was
created, it must follow Logo's dynamic scope, in which the new environment
extends the current environment.

The version of LOGO-APPLY we give you doesn't handle compound procedure
calls.  Modify it as needed, along with any other changes required to go
along with this one.  (Hint:  Start by looking at the MC-APPLY version.)

**** Once you've solved these problems, you should be able to define and
**** invoke procedures:

        ? make "x 3
        ? to scope :x
        > helper 5
        > end
        ? to helper :y
        > print (sentence :x :y)
        > end
        ? scope 4

**** Now comes another split problem.


A8.  Add the STEP and UNSTEP primitive commands.  They take a word as
argument, which must be the name of a user-defined procedure.  STEP sets
to true, and UNSTEP sets to false, a flag inside the procedure structure
(you'll have to add this to the procedure ADT).  When a defined procedure
is called, if the stepping flag is set, Logo should print each line of the
procedure definition, followed by a ">>> " prompt, before evaluating that
line, and then wait for the user to enter a line (it'll usually be an
empty line, but in any case you can ignore what the user types; you're
just waiting for him/her to type it).  Then run the line from the
procedure.  For example:

        ? to garply
        -> print "hello
        -> print "goodbye
        -> end
        ? garply
        ? step "garply
        ? garply
        print "hello>>>         [user hits return/enter key]
        print "goodbye>>>
        ? unstep "garply
        ? garply

This is a Logo debugging assistance feature.  Try it on a recursive



B8.  Add the commands TEST, IFTRUE (abbreviation IFT), and IFFALSE
(abbreviation IFF).  These are alternatives to the IF/IFELSE style of
conditional evaluation, provided in Logo because an IFELSE that carries
out several conditional instructions can lead to one very long instruction
line, hard to read and hard to edit.  Here's how it works:

The command TEST takes one argument, which must be TRUE or FALSE.  It
remembers the value for later, and does nothing else.  Note:  If TEST is
called inside a procedure, the argument value is remembered locally, but
does not modify the caller's test result (or the global one).

The command IFTRUE takes one argument, an instruction list.  If the
remembered TEST value is TRUE, then the instruction list is run.  If the
remembered value is FALSE, nothing happens.  The command IFFALSE is the
same only backwards.  It is an error if IFTRUE or IFFALSE is used before
any TEST has been done.  Note:  It is *not* an error to use IFTRUE or
IFFALSE inside a procedure, before the procedure does a TEST, provided
that a TEST has been done by the caller.  That is, each procedure call
inherits its caller's test flag.

Suggestion:  Put a variable with an untypeable-in name, such as the
string " TEST", in every frame.


9.  Static variables.  This is a feature that isn't in normal versions of
Logo, but our version will be extra powerful!  As we've discussed in class,
one of the problems with dynamic scope is that you can't create local state
variables by defining a procedure inside the scope of a variable the way we
do in Scheme.  We are going to invent a mechanism by which a procedure
definition can specify the names and initial values of local state variables.
Here is an example showing the notation:

        ? to count :increase static :counter 2+3
        -> make "counter :counter + :increase
        -> print :counter
        -> end

        ? count 20
        ? count 1

        ? print :counter

In the first line of the procedure definition, STATIC is a keyword that
indicates the end of the formal parameters and the beginning of alternating
names and values of local state variables.  In the example shown here, there
is only one local state variable, named COUNTER, with an initial value of 5.
(Notice that the name is not evaluated, but the initial value expression is
evaluated, in the global environment.)

When the procedure is defined, it is given a local state variable named
COUNTER whose value is 5.  Each time the procedure is called, it changes
the value of that variable.  As the example shows, the name COUNTER is
not defined in the global environment.

To make this work, you must give every compound procedure a private frame
containing its static variables.  This frame will be a fifth element of the
list that represents a procedure.  When a compound procedure is invoked,
you will still extend the current (dynamic) environment, but you'll extend
it with two frames: the remembered static-variable frame, and the standard
newly-created frame in which formal parameters are bound to actual arguments.

Most of your work will be done in two places: the place where TO lines are
parsed, and the place where procedures are invoked.

The interpreter is now complete.  Congratulations!

Optional for hotshots:  Handle infix precedence properly.

(Of course there's a lot more that could be done, especially about error
handling, but also including missing primitives.  Logo enthusiasts might
like to try to invent LOCAL, CATCH, THROW, DEFINE, TEXT, etc.)