10 ms·

CHIP-8 in Common Lisp: The CPU

125 points by stevelosh 10y ago

macournoyer 10y ago
CHIP-8 is pretty fun! Here's one I made in JavaScript w/ debugger: http://greatcodeclub.github.io/chip8/ http://greatcodeclub.github.io/chip8/ Code: https://github.com/greatcodeclub/chip8 https://github.com/greatcodeclub/chip8
davexunit 10y ago
This is very neat, but he's right that some won't like the unhygienic variable definitions in the with-chip macro. ;) If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. This way everything would remain hygienic. I guess it's just another example of the usual difference in software design between CL and Scheme programmers. I'm excited to see this blog series develop to the point where there is graphical output.
- deleted 10y ago
  [deleted]
- junke 10y ago
  > I guess it's just another example of the usual difference in software design between CL and Scheme programmers. You mean, nitpicking about trivialities ;-) ?
  - davexunit 10y ago
    You're joking, right? It's not a trivial matter. I appreciate both design methods (I associate myself with plenty of CL programmers), but I can't hide that I think Scheme made the better design decisions.
    - junke 10y ago
      > You're joking, right? It's not a trivial matter. It is a matter of context. There is a whole blog post full of hard work and you comment about an unhygienic macro. Author said: This is nice and readable. Some folks will dislike the fact that it introduces new variable bindings that are “hidden” in the macro definition, but I like the concision you get from it, especially for a small project like this. This is a small project, the code is deliberately using macros in a way that is regarded as poor style (even in CL), but this is not important here. There is no need to start a flame about single namespaces.
      - sigjuice 10y ago
        Can't similar brevity be achieved by using a special variable called 'chip'?
        junke 10y ago
        Yes, sure (defvar *chip*) (defun memory (&optional (chip *chip*)) (chip-memory chip)) Just binding the variable is enough. If you want to hide this variable as an implementation detail, you can use a macro: (defmacro with-chip (chip &body body) `(let ((*chip* ,chip)) ,@body)) You could also have a symbol-macrolet so that "memory" expands as a call, i.e. "(memory)", but then you would have the same syntax as the above poster wanted to avoid ;-) (except that accesseors already provide setf functions)
      - davexunit 10y ago
        HOLY SHIT I SAID I LIKED THE POST. I have talked to the author on IRC. I was just playing off of what he wrote about certain people not liking the with-chip macro. The amount of downvotes I'm getting is ridiculous.
    - progman 10y ago
      I know both Lisp and Scheme pretty well. Scheme's macros are hygienic, Lisp's macros however are much easier to handle. The hygiene problem can be solved by using (gensym) for local identifiers. Example: http://stackoverflow.com/questions/267862/what-makes-lisp-macros-so-special http://stackoverflow.com/questions/267862/what-makes-lisp-ma...
- bitwize 10y ago
  Lack of macro hygiene is just peachy keen among Scheme programmers as long as you are explicit about which identifier bindings can leak into, or out of, the macro definition from the macro call site. Scheme standards before R6RS[0] were a rough consensus on which language features everyone could agree on as useful additions. That's why only syntax-rules made the cut, not because Scheme programmers object to the ability to break hygiene. Implementors disagreed on which mechanism for breaking hygiene was most "correct", so none made the cut and unhygienic macros weren't standardized. [0] R6RS, in a break from Scheme tradition, adopted a systemd-esque "come up with a standard for these needed features, any standard, and everybody else needs to fall in line whether or not they like it" approach.
  - davexunit 10y ago
    >Lack of macro hygiene is just peachy keen among Scheme programmers as long as you are explicit about which identifier bindings can leak into, or out of, the macro definition from the macro call site. I haven't encountered a single case where I didn't prefer hygiene over an unhygienic solution.
    - lmohseni 10y ago
      I'm not a lisp master, so please take the following with a grain of salt: One case where you'd want unhygienic capture is with anaphoric macros, which introduce a binding (usually named `it` as in english). For example, using an anaphoric if called aif, we can transform: (let ((result (big-long-calculation))) (if result (foo result))) into: (aif (big-long-calculation) (foo it)) cf: http://www.bookshelf.jp/texi/onlisp/onlisp_15.html http://www.bookshelf.jp/texi/onlisp/onlisp_15.html
      - aidenn0 10y ago
        Anaphora have been controversial in the common lisp community as long as I have been involved. I imagine the same is true of the scheme community.
- tangus 10y ago
  > If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. Do you mean to create global functions with those generic, unqualified names? The unhygienic solution at least keeps them nicely inside the lexical scope of the "with" construct. That actually looks more hygienic, for another, more traditional, meaning of hygienic.
  - davexunit 10y ago
    I find it confusing that something is magically introducing variable bindings. I see the convenience it adds, for sure, but my personal style would be to opt for a more verbose approach that didn't do this.
- kazinator 10y ago
  It is not unhygienic. The with-chip macro is understood as creating a lexical environment in which certain local identifiers are visible. There is no accident there; it is documented. You use the macro to obtain exactly that; as it's raison d'être. > If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. And then what, use the flimsy hack known as "fluid let" to locally rebind this parameter to a desired chip instance? Let's avoid lack of macro-expansion-time hygiene, by introducing run-time variable mutation?
  - kazinator 10y ago
    Another point grandparent is missing: when macros of this type introduce the well-known symbols into a scope, those macros themselves are not "surprised" when user code shadows those same symbols. That is to say, those macros usually provide the symbols to the user code, but do not themselves rely on those bindings (while that is possible, it would be a correctable mistake in the implementation).
- qwertyuiop924 10y ago
  I find parameters an unpleasant hack. I can't understand why RnRS doesn't just add dynamic variables back in (as lispm pointed out to me, they were in R0RS).
  - groovy2shoes 10y ago
    What do you gain by having fluid variables rather than parameters? As I understand it, they serve the same purpose, and the difference between them is just an implementation detail.
    - qwertyuiop924 10y ago
      Firstly, parameters are functions. That means that if the function you're using didn't plan for use with parameters (maybe the code predates R7RS, maybe that value was never supposed to be changed), you're out of luck: have fun with your globals. Secondly, parameters must be global. You can't, say, have a function that depends on which parameters were bound in a parent function. This is because parameters aren't true dynamic scoping: they're using lexical scoping to emulate dynamic scoping. All well and good, but why not just implement dynamic scoping? Thirdly, Parameters are fiddly to get right. The path to RnRS parameters is paved with the bones of many a construct (like fluid-let) that tried and failed to safely handle parameters, whether it be because of multithreading, or because of those two famous bugbears of Scheme programming, call/cc and dynamic-wind. The reason for this is that all these constructs, at their heart, are changing the value of a global for the dynamic extent of a function. In scheme, as you no doubt know, dynamic extents aren't guaranteed contiguous. OTOH, true dynamic variables are a lot simpler to get right in the prescence of continuations: a continuation is a copy of the stack, in low level terms. Dynamic variables are bound to the stack, so dynamic variables and continuations should Just Work. The same is true with threading. In short, parameters are a construct less flexable than true dynamic variables and a more complicated one to implement, to boot.
      - groovy2shoes 10y ago
        Ah, I see. Thanks for the explanation. I disagree that dynamic variables are more complicated to implement, though. As you mentioned, parameters are fiddly to get right. Dynamic variables, on the other hand, only need to be defined in what I'll call a "fluid environment", which is basically the same as a lexical environment, but it gets passed to `apply` whenever a procedure is applied, the same way the lexical environment gets passed to `eval` whenever it's applied. Under the hood, all the usual operations on environments work without change, because the data structure is the same, though you'll need to expose an API to the extra environment for it to be useful. Anyway, I don't think the implementation of parameters as procedures (even global ones) necessarily prohibits them from working with call/cc. Consider an implementation like this: (define (make-parameter value) (case-lambda (() value) ((x f) (let ((old value)) (dynamic-wind (lambda () (set! value x)) f (lambda () (set! value old))))))) (define-syntax parameterize (syntax-rules () ((parameterize ((param val)) body ...) (param val (lambda () body ...))) ((parameterize ((param val) (params vals) ...) body ...) (param val (lambda () (parameterize ((params vals) ...) body ...)))))) Yes, it's still a kludge compared to real fluid variables, but I think it's safe in the face of continuations (I only did minimal testing, so I don't guarantee it). This kind of thing is exactly what dynamic-wind is for :)
Avshalom 10y ago
Okay but can I get a chip-8 emulator written in dcpu-16 assembly running on redstone?
krat0sprakhar 10y ago
This is awesome! A couple of days ago, I'd asked an asinine comment[0] about building a NES emulator & someone had suggested to start with a CHIP-8 emulator first. For someone who's looking to write the same in Clojure, I'm super glad that Steve wrote this guide! 0 - https://news.ycombinator.com/item?id=13145864 https://news.ycombinator.com/item?id=13145864
fernly 10y ago
I believe this suffers, as do several other CHIP-8 emulators I've seen, from the early mis-documentation of the SHR and SHL instructions. Forgive me if I am reading this incorrectly; I am not used to Lisp: (define-instruction op-shr (_ r _ _) ;; SHR (setf (values (register r) flag) (>>_8 (register r)))) (define-instruction op-shl (_ r _ _) ;; SHL (setf (values (register r) flag) (<<_8 (register r)))) Since there is only one reg argument, it seems these are shifting the source register in place. It should put the shifted value of the source register into the target register (8XY6: VX <- VY>>1) This was recently clarified in an exchange on the retrocomputing forum [1]. [1] https://groups.yahoo.com/neo/groups/rcacosmac/conversations/messages/328 https://groups.yahoo.com/neo/groups/rcacosmac/conversations/...
- aidenn0 10y ago
  Your analysis looks correct. FWIW: (setf (values X Y) Z) is roughly equivalent to the Python: (X, Y) = Z So (setf (values (register r) flag) (<<_8 (register r))) might be idiomatically in python: (registers[r], flag) = leftShift8(registers[r]) And in any event is using the same register "r" as both source and destination.

125 points by stevelosh 10y ago

CHIP-8 is pretty fun! Here's one I made in JavaScript w/ debugger: http://greatcodeclub.github.io/chip8/ http://greatcodeclub.github.io/chip8/ Code: https://github.com/greatcodeclub/chip8 https://github.com/greatcodeclub/chip8

davexunit 10y ago

This is very neat, but he's right that some won't like the unhygienic variable definitions in the with-chip macro. ;) If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. This way everything would remain hygienic. I guess it's just another example of the usual difference in software design between CL and Scheme programmers. I'm excited to see this blog series develop to the point where there is graphical output.

deleted 10y ago
[deleted]
junke 10y ago
> I guess it's just another example of the usual difference in software design between CL and Scheme programmers. You mean, nitpicking about trivialities ;-) ?
- davexunit 10y ago
  You're joking, right? It's not a trivial matter. I appreciate both design methods (I associate myself with plenty of CL programmers), but I can't hide that I think Scheme made the better design decisions.
  - junke 10y ago
    > You're joking, right? It's not a trivial matter. It is a matter of context. There is a whole blog post full of hard work and you comment about an unhygienic macro. Author said: This is nice and readable. Some folks will dislike the fact that it introduces new variable bindings that are “hidden” in the macro definition, but I like the concision you get from it, especially for a small project like this. This is a small project, the code is deliberately using macros in a way that is regarded as poor style (even in CL), but this is not important here. There is no need to start a flame about single namespaces.
    - sigjuice 10y ago
      Can't similar brevity be achieved by using a special variable called 'chip'?
      - junke 10y ago
        Yes, sure (defvar *chip*) (defun memory (&optional (chip *chip*)) (chip-memory chip)) Just binding the variable is enough. If you want to hide this variable as an implementation detail, you can use a macro: (defmacro with-chip (chip &body body) `(let ((*chip* ,chip)) ,@body)) You could also have a symbol-macrolet so that "memory" expands as a call, i.e. "(memory)", but then you would have the same syntax as the above poster wanted to avoid ;-) (except that accesseors already provide setf functions)
    - davexunit 10y ago
      HOLY SHIT I SAID I LIKED THE POST. I have talked to the author on IRC. I was just playing off of what he wrote about certain people not liking the with-chip macro. The amount of downvotes I'm getting is ridiculous.
  - progman 10y ago
    I know both Lisp and Scheme pretty well. Scheme's macros are hygienic, Lisp's macros however are much easier to handle. The hygiene problem can be solved by using (gensym) for local identifiers. Example: http://stackoverflow.com/questions/267862/what-makes-lisp-macros-so-special http://stackoverflow.com/questions/267862/what-makes-lisp-ma...
