Questions tagged [combinatory-logic]

For questions about logical systems defined via the application and term-rewriting of combinators. These systems often have a close connection to the lambda calculus.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 views

Relation between NOT gate and negative numbers 2's complement

The steps to get a number in 2's complement are simple: Flip the bits (Using NOT) Add +1 (afaik this step is done to eliminate the duplicate 0) Recently I've seen an ALU design that can operate ...
redigaffi's user avatar
  • 101
0 votes
3 answers
84 views

Is there a 2SAT encoding for a NAND gate

I am trying to encode some circuit checking algorithms, but encountered difficulty creating a 2SAT representation for a NAND circuit. Is there a proof that this is not possible?
Hovercraft2's user avatar
4 votes
1 answer
85 views

Book references for combinatory logic as applied in Haskell?

I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell? I found "Combinators: ...
tryst with freedom's user avatar
1 vote
1 answer
171 views

Iterating over combinations of 4 timestamps from 2 timelines *efficiently*

I need help in finding a more performant algorithm. I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
Enyium's user avatar
  • 11
1 vote
1 answer
55 views

K in SKI combinator calculus: why doesn't it take one parameter since it ignores its second?

In the SKI combinator calculus, Kxy returns the constant function which always returns x. Since y is always ignored, why not just define K as having a single parameter, namely, x? What is the purpose ...
Hank Igoe's user avatar
  • 179
0 votes
0 answers
32 views

optimization problem about capacitated vehicle routing problem

I have an optimization problem. The problem consists initially of the presence of several trucks, each one having different maximum capacities. There are also multiple customer orders, each with a ...
Fernanda's user avatar
1 vote
1 answer
62 views

Must the evaluation strategy for a language be specified in order to apply the Church-Rosser Theorem?

The Church-Rosser Theorem [0] states that the Lambda Calculus (LC) is confluent: between a source expression S and target expression T, the latter in normal form, for any given P, a sequence of ...
jpt4's user avatar
  • 39
0 votes
2 answers
54 views

Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)

I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than O(N²) ...
David Hoyos's user avatar
1 vote
2 answers
247 views

Combinational logic check if bits is prime

I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not. For example given input fixed 8-bit that will produce 1-bit output. 00000101 will ...
Muhammad Ikhwan Perwira's user avatar
2 votes
2 answers
91 views

Why do combinators look this way?

Out of curiosity, why do combinators look this way? For example, why is $K = \lambda x y \to x$ and why is it called $K$? Why is it not $\lambda x y f m \to f m x$? These are just arbitrary letters, I ...
alexey polusov's user avatar
3 votes
1 answer
133 views

How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?

In Haskell, we can use the following code to define fibonacci numbers, fibs = 1 : 1 : zipWith (+) fibs (tail fibs) And its time complexity is linear. I cannot find ...
Lin Jin's user avatar
  • 63
2 votes
0 answers
61 views

What are the fixed-points of the Y combinator?

Since the Y combinator itself is a function (albeit a higher-order one), I was wondering what the fixed-points of Y itself are.
brj's user avatar
  • 121
0 votes
1 answer
331 views

What benefits are obtained by allowing the occurrence of free variables and open terms in lambda calculus?

Because of the existence of free variables in lambda calculus, the evaluation of open terms (at least as outlined here) is more complicated relative to the evaluation of closed terms since the ...
nicoty's user avatar
  • 111
3 votes
0 answers
60 views

Equality of lambda terms which do not have normal form

