Lazy Strong Normalization | Zendy

Luca Paolini | Zendy; Elaine Pimentel | Zendy; Simona Ronchi Della Rocca | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Lazy Strong Normalization

Author(s) -

Luca Paolini,

Elaine Pimentel,

Simona Ronchi Della Rocca

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.06.013

Subject(s) - haskell , functional programming , lazy evaluation , lambda calculus , normalization (sociology) , computer science , combinatory logic , programming language , class (philosophy) , typed lambda calculus , intersection (aeronautics) , theoretical computer science , characterization (materials science) , mathematics , calculus (dental) , discrete mathematics , artificial intelligence , medicine , materials science , dentistry , sociology , anthropology , engineering , nanotechnology , aerospace engineering

Among all the reduction strategies for the untyped λ-calculus, the so called lazy β-evaluation is of particular interest due to its large applicability to functional programming languages (e.g. Haskell [Bird, R., “Introduction to Functional Programming using Haskell,” Series in Computer Science (2nd edition), Prentice Hall, (1998)]). This strategy reduces only redexes not inside a lambda abstraction.The lazy strongly β- normalizing terms are the λ-terms that don't have infinite lazy β-reduction sequences.This paper presents a logical characterization of lazy strongly β-normalizing terms using intersection types. This characterization, besides being interesting by itself, allows an interesting connection between call-by-name and call-by-value λ-calculus.In fact, it turns out that the class of lazy strongly β-normalizing terms coincides with that of call-by-value potentially valuable terms. This last class is of particular interest since it is a key notion for characterizing solvability in the call-by-value setting

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research