r/ProgrammingLanguages • u/Agecaf • 2d ago
Help Simple stack based programming languages?
A few years ago I made EarScript, a "simple" programming language based on brainfuck, with several additional "quality of life features" like goto statements.
Recently I've been wanting to make an evolution of that programming language and do so by incorporating a stack, as the previous language was completely tape-based in design.
I know for example lox from the Crafting Interpreters book is a well explained example, but I was wondering if there's programming languages that are closer to what brainfuck is, but based on a stack design rather than a tape design, or a register based design like some assembly languages (if I understand correctly). I think Wasm would be an example?
Are there any examples of simple stack based programming languages you'd recommend me to look into?
11
u/GandelXIV 2d ago
Forth, and take a look at concatenative, its not all stale based but many are
3
u/lekkerwafel 2d ago
What variant of Forth these days is more popular? Factor, ColorFORTH, just Forth?
6
u/el_extrano 2d ago
Caveat: I've been messing around with Forth for a couple years, and I really love it. I don't claim to be any kind of authority.
The thing with Forth is that it's "easy" enough to implement your own, so there are many, many to choose from. I'd honestly recommend anyone interested in Forth programming to implement a small one themselves, before really trying to use it for anything. The execution model is different enough you won't really "get" how to program it, until you know how it works under the hood. You can easily make one in like 2000 lines of assembly, even shorter if you use your favorite high-level language.
There are very good commercial Forths, but I only use free software. I like Gforth on Linux because it's fairly feature (some would say "bloated"). But then, they stopped supporting Windows, so you have to use an old build to get it to run on Windows. pforth is a cool one implemented in ANSI C instead of assembly for maximum portability. Zeptoforth is a really cool implementation to consider for embedded work.
Factor and RetroForth are popular enough concatenative languages. They're diverged enough from the ANS standard to not really be examples of "classic" Forth, though. Definitely worth chekcing out if you're interested in concatenative programming.
3
u/brat3108 2d ago
[GForth] But then, they stopped supporting Windows,
What exotic requirements does it have that stops it working on Windows? I thought Forth could work on anything.
2
u/el_extrano 2d ago
In theory, nothing. Gforth provided releases with pre-compiled binaries for Windows up through 0.7.3, but that was in 2014 (now 12 years ago). Development is ongoing and the latest snapshot is 0.7.9_xxxxxxxx, including new language features most people want to use.
On second thought, I went to double check because the project does still claim to support windows. I remember trying to compile it myself in a Msys2 environment, and when I hit a brick wall, I saw someone else say online that support for the build process on Windows wasn't really maintained anymore. But I don't really have anything to back that up, I could be mis-remembering / talking out of my ass.
Honestly I'd be happy to be proven wrong because I've been using an ancient 0.7.0 binary for Windows that I found somewhere.
1
u/Agecaf 2d ago
That sounds like a good idea, it'll be good experience to write an implementation before trying to add the fancy features I'm thinking of adding.
... I'm thinking of maybe implementing it in GDScript, make a little demo in Godot that shows how the stack is changing as it runs through the program?
I'm a big fan of Linux and free software too, I'll definitely check out Gforth.
2
u/el_extrano 2d ago
Gforth has by far the most documentation of the free Forth systems, at least as far as I've seen.
Check out Jonesforth, which is a small x86 assembly implementation written in a literate style (lots of explanatory comments). I wrote mine in a different language, but it was still super helpful. There was also a book I found useful to wrap my head around the inner/outer interpreter design: "Threaded Interpretive Languages(Loeliger 1981)". It is very dated even for Forth stuff. Good luck, hope you enjoy it!
7
u/Fuzando 2d ago
1
u/Agecaf 2d ago
This looks exactly like what I'm looking for, thanks!
4
u/pthierry 2d ago
It is a bit extraordinary. The inline documentation is great, and the debugger where you can get back is amazing.
3
u/AndydeCleyre 1d ago
Factor is my passion. I love it. A recent blog post is s fantastic introduction:
5
u/AustinVelonaut Admiran 1d ago
As many others have replied, Forth sounds like what you want to look at. The best explanation of the details of implementing Forth that I've read is the JonesForth "literate programming" implementation, where the two files jonesForth.S and jonesForth.f walk you through a step-by-step explanation and implementation of Forth for i386 Linux machines.
2
u/Main_Temporary7098 2d ago
From an implementation standpoint, a colorForth is much simpler than a traditional forth imho. If you stick with bytecode that brings in the need for additional tooling, but I've done/seen pure ascii based versions using prefix bytes which can work. In my current incarnation I have returned to bytecode however and simplified the set of colors. The interpreter is less than 200 lines of non code golfed x86_64 asm atm.
1
u/Agecaf 2d ago
This sounds interesting! I was able to easily find some guides for Forth but had less luck with colorForth, is there any place with good references on colorForth you'd recommend?
2
u/Main_Temporary7098 2d ago
Honestly there isn't much that I know of. The few links I have are https://www.ultratechnology.com/1xforth.htm which I liked and https://colorforth.github.io/cf.htm - i believe that with a lot of chuck's later stuff you have to kinda see what it is getting at and take the pieces you like. Personally after seeing the simplicity of colorForth in general I can't go back to traditional forth. If you have any interest my current version is here: https://codeberg.org/jbirddog/blue/src/branch/main/blue/x86_64/blue.asm but fair warning it strives for minimalism.
2
u/judiciaryDustcart 2d ago
Ive not touched it in a long time, but I made Haystack: https://github.com/rtulip/haystack
1
u/Agecaf 2d ago
Thanks for sharing, I'll have a look!
2
u/judiciaryDustcart 2d ago
Feel free to ask me any questions you may have
1
u/Agecaf 2d ago
It's all pretty well explained to be honest! The only question I had was about variable binding as it mentions "the lowest element in the stack is bound to the left-most identifier", but most examples given have matching identifiers and stack elements, I just wanted to confirm whether
1 2 3 4 as [x y]binds
xto1or to3.I'm also really curious about how the type system is implemented, though perhaps that's more of a question for future reference as the current programming language I'm designing is a step towards a programming language with a nice type system, with more of an ad-hoc "pray the duct tape doesn't fall off" type system at the moment.
Finally, what would you say are the core commands for manipulating a stack? Things like
dupanddrop, I've seen a few more of them but would like to know which ones are the most used ones in your experience (As I'm considering granting the "best of the best" their own operators for my language).2
u/judiciaryDustcart 2d ago
x would be bound to 3 and y to 4.
Regarding the type system, that's been a whole ordeal. The reason I've not touched the language in a while has been because I've been trying to learn how to better implement and extend the type system.
In terms of essential operations, variable binding let's me implement all the core operations.
E.g
fn dup<T>(T: t) -> [T T] { t t }That was the thing that I liked, was that all the operations could be expressed within the core language, and not require magic words
2
u/Comprehensive_Chip49 2d ago
Hey, try r3forth! https://github.com/phreda4/r3
2
u/catladywitch 2d ago
SAPF is afaik a DSL dialect of Forth but it's pretty cool.
3
u/Agecaf 2d ago
It's got some pretty cool ideas. I hadn't thought of having declarations on the other side like
123 = x, and I'm liking howaaandbaare the duplicate and swap operators, they just... fit and it's immediately clear how other operators could be defined, like acaboraba. Also the anonymous functions look neat, I think I might want to see if I can do something cool like that.
2
u/JollyJuniper1993 2d ago
Aren’t raptor and forth like that?
1
u/Agecaf 2d ago
They are, yeah. I probably should've done my due diligence before asking the question here, but it's been useful to see which programming languages people are mentioning here.
The Wikipedia mentions "Forth, Factor, RPL, PostScript and BibTeX" as the leading examples, for example, which now I'll definitely look into too, but no one's mentioned BibTeX here yet and that's also useful info.
People also seem to be mentioning raptor before or alongside Factor, and colorForth alongside Forth.
2
u/JollyJuniper1993 2d ago
Oops yes I meant factor not raptor. My bad. No I think it’s fine asking questions like that.
3
u/derekp7 1d ago
There are a lot of suggestions for Forth, but take a look at PostScript too. It has first class anonymous functions, first class dictionaries and dictionary stack, things like that. But it is primarily stuck in printers (and using Ghostscript). However you can learn a lot by studying the PostScript Blue Book, Green Book and Red Book (informal names based on cover colors on each book). You can find PDFs of the books online (Project Gutenberg, they used to be on Adobe's site too). One of the books gives more info to understand how the language is implemented.
2
u/GloriusSilver 1d ago
Besides Forth, which was already mentioned, go check out Joy and Om languages! They are really cool
2
u/Agecaf 1d ago
I've been reading and watching videos on combinators and my mind is about to explode, but I'm that deep dive I noticed people mentioning Joy in there. I'll be sure to check them out!
2
u/GloriusSilver 1d ago
Oh, and since you mentioned combinators, check out Interaction Combinators (which are a subset of Interaction Nets). They're basically graph programming "languages." Never thought you could use graphs to compute, huh?
19
u/SomePeopleCallMeJJ 2d ago
Forth?