bitwize 10y ago
Lack of macro hygiene is just peachy keen among Scheme programmers as long as you are explicit about which identifier bindings can leak into, or out of, the macro definition from the macro call site. Scheme standards before R6RS[0] were a rough consensus on which language features everyone could agree on as useful additions. That's why only syntax-rules made the cut, not because Scheme programmers object to the ability to break hygiene. Implementors disagreed on which mechanism for breaking hygiene was most "correct", so none made the cut and unhygienic macros weren't standardized. [0] R6RS, in a break from Scheme tradition, adopted a systemd-esque "come up with a standard for these needed features, any standard, and everybody else needs to fall in line whether or not they like it" approach.
- davexunit 10y ago
  >Lack of macro hygiene is just peachy keen among Scheme programmers as long as you are explicit about which identifier bindings can leak into, or out of, the macro definition from the macro call site. I haven't encountered a single case where I didn't prefer hygiene over an unhygienic solution.
  - lmohseni 10y ago
    I'm not a lisp master, so please take the following with a grain of salt: One case where you'd want unhygienic capture is with anaphoric macros, which introduce a binding (usually named `it` as in english). For example, using an anaphoric if called aif, we can transform: (let ((result (big-long-calculation))) (if result (foo result))) into: (aif (big-long-calculation) (foo it)) cf: http://www.bookshelf.jp/texi/onlisp/onlisp_15.html http://www.bookshelf.jp/texi/onlisp/onlisp_15.html
    - aidenn0 10y ago
      Anaphora have been controversial in the common lisp community as long as I have been involved. I imagine the same is true of the scheme community.
