LtU Forum

Co-continuations: a dual to shift/reset?

Shift/reset allow convenient expression of monadic computations, as a kind of generalized, functional version of do-notation. From the beginning of that link:

Continuations represent the rest of the computation. Manipulation of continuations is a powerful tool to realize complex control flow of programs without spoiling the overall structure of programs. It is a generalization of exception handling, but is far more expressive.

The obvious question is whether there is an analogous construct for comonads. Given that there is a codo-notation I believe there is.

In a concatenative language, shift/reset can be written as:

[F] shift K reset = [K] F reset

The F block observes the future of the computation (delimited by the nearest reset) and may select a new one.

I believe the comonadic dual is:

coreset E [F] coshift = coreset [E] F

The F block observes the past of the computation (delimited by the nearest coreset) and may select a new one.

This leads to a combined operator:

{ E [F] shift K } = { [E] [K] F }.

The F block observes the future and past of the computation (delimited by the nearest braces) and may select new ones. This is first class (co)control flow.

I want to say something like "the dual of continuations is environments", as "environment" is an existing concept that seems conceptually close to "store". Note that on this page, someone posts functions analogous to shift/reset for "codensity" or "store".

    { E [F] shift K }
      ^           ^
  environment continuation

I believe this notation allows the convenient expression of arrows (and monads and comonads) in the same way shift/reset allows expression of monads. Arrows allow decoration of both inputs and outputs, as opposed to only inputs for comonads and only outputs for monads.

This makes sense to me but I'm not totally sure since there's not much information on comonads/codo notation and such. I'd appreciate any comments.

EDIT: I think the correct format is actually

{ E [F] shift K } = [{ E }] [{ K }] F

A pointer is an integer with a shiv

AsyncFlows: Structured Asynchronous Programming

I've just made a public release of AsyncFlows framework 0.1.0 that offers DSL for structured and object-oriented asynchronous programming.

Some differences from competing solutions:

  • The framework is implemented in pure Java, there are no compiler extensions used. The same ideas are implementable in any garbage-collected language with reasonable lambdas and where it is possible to implement event queues and promises. The better are lambdas, the better code looks. Kotlin and Groovy versions looks much better than Java version.
  • There is no event matching and alomst no explict working with events. Explicit sending and event receiving are considered in the framework as "go to" of asynchronous programming and they should be avoided for the same reasons. Actually framework just uses one type of events: executable action.
  • The focus is intra-process coordination. The inter-process communication is considered as subject for libraries, there is no communication model enforced.
  • The focus during development are asynchronous operations and their combination using operators. Just like when developing in Java or C the focus are composing blocks, statements, loops, etc. The DSL is inspired by Occam and E language and it provide a set of orthogonal operators (all, seq, any, seq while, etc.).

I would like feedback on DSL struture and on the thesis that explicit event sending to queues or channels is "go to" of asynchronous programming and that it should be avoided if we try to get understandable code.

Semantic Design with SEDELA

I'm working on specifying a language for specifying program design, or 'semantic design', called SEDELA. 'Semantic design' is a program design tool inspired by Conal Elliott's 'denotional design' as presented in "Denotational Design: From Meaning to Programs" here -

Denotational Design Talk

Currently, I have specified a rough outline of the syntax and semantics here -

Semantic Design Language

I am thinking very seriously about writing a parser, type-checker, and a Visual Studio Code editing plug-in for SEDELA. But first, I want to get the community's feedback on the current specification as well as the idea in general.

Thank you all once again for any assistance provided in these endeavors!

How to decrease bugs in the code

After couple of years of using a Haskell, I noticed that errors in the code were not decreased (lie, as well as "you will be more productive", "you will write code faster", "code will be smaller" - all of these sentences were a lie), so I thought about it: how to decrease bugs. I know these methods:

  • More unit and properties tests (it's available in most languages)
  • Free monads - allows to check logic in code which looks like "imperative" without to involve real IO
  • Indexed monads - to prevent denied transitions in monad (IO, etc) - IMHO leads to complex less readable code
  • Prove tool (Agda, Idris, etc) - seems difficult to use, not sure
  • Liquid Haskell - not sure how it helps in real world applications, also not sure will it alive after dependently types introduction in the next GHC versions
  • Literate programming - good to decrease logical errors IMHO

The most embarrassing of me circumstance is that, as I understood, most real world errors (not typos and other stupid errors) can not be caught by type system because: 1) they happen in run-time 2) their roots are unexpected behavior of something external 3) often they are logical: some complex business logic is not fully correct but it's difficult to describe it formally even. Also I'm not sure is it possible to qualify anything as some kind of type: types of typical Haskell app are so many, that attempt to use more complex types will lead to something absolutely unreadable and unsupportable.

