Jump to content

Talk:Jensen's device

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Discussion about Jensen's Device

[edit]

Glrx (talk) 18:35, 4 July 2012 (UTC)[reply]

Glrx (talk) 18:51, 4 July 2012 (UTC)[reply]

The reference to Knuth, D. E. (October 1967), "The Remaining Troublespots in ALGOL 60", Communications of the ACM 10 (10): 611–617 appears misaimed. Google fingers [Ellis Horowitz, Programming Languages: A Grand Tour, 1983, Computer Science Press, pp 61–68]link removed which indeed has the required title but its page span is 61-68, whereas the reference to it fingers page 613 (reference 6 in the current article, via reference 4 to the author and title) which may be the page numbering in the original journal. This .pdf file is an image file only (and with misaligned pages); no searchable text. Anyway, on page 63, near the base of the first column is indeed a criticism of call-by-name via "increment(A(i))", the problem being that "i" might be a function (with no parameters) or an expression that has side effects or in any case produce a different result on the second invocation in the equivalent of "increment", namely "a(i):=a(i) + 1;" It seems to me that this criticism ought to be found in the call-by-name article as it is general.
The reference to the comp.compilers is particularly interesting as it is written by someone who has produced a working Algol compiler, and indeed notes the two sorts of call-by-name implementation details: at the call site, for each parameter there is provision for when a value is being assigned to the parameter, and a second provision for when a value is being obtained from the parameter, with remarks about run-time errors being invoked as when the actual parameter is an expression and an assignment of a value to it is attempted. Likewise mention of call-by-reference equivalence for simple variables as actual parameters. NickyMcLean (talk) 20:23, 4 July 2012 (UTC)[reply]
The CACM ref is correct; I used the actual Journal. If you look at your ref on the first page, the title has an asterisk. The note associated with the asterisk is "Reprinted from Comm ACM 10, 10, 1967, 611-617". The variable i might also be a call by name parameter. Yes, this article is now going into detail about CBN, but that is because CBN is needed to explain JD. When things settle out, I won't have a problem with moving/copying parts to CBN.
I've seen a few of descriptions about how CBN is implemented and some other sources that suggest other possibilities. Evaluation is clear, but the setting is not. If we take the Copy Rule to be the absolute truth, then separate thunks seem required, but I don't have any RS for that. I object to comparing it to CBR. Yes, both induce a side-effect, but that does not mean it looks like CBR. Certainly the called procedure isn't making a choice based on whether the passed argument was a variable or an expression. I've come across some class notes where a prof claims that a single thunk computes an L-value that is either read for an access or filled for a set. I'm not sure that is right. Consider
begin procedure foo(x)
     real x;
     begin
       print(x);
       x := 3.14159;
     end;
end;

integer i;
i := 6;
foo(i);
I'm not an Algol expert, but if common integer-real casts occur and I believe the Copy Rule, then the code above is clear and i gets assigned the value 3. The eval thunk picks up i and converts it to a real. The set thunk takes a real argument and computes i := arg;. If a variable looked like call by reference, then there would be an error or i would contain a bit rep of pi. Maybe the casts are prohibited. But the take away is the dual thunk can do an exotic assignment -- something that has a side effect but does not look like CBR.
Glrx (talk) 21:02, 5 July 2012 (UTC)[reply]

I think that the article's mention of "increment(i)" should contain the detail that the "i" might be something tricky because as it stands, it is not at all apparent what might be the problem. This is explained in the article that you indeed referenced correctly: I missed the starred footnote, so suitable words need not be rejected as Original Research/unsupported.

