Stack-Oriented Programming | Hacker News Reader

Stack-Oriented Programming

en.wikipedia.org

103 pointsazhenley77 comments

The old RoboWar game on the Mac featured a stack oriented language for programming your battle robots. It was a great introduction to RPN and thinking about the stack.

One of the interesting aspects of the game was the way the CPU was limited to a very small number of instructions per tick. At most you would get 50. So if you had a complex task that had to be executed in one tick, like filling the screen with bullets before your robot shut down due to lack of power, the way to do it was to preload all of the arguments onto the stack, wait for the tick to turn over, then call all of the functions at once. Basically allowing you to bank processing time for the turn you needed it.

In CoreWars, which used assembly-like language to create programs fighting each other, one of the most powerful strategies was to inject a SPL instruction (basically fork) into an enemy program, preferably jumping to the SPL instruction itself. As a result, the enemy program would quickly be split into 64 processes (usual maximum number), so the actual logic would be running at 1/64 speed, bogged down by the dummy processes.

If you could successfully do that, why wouldn't you just bomb a DAT in instead?

Because the opponent could already be running multiple processes - killing one would only speed up the others.

The programs that uses the SPL-bomb tactic usually tried to catch all the enemy processes (slowed down to uselessness by the SPL-bomb) in the same place before finishing them off with a DAT.

I see. I don't think the original version of CoreWars had multiple program counters? Got to admit it's been a while.

You're right, the version described in the original article in the Scientific American did not have the SPL instruction, but the first "Core Wars Standard" proposal in 1988 introduced it.

You can see the different versions collected here: https://corewar.co.uk/standards/

I went through a basic Forth tutorial [0] a couple of years ago and really enjoyed the process. It gets you to the point of building a real game of "snake", although it slightly glosses over the actual canvas interface.

[0] https://skilldrick.github.io/easyforth/

Interesting. But in iphone we do not have arrow keys sadly. Possibly can hack ... but not forth.

I try to find a better way to try this and after reading hackaday on Forth 2017 which highlight the latest (2017) update on Forth development:

https://hackaday.com/tag/forth/ (mainly this: https://hackaday.com/2017/08/04/take-the-blue-pill-and-go-fo... )

I find this and you can run the whole thing on my MacBook in 5 minutes. It is great:

https://jeelabs.org/article/1720b/

The really interesting thing about Forth is just how minimalistic a bare-metal Forth implementation can be - not even an interpreter, but literally a few words handcoded in machine code, and the rest built from there (and then possibly optimized with more machine code, if you need that).

Given the ease with which Forth can be ported to other platforms and architectures, I often wonder why there's no C-to-Forth translator - it seems like it would be just about the easiest way to bootstrap things.

Bare metal like on the Ace.:)

https://en.wikipedia.org/wiki/Jupiter_Ace

http://jupiter-ace.co.uk/

Bitcoin also uses stack oriented language, and the interpreter is actually very short and simple:

https://en.bitcoin.it/wiki/Script

https://github.com/bitcoin/bitcoin/blob/master/src/script/sc...

Yes! Stack-based abstract machines are often used because they allow compact code that is very easy to create and interpret.

As another example, Pascal p-code (UCSD p-code) is also stack-based:

https://en.wikipedia.org/wiki/P-code_machine

The Java Virtual Machine (JVM) also uses an operand stack:

https://en.wikipedia.org/wiki/Java_virtual_machine

That P-code was not (quite!) portable between computers, was a lost opportunity. How cool it would have been.

Oddly, that article doesn't link to the most interesting modern use. It's for security exploits. People have built compilers that output a binary that consists largely of return addresses that point into the middle of normal functions.

https://en.wikipedia.org/wiki/Return-oriented_programming

you're mixing 2 different concepts. Yes they end in oriented-programming in the end but one is an exploit technique and one is a programming model.

This deserves a bit of clarification: ROP is an application of threaded code technique. Conventional Forth (proto-father of stack-based/concatenative languages, alongside with Joy) is based on indirect-threaded code (ITC), so the connection between ROP and stack-based programming is rather indirect (pun intended).

For anyone interested, Book by Loeliger [1] and "Moving Forth" series [2] are essential readings on this topic.

[1]: https://archive.org/details/R.G.LoeligerThreadedInterpretive...

