Newsgroups: comp.lang.pop

Here's a lengthy response to Robin's provocative and interesting
message.  Being a response, it moves around several topics which
should probably be in distinct messages.  However, there is a common
thread of possible revisions to POP and revisiting old design 
decisions that makes them hang together is quite an intriguing way,
I believe .....

Robin Popplestone writes about POP's list syntax:
>  Probably if we had
> had a supply of curlies in the early days we would have used {this is a
> list} as being somehow suitable for lists as set-like things (and perhaps
> we would have been wrong - certainly it is no help to think of an
> application as a set!, [text deleted]

It is interesting to see that GLOW took the route of using braces 
and brackets to distinguish quoted and unquoted lists.  It seems that
POP language designers are keen to be able to conveniently denote 
nested list constants.  My own view is similar to Robin's -- it is waste
of precious bracketing symbols and not mnemonic to use braces in this
way.

I was fascinated to watch Chris Dollin, the designer of Pepper, slowly and 
reluctantly accepting the need for list quasi-quoting.  His solution was
to integrate the list and vector syntax into the single quote context.
So in Pepper, you can write "[ ... ]" to achieve the same effect as POP-11's
[ ... ] and, naturally enough, "{ ... }" to do the same as POP-11's { ... }.
(There are minor semantic differences discussed below.)

The result in Pepper is that there is only one quoting system which is
introduced by the quote symbol '"'.  The disadvantage is that the quote
is really a quasi-quote and more complex to learn -- although not as hard
as POP-11's list syntax since it has a more regular semantics and a single
escape mechanism.

One of the most powerful arguments for the kind of solution Pepper has
pioneered is the rationalisation of quoting semantics.  Here's a question
for all you budding POP-11 experts out there (yes, I'm talking to you
James) that illustrates the needless complexity of its quoting
semantics.  Try to answer without referring to any manuals and without
typing the answer to a POP-11 interpreter ...

What are A, B, C, and D bound to after the following statements are executed?
    vars A, B, C, D;
    vars L = [a b c];
    vars V = {a b c};
    {1 ^^V 2} -> A;
    [1 ^^L 2] -> B;
    {1 ^^L 2} -> C;
    [1 ^^V 2} -> D;

And if you got that right, try this one:
    vars L = conspair( "a", "b" );
    [1 ^^L] -> A;
    [1 ^^L 2] -> B;

As I alluded to above, the separation of quoting from list and vector
construction, as in Pepper, makes the above irregularities vanish.  Since
the semantics of the anti-quotation operator '^^' are defined with 
respect to quotation rather than list or vector construction. 


Robin then moves onto a few of his least favourite things:
> My pet HATE is having to declare my lexicals as lvars. I have from time to
> time tried to do little hacks to avoid this, but have not got a stable one.
> Also, while we are at it, the control variable of a for loop should be
> automatically local to the loop. All these things are being incorporated in
> Pepper.

I completely agree.  I think that Scheme shows the correct way to do
loop variables -- it makes them local to the loop and the loop-start
is outside of that local context.  As a consequence, each time around the
loop, the control variable is declared.  This means that simple loops 
such as 
    for i in [a b c] do
        procedure(); i endprocedure
    endfor
would deliver 3 separate procedures instead of just one.


But then Robin starts to edge off the rails by complimenting ML:
> Another thing I would like is a neat, concise syntax for anonymous
> functions. The old LAMBDA .......END construct was painful enough, without
> being replaced by procedure.....endprocedure. ML's  fn <patt> => <body> is
> neat.

It might well be nice to have a concise pair of procedure brackets (and I
tend to use fun ... endfun) but let's not have the ML model.  ML makes 
several dire misdesign moves that makes the kind of mistakes I have been
discussing in POP-11 look like models of excellent design.  The "fn" 
syntax is a prime example.  Suffice it to say that there are two serious
blunders in the design of the anonymous function syntax in ML which
are (1) the lack of a closing keyword (2) using the same pattern continuation
symbol (the vertical bar '|') as the "case" and "fun" constructs where
anonymous functions frequently appear.  The result of this is that it
is usual to write 
    (fn <patt> => <expr>)
in order to prevent unwanted ambiguity from creeping in.  Come back LISP,
all is forgiven!

And I would also like to see the "anonymous" procedure syntax extended to
allow the addition of a name for the procedure.  e.g.
    procedure fact( n );
        if n <= 1 then 1 else n * fact( n - 1 ) endif
    endprocedure
And this wouldn't merely be describing the -pdprops- of the procedure.  The
intention would be that the procedure would be able to refer to itself by
that label.  

What is the point?  Well, it means that the definition of the factorial
function given above is immune from the assignment to "fact".  
Normally writing directly recursive functions means that they are
vulnerable to manipulation of the top-level identifer.  This device
ensures that they keep their meaning.  And this
property means that directly recursive functions can often be significantly
optimised.  This is one of those lovely additions that is completely in
harmony with the language and benefits all users, direct and indirect.

[For compiler writers, note that this means that tail-call optimisation
is safe.]


Finally, Robin moves onto a subject which he clearly worries about
a great deal -- the disparity between POP-11 and functional languages
in the way they effect partial application:
> An interesting point is whether there is any way of getting rid of the
> distinction between application and partial application, which is not a
> fundamental distinction of the lambda calculus, but is only (there) an
> implementation issue. 

I don't think this is the right way of looking at POP-11 at all.  The
proper comparison is that a multi-argument POP procedure is like a 
function with a tupled argument.  POP's partial application freezes
in the first element of the tuple yielding a function whose domain
is one type shorter. 

To illustrate this, let's write a trinary function in both POP-11 and
an imaginary version of ML that dynamically typechecks.

    define foo( z, y, x ); <EXPR> enddefine;

    fun foo( x, y, z ) = <EXPR>;

Now we specialise on the argument x, with x = X.

    vars fooX = foo(% X %);

    val fooX = 
        let fun freeze( frozval, func ) tuple =
                    let val L = tuple_to_list tuple;
                        val T = list_to_tuple( frozval :: L )
                    in
                        func T
                    end;
        in
            freeze( X, foo )
        end;

Now we can see the real advantage of partial application!  There's no
equivalent in strongly typed functional languages because tuples are
not abstracted over in the type system.  But in a dynamically typed
system, such as POP, the advantages are clear.  

In a language like ML, there is always a tension between defining a 
function in curried form or tupled form.  This is because the ML
syntax is geared up to deal more conveniently with tupled functions
but curried functions work with partial application more elegantly.

But in a dynamically typed language such as POP-11, this tension
disappears because we can write our functions in tupled form *and*
partially apply them.  So it is very uncommon to see code such as 
this
    define foo( z );
        procedure( y );
            procedure( x );
                <EXPR>
            endprocedure
        endprocedure
    enddefine;

The closest one gets to writing this is when you wish to partially
evaluate on the basis of the frozen argument.  An example of this
might be the form of a regular expression matcher.  One would typically
write
    define re_match( regexp );
        lvars fast_matcher = re_compile( regexp );
        procedure( target );
         .... fast_matcher( target ) ...
        endprocedure
    enddefine;



> A related problem is that partial application
> in POP-11 "works backwards", as compared with the lambda calculus (and
> therefore ML and Haskell). This is a real problem in mixed language
> working, because there are actually some arguments that are more usefully
> partially applied than others. E.g. we (Burstall and I) chose the order of
> arguments in maplist so that the function argument could be bound by
> partial application.  The order is OPPOSITE in ML.

If one accepts my comparison between partial application and tuple
instantiation, then this is plainly the wrong comparison.  The strongest
statement that you can make is that people (such as Robin and myself)
who come from a functional programming background will find POP-11's
partiall application order counter-intuitive.  However, since no
functional language that I aware of permits partial instantiation of
tupled functions, why should we expect our intuitions to be satisfied?

In short, the analogy between POP-11's partial application and the
kind of partial application we encounter in functional languages
is flawed.  There is no difference between application and partial
application in the lambda calculus because they are the same.  There
must be a distinction between partial application and procedure
application in POP-11 because they are profoundly different.

The order of arguments in functions such as maplist is naturally 
different in ML and POP-11 _because_ their very types are different.
Speaking most approximately ....

In ML    maplist: ('a -> 'b) -> 'a list -> 'b list
POP-11   maplist: ('a -> 'b) * 'a list -> 'b list

When you write the equivalent to ML's maplist in POP-11 the difference
vanishes ....

    define ml_maplist( proc ); 
        maplist(% proc %)
    enddefine;

Now ml_maplist takes the arguments in the expected order and partial
application and application are the same thing.  


> However the lambda calculus  lambda v1...vn.E is really shorthand for
>     lambda v1 lambda v2....E,
> so that the v1 is the first variable to be bound in a beta-reduction, and
> hence should be taken off the top of the stack. POP does it the other way.

Again, this pursues the weak analogy for POP.  Much better would be add the 
following syntax to POP to fix up the problem.

    define ml_maplist( proc )( list );  ;;; allow multiple apps
        maplist( list, proc )
    enddefine;

In fact, I'm all in favour of allowing any expression in the position
of the procedure header that reduces to the application(s) of a variable
to a sequence of variables.  For example, you should be able to write

    define list.proc.ml_maplist;
        maplist( list, proc )
    enddefine;

Not everyone will feel happy with this -- after all which is the
variable name that is introduced with this syntax?  
    list, proc, or ml_maplist
It isn't as visually obvious as in today's POP syntax.  But I feel 
the additional regularity is a worthwhile benefit.


The introduction of this new procedure header syntax really only
gets tricky when we consider dynamic-local formal parameters.  But
that's really very easy -- the binding to dynamic locals only occurs 
when the final parameter is bound in.  In other words, the general
translation of curried procedure definitions would introduce hidden
lexical variables so you can write

    define foo( current_directory )( bill ); dlocal current_directory;
        ....
    enddefine;

and have the current directory set to the frozen value when the 
inner procedure is applied to the second parameter.  In other words
this would get converted into ...

    define foo( v1 ); lvars v1;
        procedure( bill );
            dlocal current_directory = v1;
            ....
        endprocedure
    enddefine;


Steve