The lecture notes you sent are interesting. I always used the terms applicative order and call-by-value (and strict, for that matter) to mean the same thing. Maybe other people do too, and when they say applicative-order Y-combinator they really mean call-by-value Y-combinator?
Here’s my attempt of explaining what’s going on: applicative order is a reduction strategy, while call-by-value is an evaluation strategy. The difference being that reduction is nondeterministic and evaluation is deterministic. You’re correct that using the Y-combinator may diverge on applicative order, but it may also produce a value in some other nondeterministic branch. Generally, we’d ignore the branch that diverges. And the call-by-value evaluation strategy wouldn’t have the same problem because it’s restricted to not reduce inside λs.
Maybe that’s why people abuse the terminology and call applicative order what they should be calling call-by-value.
Thank you very much! This makes sense.
Wait a minute. The applicative order reduction needs to reduce the leftmost-innermost first. While the reduction in general is allowed to be non deterministic, the leftmost-innermost order forces the reduction to be deterministic, no?
I guess another interpretation of “nondeterministic” here means we can stop reduction at anytime, but given a term like ((Y (lambda (fact) ...)) 5) where ... is the usual implementation of the factorial function, we would want the term to evaluate to 120. Now we are in the situation where “we can stop at anytime” doesn’t help.
what is the best way to typeset racket code in a general LaTeX document? the listings package doesn’t even support scheme, only a generic Lisp
I think somehow it is possible to use the LaTeX produced by Scribble.
I’ve done a variety of things. Use Scribble, use Slatex, just use verbatim.
Just out of curiosity, is anyone here participating in this year’s Advent of Code (https://adventofcode.com/)? I’m using it to learn Racket (started some of the exercises in Elvish, but switched to Racket for Day 6)