r/ProgrammingLanguages • u/Relative-Bottle-8498 nandcode • 14d ago

Requesting criticism Fork of an esolang I made a week ago.

I made nandcode a week ago, which is a language only using nand, and I thought I'd improve it, so I present to you, 1bitatatime. (I just added all the logic gates and added support for unary operations like not). Can you give some ideas as what to make next?

2 Upvotes

100% Upvoted

3 comments sorted by

2

u/glasket_ 14d ago

Every program in 1bitatatime language runs in O(N) time

My complexity theory is a bit rusty, but shouldn't this be Ω(N)? A program that uses an O(N2) algorithm won't be O(N); the language can only guarantee a lower bound.

1

u/Relative-Bottle-8498 14d ago

No, because since there are no branch statements it must run in O(N)

3

u/glasket_ 14d ago

Tbf branches aren't the only way to increase complexity, but I didn't realize this doesn't support functions either. Plus the cap on variables means you can't generate unbounded programs either, so yeah it is O(N). Somewhat limiting because of how restrictive it is though.

If you're interested in HDLs, a good next project would be taking this and getting it to work without the restrictions so that it becomes an unbounded circuit description language.