In the context of lambda calculus, how should one prove $\beta$-equality of terms that do not have normal form? In particular, how to prove that these are different combinators: $$ Y = λf.(λx.f(xx))(...
prog's user avatar
  • 93
2 votes
1 answer
68 views

Combinator terminology: What is "strong" about strong composition?

A strong composition operator seems to be very fundamental. (Hindley and Seldin use the notation S for "strong" composition combinator). It abstracts the pattern $f(x, g(x))$, i.e. a direct ...
JRC's user avatar
  • 163
2 votes
1 answer
78 views

Computation equivalence of functional and procedural programming

I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
Java Machine's user avatar
3 votes
1 answer
54 views

Coding max as an interaction net

I am reading Yves Lafont's introductory paper Interaction Nets. Early in the beginning he mentions that max cannot be coded as follows since in this coding it is not possible to choose which argument ...
Faustus's user avatar
  • 237
1 vote
1 answer
119 views

Beta reduction of S combinator in pure lambda calculus

S is defined as S x y z = x z (y z) This suggest that (y z) should be evaluated just after ...
geckos's user avatar
  • 243
0 votes
0 answers
29 views

Algorithm for specific load balancing/arbitration problem

I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
user234461's user avatar
2 votes
1 answer
199 views

Tried to derive the Z combinator and instead derived another

I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake? Here are the ...
mlhaufe's user avatar
  • 311
0 votes
0 answers
94 views

Implementation of logic function using a multiplexer

A question asks me to simplify the following boolean expression then use a multiplexer to implement it. $$\overline{A}BC + \overline{A+B+C}+A\overline{B}\overline{C} + B\overline{C}$$ I evaluated ...
Fëanor Tang's user avatar
0 votes
1 answer
70 views

Full adder carry expression

I'm learning about logic circuits and I've come across full adder. In the book they derived its two carry out expressions - Cout = x&&y || x&&z || y&&z and Cout = x&&...
Abhirup Bakshi's user avatar
1 vote
0 answers
29 views

Is there an algorithm to switch from classical notation to concatenative stack-based notation?

Reading a bit about Joy, I was wondering if there wasn't an algorithm to switch from classical notation and style to concatenative and stack-based style. Of course, for simple mathematical ...
Foxy's user avatar
  • 255
-1 votes
1 answer
2k views

How to compute total number of subsequences of length k from a word of length N?

A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all subsequences of the word banana. We ...
Abhimanyu Singh Rathore's user avatar
3 votes
2 answers
98 views

What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$?

Is there a standard name for the operator that takes a function $f:X\rightarrow(Y\rightarrow Z)$ and returns the function $f':Y\rightarrow(X\rightarrow Z)$ that satisfies, for every $y \in Y$ and $x \...
Evan Aad's user avatar
  • 237
14 votes
2 answers
425 views

Is the SK2 calculus a complete basis, where K2 is the flipped K combinator?

Specifically, if I defined a new $K_2$ as $$K_2 = \lambda x. (\lambda y. y)$$ instead of $$K = \lambda x. (\lambda y. x)$$ would the $\{S, K_2,I\}$-calculus be a compete basis? My guess is "no," ...
cole's user avatar
  • 243
5 votes
1 answer
74 views

Find a lambda term satisfying two equations

I'm just looking for the general idea on how to approach the following problem: Find a term $\Delta=\lambda x.xUV$ such that: $\Delta\Delta=K$ $\Delta K=S$ (it's a system of 2 equations, I didn't ...
Marco's user avatar
  • 95
1 vote
0 answers
29 views

Combinatory Logic formula obtained from lambda term, proof?

I translated the following $\lambda$-term: $z(\lambda b.ba)(tt)(\lambda y.y)$ in the following CL formula: $z(CIa)(tt)I$ through the Markov algorithm. Now I'd like to prove the translation was ...
Emanuele Giona's user avatar
1 vote
0 answers
52 views

Job shop scheduling with events that should be completed simultaneously

I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times. However, some events require more than one agent to be ...
Alex Williams's user avatar
1 vote
0 answers
135 views

Combinatory logic equivalent to System F

Simply typed lambda calculus has a combinatory logic equivalent with the same expressive power without the need of defining names via lambda abstraction. Is there a formalism as powerful as System F ...
user3368561's user avatar
1 vote
1 answer
65 views

Is there a combinator that introduces brackets to a combinatory logic expression using just B?

Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this: $Xabcdef=a(bcd)(ef)$. Is it possible to express $X$ using just the $B$ combinator, defined by $Babc=a(bc)$? Is ...
baronbrixius's user avatar
3 votes
1 answer
765 views

Reduction of the Y combinator

The Y combinator expression is as follows: $$ Y \equiv \lambda f .(\lambda x .f(xx) )) .(\lambda x .f(xx) ) $$ Now , if I am not wrong , then this expression can be reduced by seeing this as the ...
Agnivesh Singh's user avatar
2 votes
2 answers
122 views

An explanation for Barendregt use of Y combinator in an equation

