just wanted to say congratulations on what you’ve got so far; it was interesting for sure, and I’m looking forward to future parts.

it makes me wonder if you’re basically modeling parallel dataflow; linear types probably means each stack can be executed pretty safely in parallel, yes? the moving values into a new stack feels very “spawn a thread” to me.

This looks very interesting! I’ll eagerly await the next installment and look forward to playing with the language.

Reading the post, I wondered how the stack names are scoped. In the example code, one can reasonably (I think?) guess that $x, $y, and $z are scoped to the function whose {spread} operation created them, or maybe they are bound to the current stack. But looking at the comment you linked to in an earlier discussion about I/O, it seemed like there were references to named stacks like $stdout from some external scope.

Perhaps I’m wrong to assume that “scope” is even a relevant concept. But presumably there has to be some way to avoid stack name collisions.

(Edit) …Huh, maybe I am wrong to assume that scope matters. I am still trying to wrap my brain around it, but maybe if the language can guarantee linearity across the whole application, you don’t even have to care about name collisions because if there is already a $x stack from some calling function, it doesn’t matter if you reuse it and push values onto it as long as you’re guaranteed to have removed them all by the time your caller looks at it again (assuming your caller wasn’t expecting you to leave behind a value on that stack, but then “leaves behind one value on $x” would be part of your function signature).

I’m not quite sure that actually works, but now I’m even more eager to read the next post.

Your introduction to Dawn was clear and compelling, really excited to follow along with Dawn’s development.

{spread $x $y $z} is syntactic sugar

Do you intend to expose a macro system to Dawn programmers?

Conceptually, these named stacks can be considered to be different parts of one big multi-stack.

How are Dawn’s named stacks represented internally? I don’t have much familiarity with stack-based languages, but it seems like it would be straightforward to understand how the machine runs a program just by reading the source. Is that lost with the introduction of named stacks, or is there a mental mapping that can be made?

Dawn is really exciting!

I’m looking forward to the rest of the series. Is there any change you could put an rss/atom feed on the site? It’s a much nicer experience than subscribing to a mailing list.

First of all, it’s a really interesting concept! One question about the linear typing aspect though: What happens if multiple functions want to access the same read-only data structure? I assume that for small values clone just copies by value, but what if the data structure is prohibitively expensive to copy? Are some values cloned by reference? If yes, don’t you need to track how many readers / writers access the data so that you know when to free the memory?

I guess another way of phrasing this question would be: How do you handle the more complex cases of borrowing data with the semantics described in the post? Rust’s borrow checker is of course useful even for simple cases of stack-allocated values, but it really shines (and this is where its complexity lies) in cases of more complex heap-allocated data structures. (And of course, even Rust with its borrow semantics needs Rc/RefCell as escape hatches for situations where these guarantees cannot be statically checked, is there something comparable in Dawn?)

Nice! Also looking forward to future parts.

a way to bind values to local named variables. Unfortunately, this breaks one of the primary advantages of concatenative notation: that functions can be trivially split and recombined at any syntactic boundary—i.e. their factorability.

You gave an example of how Dawn still has this but can you give an example of why Factor or Kitten do not? Or more generally, why a concatenative with bind values to local named variables cannot.

Here’s a example of Fibonnaci from Flpc (Disclaimer: I’m the author).

    [ 1 return2 ] bind: base-case
    [ newfunc1 assign: i
      pick: i pushi: 3 < pushf: base-case if
      pick: i 1 - fib pick: i 2 - fib + return1
      ] bind: fib

Any part of the body can be split off. For example

    [ 1 return2 ] bind: base-case
    [ pick: i 1 - ] bind: one-less
    [ pick: i 2 - ] bind: two-less
    [ newfunc1 assign: i
      pick: i pushi: 3 < pushf: base-case if
      one-less fib two-less fib + return1
      ] bind: fib

    [ 1 return2 ] bind: base-case
    [ pick: i s21 - ] bind: recurse-fib
    [ newfunc1 assign: i
      pick: i pushi: 3 < pushf: base-case if
      1 recurse-fib 2 recurse-fib + return1
      ] bind: fib

For your example, this would be

[ newfunc3 assign: z assign: y assign: x
  pick: y square pick: x square + pick: y abs - return1 ] bind: f

(z needs not be dropped explicitly since return1 takes care of that.)

The key insight is that concatenative languages pass a data structure from word to word, and that data structure doesn’t have to be a stack.

