WingNews logo WingNews
top | item 44196589

Show HN: Lambduck, a Functional Programming Brainfuck

70 points| jorkingit | 9 months ago |imjakingit.github.io

What if Brainfuck was less like C and more like Scheme?

The interpreter implemetation is pretty bad. It's not very fast, it's not very good, and it's probably not very correct. But maybe there's some vaguely interesting programs you could write with it!

For example, the Y combinator:

  λf. (λx. f (x x)) (λx. f (x x))
is written as:

  \` \`1 `0 0 \`1 `0 0

27 comments

order

tromp|9 months ago

How is a program like

    ``f`,\0`,\0
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/

jorkingit|8 months ago

I saw this the other day! I salute you, it's so much more evil :-)

And yup, the order of evaluation is leftmost innermost.

  ``\\0`,.`,.
with stdin "hi" will print "hi".

mmoskal|9 months ago

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!

jorkingit|9 months ago

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 ;-)

catlifeonmars|8 months ago

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?

90s_dev|9 months ago

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.

jorkingit|9 months ago

Hello world should be:

  ``\\1`.'h``\\1`.'e``\\1`.'l``\\1`.'l``\\1`.'o``\\1`.' ``\\1`.'w``\\1`.'o``\\1`.'r``\\1`.'l``\\1`.'d`.'!

somat|8 months ago

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/

jorkingit|8 months ago

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!

stronglikedan|8 months ago

> 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.

reuben364|8 months ago

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.

jorkingit|8 months ago

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 ;-)

naikrovek|8 months ago

I’m too stupid to even recognize how esoteric this is.

reverendsteveii|8 months ago

from the least cute name for a programming language instantly to the most cute name for a programming language. Let's go LambDuck!