[Fwd: Language Syntax Suggestion]

[Matthew Tuck]

Hans-Dieter Dreier wrote:

> I would appreciate if you could give your definition of an AST along with
> some examples. It seems to me that your concept of an AST is somehat
> different from mine (which is rather informal).

Well it's basically just a tree that represents the program.

                                  ...
                                   |
                                   |
                                 while
                                /     \
                               =      call
                              / \    /   \
                             x   y  procA y

for "while x = y do procA(y)"

> That confuses me. I would think that if you extended the syntax (i.e. the
> formal description of the language) without changing the AST (representing
> a particular program), the meaning would not change. And isn't "extending"
> a change ?

Perhaps you're confused by my use of extensions here.  What I meant was
that  you create a new sort of tree node that can appear in the tree. 
This subtree would be simpler than the corresponding full form subtree,
but shorter.

> OK. What about local variables that are initialized on funtion entry and
> lost on exit?Strictly speaking, assignments to these are side effects, but
> since they depend solely on the start conditions and do not constitute
> persistent "state", allowing them should make no difference. Using them
> couldn't produce different results from the same start conditions.

Ok.  You can pass these as parameters to procedures, providing these
procedures don't have any bad side effects, such as holding onto values,
storing them elsewhere etc.  These would be procedures which are really
just computations and hence similar to functions.

Procedures could have side effects in a nested procedure language like
Ada, e.g.

func C
	var X: integer

	proc D
		X = 3
	end D

begin

	call D

end

The side effect has no effect outside the function and hence is OK.

> A higher-order function is one with some of the parameters already
> provided, and some not, am I right?

No, that's partial application, aka currying.  This is where you could
say take +, and bind a value to one parameter at run-time, giving a
unary function.  It's standard practice functionally, possible to do in
OOP (by binding parameters inside a wrapper object), and impossible to
do in general in imperative languages, although possible, if kludgey, in
most circumstances.

A higher-order function is a function that can take code as a
parameter.  A first-order function could only take data.

> A naughty-object! What a funny term. Do you mean a non-constant object
> that does not belong to the local scope of the function? Such as a
> instance variable or class variable ? Read accesses to those could produce
> different function results from the same start condition as well.

Basically you can't write to anything that has not been generated inside
the function.  Read accesses outside the function should be ok since
they can't have been changed in the meantime.  So local variables and
locally allocated heap is OK.

> BTW: The information whether a function causes side effects IMO is a
> valuable one for the compiler, since being side effect free might be a
> neccessary condition for some kinds of uses (conversions, conditions, all
> kinds of stuff that the compiler is free to use or omit). So I think the
> compiler will check for this and mark the function accordingly. Or the
> user may mark the function as intended to be side effect free, and the
> compiler checks this, or both.

I think the latter is useful since it's useful for the programmer too. 
Also, this might be useful typing information, e.g. a method declared to
be side-effect free can not be overridden by one with side-effects. 
This would be useful for a call to a.b(c) ensuring there is no side
effect regardless of what class a happens to be.

> I agree. At least the programmer must be aware of it and take it into
> account, but I think if the rules of lazy evaluation can be made clear
> (and are not too awkward), it might be a nice thing even in the presence
> of side effects. Or it could be defined that evaluation is guaranteed to
> take place sometime before the first side effect occurs - results should
> then remain the same.

Interestingly enough, some functional languages are moving away from
lazy evaluation.  Also, lazy evaluation is similar to the concept of
call-by-name parameter mode, and it can suffer the same problems of
different value depending on where it has calculated.

-- 
     Matthew Tuck - Software Developer & All-Round Nice Guy
             mailto:matty@box.net.au (ICQ #8125618)
       Check out the Ultra programming language project!
              http://www.box.net.au/~matty/ultra/