retroCHallEngE 2010!

ThiS is thE real deal!


Saturday, July 31, 2010 11:59:59 PM (Pacific Standard Time)

 1 ON NOT T GOSUB 50: FOR Q = 0 TO T STEP 0: INPUT ">";E$:R$ = "":Q = LEN (E$) = 0: GOSUB 19: PRINT R$: NEXT : END

 2 L = LEN (X$): ON L < 3 OR FN A(T) GOTO 98:A = FN A(2):P = 0: FOR I = 2 TO L:R = I:K$ = MID$ (X$,I,T): ON A AND K$ = Z$ GOTO 96:P = P + (K$ = P$): IF K$ = Q$ THEN P = P - T: IF NOT P THEN R = I - A - T: RETURN


 4 GOSUB 2

 5 R$ = RIGHT$ (X$, FN L(L - R - 3 + A * 2))

 6 IF LEFT$ (R$,T) = Z$ THEN R$ = RIGHT$ (R$, LEN (R$) - T): GOTO 6

 7 R$ = P$ + R$:X$ = R$: RETURN

 8 GOSUB 11

 9 GOSUB 4

10 GOSUB 4

11 GOSUB 2:R$ = MID$ (X$,2,R - A * 2):X$ = R$: RETURN

12 GOSUB 11: GOTO 10

13 GOSUB 11: GOTO 11

14 N = Y$ < > F$:P = MID$ (Y$,T,T) = P$:R$ = P$ + X$ + MID$ (Z$,T,N) + MID$ (Y$,T + P, LEN (Y$) - P) + MID$ (Q$,T, NOT P): RETURN

15 FOR I = U TO 0 STEP - T: IF X$ = U$(I) THEN R$ = V$(I): RETURN


17 GOSUB 10:E$ = R$: GOSUB 20:X$ = R$: RETURN

18 GOSUB 40: GOSUB 17: GOSUB 47:S$ = R$: GOSUB 36:X$ = E$: GOSUB 9:E$ = R$: GOSUB 20: GOTO 43

19 O$ = E$:O = U

20 X$ = E$:Y$ = A$: ON FN A(T) GOTO 15: GOSUB 11: IF NOT ( FN A(T)) THEN GOSUB 11: ON R$ = "LABEL" GOTO 28: ON R$ = "LAMBDA" GOTO 29:R$ = E$: RETURN

21 X$ = E$: ON R$ = "QUOTE" GOTO 10: IF R$ = "ATOM" THEN GOSUB 17:R$ = A$( FN A(T)): RETURN

22 IF R$ = "EQ" THEN GOSUB 18:R$ = A$(S$ = R$): RETURN

23 IF R$ = "COND" THEN GOSUB 4:C$ = R$: GOTO 33

24 IF R$ = "CAR" THEN GOSUB 17: GOTO 11

25 IF R$ = "CDR" THEN GOSUB 17: GOTO 4

26 IF R$ = "CONS" THEN GOSUB 18:X$ = S$:Y$ = R$: GOTO 14

27 X$ = R$: GOSUB 15:S$ = R$: GOSUB 36:X$ = E$: GOSUB 4: GOSUB 43:X$ = S$:Y$ = R$: GOSUB 14:E$ = R$: ON E$ < > O$ OR U < > O GOTO 19: RETURN

28 GOSUB 40:X$ = E$: GOSUB 11:Y$ = R$:X$ = E$: GOSUB 12:U = U + T:U$(U) = X$:V$(U) = Y$:X$ = E$: GOSUB 4:Y$ = R$:X$ = E$: GOSUB 8: GOSUB 14:E$ = R$: GOSUB 20: GOTO 47

29 GOSUB 40:X$ = E$: GOSUB 4:M$ = R$: GOSUB 35:Y$ = R$:X$ = E$: GOSUB 12

30 IF X$ < > F$ OR Y$ < > F$ THEN ON FN A(1) OR FN B(1) GOTO 97: GOSUB 32:U = U + T:U$(U) = CA$:CD$ = R$:X$ = Y$: GOSUB 32:V$(U) = CA$:X$ = CD$:Y$ = R$: GOTO 30

31 X$ = E$: GOSUB 8:E$ = R$: GOSUB 20: GOTO 47

32 GOSUB 2:CA$ = MID$ (X$,2,R - A * 2): GOTO 5

