▲ 63 points
back
25 comments
At one point I was seriously fascinated by the lambda calculus and particularly the S and K combinators - two very simple functions that you can build any computation from:
http://en.wikipedia.org/wiki/SKI_combinator_calculus
More recently I found out about the U combinator which is a single combinator that can be used to define S & K:
http://en.wikipedia.org/wiki/Iota_and_Jot
Having a system that implemented recursion using the Y combinator in terms of S & K and have it actually compute stuff was rather amusing. I'd be fascinated to see what it would look like using just U.
It would look like a very (very!) long string of U's. :-)
You might enjoy this:
Actually, one of the many things I learned from doing a final year project for my CS degree on "benchmarking" different sets of combinators was how to write a garbage collector - I was doing this in '87/'88 on a Unix mini (HLH Orion) and memory was tight and my trees were comparatively huge!
Presumably a tree of U's.
Oh, right. Good point.
It's worth noting, BTW, in case anyone is still following this thread, that what is going on here in all of these single-instruction languages is not particularly interesting. You're just encoding the program semantics in the arguments, or in the structure of the tree, or the length of the program, or something like that, rather than in the instructions.
Here's a single-instruction computer built out of the page translation behavior of X86 processors:
http://events.ccc.de/congress/2012/Fahrplan/events/5265.en.h...
If programming with just one instruction seems too low-level, I have just the solution for you! Now you can compile the user-friendly, high-level language of Brainfuck to this single-instruction machine!
http://gergo.erdi.hu/blog/2013-10-05-yo_dawg_i_heard_you_lik...
I wrote a little implementation of an OISC virtual machine many years ago [1]. Feel free to have a play. There are some sample 'one instruction assembler' programs in the test programs folder.
I'm curious, is there any real-world application for this? Or is it mostly interesting from a research perspective?
It seems like this wouldn't perform very well in the real world for most applications, but I could see it being useful for very simple architectures.
My final year project was a hardware implementation of this. My group made an 8 core coprocessor and an OpenCL-like implementation complete with an LLVM IR to SUBLEQ translator. We actually got performance better than the proprietary NIOS II e soft processor on our image processing demo (Y colorspace conversion).
Well it could be interesting as a test architecture for a new logic family as long as you have wide memory.
The Manchester Baby was the first programmable electronic computer and was close to a single instruction computer. It can emulate the single instruction computer with 5 of its 7 instructions: load, subtract, store, skip if negative and jump. The two extra instructions were halt and relative jump.
http://en.wikipedia.org/wiki/Manchester_Small-Scale_Experime...
Side note: Douglas W. Jones was touting this [1] in a computer architecture class in the mid-1980s. Fun stuff. He later went on to do a lot of work with computerized voting [2][3]. Great instructor...
[1] http://homepage.cs.uiowa.edu/~jones/arch/risc/ [2] http://homepage.divms.uiowa.edu/~jones/voting/pictures/ [3] http://homepage.cs.uiowa.edu/~jones/voting/
also my favourite wikipedia disambiguation page, for the sheer, entertaining unrelatedness of the items therein: http://en.wikipedia.org/wiki/OISC
How about the simplest Turing machine?
http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Tu...
A fun challenge is to try to write a quine [http://en.wikipedia.org/wiki/Quine_(computing)] in an OISC.
The awesome WireWorld prime number calculating computer is also a one instruction computer.
How about the one instruction "RunInst a, b, c, d", whose behavior is defined as "Do the instruction described by parameter a in [your favorite architecture], upon parameters b, c, d"?
Yeah, the notion of "a single instruction" really doesn't mean a whole lot, just like how (in many languages) "a single line of code" doesn't mean much.
Well, a long line of code could hold a lot of meaning.
I think you just reinvented assemblerprogramming.
OISC is something you sometimes get to build in EE labs, usually as the last project for that class. It's something that you can put together out of 7400s and, at least in our case, an eeprom for a lookup table. It's a fun thing to do and I recommend it.
See also John Tromp's "interpreter for the simplest language possible"
I always thought MADD (Multiply + Add) made a great candidate for a single instruction set computer, if the program counter was usable as an operand to the instruction.
You will want a way of decreasing registers, hence the subtract parts of the single instruction sets.
If you've got fixed length registers you can subtract via addition or multiplication.