And there are probably more alternate structures, besides a stack and a map-of-stacks. This has a lot of potential as an unexplored area of programming language design.

This is a nice insight. But are you willing to consider alternative structures that aren’t stacks (with the dup drop swap style of coding that accompanies them)? And if you aren’t using stacks, is it still concatenative programming?

The thing I like about concatenative languages is the idea of programming with pipelines, where data travels left to right through a series of operations, being transformed by each operation. The thing I dislike about the Forth family of languages is that the data is a stack, and you use dup pop swap etc to access data elements. I find the resulting code too difficult to understand. I like pipeline programming so much that it is a central part of the new hobby language I’m working on. In pipeline programming, the data that passes from one operation to the next is not a stack, or a map of stacks, but is instead just values belonging to application data types. For example,

a + b + c

is a pipeline where the data are numbers. In Unix shell programming,

ls | wc -l

is a pipeline where the data is Unix line-structured text. My idea (which isn’t very original) is simply to write pipelines as a chain of left-associative infix operators which all have the same precedence. Data flows left-to-right. The Unix pipeline operator is one of those infix operators, so that ‘x | f’ is a function call ‘f(x)’. This clearly isn’t concatenative programming, but it is simple and easy to understand. And you could embed concatenative programming by providing a stack data type and dup drop swap etc functions.

I would have to go back through a lot of brainstorming notes to identify when and how this notion of a multi-stack concatenative language came about, but I’ve been interested in concatenative languages for a while, despite their disadvantages. When I further realized that concatenative notation is a natural fit for linear types, I knew that it had to be the notation for the linear language I’ve been dreaming of.

I’ve been rather obsessed with stack-based concatenative languages for a while, so recently I began experimenting with a toy language and various new syntaxes and language features. I fiddled with scoped variables for a while, but eventually realised that using them kind of defeated the point of having a stack in the first place. I then took a note from /bin/dc (which has about 256 alternate stacks, one for each byte value) and thought about using variables as mini stacks. I went a step further, and began experimenting with code blocks that switched from the main stack to variable stacks.

My take slowly came about after reading Look Ma, No Garbage![1], then similarly realising stack-based languages also naturally fit with linear types.

I later veered off into more syntax-based metaprogramming after failing to reconcile my attempt at concatenative purism with the existence of parentheses.

[1] CHICKEN Scheme fans may recognise the author’s other work.

I’ve also been thinking about the idea of multiple stacks in a Joy like language, and have been for years now. But, I don’t give myself enough time to make progress on this idea enough to understand its impacts and how they interact / don’t interact. I am glad to see my nascent thoughts validated with so many others sharing similar ideas!

The way I’ve been considering multiple stacks is two fold:

1. since my language has both Joy and scheme roots, the ability to capture a stack as a “continuation” allows error handling to preserve the stack on failure of some function and restore it.

2. a week idea of parallelism. But my language is not intended for high performance situations, more of a day to day scripting lang / embeddable. Thus, I never gave a ton of thought beyond an initial “this could work.”

Reading this post is like “Oh, duh! Of course!” So, I am super stoked to see where this goes, next. And, I definitely can’t wait to see what’s next / steal some ideas for my own use (with credit due, of course).

Ah, nice. I had mentioned the idea in a comment here, previously: https://lobste.rs/s/bm6tuc/we_need_less_powerful_languages_2015#c_2rscq5 . Dunno if you might have seen that. But a lot of these ideas seem to be in the air. The time is ripe for them.

Semantically, IO on a single stack could indeed be run concurrently with non-IO operations on another stack. Whether or not a runtime takes advantage of that concurrency is another matter. I don’t currently plan to implement such a runtime.

If you had two different stacks doing IO, though, then the ordering is explicit in the text. So you would need a separate explicit mechanism for concurrency in that case. I have some nascent ideas about that, but selecting the best approach will require experimentation with a working implementation.

To quote a user on #lobsters who seemed to be having the same issue:

19:49 <Stekke> I don't have an account, but to comment about some confusing user azazel / johnaj is having in the "Introducing Dawn" story: the weird font spacing is caused by the 'Noto Color Emoji' font on Firefix / Linux, it doesn't happen with Chromium on the same system
19:50 <Stekke> just removing that font from the CSS makes the spacing normal for me

Really? Looks like any other article I’ve seen. Maybe try reader view in your browser.

Do you mean the text or the code? The text uses the system font, without any custom word-spacing. In the code, the spaces separate one item on the stack from another.