tangus 10y ago
> If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. Do you mean to create global functions with those generic, unqualified names? The unhygienic solution at least keeps them nicely inside the lexical scope of the "with" construct. That actually looks more hygienic, for another, more traditional, meaning of hygienic.
- davexunit 10y ago
  I find it confusing that something is magically introducing variable bindings. I see the convenience it adds, for sure, but my personal style would be to opt for a more verbose approach that didn't do this.
kazinator 10y ago
It is not unhygienic. The with-chip macro is understood as creating a lexical environment in which certain local identifiers are visible. There is no accident there; it is documented. You use the macro to obtain exactly that; as it's raison d'être. > If I were to do this in Scheme, I'd use a "parameter" called 'current-chip' (think of it like a dynamically scoped variable) and write getter/setter procedures that operate on the current chip. And then what, use the flimsy hack known as "fluid let" to locally rebind this parameter to a desired chip instance? Let's avoid lack of macro-expansion-time hygiene, by introducing run-time variable mutation?
- kazinator 10y ago
  Another point grandparent is missing: when macros of this type introduce the well-known symbols into a scope, those macros themselves are not "surprised" when user code shadows those same symbols. That is to say, those macros usually provide the symbols to the user code, but do not themselves rely on those bindings (while that is possible, it would be a correctable mistake in the implementation).
