LtU Forum

terminology for scope of discourse, i.e. CS-domain

I noticed a lack of good terminology to discuss mixed content intended for different uses -- or merely for alternate focus -- depending on 1) what sort of tool might work with it, or 2) what kind of activity or analysis is in scope. The idea I want means something like "asset class" but is also covered by "domain" in its general sense, except many people accept only one sense of a word upon first hearing. (Insert a comedy dialog here: a physicist mentions a magnetic domain in an iron object, only to be blind-sided by a troll who explains internet domains do not apply in that context.)

Typically people put different asset classes in different files, and say "this file's content is for that tool", but never talk about what they have in common besides that they are "files". Some tools might want to perform cross-domain analysis, or code generation. But it's hard to describe without enumerating "now we do X" and "now we do Y"; and the relation of X and Y is idiosyncratic and specific, rather than being generally alternate asset class domains.

The term "aspect" in aspect-oriented-computing is related, except no one will know what you mean if you use aspect as a synonym for domain. If you take content from different asset class domains, and mix them together in one file (with related things near each other for easier reference), with each one scoped suitably via syntax of some kind, there isn't a good word that denotes what is inside each scope. In one you have "stuff about X", and in another you have "stuff about Y", but stuff is pretty vague. You can put them in different logical files in an archive, but a problem of crummy terminology remains.

For example, suppose in one scope you have a bunch of code that "does task X", and in another scope you put a description of sequence diagrams that ought to result from that, so a tool can generate test code or perform analysis for verification. (A typical reason to do this might be that one asset is an emergent result of another asset class, and very hard to see unless explicitly described.) In a more general case, you might want to characterize what several sorts of program are doing in a larger system.

What I'm looking for is terminology about the semantics of expressing different things, perhaps in different languages, and making statements or queries about their relationships in space, time, or causal interactions. (The obvious response is "don't do that"; in a comedy dialog, one party can ask "why do you want to do that?" while pushing either focus on X or focus on Y, with no concern about how they relate -- it's someone else's problem.) Probably each domain has its own type system, but that doesn't seem very helpful here.

Expressions of Change

I have been working on a project called "Expressions of Change"; I thought the audience of Lambda the Ultimate might find it interesting.

The aim of the project is to improve the tools for constructing ever-changing computer programs by putting the changes themselves central in the programming experience. That is: reify changes, and use those reified changes as the main interface across the programming toolchain. Because the project rejects the history-less file as a basic building block, a first implementation step is to build the prototype of an editor that constructs such primitives of change instead.

More information may be found on the website. The best summary of the present status is probably in the form of the videos of presentations that may be found there. A paper discussing some of the first steps may be found there as well.

I'd love to answer any questions you might have, either on the website in the form of comments or on the present forum.

Popr Tutorial: Dot Machines

I have been working on a series of tutorial articles for my language, Popr.

For the first article, I designed a notation to present the semantics of the language in a way that I hope is easy to understand, and yet similar to how it is implemented in the compiler.

Concatenative languages, such as Popr, can be very terse. While this conciseness can make code both easier to read and to write, it can also make the same tasks difficult for those without a good understanding of the language. Furthermore, without the right semantic model, it is possible to develop a false understanding of the language that works for simple programs while leaving other programs as a mystery.

For this reason, I have developed a graphical notation for Popr that, while impractical for larger programs, can help develop an intuition for how the language works. In this notation, we will build machines that consume and produce dots.

Egel Language v0.0.2

I wrote a little toy language you now can read an introduction to. I fully blame LtU for getting me interested in hacking around languages so don't laugh, it's embarrassing enough as it is. You can try a small Conway's Game of Life example on TIO.

Anyway, just a short heads up. It's a small language based on untyped eager combinatorial rewriting of a DAG in C++, which isn't too fast.

You're all invited to break the thing, I am at version 0.0.2 and I want to get rid of possible bugs so your expertise can matter.

Anyway, leave your comment here. Preferably, a nice one.

Non-transitivity of type unification

We know type unification is not transitive in general

a ~ b /\ b ~ c does not imply a ~ c

And it's easy to find examples that don't unify

a |-> Int; b |-> b; c |-> Bool
a |-> (Int, a'); b |-> (Int, Bool); c |-> (c', Bool)

In all the examples I can make up, there's two outer types that don't unify, and a piggy in the middle that is either strictly more general than the outers (bare b) or strictly subsumed (Int, Bool).

For some (malicious) testing, I want an example where each three pairings of types unify, but the three types together do not. That is

a ~ b /\ b ~ c /\ a ~ c but not mgu(a, b) ~ c

