BF Interpreter?

Discuss software for the Apple 1/replica 1

BF Interpreter?

Postby djxfade » Feb Sun 11, 2007 7:31 pm

I do not know assembly, but I got this cool idea. Why not make a Brainfuck interpreter for the Replica 1? It would be awesome. For you who dont know what Brainfuck is, it is a very simple, yet very difficult turing complete programming language. As wikipedia says: "The brainfuck language is an esoteric programming language noted for its extreme minimalism. It was designed to challenge and amuse programmers, and is not suitable for practical use. Its name has been variously bowdlerized, as in brainf*ck, since its name contains the expletive "fuck". The name of the language is generally not capitalized, despite the fact that it is a proper noun.". The language only have eight commands:

> increment the pointer (to point to the next cell to the right).
< decrement the pointer (to point to the next cell to the left).
+ increment (increase by one) the byte at the pointer.
- decrement (decrease by one) the byte at the pointer.
. output the value of the byte at the pointer.
, accept one byte of input, storing its value in the byte at the pointer.
[ jump forward to the command after the corresponding ] if the byte at the pointer is zero.
] jump back to the command after the corresponding [ if the byte at the pointer is nonzero.

I know it have been ported to the AMIGA. If anyone have the experience to do this it would be extremely cool. Some few tweaks would have to be done, like the 32K RAM usage, that wouldnt fit into the Replica, and it couldnt use the standard ASCII table, as it isnt compatible with the Replica. More info about the language: Wikipedia
Dj X-Fade:

Replica 1 SE w/USB. (kit).

My PC:
Intel Celeron D 351+
1024 Dual Channel RAM
200 GB SeaGate HD
Asus P5GPL
Sapphire ATI Radeon x1300 PCIe.
Running Mac OS X 10.4.6 (hacked :D )
djxfade
 
Posts: 6
Joined: Feb Sun 11, 2007 7:02 pm
Location: Bergen / Norway

Postby lorddoomicus » Feb Mon 12, 2007 9:49 am

I wrote one of these in perl for UNIX a couple of years ago. I thought about writing one for the Replica, but the problem is addressing the 30000 bytes needed for the memory space of the program, and still having room for the bf program and the interpreter. You really need a 48k or 64k machine to pull it off the the spec of the language.

Having said that, if you wanted to make on with a smaller memory space, say 10000 bytes, it shouldn't bee to hard to even write in basic.

- Derrik
Derrik Walker v2.0, RHCE
http://www.doomd.net
lorddoomicus
 
Posts: 32
Joined: Sep Thu 07, 2006 10:30 pm
Location: Mentor Ohio

BF

Postby djxfade » Feb Mon 12, 2007 3:03 pm

Well.. yes I know. But we wouldnt have to make a 100% compatible BF interpreter. We could make it to not need to adress 30000 byte of ram, but 1000 instead, or something like that. I am not sure how this could be done in BASIC, one idea I figured might work, would be to make one string for each memory cell.
like: A$(1) or someting like that. But it would be very innefective to do it in this way. But maybe I am going to try to write it in BASIC anyway. I love challenges, and maybe this will be the challenge i need. I will post it here as soon as i get to start this project. Would be pretty interesting, even thoug it has noe practicall use. :)
Dj X-Fade:

Replica 1 SE w/USB. (kit).

My PC:
Intel Celeron D 351+
1024 Dual Channel RAM
200 GB SeaGate HD
Asus P5GPL
Sapphire ATI Radeon x1300 PCIe.
Running Mac OS X 10.4.6 (hacked :D )
djxfade
 
Posts: 6
Joined: Feb Sun 11, 2007 7:02 pm
Location: Bergen / Norway

Postby cclaunch » Feb Mon 12, 2007 9:04 pm

I did some digging and it appears there are many different implementations, not all of which provide 30,000 bytes of data area. The language is not tightly specified and there are lots of undefined issues, among which are what happens if you step past the end of the data area, or how do you detect EOF, or what are the valid ranges for each cell, or even how big each 'byte' might be.

There are a few "portability guides" that seek to minimize the impact of different implementations on different source programs written in brainf*ck and these all allow less than 30,000 locations in the array.

The maximum size of a source program is also not defined. Programs that assume any specific behavior of ASCII control characters are not portable, which helps us enormously as we have the eight essential characters that matter to the language -- these are all standard keyboard and monitor characters.

