Questions tagged [lambda-calculus]

For challenges pertaining to Lambda Calculus model of computing.

Filter by
Sorted by
Tagged with
4
votes
0answers
210 views

λ-calculus to js arrow notation transpiler [closed]

Not an interpreter. Arguably a compiler. But I'm talking about a transpiler. It can be in any language, but it must return js-valid arrow notation code. The λ-calculus string would be passed as an ...
20
votes
1answer
660 views

Convert λ-expressions to SK-expressions

The λ-calculus, or lambda calculus, is a logical system based on anonymous functions. For example, this a λ-expression: λf.(λx.xx)(λx.f(xx)) However, for the ...
6
votes
1answer
410 views

Convert between Lambda Calculus Notations

The lambda calculus is a system of functional programming. Lambda calculus consists of variables, abstractions, and applications. A variable is simply a name denoting a function parameter. It is a ...
9
votes
4answers
450 views

Visualize Church numerals

Background Visualizing λ-calculus terms Famous lambda-juggler (and code golfer) John Tromp devised an interesting visualization of terms in the λ-calculus. In his words: abstractions (lambdas) ...
8
votes
3answers
802 views

Sort a list of numbers on the λ-calculus

Write a term on the pure untyped lambda calculus that, when applied to a church-encoded list of numbers, returns it with its numbers sorted in ascending or descending order. Church lists and numbers ...
22
votes
4answers
779 views

Optimizing SKI compiler

The SKI calculus is a variant of the Lambda calculus that doesn't use lambda expressions. Instead, only application and the combinators S, K, and I are used. In this challenge, your task is to ...
45
votes
13answers
13k views

Write an interpreter for the untyped lambda calculus

The challenge is to write an interpreter for the untyped lambda calculus in as few characters as possible. We define the untyped lambda calculus as follows: Syntax There are the following three ...