News for hackers. Stuff that matters.
Re:Notch's Specification for the In-Game DCPU-16 by unwind on Wednesday April 04, 2012 @07:48AM (#3797099)
Just waiting for the first post about programming this CPU to pop up on Stack Overflow ... :)

It's quite an interesting architecture. From an initial perusal, I found these features note-worthy:

* Explicit access to PC as a register, makes "computed goto" trivial and very natural.

* Because of the above, there is no JMP instruction.

* Treating operations on registers as "values" makes the instruction set very orthogonal.

* No instructions for bit-manipulation.

* Lots of possible NOP instructions, like "SET PC,PC" (which I think should work, depends a bit on exactly when it's incremented but it looks safe).

* Word-addressed memory will make string processing interesting to implement. Maybe in space, everyone uses UTF-16.

* Single 64 K address space will put quite the limit on the amount of code, I guess the game will show how much code is needed to do anything.

* No I/O instructions means I/O must be memory-mapped, further reducing the space available for code. Maybe there will be bank-switching?

* No interrupts.

Re:Notch's Specification for the In-Game DCPU-16 by keenerd on Wednesday April 04, 2012 @09:01AM (#3797320)
> No instructions for bit-manipulation.

What? Plenty of opcodes for that. SHL, SHR, AND, BOR, XOR are all bitwise operators.

Unless you mean bitset and bitclear macros, but no self respecting embedded programmer uses those. I've disagreed with almost everything else Notch has done, but from a simple pedagogical standpoint, he's doing the right thing by leaving those out.

Re:Notch's Specification for the In-Game DCPU-16 by jimktrains2 on Wednesday April 04, 2012 @09:17AM (#3797380)
Why do you disagree? I've only been following this casually and don't now too much about the depths of what's going on.
Re:Notch's Specification for the In-Game DCPU-16 by unwind on Wednesday April 04, 2012 @09:48AM (#3797528)
Yeah, that was I meant, and they certainly don't have to be "macros", they can be full-blown instructions. Considering that even ARM's smaller "Thumb" instruction set has a bunch of them, I doubt that they're never used. Or, of course, they're just used by embedded compilers. :)
Re:Notch's Specification for the In-Game DCPU-16 by aidenn0 on Wednesday April 04, 2012 @12:55PM (#3798467)
No rlwinm
Re:Notch's Specification for the In-Game DCPU-16 by wagabond on Wednesday April 04, 2012 @08:32AM (#3797216)
I'm a self-taught programmer, and don't know much about CPUs. Would someone mind putting this into relatively plain english, I'm quite curious to know the practical implications of this. Can we expect to see Python running on it in the near future for example :) ?
Re:Notch's Specification for the In-Game DCPU-16 by exch on Wednesday April 04, 2012 @09:27AM (#3797439)
I strongly recommend you to read the course book "The Elements of Computing Systems" [1]. This explains the whole principle in very plain English. It has an extremely intuitive and easy to follow logic and set of exercises you can do.

It has completely demystified the whole low level world of computers for me.

If you can't get the book, a number of exercises and chapters are available for free at this website[2].

[1]: http://www1.idc.ac.il/tecs/ [2]: http://diycomputerscience.com/courses/course/the-elements-of...

Re:Notch's Specification for the In-Game DCPU-16 by wglb on Wednesday April 04, 2012 @08:43PM (#3800689)
I would be astonished if there wasn't soon a FORTH running on it. And something like http://code.google.com/p/femtolisp/ might not be totally out of the question.

But who can say. The second Fortran compiler I used ran on an IBM 1800 (equivalent to the IBM 1130, but for process control) had something like 29 phases, and ran on a machine with a total of 4k 16-bit words.