A good compromise for the Replica 1 might be a 7,500 byte program area, a 20,000 byte data area and hopefully we can fit both the interpreter and the 'monitor' needed to enter and list programs in the remaining space. We have a 32,768 byte area with only the first page of 256 bytes used, thus we have 32,512 - 27,500 or 5,012 bytes for the function. Since Woz Basic fits in only 1,024 and the Woz monitor and Krusader share 1,024 bytes, an ultra simple interpreter and simple monitor ought to be a breeze to stuff into almost 5K.

We could divide this up as a project, once we agreed on memory layout for the brainf*ck environment. In fact, we could easily re-use the data area while the monitor is running for buffers and other work areas, zeroing it out just before we transfer control to the actual interpreter.

The ideal order of development would seem to me:

* commit to memory map for data and instructions (since this is a Harvard architecture and not a Von Neumann one, they are disjoint).

* Also commit to the maximum depth of the execution stack (nested unmatched [ that can be outstandinding).

* Agree on some implementation choices, such as what happens when the pointers advance beyond the end of their respective areas or back up

* Agree on how we will handle input (type the decimal equivalent or the actual ASCII character) and output (emit ASCII even if unprintable or always emit decimal or emit decimal only when the value is not a determined mainstream monitor character). How to signal EOF is another issue that is thorny. We could define special escape sequences that specify decimal input, else it is ASCII, as well as toggling output mode and indicating an EOF. Of course, we also have to decide what EOF returns to an input command (0 is highly suggested but not universal in BF implementations).

* Agree on how we know a program has ended and should pop back to the monitor. This is also nontrivial.

* program the interpreter itself, a very tiny program that maintains the data and the instruction pointers, fetches instructions from the instruction pointer, implements a stack for the bracket locations, and executes the intent of the instructions.

Once we reach this point, we can use a PC or Mac to convert the typed program source into decimal values that are then loaded to the intended instruction area by the Woz monitor. That and a woz command to branch to the interpreter woudl be enough to run stuff without our having written the next phases.

* write the BF monitor that allows source code entry, optionally lists source code, and transfers to and back from the interpreter
cclaunch
 
Posts: 31
Joined: Jan Wed 03, 2007 8:18 pm
Location: Silicon Valley

BF

Postby djxfade » Feb Tue 13, 2007 5:30 am

Hey sounds great. I am curently learning 6502 assembly. It would be very coll if we could get this project a reality. I would like to contribute to this project as much as possible. But at this point I am not cappable of writing assembly. But I am a fast learner. So if anyone could give me links to good tutorials or ebooks or articles or anything else that have anything with 6502 assembly, that would be very nice :) . At this point I am only cappable of writing Apple BASIC. But if theres anything I can do in the meantime, to help contribute, just PM me. :D
Dj X-Fade:

Replica 1 SE w/USB. (kit).

My PC:
Intel Celeron D 351+
1024 Dual Channel RAM
200 GB SeaGate HD
Asus P5GPL
Sapphire ATI Radeon x1300 PCIe.
Running Mac OS X 10.4.6 (hacked :D )
djxfade
 
Posts: 6
Joined: Feb Sun 11, 2007 7:02 pm
Location: Bergen / Norway

Postby Kallikak » Feb Tue 13, 2007 7:35 pm

For info on 6502 assembly programming, here's a good, short and simple introduction: http://www.obelisk.demon.co.uk/6502/

This book is also pretty useful, though some of it is not relevant to the Apple 1: http://linux.cis.monroeccc.edu/~paulrsm/6502/HYDE6502.TXT

You should read the Apple 1 manual to see how to do character input and output using the monitor subroutines.

There are a few sample programs provided with the Krusader assembler that might also help once you've gotten started, plus various snippets and tutorials at http://www.6502.org/. I'm not sure what version of Krusader is in the Replica 1 SE ROM, but if it's version 1.2, you can use the mini-monitor to step through your assembled code and see things as they happen instruction by instruction. (There are a couple of worked examples in the Krusader manual.)

Ken
Kallikak
 
Posts: 172
Joined: Jan Sun 29, 2006 7:42 pm
Location: Sydney

Re: BF Interpreter?

Postby BigBill » May Mon 10, 2010 9:28 pm

Ok, I have been working on a Brainfuck interpreter in assembly, and seeing as there is already a old thread for this, it seems this would be the place to post.

I'm not very experienced at assembly, so my code might seem a bit inefficient, and well, a headache, so bare with me. But it works, and will run small programs. The problem is that when BF code is entered, it is stored starting at $800. The Y register keeps track of where each byte of code is stored and read. Since $FF is the highest byte a register can store, the interpreter can only work with 255 BF instructions. Anyone have any advice to fix this problem? It can't seem to wrap my head around it.

