Kitten – A statically typed, stack-based functional programming language | Hacker News Reader

Kitten – A statically typed, stack-based functional programming language

kittenlang.org

150 pointsthrowaway764549 comments

Author of Kitten here, happy to answer any questions.

The site is pretty far out of date—it describes an older version of the language/compiler, so it’s better to check out the GitHub repo[1]. I figure I’ll send a pre-release announcement to all the stargazers, when the time is right.

One of my new year’s resolutions is to work on Kitten every week this year, and release it before the end of the year. I’m also working on a short ebook (“Programming with Kitten”) to serve as the standard tutorial.

I could really use help with all this—building and marketing a language is no small task. If you’re interested in contributing, even if you’re not familiar with Haskell or compilers, I’d be glad to help you get involved. :)

[1]: https://github.com/evincarofautumn/kitten

> I figure I’ll send a pre-release announcement to all the stargazers, when the time is right.

Completely tangential: how do you send a message to all stargazers?

Using the GitHub API, you can get the list of stargazers for a repo, then get the public email (if any) from each of their profiles.

If the number of stargazers was relatively low, you could @mention everyone in an issue.

> I’ll send a pre-release announcement to all the stargazers

please don't, IMHO that is too spammy.

(But it is a good point, why does Github have no "get notified of releases" level of watching?)

I know it’s not ideal, but I can’t think of a better way to directly reach people that have expressed interest. Nim did the same thing, and I’m happy to get the occasional direct update from them. Obviously I’d have to include an “unsubscribe” link or whatever.

Thanks for jumping on this (I submitted it after reading it on Reddit awhile back). I like the concept of Forth, but getting started is daunting and JonesForth just isn't enough. Kitten does seem pretty neat for sure and it probably wouldn't be too hard to get into like Haskell and Forth are. I'd love to use a lightweight stack/functional/imperative language if it compiles to native code and is fairly fast. Would it be possible to build someone an .exe or binary and have them run it without any runtime?

Thanks! Codegen isn’t done in the new compiler, but yes, the goal is to compile to native, statically linked executables, much like Go does. Ideally we wouldn’t even incur a libc dependency, but malloc is just so damn convenient.

You might also give Gforth a try. https://www.gnu.org/software/gforth/

Good to know. I think a small dependency is fine. There are precious few languages that allow a static binary. I wonder what the size would be though. HelloWorld in Nim is ~10 MB, although there may be an optimization setting I skipped. GForth can't make standalone executables though and doesn't have good beginner information either. I'm also under the impression that Forth shines best as a special purpose implementation for that particular project (how Chuck Moore does it). Not sure if Kitten works better as a general purpose language or not yet, but i like the concepts so far.

> HelloWorld in Nim is ~10 MB

That sounds like a gross exaggeration: https://hookrace.net/blog/nim-binary-size/

I downloaded Nim last year, wrote the line: echo "Hello World" , and then used the Aporia IDE's feature to compile to executable I believe. That or the command-line method. This was on Windows and the resulting exeutable was indeed sized around 10 MB. I did state that there could have been more optimizations like a release mode flag.

Edit:

The sizes in the link you submitted are very small and rational (what I was expecting to see). I can't remember what it does on Windows without GCC. It might have used Cygwin, but it should have still not been orders of magnitude bigger. This turned me off immediately.

The reason you saw that is because the default compilation includes lots of debug info.

9.95 MB worth? Dang that is a lot of info. Glad to see they can be made to be really small.

You could do what the Spitbol compiler (for the SNOBOL language) does, which is to statically link against musl libc.

Great project! I've been thinking a lot about concatenive languages lately. I haven't had the time to run it or look at the compiler code, I'll do it tomorrow.

I'm curious about how it compares to Joy, is it also homoiconic?

I'm also curious about how you implement the ffi to C.

I might try to contribute :)

I wouldn’t call it homoiconic, but I’m working on a macro system which will let you manipulate terms as regular data structures at compile time. That was an early insight about Kitten—things are much easier to statically type if you differentiate data from code, and you can recover a lot of the flexibility with other approaches to metaprogramming.

