Re: Call by name in Algol-60

RogerHA <RogerHA@aol.com> wrote:
> > ...... Andrejs assumes that the
> > thunks are _done_ in the called procedure code, but this is not right,
> > you have to do it at the place where the procedure is called. This is
> > the environment where everything is known about how to evaluate the
> > parameter and calculate its adderss (if allowed) to do an assignment.


For clarity, I suggest using the terms: thunk being compiled
(involving the encoding of the names known and block nesting at the
point at the point of a procedure call) and thunk being executed
(during the execution of the body of the called procedure as noted by
Andrejs). Thunks for element variables can each be thought of as two
procedures or one 2-entry point procedure with 0 parameters;
typically, calling the one entry point returns a value, and calling
the other returns an address. If the actual parameter is an array, a
further complication arises.


xxx@info.lv wrote ( occasional snips .... and added _emphases_):
> Many thanks for explanations.
>
> I understand that a thunk is executed in the calling procedure's
> environment and that all the identifiers in the thunk have
> associations as if this thunk would be a function defined inside the
> calling procedure's body. I also understand that a thunk is compiled
> for each actual parameter, not for a formal one. Perhaps, I haven't
> explained that clear enough in my original posting.
>
> > Actually, the compiler does not have to remember much, if
> > anything. What you do is compile the code to evaluate the parameter,
> > and separate code to assign to it, at the point of the procedure
> > call. This code is not executed at the call, you just jump over it.
>
> Yes, this was how I always thought it should be implemented.


Right.


> >What you pass to the called procedure is the addresses of the two
> > routines, and a pointer to the stack frame. So, when the parameter is
> > to be fetched or assigned to, all you have to do is temporarily re-set
> > the variable stack pointer (to somewhere lower down) and call a
> > subroutine. If the parameter is passed on as a parameter to yet
> > another procedure, or recursively, all you do is pass on the three
> > pointers. Type conversion may have to be taken care of, one way way of
> > doing this is to put the required/actual type on the stack as a
> > parameter of the evaluation/assignment subroutine. Jensen's device
> > invloved having two parameters by name. The actual parameters were an
> > array element whose index is the other parameter. e.g. the formal
> > parameters might have been REAL a; INTEGER i; and the actual
> > parameters A[B], B.
> > >>
> > So, if the actual parameter is K+1, the routine to fetch the value
> > does it, and the routine to do an assignment causes a run-time
> > error. All this is possible in a one-pass compiler, even without
> > forward declarations. What you do is have code which sorts out the
> > parameters at the point where a procedure starts executing. At this
> > point the type of all the formal parameters is known. Any parameters
> > which are by value get de-referenced at that point, and then behave as
> > local variables. Within the body of the procedure, any reference to
> > one of the parameters by name causes the thunk whose address is on the
> > stack to be called.
>
> Well, I still don't understand why such a very complex solution (with
> two separate thunks for each actual parameter) is necessary. Why much
> simpler one, where a thunk always returns an address (of a temporary
> location in memory in the case of expression) will not work properly ?


The reason is buried in the ideas of an assignment statement such as


y := x + 1


In order to do this, a computer needs the *value* of x (sometimes
called the r-value of x, the x occurring on the right of the := ), and
not the value but the *address* of y (sometimes called the l-value).
In some Algol 60-related machines as the Burroughs mainframes, there
were 2 machine instructions VALC (value call) and NAMC (name call) to
load the value or address of a variable to the top of the run-time
execution stack. Correspondingly, usually, thunks have the 2 entry
points.


> If we go for your solution, then I wonder how it should be
> implemented:
>
> 1. A compiler scans each actual parameter two times and generates the same
> code twice, the only difference being at the end of the code (fetching or
> assignment).
>
> 2. The part of the code identical for both thunks is simply copied from the


> first thunk to form the second one (except the difference mentioned in
> the p. 1).
>
> If, in the case of an actual parameter being an expression, the second
> thunk is there only to cause a run-time exception, wouldn't it be
> better to check this already in the compiling time ?


Sometimes the check is effectively impossible, especially if the
actual parameter is passed down through a couple of layers of
procedure calls. It may happen in a program that in those cases where
an expression is passed as an actual parameter, the formal parameter
is never assigned to, but in some of the cases where the actual
parameter is a variable or array element, the formal parameter is
assigned too.


> [I believe it's not possible to verify statically whether or not a
> call-by-name routine assigns to a variable. Imagine a situation where
> it depends on the input, and you know that for external reasons the input
> will always make it do something valid. Also consider that useful algol60
> systems needed to support separate compilation and libraries. -John]


Aha ! Extensions ! Vive l'Algol 60.
--
John H. Lindsay lindsay_j@rmc.ca
Department of Mathematics and Computer Science
ROYAL MILITARY COLLEGE OF CANADA
P O BOX 17000 STN FORCES
KINGSTON ON K7K 7B4 CANADA


Phone: (613) 541-6000--1--6419
Fax: (613) 541-6584




--

Return to the comp.compilers page.
Search the comp.compilers archives again.