Re:Notch's Specification for the In-Game DCPU-16 by calebmpeterson on Wednesday April 04, 2012 @09:01PM (#3800745)
I wondered if I'd be the first to suggest a LISP implementation... glad to see I wasn't.
Re:Notch's Specification for the In-Game DCPU-16 by ericbb on Thursday April 05, 2012 @12:01AM (#3801245)
Pico Lisp might be a good starting point. Its interpreter for x86-64 machines is written using a simplified custom assembler and already uses a reduced number of registers.
Re:Notch's Specification for the In-Game DCPU-16 by SoftwarePatent on Wednesday April 04, 2012 @08:47AM (#3797269)
Good question. To run python on this CPU, someone (you?) needs to port Cpython to it. A CPU runs assembly language, and it's not hard for a hacker to port C to a new CPU, because C is small. In addition, implementing C is the sort of thing that hackers like to do. So you can count on C running on any given CPU, virtual or real.

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

Re:Notch's Specification for the In-Game DCPU-16 by Tuna-Fish on Wednesday April 04, 2012 @10:17AM (#3797669)
This thing will have a total of 128kB directly addressable ram (as 64k 16b words). There's no way, no how that CPython would ever do anything remotely useful here.
Re:Notch's Specification for the In-Game DCPU-16 by hythloday on Wednesday April 04, 2012 @11:12AM (#3797930)
It depends what the purpose of the DCPU is. If it's the scripting engine, well, you can easily write an aimbot in 128KiB of .pyc files and the python VM. If your only access to the world is through the DCPU, yeah, you're probably out of luck, but the second scenario makes for a much smaller and less interesting game.

It's also an obvious in-game/micropayment reward to expand the address space, somewhat analogously to the N64's memory expansion pack.

Re:Notch's Specification for the In-Game DCPU-16 by phreeza on Wednesday April 04, 2012 @08:49AM (#3797276)
"real" python seems unlikely, given that the standard executable is well over 64KB in size.

A variant like cython that compiles to this assembly? maybe...

Re:Notch's Specification for the In-Game DCPU-16 by hythloday on Wednesday April 04, 2012 @09:10AM (#3797344)
You don't need the full python repl/compiler/interpreter/libraries, you "just" need the python virtual machine. Once there's a C compiler for the platform that should be relatively straightforward, because I sincerely doubt that takes all 128KiB.
Re:Notch's Specification for the In-Game DCPU-16 by enygmata on Wednesday April 04, 2012 @10:07AM (#3797613)
I wonder how hard would it be to get a working DCPU-16 backend for GCC or Clang.
Re:Notch's Specification for the In-Game DCPU-16 by abrahamsen on Wednesday April 04, 2012 @11:27AM (#3797990)
GCC already has 4 other 16-bit backends (e.g. pdp11), so it should be achievable.
Re:Notch's Specification for the In-Game DCPU-16 by Ralith on Wednesday April 04, 2012 @12:22PM (#3798264)
A Clang backend means a LLVM backend, which I believe is a lot easier than extending GCC, and gets you support for all sorts of languages.
Re:Notch's Specification for the In-Game DCPU-16 by chrismsnz on Wednesday April 04, 2012 @05:30PM (#3799949)
RPython, perhaps?
Re:Notch's Specification for the In-Game DCPU-16 by nknight on Wednesday April 04, 2012 @08:47AM (#3797266)
Although some of the implications require experience to understand, I'd say it already is in "relatively plain English", you simply haven't been exposed to the vocabulary and concepts necessary. Trying to explain in any detail would basically be reproducing Wikipedia, so here are some links:

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

http://en.wikipedia.org/wiki/Word_(computer_architecture)

http://en.wikipedia.org/wiki/JMP_(x86_instruction)

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

http://en.wikipedia.org/wiki/Orthogonal#Computer_science

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

http://en.wikipedia.org/wiki/Memory-mapped_I/O

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

And no, don't expect Python anytime soon. Expect a C compiler, FORTH, possibly some sort of Pascal, but a highly dynamic language is unlikely. The system is too resource-constrained to make it practical. A static language that looks kind of like Python isn't out of the question, but it won't do a lot of the things you expect from Python, Ruby, PHP, or Perl.

Re:Notch's Specification for the In-Game DCPU-16 by akavel on Wednesday April 04, 2012 @09:22AM (#3797401)
> a highly dynamic language is unlikely

Lua, perhaps? There was an article how to reduce its binary size, for an older version of the language (Lua 4.0): http://www.lua.org/notes/ltn002.html