Years ago, I noticed the similarity in fortran between the mention of f(i) as an array and f(i) as a function of an integer. (Pascal insists on f[i] for arrays and f(i) for functions, alas) and made use of this in the case when the array was actually stored in a disc file, and f(i) was a function that read the appropriate record, etc. This was also useful for counting usages, checking bounds, debugging, etc. Alas, there was no provision for the likes of f(i):=value; in the same convenience of not having to modify the source file very much for an array becoming a function. Thus I thought about "palindromic" functions, that is a function pair where a function could be evaluated backwards, so to sprak. Then I encountered pl/i and its rather blathersome text handling - it required a function "substr" as in substr(text,StartIndex,Length) to obtain a substring of a text-holding variable. But it also allowed substr(blah) = newtext; to replace a portion of text variable. Oho! Palindromic! And similarly, rather than having v:=sin(a) and a:=asin(v) as inverse functions, why not allow sin(a):=v; instead? Whee! In such an environment, supplying an expression that provides a result that instead is invoked backwards might become a notion more clearly thought about and handled or disallowed. An attempt at generality would involve the compiler attempting to invert an expression so that if the actual parameter were "x + 1" then an attempt to assign a value to this expression would come out as "x + 1 = v" which would be inverted to x:=v - 1" but this is surely going to be difficult if not outright impossible in general. Perhaps there could be a class of allowable expressions/functions that are restricted to expressions that are easily inverted, and functions for which there is a palindromic entry available. For instance, integer/floating-point/double-precision approximations: I've always been uncomfortable about "promotion" but on the other hand am annoyed by the proliferation of combinations to do the same thing but to variables of different type, especially as the count of parameters increases. Thus, abs(x) is "generic".

Retreating from these amusements, it seems to me that pass-by-reference could still be used as a stepping stone to the understanding of pass-by-name, in the style of compare&contrast. And possibly the bulk of the criticism should be in the call-by-name article, except that suitable usages of perverse expressions could cause odd behaviour. Both the swap and increment examples are of statements rather than value-generating expressions as would be the usual fodder for Jensen's device. A perverse example could be devised, such as the expression A(i:=i/2) but obviously a reader would object that no-one would do such a thing, and offhand, I can't contrive a semi-sensible expression that would display the problem. Your foo function would do as of course, given a function, one might reasonably desire the sum of a few evaluations, and a function might contain anything (for debugging, record-keeping) but again one might ask why such a thing would be done.

For the general criticism of call-by-value I can imagine a run-time speed issue: pass-by-reference in many of the cases where it has the same result will surely be much faster, and, require less code. NickyMcLean (talk) 00:21, 6 July 2012 (UTC)[reply]

Yes, the increment problem should get more explanation. Screwy failure is increment(A[increment(i)]).
Some varieties of Lisp have a SETF macro. Originally intended for setting array elements and structure elements, its mechanism allowed some simple expression manipulation/solving. It could be hacked so (SETF (sin y) 0.5) would set y to the arcsin.
No, pass by reference should not be used as a stepping stone. It has no relationship to the Copy Rule, and it ends up suggesting the wrong thing. The two methods share the notion that variables can be side-effected, but that does not mean they are achieved by similar mechanisms. As I said, some prof issued class notes that has a single argument thunk computing the L-value, so it cannot do a general Copy Rule. I can see the prof/somebody else coming up with that idea because they've been poisoned with the notion that a side-effect must be done with an L-value.
Call-by-name is "involved" rather than "subtle". There's a lot of machinery working behind the scenes: the arguments are turned into subroutines with private environment pointers. It is not a trivial mechanism that has some subtle points. Its all the overhead that makes the CBN unattractive.
Couple in the semantic problems, and call-by-name is essentially dead. Algol 68 added call-by-reference.
The second version of the swap code is unneeded. Simply pointing out that the code works for most cases (even Swap(A[i],i)), but it cannot be made to work for all cases.
Glrx (talk) 16:18, 9 July 2012 (UTC)[reply]

