A Quine in Oberon

One of the courses I took this term was the imaginatively titled "Imperative Programming I" (aka. Programming II as "Functional Programming" - Haskell - was last term). The lecturer for this course is very good, but the language used for this course is one that most people won't have heard of: Oberon 2. The rationale for choosing this language is given here and here - in short saying that "modern" languages (Lua, Python, Ruby, etc.) are too high-level, and languages like C are too hard. After using Oberon for a term, I still have no love for the language (unlike using Haskell for a term, which resulted in some affection for it), and could argue for using C / Lua instead of Oberon for a long time (the Physics dept. teaches their 1st year undergrads C, so it can't be too hard for the 1st year Comp Sci undergrads, and so on...), but doing so wouldn't benefit anyone (as the choice of language is at the lecturer's discretion, and he likes Oberon - as I like Lua).

As previously said, the lecturer for this course is very good. One of the reasons for this is the interesting practical exercises and problem sheets which he set. For example, the last question on the last problem sheet was to "Write an Oberon program that, when you run it, prints out its own source text". The question nicely avoids using the term "quine" (giving that term would allow students to easily search the web for information), but it is asking you to write a quine in Oberon. One simple way to implement a quine is to list each line of the source text as a string literal, along with some logic to reproduce this list of string literals from the string literals themselves, which is what I did:

MODULE Quine;
IMPORT Out;
VAR i: INTEGER; L: ARRAY 13,57 OF CHAR;
BEGIN
L[0]:="MODULE Quine;";
L[1]:="IMPORT Out;";
L[2]:="VAR i: INTEGER; L: ARRAY 13,57 OF CHAR;";
L[3]:="BEGIN";
L[4]:="FOR i := 0 TO 3 DO Out.String(L[i]); Out.Ln END;";
L[5]:="FOR i := 0 TO LEN(L)-1 DO";
L[6]:="  Out.Char('L'); Out.Char('['); Out.Int(i, 0);";
L[7]:="  Out.Char(']'); Out.Char(':'); Out.Char('=');";
L[8]:="  Out.Char(22X); Out.String(L[i]); Out.Char(22X);";
L[9]:="  Out.Char(';'); Out.Ln";
L[10]:="END;";
L[11]:="FOR i := 4 TO LEN(L)-1 DO Out.String(L[i]); Out.Ln END;";
L[12]:="END Quine.";
FOR i := 0 TO 3 DO Out.String(L[i]); Out.Ln END;
FOR i := 0 TO LEN(L)-1 DO
  Out.Char('L'); Out.Char('['); Out.Int(i, 0);
  Out.Char(']'); Out.Char(':'); Out.Char('=');
  Out.Char(22X); Out.String(L[i]); Out.Char(22X);
  Out.Char(';'); Out.Ln
END;
FOR i := 4 TO LEN(L)-1 DO Out.String(L[i]); Out.Ln END;
END Quine.

We can express exactly the same idea in Lua, with the resulting code being shorter and (in my opinion) looking nicer: (largely due to keywords being in lowercase, and assignment using = rather than :=)

L = {
  "L = {",
  "}",
  "print(L[1])",
  "for i = 1, #L do print((\"  %q,\"):format(L[i])) end",
  "for i = 2, #L do print(L[i]) end",
}
print(L[1])
for i = 1, #L do print(("  %q,"):format(L[i])) end
for i = 2, #L do print(L[i]) end

We can of course strip out a a lot of the code in the above, to leave a quine seen in a previous post:

s="s=%q print(s:format(s))" print(s:format(s))

Footnote: I suspect that at least some of the recent updates to the rationale for Oberon were due to some of my comments on the course feedback form. This is great, as it shows that the lecturer is reading and responding to feedback. I'm slightly confused by the statement on that page "I can't stand the 'used to be the bees knees, but is deprecated in version 5.1' business" - I suspect that he is referencing Lua 5.1 as neither Python nor Ruby are anywhere near a version 5.1, yet the list of things changed / made deprecated in Lua 5.1 contains nothing that I would class as "the bee's knees". One could also the discuss the general point of whether languages changing (or, if you prefer, evolving) is a good thing or a bad thing, but again, this is not the place to do so.

