Functional programming in Python

Brook Conner me@nellardo.com
Tue, 29 May 2001 18:45:44 -0400


On Tuesday, May 29, 2001, at 04:44  PM, Ketil Malde wrote:

> Jerzy Karczmarczuk <karczma@info.unicaen.fr> writes:
>
> Wouldn't
>         x f g
> in a Forth'ish machine mean
>         g(f,x)   -- using "standard" math notation, for a change
> rather than
>         g(f(x))
> ?

In PostScript, a Forth derivative, it would mean g(f(x)). The 
difference comes down when tokens in the input stream are 
evaluated: as they are encountered or at the very end. The input 
stream is a queue - first in, first out (FIFO). A language *could* 
treat the input stream as a stack (LIFO), but that would require 
storing the entire stream in memory before computation could begin. 
As Forth-like languages are usually designed for embedded systems 
with low memory and processing power, a large LIFO stack including 
the entire program is contra-indicated :-) Instead PostScript (and 
other Forth-likes I've seen), treat the input stream as a FIFO 
queue. This way, the interpreter can handle tokens immediately and 
the stack doesn't get any larger than intermediate values in 
computations. And it also matches well with the serial 
communication these machines usually have with the producer of the 
program (there's a reason PostScript laser printers used serial 
ports easily enough, not parallel ones).

So, evaluation proceeds as follows:

for each item in the stream (FIFO)
    evaluate it
    pop items off the stack if evaluation requires it
    push result(s) on to stack

So, presuming x is a variable with value "3", and f and g are 
functions of one parameter:

x is identified and its value is pushed on to the stack.

so the stream is now "f g" and the stack is now "3"

f is identified as a function. The value of x is popped off the 
stack (if f needed more than one parameter, more values would be 
popped off - in this case, resulting in an error from an empty 
stack).

The stream is now "g" and the stack is empty. The interpreter is 
loaded with the function f and the value 3.

f is evaluated with the value of x. The result is pushed onto the stack.

The stream is "g" and the stack contains the result of f(3).

g is identified as a function and the stack is popped.

The stream is empty and the stack is too. The interpreter is loaded 
with the function g and the value f(3).

g is evaluated with the value f(3). The result is pushed onto the stack.

As the stream is now empty, but the stack has items in it, a 
PostScript interpreter would typically print the contents of the 
stack.


This is of course g(f(x), not g(f,x). If the input stream was a 
stack, too, then "g" would be evaluated first. If g took two 
arguments, it would produce g(f,x). If g took one argument, it 
would produce g(f). If that was a function, then it would continue 
with (g(f))(x), otherwise it would end with a stack containing two 
items: g(f) on top of x.

The way you get g(f,x) in PostScript or other forths is quoting (as 
in Lisp). PostScript handles this with a /slash for a single token 
or {braces} for lists. Either can be evaluated later: if it's a 
stream of tokens, then those are evaluated (FIFO). So, procedure 
definition in PostScript looks like this:

/inches { 72 * } def

which pushes the symbol "inches" onto the stack and then the list 
of tokens "72 *"  onto the stack (PostScript's native unit is the 
point, defined as 1/72 of an inch). "def" pops the top of the stack 
and attaches it as a value to the variable named in the symbol next 
in the stack (no symbol equals an error). Later, a statement like 
"3 inches" (an unusually readable statement in a Forth-like 
language :-) is equivalent to "3 {72 *}" which is equivalent to "3 
72 *", or 216.


Brook