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$ Aug 14, 2016 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$ Aug 15, 2016 at 11:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.