Brainfsck in Haskell

Recently, I had to sit an exam which involved questions on/about the functional language Haskell (it was an Oxford start of term exam, also known as a collection, if you're interested). To revise the feel and syntax of Haskell, I decided to write a minimal interpreter for my favourite esoteric language, Brainfsck, in Haskell.

Writing such an interpreter in C/C++ is fairly trivial, with the only slight difficulty being providing an array which is infinitely long in both directions. As Haskell is a functional language (function in the mathematical sense, rather than the sub-procedure sense), providing an infinitely long array is extremely simple, and it is everything else which is non-trivial. The code ends up making heavy use of monadic I/O (ironically, monadic I/O isn't really covered in the course syllabus beyond "you can construct a string and then pass it to putStr to write stuff"), and looks very different to how you'd implement it in C/C++:

code = "++++++++++[>+++++++>+++++++++++>+++>++++++++++<<<<-]>+.>+.>++.<<++++.>.+++.>>+.<+.<<<."

data Token = C Char | L [Token]
join a (b, c) = (a:b, c)
parse ('[':xs) = join (L inner) (parse etc) where (inner, etc) = parse xs
parse (']':xs) = ([], xs)
parse (x:xs) = if elem x "<>+-.," then join (C x) (parse xs) else parse xs
parse [] = ([], [])
evalWith l c r = eval (return (l, c, r))
evalRaw (C '<') (l:ls) c r = evalWith ls l (c:r)
evalRaw (C '>') l c (r:rs) = evalWith (c:l) r rs
evalRaw (C '+') l c r = evalWith l (if c == 255 then 0 else (c + 1)) r
evalRaw (C '-') l c r = evalWith l (if c == 0 then 255 else (c - 1)) r
getCharNoR = getChar >>= \c -> if c == '\r' then getCharNoR else (return c)
eval s ((L  cs):xs) = s >>= (\(l, c, r) -> if c == 0 then (eval s xs) else (eval (eval s cs) ((L cs):xs)))
eval s ((C '.'):xs) = s >>= (\(l, c, r) -> (putStr [toEnum c]) >> (eval s xs))
eval s ((C ','):xs) = s >>= (\(l, _, r) -> getCharNoR >>= \c -> evalWith l (fromEnum c) r xs)
eval s (x:xs) = s >>= (\(l, c, r) -> evalRaw x l c r xs)
eval s [] = s

result = evalWith (repeat 0) 0 (repeat 0) (fst (parse code)) >>= (\_ -> return ())

The parse function (along with its helper, join) is used to perform a first-pass over the Brainfsck code. This removes non-code characters, and performs bracket matching to simplify the evaluation stage. The output of the parse function is a list of tokens, where each token is either a code character, or a loop (which is just another list of tokens). To simplify the implementation of parse, it also returns the tail of the code which it could not understand as a second return value.

The eval function (along with helpers evalWith, evalRaw, and getCharNoR) handles the transformation of the tokenised Brainfsck code into a monadic I/O object representing the evaluation of the Brainfsck code.

Finally, the result function ties everything together. Note the incredibly simple creation of the infinite array - it is just (repeat 0) 0 (repeat 0), which also describes the infinite array fairly well.

CorsixTH - Playable Beta 1

Today marks the release of the first playable beta of CorsixTH, an open source Theme Hospital clone which I started a few months ago.

Relevant links: CorsixTH Homepage | Downloads | Release Annoucement.

Theme Hospital Update

It's been a while since since my first blog post on Theme Hospital, and there has been a reasonable amount of development since then, so I thought I'd post a video showing some of the new stuff:

As before, if you're interested in grabbing a copy, or contributing, then see the Google Code project.

Lua can be ASCII Art

Observe my wonderful Lua ASCII art creation:

                                                                _={_=_G
                                                              }for--[[--]]__
                                                            in(next),_["_"]do
                                                           (_)[_]=(__)_[#_[_]]
                                                          =_[_]_[_]="sub"end(_)
                              [_]=_[_]                    [_[_]]_[_._]=#"_._"_[
                       _[_._]]=_[_](_[_[_._]*_             [_._]],_[_._],_[_._
                    ]).._[_](_[(_[_._]+_[_._]/_[_._         ])*_[_._]],_[_._]/
                _[_._]+_[_._]/_[_._],_[_._]).._[_](_[_       [_._]*_[_._]],_
             [_._]+_[_._]-_[_._]/_[_._],_[_._]+_[_._]-_[       _._]/_[_._]
           ).._[_](_[_[_._]*_[_._]],_[_._],_[_._]).._[_](_[         _
         [_._]*_[_._]],_[_._]/_[_._]-_[_._]           ,_[_._
        ]/_[_._]-_[_._])_[_[_._]*_[_._]+_               [_._]-
      _[_._]/_[_._]]=(_)_[_[_._]*_[_._]+                  _[_._
     ]+_[_._]/_[_._]]=(_)_[#_+_[_._]/_[                    _._]]
    =_._[_[#_-_[_._]-#_/#_]]_[_[#_]]=_[                    #_](_[
   _[_._]].."(".._[#_-#_/_[_._]].."('"                     .._[_[_
  ._]]..[[("\\'..(...+#_*(_[_._]+_[_._]                   ))..'")')
  )()]])_[_[#_]]=_[_[_._]][_[_[#_]](_[_.                 _]*_[_._])
 .._[_[#_]](#_-_[_._]/_[_._]).._[_[#_]](_               [_._]+_[_._]
 +_[_._]/_[_._]).._[_[#_]](_[_._]^_[_._]-_[_         ._])]_[_[_[#_]](
 #_)]=#_*#_/_[_._]_[_[_[#_]](#_)]=_[_[_[#_]](#_)]+_[_[_[#_]](#_)]/_[(
 _._)]_._[_[    _[#_]](_[_[_[#_]](#_)]+#_-_[_._],_[_[_[#_]](#_)]+#_-
 #_/#_,_[_[_[   #_]](#_)]+#_/_[_._],_[_[_[#_]](#_)]+#_-#_/_[_._], _[
 _[_[#_]](#_)   ]+#_+#_/#_)](_[_[#_+_[_._]-_[_._]]](#_*#_/_[_._]-_[_.
 _],_[_[_[#_]   ](#_)]+_[_._]    /_[_.   _],_[  _    [_[#_]](#_)]+#_
 /_[_._]+_[_.   _],_[_[_[#_]](   #_)]+   #_/   _[_.   _]+_[_._],_[_[
  _[#_]](#_)]   +#_-_[_._]-_[_   ._]/_   [_._  ],#_   +#_+_[_._]-_[
  _._]/_[_._]   ,#_*(_[_._]+_[   _._])   -_[_.    _   ],_[_[_[#_]](
   #_)]+#_-_[   _._]-_[_._ ]/_   [_._]   ,_[_   [_[   #_]](#_)]+#_
    -#_/#_,_[   _[_[#_]](  #_)   ]+#_/   _[_   ._]+   _[_._],_[_[
     _[#_]](     #_)],#   _+#_    +#       _    /# _  + #_/#_,_[_
     [_[#_               ]](#_)     ]+_   [_._    ]-_  [_._]/_[_
      ._],_[_[_[#_]](#_)]+#_-_[_._]/_[_._],(_[_._])^_[_._]*(_[
        _._]+_[_._]/_[_._])+_[_._],_[_[_[#_]](#_)]+_[_._]*_[_
         ._],#_+#_+#_/#_+#_/#_,#_*#_/_[_._]+_[_[_[#_]](#_)]/
            _[_[_[#_]](#_)],_[_[_[#_]](#_)]+#_+_[_[_[#_]](
              #_)]/_[_[_[#_]](#_)]+_[_[_[#_]](#_)]/_[_[
                 _[#_]](#_)],_[_[_[#_]](#_)]-_[_._]))
                    _._=_[_[_._]][_[_[_[#_]](#_)]
                         ]_[(#_)^#_-_[_._]]=
                                 _._

As an improvement on my prior post, this valid Lua program has a more interesting whitespace arrangement, has less string literals, and less alphanumeric characters (no "byte" in this code, whereas the previous post does).

page: 15 16 17 18 19