qwertyuiop924 10y ago
I find parameters an unpleasant hack. I can't understand why RnRS doesn't just add dynamic variables back in (as lispm pointed out to me, they were in R0RS).
- groovy2shoes 10y ago
  What do you gain by having fluid variables rather than parameters? As I understand it, they serve the same purpose, and the difference between them is just an implementation detail.
  - qwertyuiop924 10y ago
    Firstly, parameters are functions. That means that if the function you're using didn't plan for use with parameters (maybe the code predates R7RS, maybe that value was never supposed to be changed), you're out of luck: have fun with your globals. Secondly, parameters must be global. You can't, say, have a function that depends on which parameters were bound in a parent function. This is because parameters aren't true dynamic scoping: they're using lexical scoping to emulate dynamic scoping. All well and good, but why not just implement dynamic scoping? Thirdly, Parameters are fiddly to get right. The path to RnRS parameters is paved with the bones of many a construct (like fluid-let) that tried and failed to safely handle parameters, whether it be because of multithreading, or because of those two famous bugbears of Scheme programming, call/cc and dynamic-wind. The reason for this is that all these constructs, at their heart, are changing the value of a global for the dynamic extent of a function. In scheme, as you no doubt know, dynamic extents aren't guaranteed contiguous. OTOH, true dynamic variables are a lot simpler to get right in the prescence of continuations: a continuation is a copy of the stack, in low level terms. Dynamic variables are bound to the stack, so dynamic variables and continuations should Just Work. The same is true with threading. In short, parameters are a construct less flexable than true dynamic variables and a more complicated one to implement, to boot.
    - groovy2shoes 10y ago
      Ah, I see. Thanks for the explanation. I disagree that dynamic variables are more complicated to implement, though. As you mentioned, parameters are fiddly to get right. Dynamic variables, on the other hand, only need to be defined in what I'll call a "fluid environment", which is basically the same as a lexical environment, but it gets passed to `apply` whenever a procedure is applied, the same way the lexical environment gets passed to `eval` whenever it's applied. Under the hood, all the usual operations on environments work without change, because the data structure is the same, though you'll need to expose an API to the extra environment for it to be useful. Anyway, I don't think the implementation of parameters as procedures (even global ones) necessarily prohibits them from working with call/cc. Consider an implementation like this: (define (make-parameter value) (case-lambda (() value) ((x f) (let ((old value)) (dynamic-wind (lambda () (set! value x)) f (lambda () (set! value old))))))) (define-syntax parameterize (syntax-rules () ((parameterize ((param val)) body ...) (param val (lambda () body ...))) ((parameterize ((param val) (params vals) ...) body ...) (param val (lambda () (parameterize ((params vals) ...) body ...)))))) Yes, it's still a kludge compared to real fluid variables, but I think it's safe in the face of continuations (I only did minimal testing, so I don't guarantee it). This kind of thing is exactly what dynamic-wind is for :)

Avshalom 10y ago

Okay but can I get a chip-8 emulator written in dcpu-16 assembly running on redstone?

krat0sprakhar 10y ago

This is awesome! A couple of days ago, I'd asked an asinine comment[0] about building a NES emulator & someone had suggested to start with a CHIP-8 emulator first. For someone who's looking to write the same in Clojure, I'm super glad that Steve wrote this guide! 0 - https://news.ycombinator.com/item?id=13145864 https://news.ycombinator.com/item?id=13145864

fernly 10y ago

I believe this suffers, as do several other CHIP-8 emulators I've seen, from the early mis-documentation of the SHR and SHL instructions. Forgive me if I am reading this incorrectly; I am not used to Lisp: (define-instruction op-shr (_ r _ _) ;; SHR (setf (values (register r) flag) (>>_8 (register r)))) (define-instruction op-shl (_ r _ _) ;; SHL (setf (values (register r) flag) (<<_8 (register r)))) Since there is only one reg argument, it seems these are shifting the source register in place. It should put the shifted value of the source register into the target register (8XY6: VX <- VY>>1) This was recently clarified in an exchange on the retrocomputing forum [1]. [1] https://groups.yahoo.com/neo/groups/rcacosmac/conversations/messages/328 https://groups.yahoo.com/neo/groups/rcacosmac/conversations/...

aidenn0 10y ago
Your analysis looks correct. FWIW: (setf (values X Y) Z) is roughly equivalent to the Python: (X, Y) = Z So (setf (values (register r) flag) (<<_8 (register r))) might be idiomatically in python: (registers[r], flag) = leftShift8(registers[r]) And in any event is using the same register "r" as both source and destination.