With no reductions, and for x86 assembly, it started at ~64KB, so not very useful here; but after dropping standard libraries and parser, they got to ~24KB. Now however, some further questions arise I'm not sure about:

- whether such a virtual machine, when without parser, would be anyhow more useful than the underlying system alone?

- how much the binary code would be bigger when compiled for the "DCPU-16" instruction set instead of x86?

Re:Notch's Specification for the In-Game DCPU-16 by nknight on Wednesday April 04, 2012 @09:31AM (#3797454)
Lua is a good place to start! And the VM minus parser is useful, though it may make debugging harder. You simply write out the bytecode and upload that.

The VM is only part of the problem, though. I consider the bigger problem to be memory management. A garbage collected language operating reliably in 128KB? I'm deeply skeptical.

Re:Notch's Specification for the In-Game DCPU-16 by quadhome on Wednesday April 04, 2012 @12:38PM (#3798352)
While I don't think Lua would be the choice, it's the quantity of garbage that matters:

"Historically, languages intended for beginners, such as BASIC and Logo, have often used garbage collection for heap-allocated variable-length data types, such as strings and lists, so as not to burden programmers with manual memory management. On early microcomputers, with their limited memory and slow processors, BASIC garbage collection could often cause apparently random, inexplicable pauses in the midst of program operation. Some BASIC interpreters such as Applesoft BASIC on the Apple II family, had terribly inefficient garbage collectors for strings which repeatedly scanned the string descriptors for the string having the highest address in order to compact it toward high memory. This one-string-at-a-time processing loop resulted in O(N * N) time performance in the number of strings, which would introduce a pause more than one minute long into the execution of string-intensive programs. A replacement garbage collector for Applesoft BASIC published in Call-A.P.P.L.E. (January 1981, pages 40–45, Randy Wiggington) identified a group of strings in every pass over the heap, reducing a pause of two minutes into less than a second depending on the size of the group. Other approaches were published, but none ever made it into a new revision of the BASIC interpreter."

http://en.wikipedia.org/wiki/Garbage_collection_(computer_sc...

Re:Notch's Specification for the In-Game DCPU-16 by RodgerTheGreat on Wednesday April 04, 2012 @12:56PM (#3798475)
Garbage collection isn't necessarily that difficult, especially when you're in a single-threaded (or cooperatively multithreaded) environment and don't have to contend with an OS. Here[1] is a cons-pair system I wrote in Forth which uses tag bits to identify pointers, a mark-and-sweep garbage collector and a free-list style allocator. GC takes linear time with respect to heap size, and allocations are constant time. The allocator itself (not counting all the list utility routines) is about 60 lines long and fairly easy to understand.

[1] https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith...

Re:Notch's Specification for the In-Game DCPU-16 by ac on Wednesday April 04, 2012 @11:16AM (#3797949)
A smarter way might be just implementing a new LLVM backend (gives us C via Clang, some other languages). However, even with C, the standard library probably won't leave much space for the user code itself -- so you might need something slimmer. Also, some kind of simple RTOS (www.freertos.org, maybe?) to run all these programs (I assume people would really want to run several programs at a time). I wonder if the 128k limitation was intentional, to make programming the computers more interesting. Anyway, I'm actually looking forward to seeing what kind of clever solutions the players come up with.
Re:Notch's Specification for the In-Game DCPU-16 by jmaygarden on Wednesday April 04, 2012 @01:38PM (#3798751)
An RTOS won't be of much use without interrupts. You could implement coroutines, but preemptive scheduling is not possible.
Re:Notch's Specification for the In-Game DCPU-16 by javert on Wednesday April 04, 2012 @02:09PM (#3798940)
Moreover, it would be very surprising if low-latency or deterministic timing properties would actally be useful in the game.
Re:Notch's Specification for the In-Game DCPU-16 by nknight on Wednesday April 04, 2012 @01:22PM (#3798639)
The ANSI C library is quite small. It originates in an era when 128KB of RAM was reasonably roomy. To this day, there are C libraries designed to fit comfortably within that size.

