Geom

From Esolang
Jump to navigation Jump to search

Geom is a simple esoteric language roughly in the style of Forth. It has a small number of primitive operations, each given by a single character. Geom's unique point (pardon the pun) is that its only datatype are two-dimensional points, and its only operators are Euclidean geometric operations. In other words, the only things that can be done to points is to draw circles and (infinite) lines through them, and find intersections of these.

Geom has a stack, which contains points or nils, and a dictionary, which maps tokens to variables or code. Tokens are space separated. Geom has lexical scoping, so definitions within an executed word do not leak into the calling namespace.

It is unclear whether Geom is Turing-complete.

Operators

 @ Circle
 / Line
 > Variable
 :; Define
 [|] If-then-else
 - Draw

Details

At the start of the program there are two points on the stack: (0,0) and (1,0). Geom remembers the previous geometric operation, and computes the intersection between it and new geometric operations.

Intersections are always placed on the stack in a defined order:

  • Two lines have at most one intersection.
  • Two circles can have two intersections; the first intersection is the first point clockwise from the line which joins the centers of the circles.
  • A line and circle can have two intersections. The first point is the the point in the direction the line is running (even though lines are infinite, they have a direction defined by the order they are defined). If both intersections are on this side of the ray, or both are behind, then the nearest point is returned first. Graphically:


  • @ Circle. a b -- c d