33 X$ = C$: GOSUB 13: GOSUB 37:E$ = R$: GOSUB 20: GOSUB 44:X$ = C$: IF R$ = T$ THEN GOSUB 12:E$ = R$: GOTO 20

34 GOSUB 4:C$ = R$: GOTO 33

35 ON M$ = F$ GOTO 95: GOSUB 39:X$ = M$: GOSUB 4:M$ = R$: GOSUB 35: GOSUB 45:S$ = R$: GOSUB 36: GOSUB 39:X$ = M$: GOSUB 11:E$ = R$: GOSUB 20: GOSUB 45:X$ = R$: GOSUB 43:Y$ = S$: GOTO 14

36 S$(SP) = S$: GOTO 42

37 S$(SP) = C$: GOSUB 42

38 S$(SP) = STR$ (U): GOTO 42

39 S$(SP) = M$: GOSUB 42

40 GOSUB 38

41 S$(SP) = E$

42 SP = SP + T: RETURN

43 GOSUB 49:S$ = S$(SP): RETURN

44 GOSUB 48: GOSUB 49:C$ = S$(SP): RETURN

45 GOSUB 47: GOSUB 49:M$ = S$(SP): RETURN

46 GOSUB 49:E$ = S$(SP): RETURN

47 GOSUB 46

48 GOSUB 49:U = VAL (S$(SP)): RETURN

49 SP = SP - T: RETURN

50 DIM S$(50),U$(50),V$(50):T = 1:T$ = "T":A$(T) = T$:P$ = "(":Z$ = " ":Q$ = ")":F$ = P$ + Q$:A$(0) = F$

51 DEF FN A(X) = MID$ (X$,X,T) < > P$ OR X$ = F$: DEF FN B(Y) = MID$ (Y$,Y,T) < > P$ OR Y$ = F$: DEF FN L(X) = X * (X > 0) + T

52 U$(0) = "NIL":V$(0) = F$

93 IF LEN (U$(U)) THEN PRINT U$(U)"="V$(U):U = U + 1: GOTO 93

94 U = U - 1

95 R$ = F$



98 PRINT "C*R "X$


4 CDR X$ 11 CAR X$ 15 associate X$ 36 save S$
8 CADDAR X$ 12 CADAR X$ 20 EVAL E$ A$ 43 un-save
9 CADDR X$ 13 CAAR X$ 33 EVCON C$ A$ 50 initialize
10 CADR X$ 14 CONS X$ Y$ 35 EVLIS M$ A$ 51 FN ATOM


Thusdaλ, Julλ 29, 2010

Mark Stock said...

If I am reading Paul Graham's implementation of eval in Common Lisp correctly, I think that the ')' goes in a different place for LABEL

eq [caar [e]; LABEL] ⇒ eval [cons [caddar [e]; cdr [e]]; cons
[list [cadar [e]; car [e]); a]];

I think that the second cons function takes two parameters:
list [cadar [e]; car [e]]

30 July 2010 04:07

There are still a few extra debugging and error messages that get printed at the moment.


Tuesdaλ, Julλ 27, 2010

Lispers complain that non-Lispers like me complain about parentheses in Lisp.  If that sentence didn't just give you a metacircular disorder, I don't know what will.  Anyways, even though I am jumping right in and implementing McCarthy's Lisp, I still have a hate on for those brackets, parenthesis.  Hate 'em, but using them none the less.

There are some bugs in McCarthy's Lisp.  I didn't find them.  I appreciate these old Lispers that did find the bugs...

from page 12 of Paul Graham's The Roots of Lisp

"There was a small bug in McCarthy's eval.  Line 16 was (equivalent to)
(evlis. (cdr e) a) instead of just (cdr e), which caused the arguments in
a call to a named function to be evaluated twice.  This suggests that this de-
scription of eval had not yet been implemented in IBM 704 machine language
when the paper was submitted.  It also shows how hard it is to be sure of the
correctness of any length of program without trying to run it.
Complete Article (Postscript)

From a few posts back, what I am calling the "everything else" function
a]];  T ⇒ eval [cons [assoc [car [e]; a];
evlis [cdr [e]; a]]; a]];
and if I am reading this bug correctly, this should be
a]];  T ⇒ eval [cons [assoc [car [e]; a];
cdr [e]]; a]];
I added yet another extraneous function:
(BUG [ON | OFF]) ; turns this bug on and off

