1. 80
  1.  

  2. 13

    Author here. Ask me anything!

    1. 9

      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.

      1. 5

        Thanks!

        Yes, that’s absolutely correct. Operations on separate stacks could trivially be parallelized by a properly designed runtime. Eventually, high-level Dawn code could be compiled to OpenCL or CUDA, similar to in Futhark. Alternatively, a compiler to assembly for a superscalar CPU could interleave operations on the different stacks to take advantage of instruction-level parallelism.

      2. 6

        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.

        1. 4

          But presumably there has to be some way to avoid stack name collisions.

          Yes, there is. Take for example the expression: {$a swap} where swap is defined as

          {fn swap => $a<- $b<- $a-> $b->}
          

          Expanded, this becomes

          {$a $a<- $b<- $a-> $b->}
          

          Or, equivalently,

          {$a {$a push} {$b push} {$a pop} {$b pop}}
          

          Without some mechanism to handle the stack collision between the inner and outer $a stack, this would not behave properly. Since we want functions to behave the same way regardless of what stack context they are executed from, that would be unacceptable. So this is handled by checking for nested stack name collisions and renaming the inner stack. So the latter would effectively be rewritten to

          {$a {$$a push} {$b push} {$$a pop} {$b pop}}
          

          In the existing type checker prototype, renamed stacks are distinguished by a prefix of more than one $. Then, if one of these temporary stack names escapes up to the inferred type for a user-defined function, an error is raised. This ensures expected behavior while ensuring we don’t need to monomorphize each function to operate on different stacks.

        2. 4

          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!

          1. 2

            Thanks!

            I’m undecided on syntactic macros, but the plan is absolutely to provide meta-programming. I haven’t prototyped this at all yet, but I hope and expect for compiler passes to be implemented in something I’ve been calling meta-Dawn in my notes—a form of staged compilation. The plan is for Dawn to be its own intermediate representation. We’ll see how that works out in practice, of course.

            1. 2

              And to answer your other questions, in the existing interpreter the named stacks are a Map String (Stack Val). The first compiler, which will be through translation to C, will use static analysis (basically the inferred types) to turn all stack slots, regardless of which stack they are on, into function parameters.

              Eventually, I plan to write an assembler in/for Dawn, in which stack names will correspond to architecture-specific registers.

            2. 2

              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.

                1. 1

                  Thanks!

                2. 2

                  Thanks for the suggestion. I’ll take a look at what that entails.

                3. 1

                  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?)

                  1. 1

                    Great question! I’m going to get to that in a future post, but there is a solution, and it doesn’t require a separate borrow checker.

                  2. 1

                    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.)

                    1. 1

                      In your example of splitting up fib, what happens if you reuse one-less in another function? Does the source essentially get inlined, so that pick: i refers to the assign: i? If so, then this appears to be similar to Dawn, but without the linearity restriction.

                      In Factor and Kitten, I don’t believe local variables work like that, though. I believe they behave more like they do in most existing languages, e.g. Python, where the pick: i in one-less would be an undefined variable error.

                      1. 2

                        In your example of splitting up fib, what happens if you reuse one-less in another function? Does the source essentially get inlined, so that pick: i refers to the assign: i?

                        Yes, that’s exactly right.

                        In Factor and Kitten, I don’t believe local variables work like that, though. I believe they behave more like they do in most existing languages, e.g. Python, where the pick: i in one-less would be an undefined variable error.

                        Oh I see. I’m wondering if it’s because of scoping. With what I’m doing and maybe what you’re doing, you can’t (easily) get lexical scoping whereas the other way you could.

                  3. 11

                    As soon as I started reading this, I got a sinking feeling: it sounded almost exactly like a language idea that I’ve been sitting on for years, wanting to write a blog post about, but never fleshed out enough to make it worth sharing.

                    It turns out that Dawn isn’t exactly the same as my idea, but it’s definitely close. 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.

                    1. 3

                      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.

                      1. 1

                        If you know, what would it look like to implement floating-point exponentiation in such a dataflow pipeline language?

                        1. 1

                          I use a ^ b to raise a to the power of b. Since there is no operator precedence, a cubic polynomial is normally written as

                            x^3*a + (y^2*b) + (z*c) + d
                          

                          Once you use parenthesized subexpressions, you have lost the purity of a straight linear pipeline, but this code is easy to understand. The concatenative version doesn’t need parentheses:

                            x 3 ^ a * y 2 ^ b * + z c * + d +
                          

                          But this code is harder to understand. I see this as a tradeoff between concatenative/linear pipeline “purity” and readability.

                          Concatenative programs avoid the impurity of parentheses by using a stack. You can push anonymous intermediate results onto the stack, and pop them later. In my pipeline language, there is no stack, but you can eliminate parentheses by using named intermediate values. You can rewrite the cubic polynomial as this:

                            x ^ 3 * a |t1-> y ^ * b |t2 -> z * c |t3-> t1 + t2 + t3 + c
                          

                          There are no parentheses, and it is a straight linear pipeline. In this case, the code is harder to read than the original. In practice, you would use named intermediates when the intermediate is used more than once, corresponding to cases where you use dup in Forth.

                          Each occurrence of ...|t->... captures the value to the left in a named temporary t then evaluates the rest of the pipeline on the right with t in scope. The | operator is just a regular infix operator such that x|f is f(x). The syntax id->expr is a lambda expression with formal parameter id and body expr, and it returns a function value.

                    2. 7

                      In addition to the author it seems like a couple of commenters have had similar inclinations. What influenced each of you to arrive at these ideas? I wonder if that is in common too?

                      1. 6

                        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.

                        1. 5

                          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.

                          1. 2

                            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.

                          2. 6

                            I can’t believe my eyes. I was just writing a blog post for the exact same idea (variables as alternate stacks)! And I’m even about halfway through with a working implementation. Wow. Congrats!

                            1. 7

                              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).

                              1. 4

                                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.

                                1. 3

                                  No, I don’t recall reading that thread, so I suppose I came up with the idea more or less independently :^)

                                  (FYI, the language I was working on was geared more towards a Lua-like language [with a one-size-fits-most tables-for-arrays style] than a general purpose language)

                              2. 2

                                A few years back I was interested in Forth, and even wrote a tiny forth as a front end to an equally tiny ray tracer. I was later interested in the conversion from stack based to non-stack based languages but never did anything with it - well because of life.

                                What I am seeing in your code is a solution to a problem forth has with understandability. The ability to localize operations looks very powerful to me. I won’t really care about the linearity of the stuff, but I think that would be a net-benefit!

                                1. 1

                                  I’m not usually interested in reading about young / experimental languages, but this is really speaking to me, and concatanative languages are totally new to me.

                                  I’m really looking forward to the next post and I’m especially interested to see how you approach IO (I also don’t know anything about Haskell so I think there will be a lot of new concepts for me).

                                  I wonder whether when IO blocks, it only needs to block one stack and the machine can potentially keep running on other stacks, or would the whole multi stack block and we would do concurrent programming in a more traditional way with a second Multi-Stack and a channel between.

                                  1. 2

                                    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.

                                  2. 0

                                    Uh, I stopped reading very soon. I’ve found the word spacing… frustrating… I’m sorry

                                    1. 6

                                      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
                                      
                                      1. 2

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

                                        1. 4

                                          Yes, It looks like this without the suggested “fix”:

                                          1. 3

                                            I see what you mean. I’d have a hard time reading that too. It seems not every browser has this issue. Which do you use? Maybe the author can address it.

                                            1. 3

                                              I’ve uploaded a modified stylesheet that hopefully fixes the issue! If it doesn’t, I would greatly appreciate it if you would let me know!

                                              1. 1

                                                Hmm. It looks like the stylesheet didn’t load? If you can point me in the right direction, I can try to fix it.

                                                1. 3

                                                  See the sibling comment: if you remove “Noto Color Emoji’” it will be fixed for Firefox users

                                            2. 1

                                              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.

                                              1. 2

                                                The text, If you use the dev tools to remove the reference to the mentioned font, it suddendly becomes more readable. I don’t know why for sure

                                                1. 2

                                                  Hm, might want to report a bug at https://github.com/kognise/water.css, that’s the stylesheet that the site uses.

                                                  1. 1

                                                    Thanks for the suggestion.

                                                    I’ve filed a bug report: https://github.com/kognise/water.css/issues/249