Ah, it hand't occurred to me to consider a double increment... With regard to "Call-by-name is involved", that can easily be read as in "X is involved [in the murder of y]", so if you don't like "subtle" perhaps because computers are deterministic, not subtle, how about "Call-by-name is an involved protocol"? That will exclude the wrong reading. But really, we're saying that a seemingly simple notion turns out to involve surprising behaviour. "Call-by-name involves subtle effects"? As for "environment pointers" I don't think that a helpful notion. My understanding is that the subroutine contains what amounts to a subroutine call to store or read a value for its parameter, yes, but the "subroutine" is in fact inline code in the caller's environment (one for "read", one for "write") with therefore by default the environment of the caller in force, without any pointers to this environment (private or whatever) being involved for the subroutine to keep secret. The pointer(s) to this inline code are the parameters, but they're not pointers to an environment as such, they are pointers to code entry points. As a semi-example, suppose a call-by-name parameter is passed as an address with the convention that (address) is the entry point of a subroutine that will return a value like a function call, and (address+1) is the entry point of a subroutine that will receive a value and do something with it, like a palindromic function. At each invocation of the Sum routine, the compiler will place appropriate code for the actual parameters, and for a parameter that is an expression (where "write" is unworkable), the (address+1) value will be a jump to some run-time error routine.

I approve of call-by-reference for reasons of speed and compactness (and the side effect risk is now seen as trivial!) but I do like the call-by-name facility for passing expressions as in the Sum function, because otherwise there is clunkiness involving the apparatus for definition of a function for each of the desired expressions. A pity then that other trickiness in the language enables confusion to the degree that Algol68 has retracted the feature - though possibly it could be enable by declaring a parameter to be "by name" as a special exemption, with expectation of polite usage... NickyMcLean (talk) 21:56, 9 July 2012 (UTC)[reply]

The mechanism is involved; the understanding is subtle? Call-by-name has a lot of behind-the-scenes machinery / overhead / complexity / (something implying the elegance is slow). There are subtle/surprising consequences of that machinery with regard to side-effects -- such as swap doesn't work. One source suggested Algol 60 designers adopted the Copy Rule for procedure semantics because it looked like the right thing, but then they were surprised by the glitches. Jensen's device shows the elegance, and swap shows the surprise. (That's the take away that should end up in another article's CBN description.)
The environment pointer is needed and is another bit of involved Algol magic. The thunks/subroutines are executed in the calling code's environment. Plus, the thunks may call procedures that will build new environments / need new stack space. The formal parameters might be accessed within new lexical scopes, or they may be passed by name to routines with a higher lexical scope. Basically, the implementation needs more than just a stack pointer. (Allowing procedures to return closures requires a heap.)
Glrx (talk) 22:55, 9 July 2012 (UTC)[reply]
[edit]

Hello fellow Wikipedians,

I have just modified one external link on Jensen's Device. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 09:44, 24 November 2017 (UTC)[reply]

This article is not clear, need a better structure

[edit]

Jensen? Who is Jensen. What problem solves? Why is called a device? How the examples work? What is the difference with macros? In the GPS example, GPS always returns 1, but is used in the condition position of several IF statements. Does 1 means true in Algol? if true then s1 else s2 is equivalent to s1 Does 1=Z has some meaning in Algol? This is the example, copy/pasted and indented 

 real procedure GPS(I, N, Z, V)
   real I, N, Z, V;
 begin 
  for I := 1 step 1 until if I=0 then -1.0 else I do Z := V;
  GPS := 1 
 end;

 I := GPS(I, 
          if I=0 then -1.0 else I,
          P, 
          if I=1 then 1.0
          else if GPS(A, I, Z, if A=1 then 1.0 
                               else if entier(A)×(entier(I)÷entier(A))=entier(I) ∧ A<I then 0.0 
                                    else Z) = Z then (if P<m then P+1 
                                                      else I×GPS(A, 1.0, I, -1.0)) 
          else P )

I don't have the cited article to understand it. Maybe someone can clarify what is going on here and what precisely the Jensen device is, and what effect is used in the example. Perhaps it behaves like a data flow machine. Lazy languages, have call-by-need semantics, close related to call-by-name, and lazy languages can deal with infinite structures, like streams, in a very transparent way, making easy to implement data-flow machines. I suppose that effect could be the idea behind Jensen devices, but I can't understand it from the article. For that reason I am suggesting to rewrite it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Jensen%27s_device&oldid=1198857594"