So here’s my question: is the interpreter more or less compact than a brainfuck interpreter? Which interpreter would have a lower Kolmogorov complexity, or could they be equivalent?
Thanks! I'm torn on having the character literals actually; they're definitely syntactical sugar, but I was struggling to write programs that printed anything without them getting super unwieldy! If someone smarter than me can write a compact-looking enough Hello World program then consider them gone ;-)
Yeah there's something wrong with the idea of brainfuck having character literals. The de bruijn indexing is definitely on point but the lack of continuations feels wrong to me given the stated goal.
Also shouldn't the indexes be expressed as a repeated character? Like "---" would be index 3. Integer literals are decidedly non-brainfuck as well.
getchar does take a continuation of sorts (as in continuation passing) which is passed the input. In one my initial drafts, getchar was a special form that would accept input at the point of evaluation, which was really funny and unpredictable.
putchar I feel kind of weird about, it acting as an identity function with a side effect is kind of weird; I'm not sure changing it to take a second argument as a continuation would make it better or worse.
Regarding the de Bruijn indices, I don't think there's a huge distinction between writing 3 vs writing ---: it would still form a single lexical token, so I feel like --- is just more noise.
Perhaps a de Bruijn index register you could move around and dereference? e.g. from index 1, index 3 is >>*, then index 2 from there is <*. But that feels less functional, because you're now imperatively manipulating some hidden state.
Entirely agreed that it's nothing but more noise, but isn't that exactly how BF is? Why ----- instead of 5-? Well, because BF of course. The point of the exercise (IMO) is having the bare minimum in parsed characters to achieve the turing tarpit.
I quite like the movable register idea but as you say that's no longer a "BF except lambda calculus" it's some other esolang at that point.
I think my objection about the lack of continuations was misplaced given that appears to be a BF take on the lambda calculus rather than a BF take on scheme.
Maybe my brain just isn't functioning right now but I don't think writing in CPS is the same as having access to first class continuations? But as previously noted I think that was a misplaced request on my part to begin with.
My line of thought had been that doing so doesn't restore execution context. But it dawns on me that without the ability to mutate variables that doesn't have the same relevance.
Still, doesn't it throw the de bruijn indexes off? Or am I wrong about that as well?
but bf is nothing like c, bf is a stack language, I would say it's closest real language analog is forth.
Anyhow, This is far too clear and straightforward, the bf analog to scheme would probably be unlambda, an implementation of the lambda calculus without lambda forms.
I did take some inspiration from Unlambda: the prefix application syntax is cool! I/O in Unlambda is super weird though! You get a read character instruction that puts it into a character register where the only thing you can do is compare it or print it out again; I don't think you can actually do any arithmetic on it.
I'm not sure if I would characterize Brainfuck as a stack language, but I suppose if you considered all the operators to be unary stack operations I could see it!
I feel like adding a bit more brainfuckery would help obscure stuff. Make people use Church numerals to form ASCII characters - it'll encourage golfing it down to something equally as obtuse as
How is a program like
where f is applied to two arguments, each of which is the next input byte as a Church numeral, evaluated? Does it depend on order of evaluation?Note that it's also possible to do I/O without additional primitives, as demonstrated in [1].
[1] https://www.ioccc.org/2012/tromp/
I saw this the other day! I salute you, it's so much more evil :-)
And yup, the order of evaluation is leftmost innermost.
with stdin "hi" will print "hi".This seems way too readable! I think you should remove the character literals in the name of purity.
Also, this is likely way more compact than Brainfuck, as the lambda calculus is written essentially as usual.
And seriously, very cool!
So here’s my question: is the interpreter more or less compact than a brainfuck interpreter? Which interpreter would have a lower Kolmogorov complexity, or could they be equivalent?
Thanks! I'm torn on having the character literals actually; they're definitely syntactical sugar, but I was struggling to write programs that printed anything without them getting super unwieldy! If someone smarter than me can write a compact-looking enough Hello World program then consider them gone ;-)
Yeah there's something wrong with the idea of brainfuck having character literals. The de bruijn indexing is definitely on point but the lack of continuations feels wrong to me given the stated goal.
Also shouldn't the indexes be expressed as a repeated character? Like "---" would be index 3. Integer literals are decidedly non-brainfuck as well.
getchar does take a continuation of sorts (as in continuation passing) which is passed the input. In one my initial drafts, getchar was a special form that would accept input at the point of evaluation, which was really funny and unpredictable.
putchar I feel kind of weird about, it acting as an identity function with a side effect is kind of weird; I'm not sure changing it to take a second argument as a continuation would make it better or worse.
Regarding the de Bruijn indices, I don't think there's a huge distinction between writing 3 vs writing ---: it would still form a single lexical token, so I feel like --- is just more noise.
Perhaps a de Bruijn index register you could move around and dereference? e.g. from index 1, index 3 is >>*, then index 2 from there is <*. But that feels less functional, because you're now imperatively manipulating some hidden state.
Entirely agreed that it's nothing but more noise, but isn't that exactly how BF is? Why ----- instead of 5-? Well, because BF of course. The point of the exercise (IMO) is having the bare minimum in parsed characters to achieve the turing tarpit.
I quite like the movable register idea but as you say that's no longer a "BF except lambda calculus" it's some other esolang at that point.
I think my objection about the lack of continuations was misplaced given that appears to be a BF take on the lambda calculus rather than a BF take on scheme.
You can always write it in continuation-passing style if you really want continuations! It's not pleasant but none of this is supposed to be ;-)
Agreed on having too many characters though, I don't like that having numerical indices makes the syntax whitespace-sensitive, too.
And once I figure out how to write hello world, those character literals are gone!
Maybe my brain just isn't functioning right now but I don't think writing in CPS is the same as having access to first class continuations? But as previously noted I think that was a misplaced request on my part to begin with.
It should be! e.g. if every function takes a continuation as its final argument, then:
Then in f you can invoke the continuation k as many times as you want, but that does involve a whole program transformation to CPS.My line of thought had been that doing so doesn't restore execution context. But it dawns on me that without the ability to mutate variables that doesn't have the same relevance.
Still, doesn't it throw the de bruijn indexes off? Or am I wrong about that as well?
Lambda calculus makes my head hurt.
but bf is nothing like c, bf is a stack language, I would say it's closest real language analog is forth.
Anyhow, This is far too clear and straightforward, the bf analog to scheme would probably be unlambda, an implementation of the lambda calculus without lambda forms.
http://www.madore.org/~david/programs/unlambda/
I did take some inspiration from Unlambda: the prefix application syntax is cool! I/O in Unlambda is super weird though! You get a read character instruction that puts it into a character register where the only thing you can do is compare it or print it out again; I don't think you can actually do any arithmetic on it.
I'm not sure if I would characterize Brainfuck as a stack language, but I suppose if you considered all the operators to be unary stack operations I could see it!
> but bf is nothing like c, bf is a stack language, I would say it's closest real language analog is forth.
I could guess the age of the author based on this. Seems like history gets rolled up to generalizations after a while.
Shouldn't it be called "Fuckbrain" then?
Genius, great work and well done, though I might not be smart enough to do anything with it.
Please share the interpreter’s code, however bad you feel it is.
Also, definition of de Bruijn index for those of us without formal education: https://en.m.wikipedia.org/wiki/De_Bruijn_index
https://github.com/imjakingit/lambduck
Since the de Bruijn indices are limited (and presumably still Turing complete), I wonder how limited you can make them and still be Turing complete.
I suspect the answer is 3: SKI combinator calculus is Turing complete and you need 3 de Bruijn indices to define S.
Good call! I got rid of all numbers above 2, I can't count that high anyway ;-)
from the least cute name for a programming language instantly to the most cute name for a programming language. Let's go LambDuck!
This is far too clever for me to even begin to understand.
How do you get the hello world working?
I tried pasting ,--('\< into the code and if it walks like a lamb and quacks like a duck into the stdin field.
Hello world should be:
I feel like adding a bit more brainfuckery would help obscure stuff. Make people use Church numerals to form ASCII characters - it'll encourage golfing it down to something equally as obtuse as
I’m too stupid to even recognize how esoteric this is.
Do Malborge next