I am going through the following lecture notes on lambda calculus by Barendregt and Barendsen : http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf Here at page 12 , after ...
Agnivesh Singh's user avatar
7 votes
1 answer
400 views

Y combinator, function composition

I am trying to understand Y combinators. Could you please explain why the following are equivalent (Y (f ∘ g)) (f (Y (g ∘ f))) (Y is a fixed point combination)...
David's user avatar
  • 163
1 vote
0 answers
110 views

Is $(X (X X)) ((X X) X) X$ the most simple representation of the identity combinator when $X = \lambda x . x KSK$?

Let combinator $X = \lambda x . x KSK$ as described by Hankin (1994). Then $K = (X X) X$ and $S = X(X X)$. Identity combinator however seems to have much more verbose form. If $I = SKK$ then also $$...
MarkokraM's user avatar
  • 385
47 votes
2 answers
5k views

How does the Y combinator exemplify "Lambda calculus inconsistency"?

On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with ...
Ben I.'s user avatar
  • 1,702
8 votes
2 answers
2k views

Why are combinators important in lambda calculus?

I just recently learned a little about the lambda calculus, from the brief intro in the text Programming Language Pragmatics and this outstanding 4-video sequence from Adam Doupé. Basically I learned ...
Dave's user avatar
  • 495
1 vote
1 answer
94 views

Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem

From pg. 35 of Lambda Calculus and Combinators An Introduction: Corollary 3.3.1 in $\lambda$ and $CL$: for every $Z$ and $n \ge 0$, the equation $$ xy_1 \ldots y_n = Z $$ can be solved ...
George's user avatar
  • 285
1 vote
0 answers
23 views

How to interpret scoped variables next to each other within Lambda Terms and CL-terms?

In both the lambda calculus ($\lambda$-calculus) and Combinatory Logic (CL), we have the notion of function application. For example: \begin{array} & \left( \lambda x . x \right) y = y & \...
George's user avatar
  • 285
3 votes
1 answer
105 views

Understanding A Recursive Definition of CL-Terms in Combinatory Logic

From page 26 of Lambda-Calculus and Combinators: Definition 2.18 (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$, thus: (a)...
George's user avatar
  • 285
12 votes
1 answer
721 views

Simplest complete combinator basis pair for flat expressions

In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions ...
user avatar
2 votes
0 answers
34 views

The range of functions defined by pure lambda terms

Consider a full set-theoretic model of the simply typed $\lambda$-calculus with infinite base types. Say that an element in this model is pure if it is the semantic value of some closed pure term in ...
Andrew Bacon's user avatar
11 votes
0 answers
205 views

When can you "invert" an equation in the lambda calculus

Suppose that $M$ is a full model of the simply typed lambda calculus. Suppose each base type is infinite. Now suppose that $f$ and $g$ are two functions in $M$ (not necessarily in the same domain) ...
Andrew Bacon's user avatar
22 votes
2 answers
1k views

Basis sets for combinator calculus

It is well known that the S and K combinators form a basis set for combinator calculus, in the sense that all other combinators can be expressed in terms of them. There is also Curry's B, C, K, W ...
N. Virgo's user avatar
  • 966
13 votes
1 answer
281 views

What functions can combinator calculus expressions compute?

A combinator expression (let's say in the SK basis) can be thought of as a function that maps combinator calculus expressions to combinator calculus expressions. That is, one can think of an ...
N. Virgo's user avatar
  • 966
6 votes
1 answer
426 views

Combinator equivalent to eta conversion

In lambda calculus, one can prove that two expressions compute the same function if they are equivalent under both beta reduction and eta conversion, where eta conversion consists of eta reduction, $$ ...
N. Virgo's user avatar
  • 966
9 votes
3 answers
3k views

What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use?

I understand what it is, but I don't see how it is any use for algorithms or anything. Maybe I am missing something. I need someone to give me an example of how it can be used so I can understand it ...
Kenneth Onyebinachi's user avatar
2 votes
0 answers
50 views

Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
letsBeePolite's user avatar
3 votes
1 answer
653 views

Iota combinator and implicational propositional calculus

There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between ...
stephenwebber's user avatar
1 vote
1 answer
40 views

"Archiving" byte sequence into human-readable set of chars

Ok, lets assume we have sequence of 1000 bytes. So the possible number of value variations is 2^100. Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as ...
Drinkins's user avatar