Most of the library code will never even be present anyway. Your (statically-linked) binary will simply contain those functions actually used, which is likely to be a small subset of what is available.

Re:Notch's Specification for the In-Game DCPU-16 by SoftwarePatent on Wednesday April 04, 2012 @08:54AM (#3797296)
Reading all these wikipedia pages is going to kill at least an hour of productivity today :/
Re:Notch's Specification for the In-Game DCPU-16 by ch0wn on Wednesday April 04, 2012 @09:17AM (#3797381)
Depends on what you define as being productive. I personally perceive learning as something productive.
Re:Notch's Specification for the In-Game DCPU-16 by SimHacker on Wednesday April 04, 2012 @09:14AM (#3797370)
And it will enable countless years of productivity!
Re:Notch's Specification for the In-Game DCPU-16 by sp332 on Wednesday April 04, 2012 @09:37AM (#3797485)
> No I/O instructions means I/O must be memory-mapped, further reducing the space available for code.

In a tweet, notch said It's going to be dynamic later on, but right now [the keyboard is] a cyclic 16 letter buffer at 0x9000. 0=no char yet. Set to 0 after read. http://pastebin.com/raw.php?i=aJSkRMyC

Re:Notch's Specification for the In-Game DCPU-16 by dspillett on Wednesday April 04, 2012 @11:28AM (#3797993)
The thing that looked odd to me was:

>* IFE, IFN, IFG, IFB take 2 cycles, plus the cost of a and b, plus 1 if the test fails*

It is a long time since I worked in assembly, but I don't remember comparison functions having different timings depending on results when I were a lad.

(FYI, most of the assembler I played with was for 6502s (in the old beebs) with a little for the Z80 family and early x86)

Re:Notch's Specification for the In-Game DCPU-16 by AnIrishDuck on Wednesday April 04, 2012 @01:17PM (#3798601)
Many CPUs with branch prediction carry a penalty of a least one cycle for mispredicted branches as the fetch stage(s) of the pipeline must be invalidated. From wikipedia:

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the higher the need for a good branch predictor.

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

EDIT: the inclusion of this is somewhat interesting as there's not much of a point in simulating a pipelined processor unless you care about hardware details. My best guess is they're adding this "feature" to make compilation to assembly MORE difficult and increase the advantages of hand-compiled assembly. Branch prediction is a tricky thing to do right in compilers.

Re:Notch's Specification for the In-Game DCPU-16 by dspillett on Tuesday April 10, 2012 @05:18AM (#3821408)
Ah, obviously my experience is somewhat out of date! My "hacking cycles off loops in assembler" days were all before I got my hands on any kit advanced enough for pipelining and branch prediction to be a consideration.
Re:Notch's Specification for the In-Game DCPU-16 by msarnoff on Wednesday April 04, 2012 @01:03PM (#3798513)
AVR behaves similarly. Branch instructions take 1 cycle if the condition is false, and 2 if the condition is true.
Re:Notch's Specification for the In-Game DCPU-16 by omgtehlion on Wednesday April 04, 2012 @02:30PM (#3799068)
low and mid-range PICs too
Re:Notch's Specification for the In-Game DCPU-16 by dy9 on Wednesday April 04, 2012 @09:54PM (#3800900)
It seems to me the extra cycle is used to read the first word of the next instruction, since it needs to know how long the next instruction is to skip it.
Re:Notch's Specification for the In-Game DCPU-16 by stephencanon on Wednesday April 04, 2012 @01:09PM (#3798552)
Re:Notch's Specification for the In-Game DCPU-16 by stusmith1977 on Wednesday April 04, 2012 @09:00AM (#3797318)
> Explicit access to PC as a register, makes "computed goto" trivial and very natural.

Am I right in thinking ARM uses this model? I haven't worked on them since ARM2, but I have a hazy recollection...

Re:Notch's Specification for the In-Game DCPU-16 by Symmetry on Wednesday April 04, 2012 @10:17AM (#3797673)
Sort of. R15 is the PC, but you also have branch instructions which have very large literal values which in practice you'll always use.

