Stack-Oriented Programming

(en.wikipedia.org)

103 points | by azhenley 172 days ago

19 comments

  • jandrese 172 days ago

    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.

    • skocznymroczny 171 days ago

      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.

      • flir 171 days ago

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

        • brazzy 171 days ago

          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.

          • flir 169 days ago

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

            • brazzy 169 days ago

              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/

    • n4r9 172 days ago

      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/

    • xiphias2 172 days ago

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

    • souprock 172 days ago

      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

      • 9214 171 days ago

        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/

        • halayli 171 days ago

          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.

        • munk-a 172 days ago

          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.

          • triska 172 days ago

            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.

            • jerf 172 days ago

              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.

              • munk-a 172 days ago

                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?

                • triska 172 days ago

                  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.
                  • haolez 172 days ago

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

                    • pedrow 171 days ago

                      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

                      • zzo38computer 171 days ago

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

                        • haolez 170 days ago

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

                          • zzo38computer 170 days ago

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

                      • PeCaN 172 days ago

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

                        • rwmj 171 days ago

                          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.

                          • RodgerTheGreat 172 days ago

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

                            • kortex 172 days ago

                              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.

                              • hnick 172 days ago

                                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.

                                • Mikhail_Edoshin 170 days ago

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

                              • narag 172 days ago

                                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.

                              • rixed 171 days ago

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

                              • olooney 172 days ago

                                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

                                • smabie 172 days ago

                                  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.

                                  • astrobe_ 172 days ago

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

                                  • punkbrwstr 172 days ago

                                    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

                                    • reedwolf 172 days ago

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

                                      • punkbrwstr 161 days ago

                                        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.

                                        • heavenlyblue 171 days ago

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

                                          • punkbrwstr 161 days ago

                                            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.

                                      • joncp 172 days ago

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

                                        • smabie 172 days ago

                                          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.

                                        • zzo38computer 172 days ago

                                          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.

                                          • pipingdog 171 days ago

                                            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.

                                            • 91aintprime 171 days ago

                                              isn't this also the relationship between Turing machines and double stacks in general?

                                            • tombert 172 days ago

                                              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.

                                              • RodgerTheGreat 172 days ago

                                                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.

                                                • rabidrat 172 days ago

                                                  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.

                                                  • astrobe_ 172 days ago

                                                    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

                                                    • pjc50 171 days ago

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

                                                      • naikrovek 171 days ago

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

                                                        • pjmlp 171 days ago

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

                                                          • pjc50 171 days ago

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

                                                      • jerf 172 days ago

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

                                                        • ngcc_hk 172 days ago

                                                          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.

                                                          • int_19h 172 days ago

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

                                                            • RodgerTheGreat 172 days ago

                                                              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.

                                                              • ngcc_hk 171 days ago

                                                                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.

                                                        • marcosdumay 172 days ago

                                                          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.

                                                          • rwmj 171 days ago
                                                            • agumonkey 172 days ago

                                                              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

                                                            • virtuous_signal 172 days ago

                                                              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.

                                                              • quintenk 172 days ago

                                                                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

                                                                • raxxorrax 171 days ago

                                                                  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.

                                                                  • wodenokoto 171 days ago

                                                                    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

                                                                    • mzs 172 days ago
                                                                      • enriquto 171 days ago

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

                                                                      • marviel 172 days ago

                                                                        Just saw this in your class this morning!

                                                                        • pagutierrezn 171 days ago

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

                                                                          • stinos 172 days ago

                                                                            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

                                                                            • rckoepke 172 days ago

                                                                              I believe that's called resume oriented development.

                                                                            • empressplay 172 days ago

                                                                              May the Forth Be With You! :)

                                                                              • CarlRJ 170 days ago

                                                                                FORTH LOVE IF HONK THEN