In the old compiler, there was no FFI. In the new compiler, codegen isn’t done yet, but the Kitten ABI on x86-64 is similar enough to the System V ABI that you can just save some registers and do a regular call. As for the front-end, it’s been a long-standing goal to allow a programmer to just import C headers, rather than write or generate a bunch of tedious FFI declarations; I have a prototype implementation of this.

If you’re interested, shoot me an email (username@gmail) and we can find something for you to work on. There are many different things to do: adding features, improving error messages, polishing the interactive environment, writing tests and documentation, integrating with editors, you name it.

For the new compiler, are you sticking with using C as an intermediate language? It seems like not, but if you're planning to support importing C headers...

If not, and you're emitting x64 object code, will you support the stack frame pointer (needed for DTrace and similar tools)? Will the ABI be similar enough that I could use a debugger on a core file (I'm assuming the absence of DWARF)?

And what are your plans with hardware threads?

I’m probably not writing another C backend. There is a convenient C parsing library for Haskell (language-c) that should let the compiler get all the information it needs from headers.

It will support frame pointers, but they might be a bit less useful than when debugging C, because Kitten guarantees tail-call optimisation. The ABI is fairly similar (not fully worked out yet), just a couple of register differences to separate the data stack from the call stack.

I’m still working out Kitten’s story for concurrency and parallelism. You’ll be able to easily spin up an OS thread if you want one, but I expect most code to use other approaches, like a green-thread library.

Heh. Will you eventually ditch Haskell and go self-hosting?

In any case, I'm happy to hear Kitten will be usable with DTrace and gdb/lldb, even with some caveats! Too few languages nowadays support dynamic analysis or post-mortem, which dramatically reduce their usefulness for industry. :)

Yes, in fact I’ve tried to write the compiler in a style that should make it easier to port from Haskell to Kitten someday. But in my opinion it doesn’t make sense to bootstrap pre-1.0.

I agree that binary debugging support is a must. I’m trying generally to make the language a “good citizen” when it comes to interop—we’ll see how it turns out. :P

>If you’re interested in contributing, even if you’re not familiar with Haskell or compilers, I’d be glad to help you get involved. :)

I remember reading somewhere that Haskell is particularly suited for building compilers. I use Elm at work which is another wonderful language written in Haskell. Has that been your experience ? curious what makes is so great. Any recommendations on resources to learn compiler building in haskell ?

Yeah, I’ve found Haskell a pleasure to work with for writing compilers. There’s no single thing, just a combination of language features and libraries. The bulk of a compiler is transforming trees of stuff, which Haskell makes very easy, and it nudges you pretty strongly in the direction of making code testable and refactorable.

I don’t have any particular recommendations. Mostly I’ve just been figuring things out as I go along, reading papers and asking for help. I’d written compilers & interpreters before, but got into using Haskell for it with Write Yourself a Scheme[1]. I’ve also heard good things about Implementing a JIT Compiled Language with Haskell and LLVM[2].

[1]: https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_...

[2]: http://www.stephendiehl.com/llvm/

Y'all might find it interesting that the first attempt at a Perl6 implementation was done in Haskell and was considered vitally important.

Pugs was, by my count, the third or fourth attempt. I can think of at least two in the Parrot repository long before Pugs was a thing, and I believe one of those had a fork/rewrite before 2005.

Lol thanks Chromatic. Always good to get corrected by someone who was there and actually knows. Thanks for your work!

Factor was a big name in 'modern stack-based languages,' but of course it's pretty dynamic. I gave Factor a couple of dives a few years ago (after walking through jonesforth prior) and it felt surprisingly complete/mature (except for lack of package manager, of course).

Given its novelty, I think it'd be lovely if Kitten took a page from some other languages and had a "QuickStart" or "Crash Course" that consisted of side-by-side examples comparing Kitten to Forth or Factor, or even some other more common language like Javascript. (Ie, elixir-lang does this comparison with Erlang on its website, and it can be helpful).

