Forsp: A Forth+Lisp Hybrid Lambda Calculus Language
xorvoid.com
xorvoid.com
Pretentiousness on my part aside, this is a pretty mind-blowing concept. The interpreter being in less than 1000 lines of (comprehensible) C is all the more commendable (most of these minimal languages turn out to be some monolithic Rust thing or similar, which kinda defeats the entire purpose imo).
Excited to take a closer look at the source to see how the various data structures etc. are laid out in memory. I won't be able to resist making comparisons to my current/other favourite mini-language 'fe' (https://github.com/rxi/fe), a sub-1000-line Lisp also written in C. If you haven't seen that one I'd definitely recommend checking it out.
Thank you for putting this online. Happy hacking!
Super cool
<< a -> << a a * >> >> 'SQUARE' STO
First HP engineers made RPL, then they attended Sussman and Abelson's intro to CS class. I think Sussman once said that, if RPL had anonymous functions it'd be a perfect lisp.
They were real good.
https://ocw.mit.edu/courses/6-001-structure-and-interpretati...
I can do whatever to a function. I can use it as an argument. I can return it from another function. I can make a function that modifies functions.
All that w/out doing anything out of the ordinary day to day programing.
I decided on using sigils and then my thought-process drifted to Perl/Php, so $ naturally felt like a variable definition (which naturally must pop from the stack). I guess ^ is “push ‘up’ to stack”. But it’s all really arbitrary irrelevant syntax. YMMV.
Awesome language, and it's definitely important from a theoretical point of view. However, you've missed the chance to call it "LiFo" :)
So you could presumably also write a Lisp interpreter AND a Forth interpreter using it?
(Might as well write a Turing machine interpreter too for the trifecta... assuming one can decide on the syntax...)
That plus some additional functionality to make it more usable in the general sense (adding math functions, string manipulation, maybe some basic I/O) and it might be a VERY interesting instructional tool.
I've heard the term "thunk" but I forget what it means...
Rebol allows you to use a block as a list/function/thunk, which is lazily evaluated. This changes the scoping in that you BIND a context to this thunk.
It's a different take on process migration in that the context can be serialised with the thunk, or a new context applied at the process site. This is in contrast to lexically scoped lambda functions which then need to account for dynamic (free) variables somehow.
The usage survives into modern times, whereby lambda arguments are sometimes called thunks.
int a=1, b=2; auto thunk = [=]() { return a+b; }Someone even asked the same question
' seems redundant. 'x could just be (x)?
(0 swap - -) $+
Division is much harder, but doable also. Generally Forsp in the camp of minimalist languages so minimizing the number of primitives seemed more interesting.
If you want to play around yourself, it’s trivial to add those operations.
> If you want to play around yourself, it’s trivial to add those operations.
Now you're using "trivial" like a mathematics professor!
pop is kinda like ! in FORTH and push is like @ so I think $foo would be more FORTHy as !foo and ^foo as @foo
Stacks have great GC properties vs. an actual GC, but for more complex scenarios, and dictionary management, some sort of GC would be preferred. I've not looked at the forsp source yet, but it may need a more general (realtime) GC, possibly via a linear-types system.
If you push, pop, push, pop, push repeatedly you’ll be wrapping the value in lots of closures. The value is no longer a value too. You’d have to “force” it to get back the value.
Semantically quite different. If you’re going all Turing tarpit, could you survive without “^a”? Maybe. But you’d be suffering for sure.
Though if `(a)` is observably "no longer a value" of course then that's an issue. Which may or may not be a problem :-)
When I learned Forth about 15 years ago, we used the { } syntax described here, not the newer(?) {: :} syntax: https://gforth.org/manual/Local-Variables-Tutorial.html
I read Forth was popular among embedded devs during 80/90s. That's not my field, though.
There you go, now it has parens, just backwards. Can even use parens instead of braces if you want, I just didn't want to overwrite comment syntax.
: >BRACES 1 CELLS BRACES +! BRACES @ ! ;
: BRACES> BRACES @ @ -1 CELLS BRACES +! ;
: { DEPTH >BRACES ;
: } DEPTH BRACES> 1+ <> ABORT"unbalanced" ;
{ 1 2 + } .
{ 5 { 1 2 + } * }Yes because I declared 30 cells, you can declare more if you want.
> Unless I am mistaken, it requires a pointless increment and decrement of a variable before and after every function call.
Yes it adds overhead, you can rebuild with : { ; IMMEDIATE : } IMMEDIATE ; and then there's zero overhead on any Forth, when you've demonstrated the braces match. This is meant as an aid for people that struggle without parens.
> Aren't those just functions? If so, it wouldn't work in compiled code.
It works in compiled and interpreted code, 'just functions' compile automatically without trouble in Forth, it's parsing words and immediate words that need care.
No that code wouldn't work with multiple threads, but if you declare the space as USER space it would, similar to just whacking 'thread_local' on something.
The example is failing in one regard, that it doesn't provide a way to reset the stack if something goes wrong. You can use something like : RESET{} BRACES BRACES ! ; to accomplish that. But it is just meant to show that Forth is quite succinct and powerful, which it does.
Does the call to DEPTH still work in that case?
> But it is just meant to show that Forth is quite succinct and powerful, which it does.
How does it show that? You could write a similar function in almost any programming language, with the only difference being the call to DEPTH which I don't see as being generally that useful. As an example in common lisp:
(defvar depth nil)
(defun { () (push (depth) depth))
(defun } () (unless (and depth (= (depth) (pop depth))) (error "Unbalanced expression")))
Code using the braces can use those definitions when you want to remove the overhead, and it disables the feature. This lets you use it as a programming aid, and then remove the overhead completely when it's not necessary or for a 'release build'.
> It's simultaneously more readable and more terse than the Forth code.
Does it still look neater when you use the syntax you've defined?
> And this example doesn't stop working after a certain number of open braces.
If you really want to remove the limit you can, Forth is just explicit about memory management. This is like C vs JavaScript. I'm quite happy playing with memory management myself, but if you don't like that or think declaring a fixed size stack is hacky then I can see why Forth wouldn't be appealing.
Here is one way to remove the limit, it has drawbacks (but so do all dynamic memory approaches, they're just hidden by managed languages).
: POP HERE -1 CELLS + @ -1 CELLS ALLOT ;
: { DEPTH , ;
: } DEPTH POP 1+ <> ABORT" Unbalanced" ;
Yes but in a few lines of simple code, and the result is actually a syntax that looks nice to use.
And you'll notice that C isn't a very powerful language.
> Does it still look neater when you use the syntax you've defined?
No because in CL you would define a with- macro that syntactic enforces equal nesting. So the CL version is:
(defmacro {} (&rest args) `(progn ,@args))
> Yes but in a few lines of simple code, and the result is actually a syntax that looks nice to use.
Those are a few lines of highly complicated code that does something very simple and just happens to use the short function names { and }. The actual implementation of those functions is easier to write in almost any other language, which is what I was demonstrating with the CL example. If you want to make the case that Forth is powerful, you need to do more to prove it than show you can hack together a half-solution for a problem Forth created. Forth simply isn't a powerful language when counting matching braces is a difficult problem.
Okay.
> I thought that would be too trivial demonstrate though. If you really don't like how it looks, you can fix it with two more lines of reader macros. The result would be a nicer syntax as you wouldn't have to put spaces around the braces.
The example is 'trivial' though. Also compare how big Forth is against CL, I mean Forths are often well under 10KB. I've written a Forth like this. I've never written a CL. Have you?
> Those are a few lines of highly complicated code that does something very simple and just happens to use the short function names
Just because you're incredulous doesn't mean that's not a feature.
> easier to write in almost any other language, which is what I was demonstrating with the CL example
CL isn't 'any other language' though, lisps specifically have quite powerful reflection.
> hack together a half-solution for a problem Forth created
Hacky half-solutions are charming, and Forth didn't create the 'problem' of structured syntax, it just didn't provide a solution out-of-box. That's one of the very explicit tradeoffs of the language.
I would say a lot of this is because CL has a large standard library, but not much of that is primitive. Even then, I would say the CL standard lacks many things, so it is too small for general use rather than too large. From a perspective of implementation, I would almost always choose a small Scheme over Forth or something Forth-like.
> CL isn't 'any other language' though, lisps specifically have quite powerful reflection.
Those functions don't use reflection.
> Forth didn't create the 'problem' of structured syntax, it just didn't provide a solution out-of-box. That's one of the very explicit tradeoffs of the language.
It created the problem of not having structured syntax and that's a trade-off that you lose as soon as you write more than a maybe a hundred lines of code.
Sorry I mean macros / or whatever. You know what I mean(?).
> that's a trade-off that you lose as soon as you write more than a maybe a hundred lines of code
And yet you can have braces with e.g. 2-3 lines of code. Anyway this is beyond tedious now, sorry for provoking you with my code, or my opinion that Forth is interesting, or with the praise I received, or that Forth kicked your dog or something; I'm not really sure what did it. I have talked with you in good faith to try and help you understand why it's interesting to me, I don't claim it's an absolute good or even necessarily practical in most situations.
> yet you can have braces with e.g. 2-3 lines of code
You can't really. You'd be better off treating braces as whitespace than having them check the stack depth before and after each function call. They wouldn't even be correct then because you could make multiple calls within the same set of them. If you want to implement braces properly, you'd need a way to introspect how many arguments a function takes, but Forth is not powerful enough to do this.
I haven't used Forth in anger for over two decades now, but in some ways I do miss how the language felt even more hackable than a good lisp, while simultaneously being easy to reason about at a low level. That said, the RPN and stack manipulation definitely make it a bit of a brain teaser, especially at first. In that sense it reminds me of Prolog and APL and, for that matter, Lisp: they're languages where the greatest joy of learning them is the way they force you to think in very different ways, and how that can promote epiphanies about computation.
I would need to spend more time grokking this language to really understand, but it appears that the author has effectively achieved something that's semantically equivalent to Forth, but has a lot of syntactic commonality with Lisp. That's rather compelling to me from a "eliminates the first and most noticeable stumbling block for newcomers" perspective. That said, I'm having to repress a bit of a desire to react the same way parts of the Racket community did when Matthew Flatt announced his infix syntax project. Is a key part of Forth's concatenative nature lost when the syntax itself is no longer concatenative? I don't know, and I'll admit it's very doubtful that I'll spend enough time with Forsp to find out. But it's an interesting thought, all the same.
The lack of local variables and named parameter is also a consequence of this search for ultra-low complexity, in dialects that follow the traditional style (the one of the creator of Forth, Chuck Moore).
The readability argument is one that should always be taken 1024 grains of salt. You say Lisp is more readable, yet you'll find some people to say that it's "Lots of Insipid and Stupid Parenthesis" and that prefix notation is unnatural. You could also find positive opinions about APL. It is just a matter of training and habits.
a b c d
(d (c b) a)
Certainly not "objectively" in the literal sense, because there's no measure of "readability". But you can define one if you want, so that we can argue about its biases and relevance ;-)
But Forth programmers sometimes use double spaces to separate sub-expressions:
(d (c b) a) <=> a b c d
(square-root (+ (square a) (square b)))
<=>
a square b square + square-root
square swap square + square-root
( a ) square swap ( b ) square + square-root
Something is harder to read if it takes more effort to read it. Reading code is converting it from the format it is written down in to the tree of invocations in your mind. Forth is more complicated to read because you must use the definition of each function to determine how many arguments it takes, and hold that information on a stack in your head. All you have to do in lisp is count the number of parenthesis. Reading Forth is O(stack depth) memory, where reading lisp is O(1).
Imagine you wrote some code and it produced an error because you didn't give enough arguments to a function. In lisp, you can look at the function and trivially see how many augments it has. In Forth you will have to scan the entire piece of code to locate the error.
Purely practically, I can almost guarantee that someone with no experience in either will learn lisp faster, and they certainly wouldn't need to write "training wheels comments" to figure out how the functions are called. In fact, the person reading the lisp code would likely understand instantly how it works, where the person reading the Forth code would spend a long time staring ant it and having to write stuff down to figure that out. It's just transparently obvious that reading Forth code takes more effort than reading lisp code for anyone who has spent equal time doing both.
I think the smiley was a sufficient warning not to go there. Define harder. For whom ? etc.
> hold that information on a stack in your head.
I have proactively addressed that point, it is a matter of coding style and "good practices". But since you can only believe me on that, the discussion can only go in circles if you don't agree.
> It's just transparently obvious that reading Forth code takes more effort than reading lisp code for anyone who has spent equal time doing both.
It depends by whom this code was written. I can certainly craft Lisp code which is a nightmare to read. I've seen many times Forth code that was not designed and written in the best style. "Readability" is a relationship between the reader and the writer, it's something that becomes clear when you do code reviews. I think people would generally agree that C++ is "more readable" than both Forth and Lisp, yet if you use lesser-known C++ features - or just omit parens around expressions because you assume that the priorities are obvious - you can easily lose intermediate level reviewers.
Anyway, after reading many online threads about "readability", I came to the conclusion that it is a non-argument, and that discussions about it are most often pointless. But I wanted to use that to show how Forth solves this apparently huge problem, and introduce a bit of its philosophy.
This is really just a hand-wave. You are saying "maybe there's some difficult to read lisp code out there, so lisp might not always be easier", whereas I am talking about objective measures. That is the exact same program translated between the two representations. This can be accomplished by taking the lisp code, reversing it, and removing the brackets. Note the opposite direction is much harder because information is lost. The lisp source code encodes more information, and what is added is highly relevant to the process of reading it. When, as in Forth, this information is not given, it must be computed which is more mentally taxing hence making Forth code harder to read.
> Define harder
The human mind is a computer. Operations on this computer require energy, as much has been verified scientifically. Reading a program can be seen as an operation in this computer, as I have previously defined. Reading a Forth program requires a greater use of working memory to store items of the stack, and hence is more difficult as this is an extremely scarce resource. Using more working memory also implies an increased number of operations, so a higher time complexity as well as space. Forth code also requires more accesses to long term memory for arities. The human mind is not nearly as subjective as you take it to be, many aspects of it have been measured and observed. In the long term, pattern recognition kicks in and the problem begins to lessen but this is analogous to function memoisation. That a function can be memoised does not prove it is easy to compute, just that after putting enough work in you don't have to do the work again.
> how Forth solves this apparently huge problem
It partially solves the problem by writing expressions in a format closer to lisp. To fully solve the problem, you end up writing lisp.
Lisp isn't that easy when you don't have supporting tools, mainly a coding editor that auto-indents, re-indents, and shows matching parenthesis. I think you're being a bit over-optimistic there.
Forth, OTOH, has been used with dumb terminals over serial lines. Old Forth systems even often featured an integrated code editor for this purpose, on systems with very limited memory. This was possible because Forth doesn't need a complex editor to be comfortable... When you don't neglect factoring, naming, etc.
> The human mind is a computer
Right. Can your human mind compute 358729358 x 5648759845 in less than 10 ns ? False premise, invalid conclusion.
Anyway, you're so right, you're so right. Have a nice day with Lisp.
So "the human mind is a computer" is a false premise, but "a computer must be able to compute 358729358 x 5648759845 in less than 10 ns" isn't? Do you know what a computer is? The human mind has a very different architecture than the Turing machines you are used to, so its performance characteristics are also different.
> invalid conclusion
My conclusion doesn't require the premise that the human mind is a computer. That is just an analogy to help you to understand my actual argument, which is as follows: there are certain things that happen in the brain which take time and energy (scientifically proven), reading Forth requires you to do more of those things than reading lisp (trivially true). Therefore it is harder, if hardness is a metric of how much effort (time and engery) something takes.
> mainly a coding editor that auto-indents, re-indents, and shows matching parenthesis. I think you're being a bit over-optimistic there.
Even Nano does this. Far from being optimistic, I struggle to think of a situation where you wouldn't have this. Unless your computer is hooked up to a teletype printer, you will have these features. People have edited lisp code on deep space missions and had these features. How? Because you can write the forms in an editor and then send them over the wire afterwards. This is a technical problem that was solved before it even existed, and it is just a sad coincidence that many people decide to edit and run code through a dumb terminal connected to a REPL instead of in an actual editor connected to that same REPL session.
> Forth doesn't need a complex editor to be comfortable
Neither does lisp. Matching brackets and auto-indenting lisp code is so simple its braindead. It would be the simplest feature of any editor that supports it. Quite frankly, this is a stupid argument anyway. Even if text editors as "advanced" and "complex" as GNU Nano were a total rarity, I would rather code in a language that's easier for my editor installed on my computer than one which caters to someone else doing everything on an embedded device which only connects to a physical printer. That's like saying we should all use Fortran because it works much better on punch-cards.
But such an editor is possible for Lisp, without it having a deep understanding of Lisp at all.
For instance :set lisp mode is quite usable in classic Vi.
Whitespace, like indentation, is used in Forth programming. Do commonly available editors support this?
w1 w2 w3 w4 w5 w6 w7
Lisp:
(w7 (w4 (w3 w2)) (w6 w5 (w1)))
I discovered Forth a long time ago and thought, there's no way this language is viable, and yet it was used in prestigious projects. It made me curious so I tried it, dropped it, picked it again and tried harder. I was young and open minded. A couple decades later Forth is my go-to language.
I have no interest in convincing people with immutable opinions who cannot listen.
Nowadays we want our text editors to handle those conventions automatically, and be able to recover them even if we delete extra white space or line breaks.
I also discovered Forth 40 years ago. It looked viable to me. I recognized then that while it's interactive like BASIC, it's way faster. Also cleaner, because Forth functions are reentrant, usually not relying on global variables.
Thank you, that's part of what I was saying.
> Nowadays we want our text editors to handle those conventions automatically
But you can't always have what you want. The other guy I was talking to apparently has no idea what it means to deal with an embedded system, hopefully you do.
> I also discovered Forth 40 years ago
And did you write Forth during these 40 decades? I'm apparently a bit younger than you but I did picked and dropped Forth a couple of times for other "nicer" interpreted languages. All in all I think I have a solid 2 decades of practice in Forth. During this time I have constantly changed my idioms, so it's not just doing the same thing for decades and getting used to it.
And I'm saying that readability became less and less of an issue as your writing skills improve. That's also something the other guy refuses to understand.
The arity issue that is often pointed out is not a bigger deal than stumbling on some unknown Javascript, Lua, Lisp or whatever function call and figuring out what each parameter does, especially when it's just a boolean (a bad practice, yet a common practice). I have programs that are made of hundreds of Forth definitions. Arity and expression structure are sometimes an issue, true. When it happens, I just use the search function of my editor.
But why do you specifically forbid yourself to mfk*g split your editor window and go look to the definition of a function when it's Forth, when you do that every day in any other language?
The tide is flowing the other way now. Kids are using editors that integrate deeply with compilers (via Microsoft's Language Server Protocol). The editors are providing code formatting and completion based on communicating with a compiler. That seems like it could work with Forth.
I would love to see you justify this. Sadly you will not, because I understand it quite well. It's a pretty basic principal that if a system is capable of handling user input interactively, you can instead connect a more powerful computer and have it receive input from that device. Hence all devices with REPLs can benefit from editors hosted on my own computer. In an embedded system, it is much more likely for you to have to hook your own computer up to something than it is for that thing to be able to accept user input independently. Most embedded devices do not have a USB slot for you to plug your keyboard in.
> That's also something the other guy refuses to understand.
It is a point which I addressed in my other post.
This manner of response is stupid and infantile. I hope you can talk to me directly next time.
I made it pretty clear I didn't wish to continue that conversation, so I wasn't responding to you. There will probably be no next time, as there's a clear gap in practical experience - on that particular topic - between you and me; it would take far too much energy for me to explain things step by step and I'd gain nothing from it.
Then why did you continue the conversation? I'm not forcing you to make snide jabs at me in a public space, and you can hardly blame me for responding to them.
> it would take far too much energy for me to explain things step by step and I'd gain nothing from it
If you cannot explain it simply, you don't understand it well enough.
Ok, sorry. That was a poor way to invite that person to read the parallel thread. It's a bit frustrating to deal with claims based on nothing but theory when I have at least two decades of practical experience on these topics.
> If you cannot explain it simply, you don't understand it well enough.
First, that answers something I didn't write (of course I can explain those things simply, the problem is that it would easily make a whole article) and secondly, what you wrote ignore the fact that teaching is a skill, so not all experts are good teachers.
-- f: returns the second argument minus the first
f :: Int -> Int -> Int
f x y = y - x
f = flip (-)
Reminds me of https://pygmy.utoh.org/3ins4th.html except the third instruction is execute rather than quote.
In the spirit of building from scratch, I'd like to highlight sectorforth/milliforth (https://github.com/fuzzballcat/milliForth/blob/master/sector...) - they implement as little as possible to get a working system ie. just the basic fetch/store ops, numerical and I/O.
The parser can probably be reduced - there's a nice paper detailing Cognition (a forth dialect, but the parsing could be broken out into a lib - https://ret2pop.nullring.xyz/blog/cognition.html) where using a couple of crank operators, you can implement custom syntax in a forth-style way (as opposed to say PEGs).
In terms of variables and scoping, Dreams (another forth dialect- http://elilabs.com/~rj/dreams/dreams-rep.html) uses mianly dynamic scoping, and builds it's structs (C-style structs) using the standard forth struct words. This allows it to be hard-realtime though as you don't need to walk the lexical tree to bind variables. You can also early bind like with CBPV. I guess this is also similar to REBOL's BINDology (https://github.com/r3n/rebol-wiki/wiki/Bindology)
Lots of overlap here with these things. Just for completeness there's also dynamic variable handling (over lexically scoped structures) with wat (https://github.com/GiacomoCau/wat-js/tree/master) though this is not realtime.
Is it possible to make the closures dynamically scoped by default here? I've not had time to think about this properly. I like the fact that eval is lazy here like in forth or REBOL, rather than eager as in lisp - the idea of passing around blocks/thunks appeals wrt realtime (well with dynamic scoping) and parallelism.
The env per-thread I guess could be compared to the forth dictionary? Dreams abstracts this by virtue of it's (token) threading model which appears useful for task switching, objects and the like.
I'd also like to highlight able forth which has: Compiler-only design (like Freeforth) - Word-classes (like Retro) - A straightforward bootstrap process using a minimal set of seed words (like seedForth) - No (ZERO) special forms, not even integers, and a consistent model for adding literals without the complexity of i.e. recognises - A single flat word-list that can be freely manipulated and composed of other word-lists - No separate [assembly] code words - Explicit optimizations (ONLY) i.e. explicit tail-call elimination
I've only started looking into able forth so can't really comment on it much, but the no-special-forms appeals here.
Sorry, random thoughts here, I'd like to discuss further when I've had time to digest your language. :)
Shame. Missed a golden opportunity to call it "Lithp" :)
Does this have potential to grow, or would most people just say 'use lisp'.
Is there any feeling that this has legs?