J.C. Mitchell cites in his "Expressive power of programming languages" the result in Riecke's "Fully abstract translations between functional languages" about the call-by-value, call-by-name and lazy versions of the language PCF.

He mentions: In lazy PCF, call-by-name evaluation order is used, but additionally termination is observed using some convergence-testing language primitive.

In general terms, he says, the main results are that call-by-value and lazy PCF are equally expressive (apparently shown in Riecke by means of an abstraction-preserving reduction), and both are more expressive than call-by-name PCF.

The first part, of this previous statement is intuitive. The second is not yet to me.

EDIT: Removed some nonsense I had written earlier.

  • $\begingroup$ I am not sure what sort of an answer you're expecting here. It would help to know whether you read the cited papers, attempted to read them, or you're just hoping someone will give an executive summary (which is what this site is good at)? $\endgroup$ – Andrej Bauer Aug 14 '16 at 20:36
  • $\begingroup$ @AndrejBauer Didn't attempt to read Riecke's paper yet. Yes, I was actually hoping for a summary that would help me when I do read it. Thanks. $\endgroup$ – Akram El-Korashy Aug 15 '16 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.