SKI Combinator Calculus
The SKI combinator calculus, introduced by Schönfinkel and Curry, is a Turing complete logic system representing lambda calculus operations with S, K, and I symbols. It encodes operations, supports recursion, and connects to intuitionistic logic.
Read original article
The SKI combinator calculus is a simple Turing complete logic system used in the mathematical theory of algorithms. Introduced by Moses Schönfinkel and Haskell Curry, it represents operations in lambda calculus using three symbols: S, K, and I. The system allows encoding all operations in lambda calculus and is considered a reduced version of untyped lambda calculus. It features combinators that act as functions applied to arguments, with rules defining their behavior. The system can be extended to include recursion and Boolean logic operations like NOT, OR, and AND. The combinators K and S correspond to axioms in sentential logic, showcasing a connection to intuitionistic logic. The system's completeness allows for expressing Boolean logic operations as prefix, infix, or postfix operators within the SKI notation. Overall, the SKI combinator calculus serves as a fundamental system in the study of algorithms and logic.
Related
F (2006)
F is a functional concatenative language with K3 list operations and Joy's dip combinator. It enforces one-time assignment, supports floating-point and symbolic datatypes, and emphasizes function-valence and -charge theories. The language is purely functional, prohibiting side-effects and reassignment, with various primitives for arithmetic, logic, and list operations. F also provides interactive commands for debugging and manipulation, focusing on simplicity, efficiency, and functional programming paradigms.
Semantics and scheduling for machine knitting compilers (2023)
Carnegie Mellon Textiles Lab develops formal semantics for knitout, enhancing machine knitting precision. Research by Lin et al. in ACM Transactions on Graphics establishes robust foundations for compiling and optimizing knit programs.
Chomsky–Schützenberger Enumeration Theorem
The Chomsky-Schützenberger enumeration theorem connects formal language theory and abstract algebra, focusing on word counts in unambiguous context-free grammars. It has applications in combinatorics and highlights ambiguity in certain languages.
Grokking the Sequent Calculus (Functional Pearl)
The paper introduces the lambda-mu-mu-calculus as a term assignment system for the sequent calculus, emphasizing its symmetry and suitability for compiler intermediate languages. It targets a broader audience and will be presented at ICFP '24.
Show HN: Programming with Bird Emojis
The programming language Birb uses bird emojis to represent lambda calculus terms. Syntax involves bird emojis, and semantics reduce birds in associative order. Birb is Turing complete, with a transpiler converting to SKI combinators and Jot.
5 comments> The simplest possible term forming a basis is X = λx λy λz. x z (y (λ_.z)), which satisfies X (X X) (X (X X) X X X X X) = K, and X (X (X X (X X (X X))(X (X (X X (X X)))))) X X = S.
Related
F (2006)
F is a functional concatenative language with K3 list operations and Joy's dip combinator. It enforces one-time assignment, supports floating-point and symbolic datatypes, and emphasizes function-valence and -charge theories. The language is purely functional, prohibiting side-effects and reassignment, with various primitives for arithmetic, logic, and list operations. F also provides interactive commands for debugging and manipulation, focusing on simplicity, efficiency, and functional programming paradigms.
Semantics and scheduling for machine knitting compilers (2023)
Carnegie Mellon Textiles Lab develops formal semantics for knitout, enhancing machine knitting precision. Research by Lin et al. in ACM Transactions on Graphics establishes robust foundations for compiling and optimizing knit programs.
Chomsky–Schützenberger Enumeration Theorem
The Chomsky-Schützenberger enumeration theorem connects formal language theory and abstract algebra, focusing on word counts in unambiguous context-free grammars. It has applications in combinatorics and highlights ambiguity in certain languages.
Grokking the Sequent Calculus (Functional Pearl)
The paper introduces the lambda-mu-mu-calculus as a term assignment system for the sequent calculus, emphasizing its symmetry and suitability for compiler intermediate languages. It targets a broader audience and will be presented at ICFP '24.
Show HN: Programming with Bird Emojis
The programming language Birb uses bird emojis to represent lambda calculus terms. Syntax involves bird emojis, and semantics reduce birds in associative order. Birb is Turing complete, with a transpiler converting to SKI combinators and Jot.