Questions tagged [lambda-calculus]
For challenges pertaining to Lambda Calculus model of computing.
17 questions
3
votes
1
answer
603
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 ...
- 1,461
10
votes
6
answers
775
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(\...
- 339
12
votes
6
answers
501
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 ...
- 22.8k
11
votes
5
answers
632
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 ...
- 79.3k
5
votes
1
answer
429
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, ...
- 2,211
28
votes
6
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 ...
- 103k
7
votes
4
answers
348
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, ...
- 79.3k
17
votes
2
answers
1k
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 \$...
- 79.3k
9
votes
3
answers
525
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 ...
- 79.3k
11
votes
1
answer
441
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 ...
user101133
3
votes
0
answers
276
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 ...
- 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 ...
- 15.6k
5
votes
1
answer
688
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 ...
- 15.6k
9
votes
4
answers
622
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) are ...
- 69.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 ...
- 381
25
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 ...
- 10.2k
52
votes
11
answers
17k
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 ...
- 1,909