I think Design by Contract can help to cover some of the errors, but I can not find good DbC framework for Haskell. IMHO it can be something like "predicate under monad", because contract, sure, should be executed with side-effects (I'm interesting to verify some external entities, etc).

In this case all functions like `f :: a -> b -> IO c` become `f :: Ctr a -> Ctr b -> CtrIO c` or something similar. But I'm not sure here, because I need to check not only pre-/post- conditions but also invariants. How they can look in Haskell where you have only spaghetti code of functions? How to code asserting conditions in those monads? I found work of Andres Loh, Markus Degen, but this does not helps me. Most of articles (Peyton-Jones, Andres Loh, etc) look very shallowly, academically or unpractical (on research/experimental level, sure, as all other in Haskell). What do you use to decrease bugs in Haskell code? Also will be very interesting real success stories!

BF Bignum: A Program Synthesis Game

BF Bignum is a program synthesis game: the goal is to synthesize a BF program smaller than a given size that outputs the largest integer possible before halting within a given time limit. A synthesizer's score is the value of the target integer divided the total number of BF operations executed in the search for the target program.

Bignum is much harder than it sounds, and requires synthesizers to learn modular and hierarchical program representations.

  • Your BF program must be smaller than a given size, and halt within the given time limit. Time is defined as the number of BF operations executed during the production of the target integer. Synthesizers compete in a size/time class akin to weight classes in martial arts.
  • Your BF program must use `.` to produce its output. Your BF program may have any number of outputs; the largest output is the one incorporated in to your synthesizer's score. Note that since there is no input, the instruction `,` is simply ignored.
  • Your synthesizer must keep track of the total work done in the search. Work is defined as the number of BF operations executed during the search for the target program, e.g. while computing a candidate program's fitness. Note that two operations done in parallel is still two operations.

    It's not clear that this is the best measure of work, and there may be borderline cases such as static analysis that may or may not be considered execution of a BF program.

  • The BF tape contains big integers, not bytes. Your BF program is scored on the largest single integer it outputs; the sequence of integers is not interpreted as a string like in some BF examples.
  • You are writing a program that writes a program. You are not writing the bignum program yourself, that's too easy. Of course there are ways to cheat, like including some high fitness program within the source code of your synthesizer. Don't do that.

A synthesizer's score is target / work: the number output by the target program divided by the number of BF operations performed during the search.

How to generate branch tables from SSA form?

I've added this question to StackExchange. I've been wondering if there is any good theory behind making the branch tables when coming from SSA form (which should lose the information that there even existed a switch statement in the source code). Does anybody know any references on that?

Lambda calculus

I have written a small introduction to untyped lambda calculus.

The article contains nothing new, but it has been written to be easy to understand. The article is not only elementary. It contains all essential results of untyped lambda calculus like the Church Rosser theorem and some undecidability theorems.

I have tried to use graphic notations to make the content more digestible and closer to intuition. I am especially proud of the proof of the Church Rosser theorem which (hopefully) is more understandable in this article than in many other presentations I have read so far.

Higher Order Functions Considered Unnecessary for Higher Order Programming

Joseph A. Goguen, Higher Order Functions Considered Unnecessary for Higher Order Programming (1987).

It is often claimed that the essence of functional programming is the use of functions as values, i.e., of higher order functions, and many interesting examples have been given showing the power of this approach. Unfortunately, the logic of higher order functions is difficult, and in particular, higher order uni cation is undecidable. Moreover (and closely related), higher order expressions are notoriously difficult for humans to read and write correctly. However, this paper shows that typical higher order programming examples can be captured with just fi rst order functions, by the systematic use of parameterized modules, in a style that we call parameterized programming. This has the advantages that correctness proofs can be done entirely within fi rst order logic, and that interpreters and compilers can be simpler and more efficient. Moreover, it is natural to impose semantic requirements on modules, and hence on functions. A more subtle point is that higher order logic does not always mix well with subsorts, which can nonetheless be very useful in functional programming by supporting the clean and rigorous treatment of partially de ned functions, exceptions, overloading, multiple representation, and coercion. Although higher order logic cannot always be avoided in specifi cation and veri fication, it should be avoided wherever possible, for the same reasons as in programming. This paper contains several examples, including one in hardware verifi cation. An appendix shows how to extend standard equational logic with quanti fication over functions, and justi fies a perhaps surprising technique for proving such equations using only ground term reduction.

This (old paper) proposes an interesting approach for formulating functional programs. But can this truly subsume all uses of higher order functions? I don't see the paper address how the uses of higher order functions in general can be replaced (not that I have a counterexample in mind).

Anyone familiar with the OBJ language? Do other languages share this notion of 'modules', 'theories'?

Prior art for reifying lifecycle

Are there any prior examples of programming languages that expose the program processing lifecycle as a value or syntax element?

By lifecycle, I mean steps like the below which many languages follow (though not necessarily in order):

  1. lex: turn source files into tokens
  2. parse: parse tokens into trees
  3. gather: find more sources with external inputs
  4. link: resolve internal & external references
  5. macros: execute meta-programs and macros
  6. verify: check types, contracts, etc.
  7. compile: produce a form ready for loading
  8. run: load into a process that may be exposed to untrusted inputs

Does anyone have pointers to designs of languages that allow parts of the program to run at many of these stages *and* explicitly represent the lifecycle stage as a value or syntax element?

I'm aware of reified time in hardware description languages like Verilog and in event loop concurrent languages like JavaScript and E, but that's not what I'm after.


I work in computer security engineering and run into arguments like "we can either ship code with dynamic languages that is hard to reason about the security properties of, or not ship in time."

I'm experimenting with ways to enable features like the below but without the exposure to security vulnerabilities or difficulty in bringing sound static analysis to bear that often follows:

  • dynamic loading,
  • embedded DSLs,
  • dynamic code generation & eval,
  • dynamic linking,
  • dynamic type declaration and subtype relationships & partial type declarations,
  • powerful reflective APIs

I was hoping that by allowing a high level of dynamism before untrusted inputs reach the system I could satisfy most of the use cases that motivate "greater dynamism -> greater developer productivity" while still producing static systems that are less prone to unintended changes in behavior when exposed to crafted inputs.

I was also hoping, by not having a single macros-run-now stage before runtime, to allow use cases that are difficult with hygienic macros while still allowing a module to limit how many assumptions about the language another module might break by reasoning about how early in the lifecycle it imports external modules.

The end goal would be to inform language design committees that maintain widely used languages.


XML feed