Re: [SPOILER] Re: Perl Quiz of the Week #25 (RPN calculator)

On Tue, 5 Oct 2004 13:01:28 -0400, Mark Jason Dominus <[email protected]> wrote:
> 
> On Oct 5, 2004, at 12:42 PM, Peter Haworth wrote:
> >
> > I'm thinking about allowing user-defined functions, but not being a
> > Forth programmer, I'm not sure how the syntax ought to look.
> 
> My dim recollection from Forth is that it looks something like this:
> 
>         'function-name' : op op op op op op ;
> 
> Where ':' and ';' are special operators.  ':' pushes a special mark
> value onto the stack, and
> also enables a quoting mode that disables ordinary evaluation.  The
> following operators are
> pushed onto the stack atop the mark.  The ';' operator tells Forth to
> pop the operators until it
> sees the special mark; this becomes the definition of the function, and
> the ';' pops the function name off
> the stack and associates the name and the definition in a global
> dictionary.

Forth looks like this:

    : function-name op op op ... op ;

For instance:

    : square dup * ;

Its memory management and parsing are a lot more primitive than what
you describe.  The word ":" reads the next word and CREATEs it in the
dictionary (i.e. puts an appropriate header and links in the word).  It also
switches to a compilation mode, where any word read is stored into the
dictionary.  Numbers are an exception: they store "LITERAL" and then
themselves in the dictionary.

Other exceptions are any words marked "IMMEDIATE", which are
executed immediately.  For example, ";" ends a definition (stores "(SEMI)"
on the dictionary and switches out of compilation mode), and "(" reads
and ignores all characters until ")" -- this is how you write a comment!

Flow control is also compiled with IMMEDIATE words, which store
helper words on the dictionary and leave appropriate placeholders if any
jumps need to be filled in later.

The dictionary is just an array of words; you only ever ALLOT space on
it, but never really free anything.
 
> Afterwards, evaluating 'function-name' is simple: just expand the
> definition and process it as usual.

Again, Forth is simpler.  The header of a word in the dictionary contains
the address to call to execute it.  In the case of a compiled word, this
address is a routine (called the "inner interpreter") which justs executes
words in a loop.  (SEMI) just ends this loop.  Both are typically just a few
bytes of machine code.

Words like LITERAL push the next words after where they're stored, which
is how something like "2" gets compiled.

> I believe PostScript is similar.  Come to think of it, I have the
> PostScript language reference on my desk here...
> Aha, yes.  I may not have described Forth accurately, but my
> description is very close to what PostScript does:
> 
> > Scanning the program fragment
> >
> >               {add 2 div}
> >
> > produces a single procedure object that contains the name object add,
> > the integer object 2, and the name object div. When the scanner
> > encounters the initial {, it continues scanning and creating objects,
> > but the interpreter does not execute them. When the scanner encounters
> > the matching }, it puts all the objects created since the initial {
> > into a new executable array (procedure) object.
> >
> > The interpreter does not execute a procedure immediately, but treats
> > it as data; it pushes the procedure on the operand stack. Only when
> > the procedure is explicitly invoked (by means yet to be described)
> > will it be executed. Execution of the procedure—and of all objects
> > within the procedure, including any embedded procedures—has been
> > deferred. The matter of immediate versus deferred execution is
> > discussed in Section 3.5, "Execution."
> 
> In PostScript you define a procedure by doing something like:
> 
>         { 2 mul } /double def
> 
> After processing the '}' operator, the stack contains an anonymous
> function.  '/double' pushes the "name object" representing the name
> "double", and then "def" is a binary operator which expects a name and
> a value and associates the two in the current dictionary.
> 
> I don't think I have mentioned this month that PostScript is a
> fabulously elegant and powerful language, and that the language
> reference manual is clear and well-written.

PostScript is much cleaner than Forth, but also much larger.