Programming Notes.: Interesting case of Mismatched Parentheses. from Kazimir Majorinc's blog

G Shubert said...

An editor which shows matching parentheses is a useful tool here. The missing close parenstheses appear to be in the last two eq clauses -- the ones with LABEL and LAMBDA. Change to:

eq [caar [e]; LABEL] ⇒ eval [cons [caddar [e]; cdr [e]];
cons [list [cadar [e]; car [e]; a]]);

eq [caar [e]; LAMBDA] ⇒ eval [caddar [e];
append [pair [cadar [e]; evlis [cdr [e]; a]; a]]])

I've used ')' to show where I inserted characters. I note that Paul Graham's implementation of eval in Common Lisp has parenthenses in these places.


There are still a few extra debugging and error messages that get printed at the moment.

One infinite loop

Sundaλ, Julλ 25, 2010

Okay, I've sort of dealt with the infinite loop and quashed a few more bugs in the process.  The "everything else" function re-evaluates the cons of the car and the evlis cdr of the expression which means that if the car and the evlis of the cdr expression return same expression then the "everything else" function runs forever -- but now I check for that and it doesn't run forever.  But, it's easy enough to evaluate other things that evaluate forever.  I think that other Lisps do more type checking and terminate with a error before getting into an infinite loop.  This Lisp is in development so many things are experiments at the moment.  I have a few extraneous functions added in for debugging, experimenting, and for the fun of putting colored blocks on the screen:

Apple Computer
(CLEAR SCREEN) ; clears the text screen
(TEXT) ; puts the screen in text mode
(GR) ; puts the screen in lores graphics mode
(COLOR color-number) ; sets the current lores color
(PLOT x y) ; plots a block on the lores screen
(PEEK memory-address) ; gets an eight bit numeric value
(DEBUG [ON | OFF]) ; turns printed debugging information on and off
(AUTOQUOTE [ON | OFF]) ; turns autoquote on and off
Autoquote determines whether things that are undefined return themselves or return nothing (or an error message.)  So for example, with AUTOQUOTE ON, typing HELLO WORLD returns HELLO WORLD.
(HELP) ; displays some help
(QUIT) ; quits

Apple Computer

There are a few extra debugging and error messages that get printed at the moment.

Evlis has left the building

Saturdaλ, Julλ 24, 2010

Some tail recursion to implement evlis and the "everything else" function is not so easy because it runs forever.

a]];  T ⇒ eval [cons [assoc [car [e]; a];
evlis [cdr [e]; a]]; a]];

evlis[m; a] = [null[m] ⇒ NIL; Tcons[eval[car[m]; a]; evlis[cdr[m]; a]]]

some related links:
Lisp in Ruby { |one, step, back| }
Lisp in Common Lisp by Paul Graham
Lisp in Small Pieces by Christian Queinnec

Is that pixel green?

Thursdaλ, Julλ 22, 2010

Some tail recursion to implement evcon and a cond function is easy.

eq [car [e]; COND] ⇒ evcon [cdr [e]; a];
evcon[c; a] = [eval[caar[c]; a] ⇒ eval[cadar[c]; a]; Tevcon[cdr[c]; a]]


Mercurrλ, Julλ 21, 2010 4:22 PM

Time to add a little color to these postings...

this code may have adverse side effects

more coding

Sundaλ, Julλ 18, 2010 10:00 PM

In between summer, I manage to sneak in coding the eq function.  quote and atom were coded a few posts back, but the internal car and cdr functions were still a bit flaky.



Fridaλ, Julλ 16, 2010 10:00 PM

I am deep in the process of implementing John McCarthy's Lisp using the recursive document from April 1960.  Any questions?  RTFM: read the fine manual.  There are some older documents by McCarthy from the late 1950's describing an Advice Taker system that could make deductions.  I am sticking with what's in the recursive document, for now.

The other half of this retro challenge is that my implementation is being done on an Apple II+ emulator called Catakig.  Catakig has a bit of a bug when pasting from the clipboard.  It locks up if you paste too much text.  And, it doesn't handle newlines very well.  So, I am really stuck with manually typing right from the emulator, sort of like using an original Apple II+ but not quite.  I feel that I am cheating a bit using a modern computer.  Rather than a flickery old TV, or composite monitor instead the screen is a small window on a bright flat screen.  And, the keyboard works.  I envy but also pity the other retro challengers using actual retro hardware. 