[2]: https://www.bradrodriguez.com/papers/

I'm a bit confused why "using postfix notation" is considered a programming paradigm - I'm semi-fond of post-fix notation (it is the second best notation after prefix after all) but[1] it's incredibly trivial to convert between prefix and postfix notation and most programming language expressions use prefix already - it's just the infix ones that are a bit weird... Allllso, expressing if statements without any infix notation is sort of terrible, I've never seen an option to do it that isn't incredibly misleading or confusable.

A core question, though, is why? Is tab-oriented programming have a wikipedia page where programs are written predominantly using tab stops instead of spaces? It's honestly a very similar sort of distinction to make.

1. I'm trying not to stray too far into all turing complete languages are turing complete and thus difference is meaningless land.

As I see it, the key characteristic of stack-oriented programming is not that it "uses postfix notation".

Rather, the key characteristic is that there is an important implicit feature available, namely the stack (or, as for example in the case of PostScript, several stacks), by which arguments can be passed along.

As a consequence, you get a form of compositionality of language elements that is not available in languages that lack this feature: A language element may consume, change and create entities on the stack, and the next language element can pick them up implicitly.

This often allows very concise and elegant code, and can also be interpreted very efficiently.

Best advocacy I know of: http://evincarofautumn.blogspot.com/2012/02/why-concatenativ...

Presented by way of being an interesting link, and the educational nature of reading the best arguments in favor of something. I haven't done anything in concatenative programming in about 20 years, since I left math class and didn't need my HP 48G anymore.

That's quite helpful, it may be a lack of in-depth reading of the page but the persistence and implicit passing of computation between operations is helpful to understand the differentiation. In more classic procedural languages you'll usually have a function stack that is being pushed and popped two but actual program values are handled using entirely arbitrarily loaded references that get juggled around as needed for computation - does stack programming often have a similar concept to frame popping when an issue with I/O or something similar is encountered or do we just get a panic that aborts computation?

To get a glimpse of stack-oriented programming, I really like and recommend PostScript, because this also automatically introduces you to a widely used programming language with important practical applications, and it's also great fun to learn.

So, for instance, let's elicit an error using Ghostscript, a freely available and efficient PostScript interpreter:

    $ gs
    GPL Ghostscript 9.27 (2019-04-04)
    ...

At the "GS>" prompt, I now define "f" via:

    /f { /hello g } def

Note that "f" refers to "g", which is not yet defined.

Therefore, when I then invoke "f" via:

    GS>f

I get an error:

    Error: /undefined in g

And importantly, the stack is retained, so I can inspect it at this point, interactively, using for example "pstack":

    GS<1>pstack
    /hello

This shows that /hello is still on the stack. From there, we can resume in various ways, for example by clearing the stack (with "clear"), by redefining and reinvoking "f" etc.

Is PostScript used beyond page description? I'm really curious :)

Sun made a windowing system based on (Display) PostScript way back https://en.wikipedia.org/wiki/NeWS

It's Turing-complete, which makes writing programs to analyse documents a bit of a problem at times.

But I think maybe you meant in the sense of "in the real world", and I can't think of any examples. Prefixing some postscript to a document to manipulate that file is something it can be suited for, rather than using an external language to do so.

Once I wrote a bingo card in PostScript which would randomize its cells every time you printed it. That's almost useful.

I found a .ps that generates timing wheel patterns (discs with alternating black and white radial bands). you'd plug in inner/outer radius, number of bands, and you'd get a printable document from that file. As in, the .ps file was code, which printed as an image. I now know this is the origin of pdf but it blew my mind.

I recently saw an announcement[0] of a Z-machine in Postscript. The Z-machine is a runtime for text adventure games. Also posted on HN[1] but no comments were made.

[0]: https://groups.google.com/d/msg/rec.arts.int-fiction/HNtntxC...

[1]: https://news.ycombinator.com/item?id=21367412

Yes; I wrote that program, and the Usenet message and the message on HN (which mentions the message ID for the Usenet message). If you have comments about it, I suggest writing a follow-up message on Usenet.

PostScript is a real programming language and can be used for many things (especially graphics). I also wrote a JSON parser in PostScript (see message <1567977875.bystand@zzo38computer.org> on comp.lang.postscript), and then someone else post their JSON parser in PostScript too.