http://www.wss.co.uk/pinknoise/ARMinstrs/ARMinstrs.html#Bran...

Re:Notch's Specification for the In-Game DCPU-16 by dasmoth on Wednesday April 04, 2012 @09:40AM (#3797495)
Yes it does.

(Thinks of a typical SWI handler...)

Re:Notch's Specification for the In-Game DCPU-16 by TomFrost on Wednesday April 04, 2012 @08:05AM (#3797137)
> * Word-addressed memory will make string processing interesting to implement. Maybe in space, everyone uses UTF-16.

Everyone in Minecraft, too -- almost. The string encoding in Minecraft's protocol spec is UCS-2, just a sneeze away from UTF-16. It seems Notch has a soft-spot for large encodings. It makes sense from a calculation and lookup perspective, but I wonder if the increased bandwidth and storage of 16-bit blocks has a measurable impact.

Re:Notch's Specification for the In-Game DCPU-16 by ajuc on Wednesday April 04, 2012 @09:33AM (#3797462)
I think Java strings are UCS-2, so that explains why Minecraft uses this?
Re:Notch's Specification for the In-Game DCPU-16 by ealloc on Wednesday April 04, 2012 @11:17AM (#3797956)
By going UTF-16, he would make the game much more accessible to those not using a latin alphabet.

If I was designing the game, I would favor internationalization vs space efficiency in the virtual computer. That way russian kids would get to have fun learning to write silly programs too.

Re:Notch's Specification for the In-Game DCPU-16 by asdfaoeu on Wednesday April 04, 2012 @08:02PM (#3800566)
UTF-8 still has all the characters UTF-16 does it just uses more bytes to encode them. UTF-8 makes more sense if most of your characters can be represented in 8 bits.
Re:Notch's Specification for the In-Game DCPU-16 by ealloc on Thursday April 05, 2012 @12:07AM (#3801259)
you can encode all characters in the basic multilingual plane with a single utf-16 code unit, while in utf-8 BMP characters have variable lengths from 1 to 3 bytes.

If Notch only allows BMP characters and uses utf-16, internationalized string maniulation is very easy, as easy as ASCII for kids to mess with.

Re:Notch's Specification for the In-Game DCPU-16 by cpeterso on Wednesday April 04, 2012 @01:16PM (#3798599)
If the DCPU has only 64KB of RAM, encoding strings using UCS-2 or UTF-16 seems rather wasteful.
Re:Notch's Specification for the In-Game DCPU-16 by Zaak on Wednesday April 04, 2012 @05:26PM (#3799938)
You're free to choose or write software for it that encodes three 5-bit characters in a 16-bit byte if you like.
Re:Notch's Specification for the In-Game DCPU-16 by spc476 on Thursday April 05, 2012 @12:42AM (#3801338)
The DCPU address 64K worth of 16 bit word (in other words, 128KB, although you can't directly address 8 bits).
Re:Notch's Specification for the In-Game DCPU-16 by tptacek on Wednesday April 04, 2012 @07:39PM (#3800479)
The DEC Alpha didn't have byte addressing either.
Re:Notch's Specification for the In-Game DCPU-16 by zoul on Wednesday April 04, 2012 @01:27PM (#3798671)
Re:Notch's Specification for the In-Game DCPU-16 by nknight on Wednesday April 04, 2012 @08:11AM (#3797154)
With cleverness, I could see the memory constraints being not so terribly constraining, even without a (real) bank switching mechanism.

The reason we use "RAM" as we generally think of it is basically that other forms of storage are obscenely slow, right? In this case, however, our "mass storage" device would actually be... RAM. Just not directly-addressable RAM. Loading code and data from "disk" as-needed could be relatively fast.

Edit:

> No interrupts.

Good catch, that's probably something we'll see added. I don't think Notch will like emulating a thousand polling CPUs...

Edit 2:

Just spotted this in Notch's twitter feed: https://twitter.com/#!/notch/status/187454444571598848

"An emulator is coming Eventually(tm). I want to sort out some more IO design first, not release too early."

So, I/O is still up in the air.