This is pretty much a retro software challenge with the added twist of using an emulation of a machine from the late 1970's.  I could be implementing Lisp in C, python, Scheme, or Lisp itself, but that would be cheating because most of it's done already.  McCarthy's document is thorough but not long winded, and it includes enough code and examples for me to understand the concepts.  I think that there are a few really big things that Lisp assumes.  It assumes there is already some kind of stack machine to make function calls and pass parameters.  I think that it assumes some kind of garbage collector.  And, there are a lot of little subtle things that are "undefined."  Software developers usually frown upon things that are undefined.  Anyways, I am trying to keep the software developer away from thinking too much about this stuff, and I am actively being the hacker coding.  Less thinking, more coding.

car cdr
page 17 says it all

car could 'er tell me more

Sundaλ, Julλ 11, 2010
Save soon, save often.  SAVE LISP.  Discarded the quit command from my second posting, but the READ function now quits when ConTRL-Q is pressed.  Whitespace: return, linefeed, tab, and of course space; are all treated as spaces.
car cdr


post meridiem — Saturndaλ, Julλ 10, 2010
66 This notation is writable and somewhat readable. It can be made easier to read and write at the cost of making its structure less regular. If more characters were available on the computer, it could be improved considerably. 4 99

9000 N = 95
9001  HGR : HCOLOR= 4
9002  FOR I = 1 TO 191 STEP 2           
9003  HPLOT 0,I TO 279,I: NEXT          
9004 D = 3                              
9005 S = N / D                          
9009  FOR I = 0 TO N                    
9010  HCOLOR= 3                         
9011 X = I + S                          
9012 Y = I * 2                          
9013  HPLOT I,Y TO X,Y                  
9015  IF I >  = N / 2 THEN 9021         
9016 Y = (N - I) * 2 + 1                
9017  HPLOT I,Y TO X,Y                  
9021 Y = I * 2 + 1                      
9025  HCOLOR= 7                         
9027  HPLOT I,Y TO X,Y                  
9029  IF I >  = N / 2 THEN 9040         
9030 Y = (N - I) * 2                    
9031  HPLOT I,Y TO X,Y                  
9040  NEXT : VTAB 24                    
9050  POKE  - 16302,0                   
4 1995: More characters were made available on SAIL and later on the Lisp machines.  Alas, the world went back to inferior character sets again—though not as far back as when this paper was written in early 1959.
- from page 16 of the recursive document


ante meridiem — Saturnday, July 10, 2010

1  GOSUB 1000" INIT
10  REM
12  REM
20  GOSUB 2000" READ
30  GOSUB 100"  EVAL
40  GOSUB 3000" PRINT
50  GOTO 20"    LOOP

3010  LET L =  LEN (R$)
3030  RETURN

>1 2 3
> ( )
> ( 1 2 3 )
1 2 3

types of distraction — coloroid

Mercuryday, July 7, 2010

I am getting almost totally distracted.  I modified COLOROID for APPLE //E to run on the Apple ][+.

cdhAPPLE2: coloroid
Back to LISP.  I am thinking about types in Lisp, specifically the types that appeared in the original Lisps:

the dimming of the stars, entropy and what that may entail

Moonday, July 5, 2010
The Last Question by Isaac Asimov © 1956

progress: I am not quitting, but there is a quit command

Friday, July 2, 2010
I've given this lisp a quit command.  Well this lisp is just a REPL at the moment.  It parses atoms and lists.  It needs to recognize empty lists.

so it begins

Thursday, July 1, 2010 (Canada Day)
canada day

countdown to madness

4:59:35 PM PST, Wednesday, June 30, 2010
the code is going to hit the road.


Saturday, June 19, 2010

name/handle = Mark Stock/mmphosis, geographical location,
and a *brief* description of my intended project:

1 document named recursive
an Apple II+ emulator named Catakig
see what happens

a link!
to my bbs/webpage/blog/phlog/twitter
or whatever I'm using to document my progress.

RetroChallenge Winter Warm-up 2008
2007 Old Computer Challenge