Factor has been a good source of inspiration when designing Kitten, and I would recommend it to people who want to try a concatenative language now. Kitten is not usable for real-world stuff yet—but it’s getting close, and eventually it should be a good alternative to Factor for those of us in the static-types camp.

I’m working on an updated tutorial, and I’ll definitely include some comparisons to other languages that people are likely to know, say JavaScript and C. But I still need to find the right balance between illustrative comparisons and standalone descriptions.

I like the concept of Factor and talked to the author awhile back who isn't actively involved anymore. My problem comes from the confusing doc and lack of beginner materials. Just because I can write a simple app in an imperative or OO context doesn't mean I can write functional nevermind efficient concatenative code without help.

I do hang out with Slava occasionally, and he’s been helpful even if he’s not that into concatenative programming anymore. For better or worse, the current Factor maintainers are focused more on language internals than onboarding new users. Concatenative/compositional programming does require a different way of thinking, which I think is easy to learn but hard to teach.

Understood. Is concatenative programming not especially good for what he is currently interested in?

Last I heard, Slava was working on the Linux kernel at Google.

He’s working on the Swift compiler at Apple these days.

That's pretty prestigious.

Kitten seems like a cool project. If I find some free time I might try to contribute something.

Somewhat relatedly, I've been fantasizing about a mobile friendly editor for source code, and it's struck me that concatenative languages can be nicely edited by moving tokens around, which should be quite doable on a smartphone.

Static typing would make it even better, since the editor could show type errors, predict input, and so on.

That is one of the goals of the project—the simple language structure and static types should let you do some interesting things with program visualisation and editing. Email me (username@gmail) if you’d like to chat about it—maybe we could build something cool together. :)

Really strange question about your username, but you're not a EE are you?

- What other programming-languages inspired this one?

- What market is this language addressing? (ie. where should I "be using it"?)

- What is the bus-factor?

- How difficult is/was it to write/design your own programming language?

Kitten is inspired mainly by:

• Systems languages (C, C++)

• Functional languages (Haskell, OCaml)

• Concatenative languages (Cat, Factor, Joy, Forth)

As a functional language without GC, it’s intended for mid-level applications where you might ordinarily reach for C++, but it remains to be seen how people might actually use it. It might be useful as a lightweight scripting language, or for writing low-level embedded code that feels high-level.

The bus factor is currently very bad—people have contributed here and there over the years, but I’m pretty much the only core developer.

Building a language is as hard as you make it, basically. You can make a pretty good toy language in a weekend, or you can go all-in and try to create something innovative, elegant, versatile, stable, usable, and performant. That takes years, and it’s a process of discovery with many false starts.

I'm glad to see a successor for the defunct cat. I love the precision and concision you can achieve with this style of programming.

Cat was a big inspiration in Michelson, another concatenative, statically typed, functional programming language that we designed to run smart contract in Tezos.

http://www.tezos.com/language.txt

I hadn’t heard of it—that’s very interesting, thanks. :)

It would be nice to use GADTs for Kitten’s AST, but last time I tried, it made inference complicated, and I never figured out a good way to encode Kitten’s permission system in Haskell types. Even just annotating Kitten types with their kinds (in the old compiler) was too cumbersome.

Parentheses, tuples, for loops... my first impression is it doesn't look very concatenative.

The Levenshtein example isn’t the best. It’s also using an older version of the language with things like mixfix operators (“from()to(){}”) which have since been removed.

Anyway, Kitten is concatenative at the term level (all terms denote functions, juxtaposition is composition) but not the token level as in Forth (e.g., “{” and “}” are not meaningful words on their own).

Interesting, I am curious as to why you are concatenative at the term level only. Is it trying to make syntax more palatable to ALGOL family programmers?

PS: I loved your "why concatenative programming matters" article

Yes, that’s basically it. Most programmers are unfamiliar with the paradigm, so I figured I should keep the syntax as familiar as possible to get people in the door. But it’s mostly syntactic sugar for regular stack machine code, with a mildly fancy type system on top.

