LtU Forum

Use Cases for Shared-Memory Concurrency?

The async/await thread got me thinking about Coyotos, and the fact that outside of the kernel I couldn't think of any use-case where mutable shared-memory concurrency was motivated in application code. Assumptions:

  • async/await integrated into the application-level languages, and
  • non-shared-memory concurrency with messages in the style of Node worker threads remains available (shared physical heap, non-shared logical heap).
  • the usual separate address space mechanisms remain available

While there are clearly algorithms that benefit from mutable shared-memory concurrency, most have equivalently efficient implementations built on messaging without use of shared memory. This becomes especially true if we add in the ability to observe when data is deep-frozen (which address many cases of "initialize before going parallel) to support immutable shared memory concurrency. For example, we did a high-performance ethernet driver in EROS that utterly relied on mutable concurrent shared memory for performance, but could have been implemented with immutable shared memory if we had had the ability to transfer an observably frozen reference as part of a message. Offhand, I'm not convinced that message ports need to support mutable shared memory data transfers at all.

    By "observably deep frozen", I mean a reference into a previously mutable graph that can no longer be reached (from anywhere) by a reference that permits further mutation. One way to do this is to return a single [transitively] read-only reference to some element of the graph that we can show has not otherwise escaped from the execution context in which it had been mutable, and whose mutable execution context is known to have terminated at the point of return.

    A similar effect can be had from deep-copy, but deep-copy can have prohibitive cost for large object graphs.

I'm sure there will be some obvious answers, but I'm prompted to ask: what kinds of codes or problem types exist that truly require the shared memory concurrent model (i.e. that cannot be efficiently encoded using a combination of async/await and non-mutably-shared concurrent threads with messaging)? Is there a common pattern to them? Is the pool of such codes large enough to warrant first-class design support in programming languages and OS runtimes? How many of those cases would be eliminated if we had reliably observable deep frozenness in the type system or the language runtime?

To be clear, this is mostly an idle ponder on my part. Putting the async/await discussion together with observable frozen-ness in my head got me to thinking on this, so I thought I'd put the question out there for discussion.

Regards and thanks...

Async/await vs coroutines?

I have noticed that in the last decade or so various programming languages have adopted an async/await model of concurrency (Javascript, C#, Rust, Zig, etc.). This surprised me as my experience with Lua had me assume that a coroutine model of concurrency was superior and would win. Obviously I have missed something. What are the advantages of async/await? More explicit? Lower level? Easier to implement? More flexible? How else do async/await and coroutines compare?

Exhaustiveness checks for algorithms that manipulate imperative data structures

Let's start with something that ought not to be controversial, although it probably is: Programming languages exist to express algorithms! Thus, programming languages ought to be judged according to the ease with which they express algorithms, especially the not quite trivial ones. Moreover, algorithms are known to be tricky beasts - you make one slight mistake and the thing does something completely different from what you want. Thus, it is reasonable to emphasize how reliably humans can write correct algorithm implementations as the main criterion for judging languages.

In this regard, one of the greatest inventions in PL history are algebraic data types and pattern matching with automatic exhaustiveness checks. As long as your programs only manipulate purely functional data structures, it is often possible to write them in such a way that the compiler can verify the exhaustiveness of your case analyses. This is a huge win for reliability, because computers are ridiculously better than humans at performing exhaustive case analyses.

Unfortunately, this advantage of pattern matching over if/else chains completely vanishes as soon as you introduce imperative data structures. As the state of an imperative data structure evolves over time, you gain the ability to perform new operations on it, and also lose the ability to perform operations on it that were previously possible, in a way that algebraic data types are “too static” to correctly describe. For example, suppose you are writing a compiler and, for efficiency reasons, you want to perform syntax tree transformations in place whenever possible. In particular, you want to replace variable names with de Bruijn indices in place. So you define your abstract syntax like this:

datatype state = Name of string | Index of int

type var = state ref

datatype term
  = Var of var
  | Apply of term * term
  | ...


However, then it becomes impossible to express invariants such as “all names have been converted to indices”, i.e., “the abstract syntax tree has been converted to an abstract binding tree”. You might want to define a helper function like

fun getIndex v =
  case !v of
      Index n => n
    | Name _ => raise UnboundVariable


This is terrible, because it means that you have failed to convince the type checker that your case analysis is exhaustive, i.e., “no variable is in the Name state by the time you call getIndex”.

For a more serious example, consider the algorithms for computing the strongly connected components of a directed graph due to Tarjan and Gabow. Both algorithms construct an auxiliary stack whose topmost few nodes belong to the strongly connected component of the node currently under consideration. When the strongly connected component has been fully explored, this stack is popped. See here and here, respectively. We know that, at this point, the stack is nonempty, this does not need to be checked at runtime. And yet, in every memory safe language that I know of, the check will be performed, creating a useless unreachable control flow path.

Long ago, when I was a reckless C++ programmer, and thought I could keep every detail in my head, I would have replied “well, then a memory unsafe pop it is!” Nowadays I expect better from programming languages. Are there any programming languages that do a better job of tracking what situations may actually arise when manipulating imperative data structures?

EDIT: I am aware of typestates. They could help with the first example, but I do not see how they help with the second.

Is character as a type meaningless?

Assume 1,2,3 creates a list of three integers, 1 and 2 and 3. Similarly, I could create a list of identifiers like func1, func2, func3. I could also have three characters, 'a', 'b', 'c'.

Having 'a', 'b', 'c' is really like having the string "abc", since strings are an array of characters. For anyone having read how Unicode works, you might have noticed that the definition of a character is kind of tricky. Some characters are composed of several characters, so what do you mean with character? A Unicode code point as Unicode would like to see it? Single UTF-8 element as C and C++ typically see it? UTF-16 element as in Windows?

All this makes me wonder, is there any reason to treat character as something else than just a short string? It would be a sub-type of string, in that it is constrained to only evaluate to a single Unicode character. Would this make sense, or are there pitfalls with this kind of thinking?

Programming in Lambda Calculus

Many texts on untyped lambda calculus are heavily loaded with math.

I have tried a different approach to look at lambda calculus from a programming point of view. The results are posted in a little paper on this website.

As a special add-on, I show how to systematically construct algebraic datatypes in lambda calculus.

Comments, hints etc. are welcome.

Idris2 is self-hosting

Edwin Brady has been working on the next version of the dependently-typed, eager, general-purpose Idris. It is now self-hosting.

tl;dr (twitter)

Edwin's press release (from the Idris mailing list):

Hi all,

I decided a couple of days ago, it was finally to time to have a go at
seriously porting Idris 2 to compile itself. To my surprise, it actually
worked (barring a couple of bits and pieces such as some details of the
IDE mode, and a couple of language issues that I'll resolve shortly.)

You can see the results here: https://github.com/edwinb/Idris2-SH

At some point in the next couple of weeks, I'll probably move to this as
the main development version - once I've ironed out the issues, and
worked out what a good process is for building and developing.

[..]

This also enables some other things that I've been holding back on for
the moment: plugin code generators, and better metaprogramming, among
other things.

Much more on this later. For now, I thought it would be nice to let
other people have a go with it.

My favourite new feature is that building the whole thing from scratch,
in the fully self hosted version, now takes about 1m45 on my machine,
which is about as long as the code generation along for the Idris 1
version :).

A shout-out to Chez Scheme, which Edwin uses for bootstrapping.

modus_ponens, a library to develop inference engines.

Perhaps some of you here might be interested in modus_ponens [1]. It is a rust library to develop forward chaining inference engines that are performant and scalable, comparing in that arena very favorably with CLIPS. In addition, the syntax for the facts that an engine developed with modus_ponens understands is provided by the developer as a Parsing Expression Grammar, with little restrictions.

[1] https://gitlab.com/enriquepablo/modus_ponens/-/blob/mirrors/README.md

Owl: A parser generator for visibly pushdown languages.

Owl is a parser generator which targets the class of visibly pushdown languages. It is:

  • Efficient - Owl can parse any syntactically valid grammar in linear time.
  • Understandable - like regular expressions, its parsing model (and error messages) can be understood without talking about parser states, backtracking, lookahead, or any other implementation details.
  • Easy to use - using Owl's interpreter mode, you can design, test, and debug your grammar without writing any code. An Owl grammar compiles to a single C header file which provides a straightforward parse tree API.

The restriction to visibly pushdown languages imposes restrictions on recursion. Rules can only refer to later rules, not earlier ones, and all recursion must be guarded inside guard brackets.

[ begin ... end ]

The symbols just inside the brackets are the begin and end tokens of the guard bracket. Begin and end tokens can't appear anywhere else in the grammar except as other begin and end tokens. This is what guarantees the language is visibly pushdown: all recursion is explicitly delineated by special symbols.

https://github.com/ianh/owl

Note: I am not the Owl author, but I found it to be a useful tool for my own projects. I play around with toy programming languages as a hobby and I am not well-versed on automata theory.

I am posting here because I would be interested to know what your thoughts are about the class of visibly pushdown languages, specifically the constraints it imposes on recursion, how that compares to recursive descent, and any pointers to variations or similar approaches that you know of.

Why is there no widely accepted progress for 50 years?

From machine code to assembly and from that to APL, LISP, Algol, Prolog, SQL etc there is a pretty big jump in productivity and almost no one uses machine code or assembly anymore, however it appears there's been almost not progress in languages for 50 years.

Why is that? Are these the best possible languages? What is stopping the creation of languages that are regarded by everyone as a definite improvement over the current ones?

Functional Constructors in Theme-D

I redesigned the constructors in Theme-D version 2.0.0, see [1]. The design is inspired by the OCaml object system. Constructors are special procedures used to create instances (objects) of classes. They are not defined like other procedures but Theme-D creates them using the construct statement in a class and field initializers in a class. The translator-generated default constructor is sufficient in many cases. For example, consider the class <complex> defined in the standard library:
  (define-class <complex>
    (attributes immutable equal-by-value)
    (inheritance-access hidden)
    (fields
     (re <real> public hidden)
     (im <real> public hidden))
    (zero (make <complex> 0.0 0.0)))
The translator-generated default constructor takes two real arguments and sets the first to the field re and the second to the field im.

The programs objects1.thp and objects2 in subdirectory theme-d-code/examples of the source code [1] demonstrate user-defined constructors. Here is the first example:

  (define-class <widget>
    (fields
     (str-id <string> public module)))

  (define-class <window>
    (superclass <widget>)
    (construct ((str-id1 <string>) (i-x11 <integer>) (i-y11 <integer>)
		(i-x21 <integer>) (i-y21 <integer>))
	       (str-id1))
    (fields
     (i-x1 <integer> public module i-x11)
     (i-y1 <integer> public module i-y11)
     (i-x2 <integer> public module i-x21)
     (i-y2 <integer> public module i-y21)
     (i-width <integer> public module (+ (- i-x21 i-x11) 1))
     (i-height <integer> public module (+ (- i-y21 i-y11) 1))))
The constructor of class <window> passes the first argument str-id1 to the constructor of its superclass <widget>. The constructors also initialize the fields using their arguments. Note that the field initializers may contain more complex expressions than just copying an argument variable.

Here is the second example:

  (define-class <widget>
    (construct ((str-id1 <string>)) () (nonpure))
    (fields
     (str-id <string> public module
	     (begin
	       (console-display "new widget: ")
	       (console-display-line str-id1)
	       str-id1))))

  (define-class <window>
    (superclass <widget>)
    (construct ((str-id1 <string>) (i-x11 <integer>) (i-y11 <integer>)
		(i-x21 <integer>) (i-y21 <integer>))
	       (str-id1) (nonpure))
    (fields
     (i-x1 <integer> public module i-x11)
     (i-y1 <integer> public module i-y11)
     (i-x2 <integer> public module i-x21)
     (i-y2 <integer> public module i-y21)
     (i-width <integer> public module (+ (- i-x21 i-x11) 1))
     (i-height <integer> public module (+ (- i-y21 i-y11) 1))))
Here we log the calls to the constructor of <widget> to the console. Note that we have to declare the constructors as nonpure if they have side effects.

[1] Theme-D Homepage

XML feed