Re: [stack] S-K Construction of Dip?

On 10/3/07 2:16 AM, "William Tanksley, Jr" <[email protected]> wrote:

> I've been hammering this in my mind, but I can't get it to work out right.
> 
>> > Compile into machine language or assembler. Assignments translate into a
>> > sequence of instructions, but that is of no interest here.  Compound
>> > statements translate into the sequence of instructions produced by the
>> > sequence of statements, also of no interest. But interestingly,
>> conditionals 
>> > and loops are  translated into a FLAT sequence of instructions containing
>> two 
>> > new instructions that are not in the source language: conditional and
>> > unconditional JUMP instructions. We also have the notion of a program
>> counter, 
>> > which is simply incremented by most instructions. Only the JUMP
>> instructions 
>> > change the program counter explicitly.
>> > 
> The problem is that machine language/assembler uses explicit offsets to
> express jumps and branches, and those destroy referential transparency. In
> effect, you can't split a valid program into two arbitrary parts and have
> the two parts still be valid -- if you cut in the middle of a branch, the
> branch will then lead off into nowhere.
> 
Since the language had assignments, there was no referential transparency to
start with. But take the purely functional subset of just about any language
(Lisp Pascal C..), and translate the expression f(g(a),h(b)) into assembler.
In the definitions of f(,) g() and (h() there will be some code ending with
a return (which also restores the program counter from the run time stack).
The corresponding calls all push the program counter. The entire expression
assembles into something like the following five instructions: push(a),
call(g), push(b), call(h), call(f). This is just postfix code, where each
operation does something to various parts (stack, stack pointer, program
counter,..) of the actual or virtual machine. And the concatenation of the
five operations computes the composition of the five functions computed by
the five parts. Concatenative according to my definition:

If P is a program which computes a function F, and Q is a program which
computes a function G, then the concatenation P Q of the two programs
computes the composition F G of the two functions.

But I suspect that it is not by your definition. (I got a similar impression
some time much earlier). You mean (or you also mean, or you mean by ³flat²):

If P is a program consisting of concatenated parts p1 p1 .., and P computes
a function F, then each of the parts compute functions f1 f2 .., and F is
their composition.

This happens to be satisfied by my assembled expression, but it is not part
of my definition of concatenative. It is true that cutting in the middle of
a branch leads somewhere else, but where it leads is still dependent on what
the cut inserts of deletes.

Of course nobody expects cuts to be permissible inside an instruction. Thus
call(h) does not have 3 parts: cal  l( h).

- Manfred






[Non-text portions of this message have been removed]