I think PostScript isn't such a good protocol or document format, but it is good as a programming language. It is what I might use if I want to make a diagram (but unfortunately Ghostscript cannot produce SVG output; it can output PDF though, as well as many raster formats).

Nice! Thanks for answering! Would you choose PostScript over Forth as a general purpose language?

I think it would depend on what I am trying to make; there are advantages and disadvantages to each. In the case of the JSON parser, I think it is helpful that PostScript has data structures (such as arrays and dictionaries) and arbitrarily typed values like JavaScript and many other scripting languages have. In the case of Z-machine, Forth would probably do as well as PostScript (or probably Forth would do better, actually).

Someone was unsure how useful would be the JSON parser I wrote in PostScript, but if you want to print some diagram based on data in JSON format, then it can be helpful.

(I could implement Z-machine in Forth too if I wanted to do, but I have not done so yet because I have other things to do; I don't know if I might do so in future or not. I could implement Z-machine in any programming language with byte arrays, including assembly language (I started but haven't finished one in 6502).)

https://www-cdf.fnal.gov/offline/PostScript/fractal-fern.ps

is a fractal fern. This is page description, but not in the normal way that it's used. Compare the output in a PS or PDF viewer with the source code which is under 1.5K.

Even in page description alone the programming capabilities are rather useful. E.g. to produce barcodes you can just generate them from data.

There's an old language, pop11, that's similar to lisp but stack oriented. A few sections of the manual will show you the kind of stack tricks that make different order useful:

https://www.cs.bham.ac.uk/research/projects/poplog/primer/#s...

Functions that return several results, implicit parameters, open stack, etc. It's a lot of fun.

Sounds like automatic currying in FPLs is equivalent to some of that.

Postfix notation isn't really related to stack programming, you could just as easily read the programs right-to-left and have prefix notation. Something like K/Q but with stacks. Anyways, stack based languages are a real distinct category, just like OO or FP or array-based languages or whatever. If you look at forth code for example, especially written by Moore, it's some... pretty crazy shit. I do agree that conditionals are pretty annoying to read using stack based languages, but they are used a lot less often due to the implicit "branching" a stack context provides.

For a stack oriented language, postfix is execution order. Consider the program "2 3 +". This is really three instructions:

1. Push the literal 2 onto the stack

2. Push the literal 3 onto the stack

3. Execute the Plus Operation

Therefore, there is no need to use a compiler, or even Dijkstra's shunting-yard algorithm[1], to reorder the statements for execution. This makes it extremely easy to write a compiler or interpreter for a stack-oriented language with postfix syntax: you never have to do any parsing at all, you just execute (or emit byte code) for each token as it comes, never needing to look forwards or backwards even a single token.

[1]: https://en.wikipedia.org/wiki/Shunting-yard_algorithm

"Paradigm" is a conveniently abstract word.

I would say that RPN is part of a paradigm - and if you pardon my bias I would say the Forth paradigm, really. The stack is part of a strategy of complexity reduction that start at the compiler/interpreter level.

The stack-oriented approach can also be used within modern languages to realize the benefits of simplicity and code-reusablility. I created a python package for data analysis that treats a data frame like a stack of columns and lets you manipulate columns using postfix operators: https://github.com/punkbrwstr/pynto

Wow, this looks really interesting. Was there any particular reason you decided on this approach?

How is that more interesting than simple .modify_column(params)?

You definitely could do a similar column-level functional approach that way, but I think the simple syntax of the stack-oriented approach makes it easier to read and catch errors. The code would be a lot longer that way.

Building up complicated time series transformations by composing simple functions helps me be sure I'm doing what I think I'm doing. Since the transformations are tacit expressions that don't define specific parameters they are then very easy to re-use and combine. And I have some combinators that can apply the functions in pretty flexible ways. Also, since its all lazy-evaluated on a per-column level I can work with huge tables, but only end up operating on the subset I need.

This makes me miss my HP 28S calculator from the 80s. What a beautiful machine that was.

I loved my HP-50g, allowed my to program all day long while stuck in stupid high school classes. RPL is a nice little language, a bit hard to read after a break though. And the fact that HP calculators throw away all whitespace and indention after saving a program certainly doesn't help.