Can anybody concoct such an example?
Or point me to something showing it's impossible.


4th Workshop on Live Programming (LIVE 2018)
November 6, 2018
Co-located with SPLASH 2018, Boston, USA

The LIVE 2018 workshop invites submissions of new ideas for improving
the immediacy, usability, and learnability of programming. Live
programming gives the programmer immediate feedback on the behavior of
a program as it is edited, replacing the edit-compile-debug cycle with
a fluid programming experience; the best-known example is the
spreadsheet. The LIVE workshop is a forum for research on live
programming, as well as work on fundamentally improving the usability
of programming, through language design, assistive environments and
tools. This year we are reaching out to the CS Education community to
include ideas on making programming more learnable and teachable.


Against The Current: What We Learned From Eve
Chris Granger


The shared spirit of LIVE is a focus on the human experience of
programming, and an interest in reconsidering traditional practices
and beliefs. Topics of interest include:

- Live programming environments
- Visual/Projectional programming environments
- Advances in REPLs/notebooks/playgrounds
- Programming by example/demonstration
- Advanced debugging and execution visualization techniques
- Language learning environments
- Language design for learnability and teachability
- Alternative language semantics/paradigms in support of the above
- Suggestive experiments and experience reports on teaching programming

Our goal is to provide a forum where early-stage work receives
constructive criticism. We accept short papers, web essays with
embedded videos, and demo videos. A written 250 word abstract is
required for all submissions. Videos should be no more than 20 minutes
long and papers no more than 6 pages long. We strongly recommend that
your submission use concrete examples to explain your ideas.


Submissions due: Fri August 17, 2018
Notification: Fri September 7, 2018
Workshop: Tue November 6. 2018

Anna: A KVS For Any Scale

Anna: A KVS For Any Scale, by Chenggang Wu, Jose M. Faleiro, Yihan Lin, Joseph M. Hellerstein:

Modern cloud providers offer dense hardware with multiple cores and large memories, hosted in global platforms. This raises the challenge of implementing high-performance software systems that can effectively scale from a single core to multicore to the globe. Conventional wisdom says that software designed for one scale point needs to be rewritten when scaling up by 10−100× [1]. In contrast, we explore how a system can be architected to scale across many orders of magnitude by design.

We explore this challenge in the context of a new key-value store system called Anna: a partitioned, multi-mastered system that achieves high performance and elasticity via wait-free execution and coordination-free consistency. Our design rests on a simple architecture of coordination-free actors that perform state update via merge of lattice-based composite data structures. We demonstrate that a wide variety of consistency models can be elegantly implemented in this architecture with unprecedented consistency, smooth fine-grained elasticity, and performance that far exceeds the state of the art.

This isn't strictly programming language related, so I didn't post this as a story, but actors and distributed systems are popular topics around here, and this builds on the CRDT and Bloom work discussed here before. The performance numbers under contention are certainly impressive compared to existing alternatives.

See also the accompanying article where the authors discuss this further.

GADTs as gaurds

Is there some reason Haskell didn't expose GADTs as guards?

    -- Haskell
    data Term t
        Lit Int :: Term Int
        App (Term (a -> b)) Term a :: Term b

    -- Guards
    data Term t 
        Lit Int where t = Int 
        App (Term (a -> b)) Term a where t = b 

It seems equivalent and semantically simpler.

Is there a functional language with explicit limits on the heap(s)?

I'm trying to make a research compiler which is supposed to run as a service, and so I'd like to use some language with cooperative, userspace threads, as (Go or) Erlang. The problem is that some user requests may consume too much memory, or possibly never halt. So I'd like to impose some restrictions, e.g., "requests from IP a.b.c.d may only use up to 80mb of heap memory and run for 5 minutes top".

Haskell has setAllocationCounter (also forkIO and STM), which would help, but that doesn't seem to take the GC into account. Erlang seems to let me limit the heap for each process, but many tasks will be computationally intensive, and Erlang's probably not a good pick.

Would anyone have some suggestion? I'd rather not have to create a new language, but it's a possibility; is there any research on such languages that could help?

Anything recent happening with multi-stage programming?

I remember that 15 years ago, multi-stage programming was new and exciting. It promised simpler implementation of programming languages, better-than-macro support for strongly-typed languages, etc.

These days, I can't find any recent publications on the topic. Am I somehow looking in the wrong place? Has the topic fuzzed out?

In particular, I'm currently working on something extremely close to multi-stage programming, applied to a JavaScript JIT compiler. I'm very surprised that nobody seems to have worked on seriously applying multi-stage programming to JIT compilers. Am I missing something obvious?

XML feed