Normal order and applicative order in Programming Languages

James had mentioned applicative and normal order in a post, on which Matthias commented and then elaborated here.

Normal order and applicative order are failed attempts to explain the nature of call-by-name programming languages and call-by-value programming languages as models of the lambda calculus. Each describes a so-called _reduction strategy_, which is an algorithm that picks the position of next redex BETA that should be reduced. By 1972, it was clear that instead you want different kind of calculi for different calling conventions and evaluation strategies (to the first outermost lambda, not inside). That is, you always reduce at the leftmost-outermost point in a program but you use either BETA-NAME or BETA-VALUE. Non-PL people were confused (and still are) because BETA-NAME looks like BETA but nearly 40 years later, everyone should figure this out. SICP was written when the majority of people were still confused. — Matthias

One thought on “Normal order and applicative order in Programming Languages”

  1. It’s the best time to make some plans for the longer term and it’s time to be happy.
    I have learn this post and if I may just I desire
    to recommend you few interesting issues or suggestions.
    Perhaps you can write subsequent articles referring to this article.
    I desire to learn even more things approximately it!

Leave a Reply

Your email address will not be published. Required fields are marked *