I have used Forth, PostScript, dc, and other stack-based prorgamming. However, mostly in PostScript code I have not seen the Forth-like notation for the stack effect, although I do use that in my own PostScript programming, because I think it is better than the notation Adobe uses.

Some virtual machine instruction sets (such as Glulx and Z-machine code) still require instruction operands but allow some or all of them to be optionally specified as stack operands. This allows you to have both stack and a register-like programming.

A Brainfuck tape can be thought of as two stacks and a register. ‘<‘ or move-left becomes push the register onto the right stack and pop the left stack into the register.

Can someone who knows more about Forth clarify this for me: what "level" is something like Forth? Is it higher or lower-level than something like C?

The reason I'm confused is that I see Forth in a lot of areas that look like they're typically for "C and lower", but looking at the syntax, Forth looks like a high-level language.

It's a lot like Lisp, especially as it was decades ago. The language itself is low-level but you can construct some very high-level-like constructs in it yourself. Where it differs is that Lisp is a low-level language for a machine that doesn't really exist unless you have a Lisp machine, and Forth is for your actual hardware... as viewed through a set of stacks, anyhow. I suspect had it ever been used for large code bases it would have had a similar problem that Lisp had, where any given program might be elegant but there would be too much convention differences between any two programs to let them work together very well, similar to the problem that Lisp has sometimes been considered to have with macros. (It's great to be able to synthesize your own entire world, but no two programmers synthesize the same world.)

Can forth handle delay execution. Or a conditional where one later parameter never need is not reached. It seems all parameters at least needed to be in first, say a rough lisp like use case.

(Def ExecN func n infinite-series)

(ExecN + 10 integer)

... can it be done in forth.

Of course. You can build whatever functional abstractions you like in Forth. Some time ago I did a number of experiments with lazy generators: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith...

The above dialect uses { } to delimit anonymous inline word definitions. RetroForth has a similar feature, and Factor uses the same syntax for "quotations", which have slightly different semantics but roughly the same meaning.

Thanks. If I start today to learn as I have searched a bit ... it seems to have a dialect retroForth whilst I see a 10 years old recommend swiftforth ...

Actually the tutorial that host a forth on js (like clojurescript just self implement).

Which path to go?

Do not want to learn lisp ended up in scheme.

On desktops I've used gforth[0]. It's rather large and heavyweight, but easy to install and has decent documentation; not a bad starting point. Alternatively, JonesForth[1] is an excellent extensively-commented implementation suitable for reading start-to-finish.

[0] https://www.gnu.org/software/gforth/

[1] https://github.com/nornagon/jonesforth/blob/master/jonesfort...

Forth can be a little troublesome in that area. There is a standard language but it is primitive. Extensions for real world problems tend to diverge in syntax. This has lead to a saying: "If you've seen one Forth, you've seen one Forth" :)

It's better than in the past with an ISO standard (IMHO) but know that if you change language providers there will be differences for things like external library linking (if available), GUI interaces etc.

There are demo versions of commericial systems at:

https://www.mpeforth.com/resource-links/downloads/

https://www.forth.com/download/

And of course a major pass-time in the Forth community is writing your own Forth. There is even a few Forths written in Python. (for instructional purposes only I assume)

http://openbookproject.net/py4fun/forth/forth.html

Immediate words in Forth are somewhat analogous to macros, and therefore can do this kind of stuff if need be - not evaluating something, or evaluating something several times. Take a look at a sample implementation of IF/ELSE/THEN and DO/LOOP: https://github.com/nornagon/jonesforth/blob/4f853252f715132e...

Forth also has anonymous words (:NONAME), so you can dynamically define a computation and pass it around on the stack, and later execute it. I don't think there's any way to clean them up, though (no GC).

It's lower-level than C. The primitive datatypes, to the extent there are datatypes, are in terms of bytes and machine-words. Most Forths include a dialect for embedding machine instructions in word definitions.

It's higher-level than C. Forth allows you to layer on dialects with custom domain-specific syntax and do other kinds of fancy metaprogramming. You can use Forth to interactively extend itself while you're working. Many Forths include a "bootstrapping" script, written entirely in forth, which defines such niceties as control structures and the syntax for comments.

Expressivity and execution costs are inversely correlated, but not perfectly so.

Forth is more expressive than C, but just a bit more expensive. It being more expressive means it is in a higher level on my book, but it's outside of the usual hierarchy, so I would say it's in a higher level, but not on the same ladder.

