This seems like a great introduction to stack-based languages!
I'm curious, why did you undertake the project? What are your goals for it, or what problems do you intend for it to solve?
I'm going to include a bit from the README here, which describes some of the functionality/design but not the why behind the language:
> Stem aims to be a minimal interpreted stack based programming language that allows for metaprogramming and a foreign language interface. It features a C API that is elegant and simple. Additionally, garbage collection is not needed in this language as the responsibility of writing memory safe operations is put in the hands of the maintainers of the builtin functions and FLI library maintainers. Therefore, the end user does not need to worry about memory allocation while the implementation remains extremely simple.
I decided to undertake the project after my friend Matthew Hinton introduced me to stack based programming -- he claimed that they were elegant because they allowed for both easy metaprogramming and side effects, to which I agreed after writing a little bit of my own language. It was really easy to implement, too -- most of it took only one day, and getting the basic functionality working took only 2-3 days.
Goals -- I eventually want to write an emacs-like text editor in stem by writing a C library that does bindings for ncurses. I think it would be fun, for one, and I think it would not be that hard of an end product to make. I also had plans of writing a stem compiler, and I already pretty much know how to do that, but there are a couple of difficulties in doing that. Namely, right now, there is no way of telling the difference between compile-time and runtime operations, which will slow the language down considerably. My solution to this currently is basically "interpret once, run binary forever", but the details are still need to be worked out.
Problems it solves -- to be honest, you can really do anything in any programming language, but this langauge aims to be a higher level rendition of stack based programming languages, mostly for scripting and creating abstract representations of things.
Note that I am still trying to write in a couple things, namely, an actual include statement as a builtin that reads from some predetermined standard include directory, and an OOP implementation using metaprogramming in the standard library.
Not to mention the fact that I have been really interested in writing programming languages since I was in high school. One interesting thing about stack based languages is that the AST need not be generated at all. I taught myself a lot of linguistics, specifically generative grammar, as a result of attempting writing various programming languages in the past, and so these types of projects are just interesting to me.
If you ARE looking for one unique thing about this language, though, it is that `def`, the method by which you define functions, is itself a word. I don't think a lot of stack based languages do this (because it is much harder to compile languages like this as mentioned above), but it offers much more internal consistency within the language as a result.
Very neat. You have tried to make a very orthogonal language from what I can see.
One of the critiques of Forth is that it is postfix at runtime but typically prefix for compiling stuff. Your use of an unassigned text label being the default to which things can be attached with def is a nice solution.
How would say the language performs at runtime vs other REPL languages.
Is it compiling to native code behind the curtain or is there a VM back there?
Intepreted... right now. There isn't a vm currently, but I'm planning to do native compilation pretty soon, as I already have an idea of how I would go about doing it.
correct me if I am wrong, but from my knowledge concatenative programming often assumes a different syntax for defining words. Usually it looks something like : add a b + ; if I am not mistaken.
You are correct, but in Forth for example, the colon is a word in the dictionary of words and so is semi-colon. They just happen to parse the input stream rather than taking arguments off the stack. Everything in Forth is called a "word".
So depending who your lawyer is, : and ; are "words". :=)
Yes. In forth some words have the "immediate" flag set. When such words are encountered during compilation they are executed nevertheless. This allows words such as ; to end a word definition and return to interpretation mode.
I am not generally knowledgeable about Forth and languages like it because the only experience I have writing in anything close to forth is in my own language. Thanks for explaining.
I think they are not ordinary words that consume arguments directly from the stack. They also need to look ahead in the input stream of tokens. With support for quoted code, there seems to be no need for any other words operating at the token stream level, like conditionals and def. They just need to consume the stack. I am still digesting this so happy to be corrected.
Forth is very free-form, it doesn't require that your words be 'ordinary' in that sense. The : word isn't the only one that can consume from the input stream, neither is it the only word that can define words (such words are called defining words). The CONSTANT word, for instance, is a convenient syntax for defining a word to push a constant value onto the stack. [0]
You can even define your own 'mirror' of the : word, which involves some fiddly management of Forth's state, but it's doable. [1]
See also [2] on Forth's execution model and [3] on defining your own defining words.
Oh, I don't know about that. Forth words can take control of the input stream! The ordinary parser eats space-deliminated tokens, sure, but how does the " word work? It takes over the input, and reads until it finds a terminal quote! It's wild: learning forth, you get used to RPN... but then you can implement an infix parser, and your "forth" can bootstrap a C-like language all in one source file.
I was not aware of this, thanks for giving me an explanation. I don't have any experience writing in forth, my friend described this type of language to me and I implemented it.
Some related goodness from Forth: there's another word, :NONAME, for defining anonymous words. [0][1]
The more common : word enters the newly defined word into the dictionary, which is Forth speak for the newly defined word now being considered 'in scope'. The :NONAME word instead returns an execution token on the stack, which is analogous to a function pointer.
See also [2], on Forth's execution model more broadly.
You should go implement the FORTH-83 wordlist. (arbitrary pick, but it's easy to find documentation for the words) Doing that will reveal exactly how powerful and succinct Forth has always been, because the compilation/execution distinction in Forth is just a bitflip.
yes, i have actually thought about this solution independently, but i still find it a little bit ugly to have to tell the parser that everything past a certain point is runtime, if I am understanding this correctly.
Indeed using a quote to provide the word’s body seems very intuitive. I was asking about this on the retro forth IRC and turned out it could be bolted on to retro forth like: [ body … ] :name
In this case, ‘stack-based language’ is used as a term of art. In particular, in programming language discourse the typical meaning of ‘stack-based’ is a language which there’s a stack threaded through successive procedure calls, where access to the values on that stack are accessed by popping them off and computing with them, then returning a result via a push. The stack is implicit and there are often no mechanisms to name values or to name particular locations on the stack, requiring all procedures to explicitly shuffle, rotate, pop, and push the stack to access data for computation.
I would say that languages where values are assigned a ‘name’ in the program text are not ‘stack-based’ in the manner implied by the term. So while C and nearly all other programming language have a stack data structure allocated as storage for values used in procedures/functions, they are not ‘stack-based’.
> In this case, ‘stack-based language’ is used as a term of art.
This is a shitty and broken term. Hence my comment.
> is a language which there’s a stack threaded through successive procedure calls, where access to the values on that stack are accessed by popping them off and computing with them, then returning a result via a push.
You're just describing a procedural language that returns values. I suppose you could also describe a procedural language that doesn't return but what would be the point? You're just describing a form of indirect subroutines that revolve around jumps rather than the natural instruction progression. This has been a wildly unpopular method outside of entering a performance loop for many decades. It knows it will never have to exit/unwind the stack/call any kind of destructor or deallocation callback when entering a non-exiting loop.
Ok so why don't people (you!) just say "concatenative" given that other languages are trivially stack-based as well? How is it surprising at all that it's mostly syntax and a mediocre runtime (as the majority of languages can boast) that differentiates your pet language from other languages? Can we just admit that one of these options has a complex syntax and the other has a trivial syntax?
I’m not sure why my comment elicited such a volatile response, but assuming you are just using emphatic language for effect I will respond.
The main point you made that I can not agree with the characterization of other languages being ‘trivially stack-based’. Other languages in the Algol, ML, Lisp families have stacks that are an implementation detail of their function semantics. In those languages the stack is an implicit storage mechanism that merely holds values which are semantically associated with some ‘variable’ in the program syntax. In ‘stack-based languages’ the stack is, most usually, an explicit semantic construct which acts as the only available value for procedures to act on.
If your primary argument is against the term ‘stack-based’ that’s a personal position, but there are semantic differences between Forth and C, where emphasizing the explicitness of the stack in Forth is a viable point of divergence. As to using the term concatenative to describe a language, I have some opinions on that which fall outside the norm, so I tend to not use it to describe any of the ‘popular’ languages usually lumped under that umbrella.
I don’t know if the ‘pet language’ remark was towards me or in general, but it was certainly baseless if directed at my comment. If it is a general statement, I would only say that it is common for a community to settle on some terminology that they like and it’s rarely out-group pressure that forces a change in that language (see the ‘Alan Kay invented the term Object Oriented and it doesn’t describe C++’ argument that occurs frequently on forums like HN).
> In ‘stack-based languages’ the stack is, most usually, an explicit semantic construct which acts as the only available value for procedures to act on.
To the extent this is true, this is also true of all languages that anyone uses these days—C, JVM, Rust, Chez Scheme, GHC, python, ruby, ocaml, blah blah blah. The only difference is the syntax used to manipulate the stack. Acknowledging that syntax is the main difference from other languages seems key to evangelization. The idea of "implicit/explicit" doesn't really make sense. how do you refer to the stack in forth? You don't. How do you refer to the stack in C? You don't. Both operate with respect to the stack without ever referring to it via syntax. In both languages, the stack is invoked by referring to procedures/words.
Look if you want to keep up this fantasy that forth or factor is somehow more stack-oriented than any other languages, go right ahead. But you're going to fundamentally misunderstand why people use the language. It's the syntax! It was always about syntax. The stack is just a necessary implementation detail to deliver this syntax, same as in every other language that people actually use.
This is very cool, well done! I love seeing people get interested in other programming paradigms, like concatenative languages. I gave a talk about them at Strange Loop / PWL last year: https://dcreager.net/talks/concatenative-languages/