I was using a really funky cross assembler (only one I could find for linux), which wouldn't let me do subroutines right, so I had to use a bunch of JMP statements that probably seem very unneccesary.

Code: Select all
   
;gets code input, and starts interpreting when 'R' is pressed.
ORG $300

   LDA #$7E
   STA $500
   LDY #$00

   LOOP:   
   LDA $D011
   BPL LOOP
   LDA $D010
   JSR $FFEF
   STA $800,Y   ;change
   INY
   CMP #$D2
   BNE LOOP
   JSR RUN
   RTS

;interprets code.
RUN:   
   LDA #$20
   JSR $FFEF
   LDA #$00
   LDY #$00
        ;loop that interprets each instruction and runs program.
   PROG:
   LDX $800,Y   ;change
   INY      ;change
   CPX #$AE
   BEQ OUT

   PL:
   CPX #$AB
   BEQ PLUS

   MIN:
   CPX #$AD
   BEQ MINUS

   IN:
   CPX #$AC
   BEQ INPUT

   FRW:
   CPX #$DB
   BEQ FORWRD

   BAK:
   CPX #$DD
   BEQ BAKWRD

   IK:
   CPX #$BE
   BEQ INKDP

   DK:
   CPX #$BC
   BEQ DENKDP

   RU:
   CPX #$D2
   BNE PROG
   RTS
;'.'
OUT:
   JSR $FFEF
   JMP PL
;'+'
PLUS:
   ADC #$00
   JMP MIN
;'-'
MINUS:
   SBC #$01
   JMP IN
;','
INPUT:
   IDP:
   LDA $D011
   BPL IDP
   LDA $D010
   SBC #$80
   JMP FRW
;'['
FORWRD:
   CMP #$00
   BNE BAK

   LEWP:
   INY
   LDX $800,Y   ;change
   CPX #$DD
   BNE LEWP
   JMP BAK
;']'
BAKWRD:
   CMP #$00
   BEQ RU

   LUUP:
   DEY
   LDX $800,Y   ;change
   CPX #$DB ;[
   BNE LUUP
   JMP IK
;'<'
INKDP:
   STY $503
   LDY $500
   STA $5000,Y
   INY
   LDA $5000,Y
   STY $500
   LDY $503
   JMP DK
;'>'
DENKDP:
   STY $503
   LDY $500
   STA $5000,Y
   DEY
   LDA $5000,Y
   STY $500
   LDY $503
   JMP RU


Well, there it is. Any improvements would be great. I'll post a hex dump as well.
BigBill
 
Posts: 3
Joined: Apr Fri 16, 2010 10:33 pm

Re: BF Interpreter?

Postby BigBill » May Mon 10, 2010 9:29 pm

Code: Select all
0300: A9 7E 8D 00
0304: 05 A0 00 AD
0308: 11 D0 10 FB
030C: AD 10 D0 20
0310: EF FF 99 00
0314: 08 C8 C9 D2
0318: D0 ED 20 1E
031C: 03 60 A9 20
0320: 20 EF FF A9
0324: 00 A0 00 BE
0328: 00 08 C8 E0
032C: AE F0 21 E0
0330: AB F0 23 E0
0334: AD F0 24 E0
0338: AC F0 25 E0
033C: DB F0 2E E0
0340: DD F0 39 E0
0344: BE F0 44 E0
0348: BC F0 56 E0
034C: D2 D0 D8 60
0350: 20 EF FF 4C
0354: 2F 03 69 00
0358: 4C 33 03 E9
035C: 01 4C 37 03
0360: AD 11 D0 10
0364: FB AD 10 D0
0368: E9 80 4C 3B
036C: 03 C9 00 D0
0370: CE C8 BE 00
0374: 08 E0 DD D0
0378: F8 4C 3F 03
037C: C9 00 F0 CB
0380: 88 BE 00 08
0384: E0 DB D0 F8
0388: 4C 43 03 8C
038C: 03 05 AC 00
0390: 05 99 00 50
0394: C8 B9 00 50
0398: 8C 00 05 AC
039C: 03 05 4C 47
03A0: 03 8C 03 05
03A4: AC 00 05 99
03A8: 00 50 88 B9
03AC: 00 50 8C 00
03B0: 05 AC 03 05
03B4: 4C 4B 03 FF


There's the dump. Basically all you have to do is enter the BF code and when you want to run what you've entered, press 'R'.
BigBill
 
Posts: 3
Joined: Apr Fri 16, 2010 10:33 pm


Return to Software

Who is online

Users browsing this forum: No registered users and 1 guest