% turtle_geometry.ps  -- by leonardo maffi, V.1.1, Oct 22 2006.

% This code defines some helper functions, the basic functions of
% the Turtle Geometry, and then few demo images, using the tutle geometry,
% of Koch and Hilbert I curves, a Sierpinski triangle, etc.
% With this turtle geometry framework it's easy to create other ideas and images.

% In this code I have added many explanations and comments, so hopefully this
% code will be readable by people that don't know the PostScript language too.
% This code can be read from any text editor, but an automatic syntax
% coloration may help the readability a lot. For example, this is the syntax
% for TextPad:
% http://www.textpad.com/add-ons/files/syntax/ps.zip

% To see the results (an image) of this program you can use the (free)
% GhostScript program:
% http://www.cs.wisc.edu/~ghost/
% PhotoShop V.6 refused to load this page, and Paint Shop Prop 6 produces
% a quite wrong image (it's not easy to implement PostScript correctly).

% This is my first PostScript (PS) program, so surely here there are
% some not idiomatic things, or things that can be improved.
% More information on PostScript:
% http://en.wikipedia.org/wiki/PostScript
% A very good introduction:
% http://www-cdf.fnal.gov/offline/PostScript/BLUEBOOK.PDF
% PS language is essentially a form of Forth, like the Forth-like
% language used in some HP calculators, and it's good enough, it's not
% nice as more modern and more powerful languages like Python, but with
% some care all kinds of programs can be created in a reasonable time.
% PS is way simpler and nicer than assembly.
% But PS has a lower level than the Forth-like language used by HP48+
% calculators, because its operators are less explicit and the local
% variables have to be managed in a partially manual way (and probably for
% other things too).

% PS is interpreted. But with a compiler like ShedSkin:
% http://sourceforge.net/projects/shedskin/
% http://shed-skin.blogspot.com/
% PS can probably partially compiled (probably the stack has to be dynamic
% anyway, but a ShedSkin-like compiler can often find the type of most or
% all variables (names)). This can speed up the execution. A Psyco-like
% (http://psyco.sourceforge.net/ ) compiler can probably be created too.


% Few operators and helper functions ==========================================

% Coming from other languages where + is the sum, and * is the multiplication,
% I have chosen to implement aliases for the main operators. Forth allows to do
% this too, it can be quite good.
% Forth is a language that shares some good things with Lisp-like languages,
% Lisp uses prefix syntax, and uses () to group things, so in Lisp you can do:
%   (< 1 5 7 55)
% That returns true. The < is a function that operated on an arbitrary number
% of operators. The () denote how many parameters to apply it on.
% Forth uses a postfix syntax, and spares the use of parenthesis, but this requires
% Functions to use e defined number of parameters. The programmer has to remember
% how many parameters every operator or word (the procedures) uses. In PS you do:
%   1 5 lt

% I have defined swap, dup2 and sto, because they are words of HP48 language too,
% that I have used for few years.

/+ { add } def
/- { sub } def
/* { mul } def
/\ { div } def        % (float or integer division).
/swap { exch } def    % Exchange the two last elements in the stack.
/dup2 { 2 copy } def  % Duplicate the two last elements in the stack.
% /< { lt } bind def  % Can't be done
/sto { def } def

% Show integer or float
% To show a number you have to cast it inside an already present string.
% The string must be long enough to contain the number. This function helps to
% print integer numbers and floating point numbers too.
% len string max = 12 (no spaces in front).
% Parameteres: n
% Requires you to have already defined a point (with moveto) and font.
/shownum { 12 string cvs show } def

% I have started to create such names (savestack/loadstack) as an idea
% to improve 'safety' of procedures. Cleaning the stack after formal parameters
% are used allows to catch a certain kind of error: the code inside the
% procedure can't 'eat' (use) other items inside the stack, if it tries to do it
% a clear error is generated. The following names aren't tested.
/savestack { count array astore /tmpstack def } def % To be tested! ***********
/loadstack { /tmpstack aload pop } def % To be tested! ***********

% Turtle geometry ==========================================

% Basic definition for a 2D turtle geometry. Other routines can be added.
% Path filling can probably be added too, but it requires some work, because
% at the moment turtle paths are a series of independent segments.

% Makes the turtle go back to its home
% Turtle global state (they must be global variables!)
/home {
  /turtle_angle 90.0 store  % turtle heading (degrees. 0 = point up).
  /turtle_xpos 100.0 store  % turtle x position.
  /turtle_ypos 100.0 store  % turtle y position.
  /turtle_penup false store % turtle pen state.
} def
% Here and everywhere else I have to modify such turtle state I have had to use
% 'store' instead of 'def', to avoid problems when these routines are called
% from other routines that define a dict of local variables.

home % Turtle global state initialisation.


% Turtle left turn (degrees)
% I do the % 360.0 float modulus to avoid the angle to grow too much.
% Note that the result of such modulus is in (-360.0, 360.0).
/L {
  turtle_angle swap +
  dup 360.0 \ truncate 360.0 * - % float modulus
  /turtle_angle swap store
} def

% Turtle right turn (degrees)
/R {
  turtle_angle swap -
  dup 360.0 \ truncate 360.0 * - % float modulus
  /turtle_angle swap store
} def


% Turtle forward (steps)
% This routine isn't as fast as possible, it defines some variables (unless
% otherwise specified, all variables are global. So here len, newx, newy
% are global too. So you don't want to use the same names inside the main code)
% because I have seen that for this routine the faster alternative (that is
% using just the stack) makes the code too much difficult to debug (I am a newbie
% in PS).
% I have chosen to not implement 'forward' 'left', etc, aliases, because this is
% enough, and there are less names to remember, that clutter the namespace too.
/F { 0 begin
  /len swap def
  /newx turtle_xpos turtle_angle cos len * + def
  /newy turtle_ypos turtle_angle sin len * + def
  turtle_penup not {
    newpath
    turtle_xpos turtle_ypos moveto
    newx newy lineto
    stroke
  } if
  /turtle_xpos newx store
  /turtle_ypos newy store
end } def
/F load 0 3 dict put
% This routine uses a trick from page 133 of the PS "Bluebook" (PS TUTORIAL
% and COOKBOOK). It is a way to define a single (once) local namespace (dict)
% for local names (variables). This trick can't be used for recursive
% functions, but for normal functions like this one it's good and avoids
% the 'len', 'newx' and 'newy' names to leak in the global namespace.
% The first 0 inside the routine is a just a makespace. Just after the routine
% that 0 is replaces by a dict defined outside, where the local 'side 'name
% goes.
% Maybe a new 'defstatloc' word can be defined to do automatically
% this kind of static local variable management.


% Turtle back (steps)
/B { 0 begin
  /len swap def
  /newx turtle_xpos turtle_angle cos len * - def
  /newy turtle_ypos turtle_angle sin len * - def
  turtle_penup not {
    newpath
    turtle_xpos turtle_ypos moveto
    newx newy lineto
    stroke
  } if
  /turtle_xpos newx store
  /turtle_ypos newy store
end } def
/B load 0 3 dict put

% Turtle penup, the turtle moves not drawing.
% No input parameters
/PU { /turtle_penup true store } def

% Turtle pendown, the turtle moves drawing.
% No input parameters
/PD { /turtle_penup false store } def

% To set the turtle in an absolute position.
% (Its heading doesn't change).
% Parameteres: x y
/setxy {
  /turtle_ypos store
  /turtle_xpos store
} def

% Changes the turtle angle in an absolute way.
% Input: heading (degrees)
/head {
  dup 360.0 \ truncate 360.0 * - % float modulus
  /turtle_angle store
} def

% Print turtle state at the current turtle position. Useful for debugging.
% It uses the current colour, but it changes the current font.
% No input parameters.
% Maybe a gsave grestore can be used too to not modify the font, etc.
/tstate {
  % Set font, and font size.
  /Courier-Bold findfont 10 scalefont setfont
  turtle_xpos turtle_ypos moveto
  ([Turtle: Ang:) show turtle_angle shownum (, ) show
  (X:) show turtle_xpos shownum (, ) show
  (Y:) show turtle_ypos shownum (, ) show
  turtle_penup {(Pen:Up]) show} {(Pen:Down]) show} ifelse
} def

% Turtle show. No input parameters.
% The turtle is shown black with default thickness.
% Useful to show the turtle at the end of the drawing.
% It changes the line colour, turtle position and heading, pen thickness,
% pen up/down state too.
/tshow {
  0.5 setlinewidth
  0.0 0.0 0.0 setrgbcolor
  PD
  90 R 3 F
  105 L 6 F
  150 L 6 F
  105 L 3 F
} def

% Points the turtle toward a given x y point (to be implemented ***************)
/towards {
} def

% To change the scale of the turtle steps (to be implemented ***************)
% To implement this, the F and B routines have to be changed too.
/tscale {
} def

% Few basic turtle geometry shapes ==========================================

% I have used such basic routines to debug the tutle geometry framework.

% Draw a square
% Input: side
/square { 0 begin
  /side swap def
  side F 90 R
  side F 90 R
  side F 90 R
  side F
  %tstate
end } def
/square load 0 1 dict put


% Draw an exagon
% Input: side
/exagon { 0 begin
  /side swap def
  side F 60 R
  side F 60 R
  side F 60 R
  side F 60 R
  side F 60 R
  side F
end } def
/exagon load 0 1 dict put


% Draw a 'house'
/house {
  30 B 90 R
  30 F 90 L
  30 F 90 L
  30 F 120 R
  30 F 120 R
  30 F
} def

% Sierpinski triangle ==========================================

% Parameters: global_size, level (Example: 150 6)
/sierpinski { 2 dict begin % this allocates new VM each time
  /level swap def
  /size swap def

  level 0 gt {
    3 {
      size 2 \ level 1 - sierpinski
      size F
      120 R
    } repeat
  } if
end } def

% sierpinski (and others below) is a recursive routine. I think this is the
% best/simpler way to make recursivity work in PS. Here I define a new local dict
% each time the routine is called. Hopefully GhostScript frees virtual memory not
% used anymore.

% The '2 dict begin' at the beginning creates a local dict able to contain 2 names,
% so the following two defs are relative to such dict, so they are local names.
% At the end, just before the final } the 'end' pops the dict, so the normal namespace
% can be used again. In PS there are 1-2 other ways to create local variables, they
% require less memory (only 1 namespace is created for each routine) but they don't
% seem fit to for recusivity.

% On the other hand, this low-level management of namespaces has the advantage
% that you can use them only when you need them, improving the speed and lowering
% the memory needed when you don't need them, or when you need static ones (like
% ones used in routine 'square').

% Maybe a new 'defloc' word can be defined to do automatically
% this kind of local variable management.

% Koch curve ==========================================

% Parameters: step_size, level (Example: 150 6)
/koch { 2 dict begin % this allocates new VM each time
  %F ==> F-F++F-F   (+ = 60 degrees)
  /level swap def
  /size swap def

  level 1 lt {
    size F
  }
  {
    size level 1 - koch
    60 L
    size level 1 - koch
    120 R
    size level 1 - koch
    60 L
    size level 1 - koch
  } ifelse
end } def

% Such functions can be defined with L-Sytems too. Probably it's not that
% difficult to implement the basic L-systems on top of this turtle geometry framework.

% Hilbert curve ==========================================

% Public function
% parameters: step_size level (tried up to level 9, more is probably possible)
/hilbert_curve {
  90 _hilb
} def


% private function
% parameters: step_size level parity
/_hilb { 3 dict begin % this allocates new VM each time
  /parity swap def
  /level swap def
  /size swap def

  level 0 gt {
    parity L
    size level 1 - parity neg _hilb
    size F
    parity R
    size level 1 - parity _hilb
    size F
    size level 1 - parity _hilb
    parity R
    size F
    size level 1 - parity neg _hilb
    parity L
  } if
end } def

% As you can see, having the turtle geometry (and knowing how to define recursive
% routines in PS) it's quite easy and short to define such fractal forms.

% Main program demo ==========================================

/dohilbert {
  0.5 setlinewidth
  0.0 0.8 0.0 setrgbcolor
  90 R PU 50 B PD
  3 6 hilbert_curve % step_size level
} def

/dokoch {
  0.5 setlinewidth
  0.0 0.0 1.0 setrgbcolor
  1 5 koch % step_size level
} def

/dosierpinski {
  0.25 setlinewidth
  0.8 0.0 0.0 setrgbcolor
  150 6 sierpinski % global_size level
} def

/main {
  %50 square
  %30 exagon
  %house
  PU 450 F PD
  dohilbert
  PU 30 F PD
  dokoch
  PU 150 B 90 R 18 F 30 R PD
  dosierpinski
  tshow % show turtle
} def

main

% Necessary, final show of the page.
% All this code creates a single page with default size and
showpage