Forth is special. It's lower-level than C, in that you have more control over every aspect of the system; but you can refactor mercilessly and change the parser with a few lines of code, so you can develop your own DSL for the particular domain of problems you're solving.

The best way to achieve maximum flexibility and efficiency is to have the freedom to hop layers. To specify the high-level logic with a suitably abstract description, and then be able to reach into the lowest layers so that you can do what's necessary without needing to contort the logic to conform to the middle layers. If you do this once, it's a hack; if you hack repeatedly, you have a hot mess of entangled spaghetti; but if you design with this hackability in mind, you can evolve a system with abstractions at just the right level, that can be hacked as needed, without it turning into spaghetti. Requires discipline though.

Because there's no grammar in forth. You are the parser you can go as high as you want, yet you're still chaining near native instructions.

A double edged sword too

Neither.

I recall that the first thing that jumped out at me was that Chuck's code didn't have all those layers that my code had. There was the abstracted code on top and the hardware drivers on the bottom and very little in between. There was not a clear distinction in style at various levels as in my code where there were always someone else's code layered under mine that I could not or dared not change. Chuck's code looked abstracted and high level right from the bottom, the top used almost as many primitives as the bottom code. [1]

The confusion seems to come from the idea that a piece of code has to be either "abstract" all the way or "close to the metal" all the way. Why should it be? If you need to flip a bit in a peripheral between a call to some filesystem function and a call to memory page management function, just do it directly, don't invent a pseudo-high-level function just for that. Bare metal ain't dirty.

[1] http://www.ultratechnology.com/levels.htm

> Bare metal ain't dirty.

No, but it's not as solid as it sounds. What happens when version 2 of the hardware appears, and moves the bit to a different register?

The same thing when a new OS release break some API call.

.. which they do far less often than hardware changes. You have a reasonable chance of running a 25-year-old Win32 program or 20-year-old statically linked ELF Linux program.

> What happens when version 2 of the hardware appears, and moves the bit to a different register?

You adapt your code for that platform. I don't know why developers today have such a love affair with unnecessary abstraction. Abstract when you need to; never before.

Lower level! Here's a two part tutorial I wrote which explains it better: http://git.annexia.org/?p=jonesforth.git;a=blob;f=jonesforth... http://git.annexia.org/?p=jonesforth.git;a=blob;f=jonesforth...

I recently wrote an accepted answer on cs.stackexchange about how to implement sorting on a stack machine: https://cs.stackexchange.com/questions/117949/stack-permutat...

The asker isolated the question well, so I had no idea what Forth or stack machines are. Still it's a nice exercise to to implement common algorithms with a restricted set of moves.

Fun to see this, I just finished implementing a stack-based language of my own design this weekend.

The language is called UnoScript, inspired by the UNO card game. UNO has a natural stack built-in (thinking of the draw and discard piles) so there's a really natural connection. Link here if you're curious: https://github.com/berlinquin/UnoScript

There are stack based languages that have an intrinsic elegance. For example:

https://esolangs.org/wiki/Pancake_Stack

And remember to Eat all of the pancakes!

An interpreter can be written rather quickly (compared to any productive program in the respective language) and it is interesting how much you can actually achieve with such primitive tools.

Is Human Resource Machine [1] basically also a stack oriented programming game, or am I confusing the physical stacks of paper you order the little guy to move around with computer stacks?

[1] https://tomorrowcorporation.com/humanresourcemachine

8087 had an 8 level stack https://en.wikipedia.org/wiki/Intel_8087#Registers

> 8087 had an 8 level stack

Why "had"? The x87 instructions are alive and well in modern intel processors. You can also generate code for them (for example, if you use "long double" in C) with all major compilers.

Just saw this in your class this morning!

I expected this to be a joke about Stack(Overflow)-Oriented Programming

I read this title and thought, hmm is this another name for 'lock-in' or similar? You know like pick a stack of tools and then only use those, to the point you can hardly do anything at all without them. (which isn't necessarily bad, if it allow you to get things done fast and good)

On topic: always good to read up on less common programming principles just to, erm, avoid lock-in

I believe that's called resume oriented development.

May the Forth Be With You! :)

FORTH LOVE IF HONK THEN

Reply on news.ycombinator.com