Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [lambda-calculus]

For challenges pertaining to Lambda Calculus model of computing.

Filter by
Sorted by
Tagged with
2 votes
0 answers
294 views

Implement the simplest functional programming language

The goal of this challenge is to compare how well different programming languages support functional programming, by seeing how much code it takes to implement BLC8, the simplest functional ...
John Tromp's user avatar
  • 1,176
9 votes
5 answers
532 views

Write a variadic fixed point combinator

A fixed-point combinator is a higher order function \$\mathrm{fix}\$ that returns the fixed point of its argument function. If the function \$f\$ has one or more fixed points, then $$\mathrm{fix} f=f(\...
Legendary Wizard's user avatar
12 votes
5 answers
399 views

Nest some addition

Lambda calculus is a system of computation based on single-argument functions; everything in it is such a function. Due to this functional nature, juxtaposition is commonly used to denote function ...
att's user avatar
  • 20.6k
11 votes
5 answers
531 views

Parse Ternary Lambda Calculus for correctness

Wheat Wizard has once tried to come up with a parsing problem unsuitable for regex, but it failed due to Anders Kaseorg's Perl regex answer. This is the second attempt. Now that we know that Perl ...
Bubbler's user avatar
  • 76.8k
5 votes
1 answer
310 views

Tips for Golfing the Lambda Calculus & Friends

This includes tips for all related derivatives, as coding in these langs often primarily consists of writing the function in the lambda calculus and then compiling it down at the end. Among others, ...
AviFS's user avatar
  • 2,111
25 votes
5 answers
1k views

Parse a lambda for correctness

The goal of this challenge is to fill a niche that is mostly lacking on this site. In my observations there most parsing verification challenges fall into two categories: Super easy parsing. This ...
Wheat Wizard's user avatar
  • 98.8k
6 votes
4 answers
270 views

Ordered, linear, affine, or relevant?

Background Supplementary reading 1, Supplementary reading 2 Linear lambda calculus is a limited form of lambda calculus, where every bound variable must be used exactly once. For example, ...
Bubbler's user avatar
  • 76.8k
17 votes
2 answers
947 views

We all know how to SKI, but can you BCKW?

Background Lambda calculus is a model of computation using lambda terms. A variable \$x\$ is a lambda term. If \$E\$ is a lambda term, the lambda abstraction \$\lambda x. E\$ is a lambda term. If \$...
Bubbler's user avatar
  • 76.8k
9 votes
3 answers
393 views

Implement Fix2 combinator

Background The fixed-point combinator \$\textsf{fix}\$ is a higher-order function that computes the fixed point of the given function. $$\textsf{fix}\ f = f\ (\textsf{fix}\ f)$$ In terms of ...
Bubbler's user avatar
  • 76.8k
9 votes
1 answer
329 views

Tips for golfing in Binary Lambda Calculus

BLC (Binary Lambda Calculus) is a binary encoding of untyped lambda calculus which was created to “provide a very simple and elegant concrete definition of descriptional complexity.” What are some ...
user avatar
3 votes
0 answers
261 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 ...
towc's user avatar
  • 344
22 votes
1 answer
2k 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 ...
Esolanging Fruit's user avatar
5 votes
1 answer
632 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 ...
Esolanging Fruit's user avatar
9 votes
4 answers
536 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) ...
lynn's user avatar
  • 68.7k
10 votes
3 answers
1k 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 ...
MaiaVictor's user avatar
24 votes
4 answers
2k 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 ...
FUZxxl's user avatar
  • 10.1k
52 votes
11 answers
16k 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 ...
sepp2k's user avatar
  • 1,869