Questions tagged [continuations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
177 views

Is there a proof of correctness for CPS translations into Appel's IR?

The IR given in Appel's book (Compiling with Continuations) is certainly well explored and battle-tested in production compilers. I have been able to find several works based on or inspired by it (...
paulotorrens's user avatar
4 votes
1 answer
134 views

Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function ...
hello world's user avatar
0 votes
1 answer
85 views

Continuation passing transform

I'm stuck on something in in Shan's article Shift to Control, about CPS. On page three he writes the CPS transform ...
Eric Auld's user avatar
  • 115
-1 votes
1 answer
951 views

Pattern finding in an array of numbers

I have an array of numbers, and I need to check if there is a repeating pattern in the array. Like, for example, if I have an array A=[1,1,6,1,1,6,1,1,6,1,1,6...] this should return "Yes" (...
Ishraaq Parvez's user avatar
1 vote
0 answers
16 views

Is it possible to implement a defer statement with delimited continuations?

A defer statement takes another statement and evaluates the given statement at the end of the current function call. See how Go does it. Delimited continuations can be abused to provide throw/catch ...
kkeey's user avatar
  • 113
1 vote
0 answers
28 views

Analogue of disjunction and existence properties for a Turing-complete programming language?

Quoting from Wikipedia: In mathematical logic, the disjunction and existence properties are the "hallmarks" of constructive theories such as Heyting arithmetic and constructive set theories ...
glaebhoerl's user avatar
5 votes
0 answers
326 views

Understanding $\lambda \mu$-calculus in more programming way

I am learning $\lambda \mu$-calculus (self-study). I learned it because it seems very useful for understanding Curry-Howard correspondence (e.g understanding the connection between classical logic ...
chansey's user avatar
  • 275
2 votes
0 answers
35 views

How can we convert between a program using `call/cc` and a program using functions written in CPS?

The Scheme Programming Language says It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-...
Tim's user avatar
  • 4,845
5 votes
1 answer
77 views

Explain auto continue passing style transformations

Recently I saw 3 cps transformation rules, but no explanations were given. expressions: $e :=x\left|e e^{\prime}\right| \lambda x \cdot e$ rules: $$ \begin{array}{l}{[[x]]=\lambda \kappa \cdot \...
Shuumatsu's user avatar
  • 151
4 votes
1 answer
354 views

Multi-prompt delimited continuations in terms of single-prompt delimited continuations

Let's call the two languages in question (untyped lambda calculus with single or multiple prompt delimited continuations) L_delim and L_prompt. Is it possible to express multi-prompt delimited ...
river's user avatar
  • 163
1 vote
0 answers
51 views

Can you use CPS to simulate state in a stateless programming language?

In a language supporting CPS, but no built in global state, we can represent a state based computation using a function. We call this function a state function. Assume the function takes three ...
PyRulez's user avatar
  • 778
4 votes
1 answer
206 views

Continuation-passing style: what is meant by "CPS'ing"?

I'm reading Dijkstra Monads for Free for a presentation I'll be doing and it's pretty meaty. One of the things that I keep running into is the term "CPS'ing". I've read a little bit on ...
Ben Kushigian's user avatar
3 votes
0 answers
90 views

Examples of continuations in pure mathematics [closed]

I am not a computer scientist and have no knowledge of programming. However, I wondered continuations occur as natural and interesting mathematical structures, perhaps as algebraic or type theoretic ...
user65526's user avatar
  • 194
22 votes
2 answers
5k views

Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects ...
CinchBlue's user avatar
  • 584
2 votes
0 answers
123 views

Continuation of strictly monotone function on a plane

I have a computational problem where I'm given the values of a function $f(x,y)$ sampled on 2D regular grid. The function is given in a compact domain of a grid and it is strictly monotone w.r.t. $x$ ...
Igor's user avatar
  • 21
11 votes
1 answer
602 views

When used as call stack, do garbage-free spaghetti stacks form a DAG?

I'm looking into implementation techniques for programming languages, and recently came across spaghetti stacks, which are supposedly a good fit for a continuation passing style model (given their use ...
Rhymoid's user avatar
  • 212
3 votes
2 answers
1k views

How would I write an if-statement in continuation passing style without an if-statement?

Using continuation passing style, many common language constructs can be written in a simple language with recursion, including loops (using trampolining), exceptions, generators and even function ...
00prometheus's user avatar
4 votes
3 answers
213 views

What does it mean to be "closed" under beta reduction?

I am reading the paper Compiling with Continuations, Continued, and in section 2.4, Comparison with ANF, the author draws attention to the fact that ANF is not closed under beta reduction. The snippet ...
bronxbomber92's user avatar
6 votes
2 answers
265 views

Reference request: Monads, continuations, and other functional CS concepts

I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about. I could visit Wikipedia and read about these two ...
Mark Cuban's user avatar
4 votes
1 answer
909 views

Are there a lambda-mu expression equivalent to the yin yang puzzle?

The yin yang puzzle was written in Scheme. Since it uses call/cc, it is not possible to express it in a pure lambda expression, unless we do a CPS transform. However, given the fact that $\lambda \mu$...
Earth Engine's user avatar
12 votes
1 answer
837 views

The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the "CPS" approach has done great harm to ...
Guy Coder's user avatar
  • 5,091