http://evincarofautumn.blogspot.co.uk/2012/02/why-concatenat...

Sorry but I have to be negative here because I love Forth.

People tried to make Lisp/Scheme less 'prefix', and it didn't fly. People tried to make Forth less 'postfix', and it didn't fly.

The whole point of concatenative languages is the simple syntax and implementation.

I wrote a Forth dialect in C - actually I wrote many over the years because it's a refinement and adaptation process, but I'll talk about the one I'm currently using. Its core is a little less than 2K SLOC that compile into a ~30Kb (yes, kilobytes) (~60Kb for Windows 32bits) . It uses a very straightforward direct threaded scheme - something like (ip++)() - but that's plenty fast already (think Lua-fast).

It's easy to modify because, well, I wrote it from top to bottom. At some point I wish I had separators for number and binary numbers. In an hour or so I could write things like 0b1010_1001. At one point I was tired to write "test.4" load*. I hacked the interpreter so that when it sees a word that ends with ".4" it tries to load the file with that name. Very handy. At some point I wish I could embed my interpreter into a large embedded application to help with debugging. No problem either.

It's easy to extend. Need more accurate time stamps? Here you go:

    static void p_getms(void)
    {
	struct timeval t;
	gettimeofday(&t, NULL);
	push(t.tv_usec/1000);
	push(t.tv_sec);
    }

And then you add the function in an array to "register" it, like you do in Lua.

I can write bindings to libraries almost on-the-fly thanks to the braindead API which consists mainly in push() and pop(). No FFI required. It's also trivial to translate a piece of code from Forth to C when you need speed. I think it could even be automated.

THIS is what Forth is really about. I don't see the point of having people "think concatenative" if they don't have all this in return.

You want static typing? I can understand, because Forth is quite unforgiving and will segfault if you make a mistake and that can be annoying. Actually, when I started to write the interpreter I'm currently using, my plan was to write some kind of "linter" to help with that. However as an embedded systems programmer I'm pretty used to printf() debugging (it might be a bad habit) and Forth is pretty good at that because you can invoke a REPL very easily. So I have yet to find the motivation to write that Linter.

Clojure syntax looks like a cross between common lisp and javascript, but it manages to be the most popular lisp around by a country mile. On the one hand I find it distasteful, on the other hand it hasn't seemed to hurt adoption. I don't know if it drove adoption though - it's probably more likely due to the fact the inventor of the language is a charismatic and prolific speaker. But I digress...

I kind of agree with you. I don't think "softening" the syntax of a concatenative languages is going to help much, and is more likely to drive away the kind of PL dabblers who are interested in concatenative languages in the first place. The vast majority of programmers will never try anything that doesn't resemble ALGOL at least a bit. It's a lost cause to try and reel them in.

IMO, the best way for nice languages to thrive is to be simple enough that it's easy for a small number of people to maintain, and powerful enough that the implementation and standard library can be constructed in as few LOC as possible to minimize bugs. Being able to attach itself to an existing large ecosystem with a minimum of fuss (ie, embedable in C or Java interop) also seems to be a great trojan horse.

> The whole point of concatenative languages is the simple syntax and implementation.

That’s a major part of it, and certainly the selling point of Forth—you can build, understand, and extend everything yourself, from the ground up.

But the reason I came to concatenative languages in the first place was that I saw the power of a compositional style of programming in Haskell, and I wanted to bring that high-level thinking over to a lower-level language with a simpler performance model than laziness+GC.

Remember also that the Forth family and the Joy family are a case of convergent evolution: Manfred Von Thun chose postfix syntax and a stack-machine implementation for Joy because it was a natural way to reason compositionally about programs. The Forth similarity was discovered soon after, and certainly had an influence on the design. But Joy wasn’t really a Forth, and neither are its descendants: Factor is more of a postfix Lisp, Kitten a postfix ML.

The REPL stack for doing calculations looks interesting (you can find it in the tutorial link: http://kittenlang.org/tutorial/). I'll have to try it out though to see how well I like it.

Reply on news.ycombinator.com