Compute (but don't draw) a circle between the top two stack points, and intersect it with the previous geometric object. Puts two new points on the stack, which can be nil, if there are not enough intersections (e.g. nil, nil if no intersections, pt, nil if one intersection or pt, pt if there are two).

  • / Line. a b -- c d

Compute (but don't draw) an (infinite) line between top stack entries, and intersect with previous line/circle. Puts intersection points back on stack.

  • > Variable. a --

Define variable from stack. Takes top of stack and associates it with the following token. The token will put that value back on the stack the next time it occurs.

  • : Define. --

Defines a new word which will execute a block of code. Format is as Forth: : word definition here ; Can be nested, and definitions will be locally scoped.

  • - Draw arc. a b c --

Draws an arc through the top three stack points, from a -> c with radius b. If a==c, draws a full circle. If a==b, draws a straight line.

  • [ If-then-else. --

Begins a conditional. Form is [ if not nil | if nil ]. If stack top is nil, executes the second part, otherwise executes the first part. Can be nested.

  • . --

Print stack to console. Not really a command, but a handy debugging tool.


Examples

Example (draws a regular hexagon): 

: under > x > y  x y x ;
: drop > _  ;
: neq > a > b a b @ drop drop b a @ drop ;
: hex_segment > x > y  x y @ drop drop y x @ drop > p p p x - p ;
: hex_loop  > x > y y x under hex_segment > p p a neq [ y p hex_loop | ] ;
> a > b b a
hex_loop

Draws some arcs (with debug mode on to show construction lines): 

> a > b a b  @ > _ > _  
b a @ > c > d 
a b c -
c b a - 
b c a - 
c a b - 
c d / > _ > _
a b / > _ > e  
e c e -

Arithmetic

Any constructible number can be evaluated in Geom. Unlike other languages which are based on integer operations, Geom's data type also ranges across rationals and numbers constructible via repeated square-roots. The current implementation uses an underlying floating-point representation, but an algebraic solver could be substituted to perform exact computations.

Some basic arithmetic operations: 

: rem Basic arithmetic in Geom ;

: rem store original points ;
> unit > origin origin unit

: rem Basic stack ops ;
: dup > a a a ;             : rem duplicate stack top ;
: dup2 > a > b b a b a ;    : rem duplicate two top entries ;
: drop_under > a > b a ;    : rem drop second entry ;
: drop > _ ;                : rem drop top entry ;
: drop2 > _ > _ ;           : rem drop top two entries ;
: swap > a > b a b ;        : rem swap top two entries ;

: rem return nil if point are equal ;
: neq > a > b a b @ drop drop b a @ drop ;

: rem extend a line along a vector ;
: extend > a > b a b @ drop2 a b / drop > d a d ;

: rem given a,b,c return if nil if a is not inside a circle from b->c ;
: circle_inside > d > a > b  b a extend > c c a @ drop2 a d @ drop drop_under ;

: rem given a,b produce c, which is the projection from b along a->b ;
: inc > b > a a b @ drop2 b a / > c drop b c ; 

: rem given a,b produce c, which is the projection from a along b->a ;
: dec > a > b a b @ drop2 a b / drop > c c b ;

: rem bisect a,b and return the midpoint ;
: bisect > a > b a b @ drop2 b a @ > c > d a b / drop2 c d / drop > e e ;

: rem given a,b, return c,d where c is twice as far from the origin as b, and d = c + (b-a) ;
: double > a > b origin a inc drop_under origin b inc drop_under > b > a a b bisect a ;

: rem given a,b, return c,d where c is half as far from the origin as b, and d = c + (b-a) ;
: halve > a > b origin a bisect origin b bisect > b > a b a dec drop a  ;

: rem given a,b, return b,c where c = b + ((b-a).y, (b-a).x) ;
: up > a > b  b a @ drop2 a b @ > c > d  b a inc > a > b b a @ drop2 a b @ > e > f d f 
  bisect > g a b @ drop2 g b / drop > h b h ;

: rem given a, return a point b which is sqrt(|b|) away from the origin in the same direction ;
: sqrt > b  unit origin @ drop2 b origin / drop > a  a b bisect > c unit origin up drop_under 
  > p a c @ drop2 origin p / drop_under ;

: rem Examples ;
.       : rem (0,0) (1,0) ;
inc .   : rem (1,0) (2,0) ; 
inc .   : rem (2,0) (3,0) ;
inc .   : rem (3,0) (4,0) ;
inc .   : rem (4,0) (5,0) ;
inc .   : rem (5,0) (6,0) ;
halve . : rem (2,0) (3,0) ; 
inc .   : rem (3,0) (4,0) ;
up  .   : rem (4,0) (4,1) ;
inc .   : rem (4,1) (4,2) ;
dec .   : rem (4,0) (4,1) ;

drop2

: rem square root test ;
origin unit inc drop_under sqrt  ;

: rem insideness test ;

origin unit inc inc inc > p1 drop       : rem p1 = (4,0) ;
origin unit bisect > p2                 : rem p2 = (0.5, 0) ; 

p1 origin unit circle_inside . drop     : nil, p1 not closer to origin than unit ;
p2 origin unit circle_inside . drop     : non-nil, p2 closer to origin than unit ;


Computational class

Ørjan Johansen thinks that Geom is Turing-complete, and has produced a Haskell program to convert a Turing machine into it. The conversion is almost entirely based on Geom's stack language nature; the only use of the geometry commands is in order to produce an initial nil value. It uses the same trick as in reduced instruction Underload of using the call stack as the right side of the tape.

While the result looks plausible, it has not actually been tested with the Geom interpreter, something which would probably require adding useful output of the result.

The output from converting the test Turing machine (Wolfram's 2,3-machine) is: 

: drop > _ ;
: neq > a > b a b @ drop drop b a @ drop ;
> t t t t neq > nil
: swap_blocks > a3 > a2 > a1 > b1 a1 a2 a3 b1 ;
: right_end [ t nil nil t tm_table right_end |
t nil nil nil tm_table right_end ] ;
: tm_table [ [ drop drop t nil nil nil |
[ drop nil nil t t |
[ nil tm_table nil nil t swap_blocks tm_table |
nil nil nil nil ] ] ] |
[ drop drop nil tm_table nil t nil swap_blocks tm_table |
[ drop nil tm_table nil nil t swap_blocks tm_table |
[ nil t nil t |
nil nil nil nil ] ] ] ] ;
nil nil nil
nil
t nil nil swap_blocks tm_table
nil t nil swap_blocks tm_table
nil nil t swap_blocks tm_table
nil t nil swap_blocks tm_table
t nil nil swap_blocks tm_table
right_end

Another plausible method would be using (exact) arithmetic to manipulate unbounded registers for a Minsky machine. Also since Geom has scoped variables, it should be possible to put arbitrary points on the call stack, which means all the methods might be combined to emulate an unbounded tape with cells that can contain points and (in effect) unbounded integers.

Implementation

There is a pure Python implementation which outputs SVG files. It also features a "debug" mode, which shows construction lines and labels points according to their assignment.

http://code.google.com/p/esolang-geom/downloads/list

Geom++

Geom++ extends Geom in several ways, and is definitely Turing-complete.

Retrieved from "https://esolangs.org/w/index.php?title=Geom&oldid=24730"