One instruction set computer(en.wikipedia.org)

63 pointsby pykellohá 11 anos25 comments

en.wikipedia.org

http://en.wikipedia.org/wiki/One_instruction_set_computer

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

lisperhá 11 anos

It would look like a very (very!) long string of U's. :-)

You might enjoy this:

http://www.flownet.com/ron/lambda-calculus.html

arethuzahá 11 anos

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!

tomehá 11 anos

Presumably a tree of U's.

lisperhá 11 anos

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.

tptacekhá 11 anos

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

gergoerdihá 11 anos

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

SimonPStevenshá 11 anos

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.

[1] - https://github.com/Creou/OISCVM

j_bakerhá 11 anos

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.

nulldozerhá 11 anos

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

jhallenworldhá 11 anos

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

fireboneshá 11 anos

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/

zemhá 11 anos

also my favourite wikipedia disambiguation page, for the sheer, entertaining unrelatedness of the items therein: http://en.wikipedia.org/wiki/OISC

jhallenworldhá 11 anos

How about the simplest Turing machine?

http://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Tu...

cbrauchlihá 11 anos

A fun challenge is to try to write a quine [http://en.wikipedia.org/wiki/Quine_(computing)] in an OISC.

watmoughhá 11 anos

The awesome WireWorld prime number calculating computer is also a one instruction computer.

http://www.quinapalus.com/wires10.html

Chinjuthá 11 anos

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"?

baddoxhá 11 anos

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.

jonsenhá 11 anos

Well, a long line of code could hold a lot of meaning.

jonsenhá 11 anos

I think you just reinvented assemblerprogramming.

spiritplumberhá 11 anos

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.

nemoniachá 11 anos

See also John Tromp's "interpreter for the simplest language possible"

https://tromp.github.io/cl/cl.html

tsmithhá 11 anos

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.

guavahá 11 anos

You will want a way of decreasing registers, hence the subtract parts of the single instruction sets.

TheLoneWolflinghá 11 anos

If you've got fixed length registers you can subtract via addition or multiplication.

[deleted]há 11 anos