subleq
how-fast-does-it-quicksort
subleq | how-fast-does-it-quicksort | |
---|---|---|
9 | 1 | |
52 | 1 | |
- | - | |
4.6 | - | |
19 days ago | about 7 years ago | |
Forth | Haskell | |
The Unlicense | - |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
subleq
-
The ancient world before computers had stacks or heaps
I wrote a Forth interpreter for a SUBLEQ machine (https://github.com/howerj/subleq), and for a bit-serial machine (https://github.com/howerj/bit-serial), both of which do not have a function call stack which is a requirement of Forth. SUBLEQ also does not allow indirect loading and stores as well and requires self-modifying code to do anything non-trivial. The approach I took for both machines was to build a virtual machine that could do those things, along with cooperative multithreading. The heap, if required, is written in Forth, along with a floating point word-set (various MCUs not having instructions for floating point numbers is still fairly common, and can be implemented as calls to software functions that implement them instead).
I would imagine that other compilers took a similar approach which wasn't mentioned.
- Show HN: Computing with just one instruction – Forth on SUBLEQ
-
SUBLEQ eForth book
I've already posted about the implementation on Forth, but you might want to see how such a system is created in detail along with the design decisions and compromises. The source code can be freely viewed at https://github.com/howerj/subleq.
- Show HN: A single instruction computer running Forth
- Forth on a SUBLEQ (A One Instruction Set Computer)
- Forth Running on a One Instruction Set Computer
- Computing with Just One Instruction
how-fast-does-it-quicksort
-
The ancient world before computers had stacks or heaps
Well first of all, both are abstract concepts.
No they aren't. A stack is a specific type of data structure. Recursion isn't even specific to computers.
in computer science stacks are considered to be an abstract data type
I think you meant data structure and they aren't both concepts.
Of course, another way to refer to this kind of a structurally induced data type is to call it recursive.
You are making a linked list. A node in a traditional linked list has data and a pointer to the next node. This is what you are making here. Just because you over complicate a stack by using a linked list, it doesn't mean a 'stack' and 'recursion' are the same thing.
Fundamentally this is functional programming silver bullet syndrome. These things really have nothing to do with recursion, they just putting a square peg in a round hole by using recursion for iteration and linked lists.
It's all fun and games until you get past trivial examples. Then pretending complex iteration and data structures are best done with recursion aren't so fun anymore and you want to control what is actually happening.
One example is this rust quicksort being 40x faster than haskell
https://github.com/LightAndLight/how-fast-does-it-quicksort
What are some alternatives?
swapforth - Swapforth is a cross-platform ANS Forth
Mako - A simple virtual game console
durexforth - Modern C64 Forth
lbForth - Self-hosting metacompiled Forth, bootstrapping from a few lines of C; targets Linux, Windows, ARM, RISC-V, 68000, PDP-11, asm.js.