Hacker News new | past | comments | ask | show | jobs | submit login
To Grok a Mockingbird (raganwald.com)
77 points by Sindisil on Sept 4, 2018 | hide | past | favorite | 10 comments

If you like this you should read "Recursion Theory and Joy" http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html

I've no wish to be provocative (today) but I have to mention that a comparison of the JavaScript code to the Joy code might be worth your while.

(Joy is an extraordinary language, and trivial to implement in almost every other language.)

Also, a crude joke: "Yeah, the Y combinator is great, but have you tried the X combinator?"

(Seriously thou, the x combinator must be one of the most beautiful conceptual artifacts ever discovered. IMHO)

From the link above:

> Possibly one of the most satisfying introductions to combinatory logic is to be found in the remarkable little book {Smullyan90} To Mock a Mockingbird in which he manages to combine humour and rigour.

I second this, Smullyan is dreamy.

Author here. I imagine that anyone with an even passing familiarity with the legendary “To Mock a Mockingbird” will recognize the inspiration for the title of this essay.

I second the recommendation to look into Joy. I wrote about combinators and concatenative languages a while ago, in “Finding Joy in Combinators:”


Factor is another concatenative language worth a look.

Oh hey! You're all over it. Excellent.

Well, I’d say that I’m a typical hobbyist. I find something, plsy with it, share my enthusiasm, and so on, but I rarely go really deep.

So comments like yours are excellent because:

1. They mention things that I might know, but didn’t mention in this post, which points other readers in new directions, and; 2. They go deeper than I’ve gone, so even if I know the general thing, I still learn something.

So... thank you.


Do you have any good resources on implementing Joy?

Funny you should ask...

There's the zip file of stuff available from La Trobe University here: https://www.latrobe.edu.au/humanities/research/research-proj...

Direct link: https://www.latrobe.edu.au/__data/assets/file/0007/240298/Jo...

And Kevin Albrecht's mirror of the original site: http://www.kevinalbrecht.com/code/joy-mirror/index.html

But allow me to mention my own implementation of Joy in Python: http://joypy.osdn.io/

(FWIW the core of this code could be converted to e.g. JavaScript trivially. Also, most of the simpler library functions are already automatically generated from their stack effects. Getting versions of those in other languages would be a matter of writing a new format string.)


I worked all summer on it, and had just finished type inference (http://joypy.osdn.io/notebooks/Types.html) and was in the middle of the compiler (Joy-to-Python) when a paper by David Warren went by here on HN about writing compilers in Prolog. I wrote a Joy interpreter in Prolog (three lines long) and then I wrote the type inferencer in Prolog (also three lines long) and I realized they were the same code.


I freakin lightbulb went off in my head and then after a day or two I realized that I also already had a compiler! (Joy-to-Prolog) See the tiny "Compiler" section at the bottom of thun.pl? The relation jcmpl(Name, Expression, Rule) generates new (Prolog) rules from Joy expressions. In other words, it's a compiler. It's not finished: loops/recursion aren't reified yet. But branches work, generating two rules for each "ifte" combinator.

It turns out, if you are writing software and NOT using Prolog, you are almost certainly working far FAR too hard. Note that there is now a very serviceable imperative/functional interpreter embedded in Prolog (namely Joy), and that existing research describes how to make compilers (to machine code, not Prolog) so I am envisioning a new working environment that consists of Prolog and Joy with automatic compilation to correct machine code.

I have been finding things like: a paper that shows how to generate code generators from a machine description; a paper that shows that if you write your type definitions in Prolog you get a type checker and inferencer for free (which is kind of what happened with Joy.) a whole batch of research on provably-correct code generation and compiling with Prolog.

So, to wrap up, use Prolog. If you encounter a problem that doesn't fit Prolog well (and those are more rare than you might think) use Joy. If you need greater efficiency, compile. I'm pretty sure that the above formula will prove optimal (except for that one dude writing a compiler-to-GPUs in K, but he's ultra-far-future tech) if I can package it up and "sell" it.

(I can't shut up! Prolog and Joy are both ridiculously simple languages. Joy may be the most simple useful language.[1] Certainly it combines the best parts of Forth and Lisp.)

[1] Kerby shows a minimal base {cake, k} (http://tunes.org/~iepos/joy.html#cakek) which, combined with the void() function from Laws of Form (http://joypy.osdn.io/library.html#joy.library.void http://joypy.osdn.io/notebooks/Correcet_Programming.html#The...), gives a Turing Complete system in three functions, I think, the only values being structures of quotes.

I don't know about resources, but I've been working on a JS interpreter/stepper for it: https://defseg.io/joyjs/

It isn't done yet (see https://defseg.io/joyjs/test/all.html), but most of the recursive combinators are there.

Follow-up (under construction): “Deriving the Y Combinator and Sage Bird from the Mockingbird”


FYI, your use of JS's `Map` class is wrong: `(new Map())['entries']` isn't undefined. The `get(k)`/`set(k, v)` methods should be used in this case.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact