1991/07/01 by Edward Cherlin · 1 citation
Computer Science · Mathematics · #Logic, programming, and type systems #Logic, Reasoning, and Knowledge #Formal Methods in Verification #Combinatory logic #Rewriting #Programming language #Expression (computer science) #Completeness (order theory) #Computer science #Conjecture #Sequence (biology) #Algebra over a field #Mathematics #Discrete mathematics #Pure mathematics
paper · doi:10.1145/114054.114065
openalex publication_date 1991/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Any expression in combinatory logic made up of combinators and variables can be abstracted into a pure combinator expression applied to a sequence of variables. Because there are great similarities between combinators and certain APL operators, a similar result obtains in many APL dialects. However, rewriting arbitrary APL expressions as pure functions requires new operators, not provided as primitives by any dialect. This paper defines functional completeness, gives a construction for achieving it, proves a conjecture of Kenneth Iverson that J is functionally complete, and shows how closely the major APL dialects have approached these conditions.