git @ Cat's Eye Technologies Flobnar / master README.markdown
master

Tree @master (Download .tar.gz)

README.markdown @masterview rendered · raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
Flobnar
=======

_Version 0.1, Chris Pressey, Oct 28 2011_

One day in September of 2011 -- though I'm not sure precisely which
one -- marked Befunge-93's 18th birthday.  That means that Befunge is
now old enough to drink in its native land of Canada.

To celebrate this, I thought I'd get Befunge-93 drunk to see what
would happen.

What happened was _Flobnar_, an esolang which is in many respects a
functional dual of Befunge-93; most of the symbols have analogous
meanings, but execution proceeds in a much more dataflow-like fashion.

This document describes Flobnar with a series of examples, presented
in the format of Falderal 0.7 tests.

Concepts
--------

A familiarity with Befunge-93 is assumed in this document.  Also,
some concepts need to be explained before the description of the
examples will make much sense.

Like Befunge-93, Flobnar programs are held in a playfield -- a
two-dimensional Cartesian grid of cells, each of which contains a
symbol.

Any cell in a Flobnar playfield may be evaluated.  The meaning of
the evaluation of a cell depends on the symbol it contains.  In the
context of execution, this symbol is called a term.

Except for the first term to be evaluated, all terms are "evaluated
from" one of the four cardinal directions: north, south, east, and
west.  The direction provides context: a term may evaluate to a
different value depending on what direction it is evaluated from.

When we say something about "what the cell to the /d/ evaluates to",
where /d/ is a direction, it is implied that that cell is evaluated
from the direction opposite to /d/.  So, "what the cell to the north
evaluates to" means "what the cell to the north evaluates to, when
evaluated from the south."

In addition, when we say "what the cell on the other side evaluates
to", we mean this to be relative to the direction the current term
was evaluated from.  So, if the term was evaluated from the east,
the "cell on the other side" refers to the cell to the west, as
evaluated from the east.

Flobnar is not a purely functional language; it permits input and
output, as well as self-modification, just like Befunge-93 does.
For this reason, order of evaluation should be completely defined.

Flobnar Tests
-------------

    -> Tests for functionality "Interpret Flobnar program"

    -> Functionality "Interpret Flobnar program" is implemented by
    -> shell command
    -> "bin/flobnar %(test-body-file)"

Basics of Execution
-------------------

Whereas in Befunge-93 `@` indicates a stopping point of the program,
in Flobnar, `@` indicates the starting point.  The program evaluates
to whatever the `@` it contains evaluates to.  The `@` evaluates to
whatever is west of it evaluates to.

    | 4@
    = Result: 4

The program must contain one and only one @.

    | 4
    ? Program does not contain exactly one @

    | 4@@
    ? Program does not contain exactly one @

Simple Constant Data
--------------------

As in Befunge-93, single digits evaluate to the common decimal
interpretation of themselves as numbers.  You've already seen this
for 4, but it's true for all of them.

    | 0@
    = Result: 0

    | 1@
    = Result: 1

    | 2@
    = Result: 2

    | 3@
    = Result: 3

    | 5@
    = Result: 5

    | 6@
    = Result: 6

    | 7@
    = Result: 7

    | 8@
    = Result: 8

    | 9@
    = Result: 9

Playfield Traversal
-------------------

Whereas in Befunge-93 `><^v` change the direction of the motion
of the IP, in Flobnar these characters evaluate to what the
appropriate adjacent cell evaluates to:

    < evaluates to whatever is west of it evaluates to
    > evaluates to whatever is east of it evaluates to
    v evaluates to whatever is south of it evaluates to
    ^ evaluates to whatever is north of it evaluates to

    | 4<<<<<@
    = Result: 4

    | >>>>>v
    | ^    v
    | ^    4
    | ^<<<<@
    = Result: 4

Also, ' ' (blank space) evaluates to whatever the cell on the other
side of it evaluates to.  So, for example, if evaluated from the
south, it evaluates to what the north of it evaluates to.

    | 4    @
    = Result: 4

    | >    v
    |       
    |      4
    | ^    @
    = Result: 4

Cells which are not specified are considered to contain blank space.
(In the example below, the two middle lines have nothing in them, not
even blank space.)

    |     v@
    | 
    | 
    | 4   <
    = Result: 4

Like Befunge-93, there is toroidal wrapping of evaluation: if we try
to evaluate something outside the bounds of the playfield, we end up
evaluating whatever is directly on the other side of the playfield.
Unlike Befunge-93, however, the bounds of the playfield are determined
solely by the minimal bounding box that encompasses all the non-' '
terms in the playfield.

    | @4
    = Result: 4

    | v@
    | <  v
    |   ^<
    |   4
    = Result: 4

There's a "Bridge" term, similar to Befunge's `#` instruction.  It
evaluates to whatever is one cell past the other side of it.

    | 5     6#@
    = Result: 5

    |  7v @
    | v8#<
    | >#9 v
    |   >^ 
    |  ^  <
    = Result: 7

And `#` is compatible with wrapping.

    | #@   56
    = Result: 5

And we were serious when we said that thing about how the bounds of
the playfield are computed.

    |             
    |     v   @   
    |    #<  17   
    |             
    = Result: 1

Arithmetic
----------

The `+` term evaluates whatever is to the north of it, then evaluates
whatever is to the south of it, and evaluates to the sum of those
two resulting values.

    | 5
    | +@
    | 7
    = Result: 12

    | 5<<    
    |   +<<  
    | 7<< +<@
    |    6<  
    = Result: 18

The `*` term evaluates whatever is to the north of it, then evaluates
whatever is to the south of it, and evaluates to the product of those
two resulting values.

    | 5
    | *@
    | 7
    = Result: 35

The `-` term evaluates whatever is to the north of it (and we call that
/a/), then evaluates whatever is to the south of it (and we call that /b/).
It evaluates to the difference, /a/ - /b/.

    | 7
    | -@
    | 5
    = Result: 2

Subtraction resulting in a negative value.

    | 1
    | -@
    | 9
    = Result: -8

The `/` term evaluates whatever is to the north of it (and we call that
/a/), then evaluates whatever is to the south of it (and we call that /b/).
It evaluates to the quotient of dividing /a/ by /b/.

    | 8
    | /@
    | 2
    = Result: 4

Integer division rounds down.

    | 9
    | /@
    | 2
    = Result: 4

Division by zero evaluates to whatever the cell on the other side
of the `/` term evaluates to.

    |  9
    | 7/@
    |  0
    = Result: 7

    | v9#@
    | >/7
    |  0
    = Result: 7

The `%` term evaluates whatever is to the north of it (and we call that
/a/), then evaluates whatever is to the south of it (and we call that /b/).
It evaluates to the remainder of dividing /a/ by /b/.  This operation is
called "modulo".

    | 8
    | %@
    | 3
    = Result: 2

Modulo of a negative value has the sign of the dividend.

    |  7
    | 0%@
    | +<
    | 3
    = Result: 1

    |  7
    | 0%@
    | -<
    | 3
    = Result: 1

Modulo by zero evaluates to whatever the cell on the other side
evaluates to.

    |  9
    | 7%@
    |  0
    = Result: 7

    | v9#@
    | >%7
    |  0
    = Result: 7

Decision Making
---------------

'Horizontal if', denoted `_`, checks what the cell on the other side
of it evaluates to.  If that value is nonzero, it evaluates to what
the cell west of it evaluates to; otherwise, it evaluates to what the
cell east of it evaluates to.  In either case, at most two evaluations
are made.

    |  0
    | 5_9
    |  ^@
    = Result: 9

    |   7
    | 
    | 5 _ 9
    | 
    |   ^@
    = Result: 5

    |   v<
    | 
    | 5 _ 9
    | 
    |   7^@
    = Result: 5

'Vertical if', denoted `|`, checks what the other side of it evaluates to.
If that value is nonzero, it evaluates to what the cell north of it
evaluates to; otherwise, it evaluates to what the cell south of it
evaluates to.  In either case, at most two evaluations are made.

    |  3
    | 0|@
    |  4
    = Result: 4

    |   3
    | 
    | 9 | @
    | 
    |   4
    = Result: 3

    |   3
    | v   @
    | > | 9
    | 
    |   4
    = Result: 3

These "if"s can be used to evaluate a cell for its side-effects only.
In the following, the sum is evaluated, but the result is effectively
thrown out, in preference to the zero.

    | 90 <
    | +|@
    | 9> ^
    = Result: 0

Like Befunge-93, `!` is logical negation: it evaluates to zero if the
cell on the other side evaluates to non-zero, and to one if the cell on
the other side evaluates to zero.

    | 0!@
    = Result: 1

    | >  v
    | ^@ !
    |    9
    = Result: 0

We don't need greater than, because we can subtract one value
from other, divide the result by itself (specifying a result of 0
if the division is by zero), then add one, and check if that is
non-zero or not with a horizontal or vertical if.

But because Befunge-93 has it, we have it too.  The <code>`</code> term
evaluates whatever is to the north of it (and we call that /a/), then
evaluates whatever is to the south of it (and we call that /b/).  It
evaluates to 1 if /a/ is greater than /b/, 0 otherwise.

    | 8
    | `@
    | 7
    = Result: 1

    | 8
    | `@
    | 8
    = Result: 0

    | 8
    | `@
    | 9
    = Result: 0

`?` picks one of the cardinal directions at random and evaluates
to whatever the cell in that direction evaluates to.  `?` should
use a fair distribution of the four possible choices, and should
be difficult to predict.  We will not present this as a testable
example program, because the Falderal test framework doesn't
provide a way to test that, currently.  (And it's not implemented
yet, but never mind that.)  Instead, here is a plain example.

     1
    2?3#@
     4

The above program should evaluate to 1 25% of the time, 2 25% of
the time, 3 25% of the time, and 4 the rest of the time.

Introspection and Self-Modification
-----------------------------------

Just like Befunge-93, program introspection and self-modification
are fully supported.

The `g` term evaluates to the north to get an x coordinate, then
to the south to get a y coordinate, and evaluates to the ASCII value
of the symbol that's found in that cell in the playfield.  The origin
(coordinates (0,0)) of the playfield is the upper-left corner of that
bounding box I mentioned above, and x values increase to the right,
and y values to the south.

    | A0
    |  g@
    |  0
    = Result: 65

The `p` term evaluates to the north to get an x coordinate, then
to the south to get a y coordinate.  It then evaluates what is on
the other side of it to get a value.  It then alters the playfield
in effect, by placing that value at that (x,y) coordinate.  The
coordinate system is the same as that used by `g`.  The `p` term
always itself evaluates to zero.

    |    0
    |   5p  @
    |    0
    = Result: 0

    |    0
    |  5 p  <
    |    0  +@
    |    g  <
    |    0
    = Result: 5

    |    0
    |  > p 5
    |  +@
    |    0
    |  > g
    |    0
    = Result: 5

Writing a space over an existing cell deletes that cell, and affects
the calculation of the bounds of the playfield.

    | 85   5
    | *p<
    | 40+@
    |   >  +
    |      9
    |      9
    = Result: 18

    |      5
    | 85   #
    | *p<
    | 40+@
    |   >  ^
    |      6
    |      9
    = Result: 6

Writing outside the bounds of the playfield expands those bounds.
Since only cardinal directions are allowed in evaluation, the space
is still topologically a torus; no Lahey-space-like construction
is necessary.

    |  99> v  
    | 7p*^@ >>#
    |  16  >+
    |       <^
    = Result: 7

Every cell in the playfield can hold a signed, unbounded integer.

    | c 00
    |   -p  <
    |   90  +@
    |    g  <
    |    0
    = Result: -9

    |  9
    |  *< 0
    |  9* p  <
    |  *< 0  +@
    |  9  g  <
    |     0
    = Result: 6561

(One consequence of the above two facts is that there are at least
two tactics available for demonstrating that Flobnar is Turing-
complete; the playfield could be used as a tape in the simulation
of a Turing machine, or two cells could be used as registers in
the simulation of a Minsky machine.)

Evaluating a cell whose value is not the ASCII value of any of the
characters which denote terms defined in this document is a
runtime error, which results in the immediate termination of the
program, without producing a result value.

    9  
    *<5
    9*p<
    *<0+@7
    9  > v

The above program will result in a runtime error.

Functions
---------

There's no real equivalent to Befunge-93's `:`, because there's no
need.  Common subexpressions can be shared geometrically.

    | v<
    | 5+@
    | ^<
    = Result: 10

Likewise, there are no equivalents for `\` and `$`.  Therefore, these
symbols have different meanings in Flobnar.

Originally, my idea for Flobnar included function values (lambda
functions.)  But eventually these struck me as un-Befunge-like.
A function is just some code you want to be able to evaluate more
than once without repeating verbatim.  And in the context of Befunge,
a function is just a part of the playfield.  It's already possible
to execute the same part of the playfield from different points in
your program, using arrows; and in Flobnar this is even easier,
since evaluation of a part of th playfield "remembers" where it was
"evaluated from".

What's really useful in a function is that it can take an argument.
So I retained the idea of having arguments available -- a call stack.
Surprisingly, it turned out to be similar to Befunge-93's stack, so I
consider that a bonus.

The `\` term takes what to the south of it evaluates to, and uses
that as the argument as it "applies" the "one-argument" "function" on
the other side of it.  The `:` term evaluates to the current argument.

    | 5\@
    |  0
    = Result: 5

    | :
    | +\@
    | 54
    = Result: 9

    | v 1#  \ @
    | > +      
    |       
    |   :   7  
    = Result: 8

    | > v :
    | ^@>\*
    |    7:
    = Result: 49

If no function is being applied, `:` evaluates to zero.

    | :@
    = Result: 0

A function can call another function.  The outer function retains its
argument after the inner function returns.

    | 1
    | +\<
    | :4+\@
    |   :7
    = Result: 12

Hellooooo, factorial!

    | >     v
    | ^\ <   
    |        
    | :v    v   \<@
    | -<      : 6
    | 1 :   > *
    |   -|    <
    |   11
    = Result: 720

The `$` term removes the top value from the call stack and "calls" the
"function" on the other side with this reduced call stack.  This, in
effect, lets you write functions which take multiple arguments.

    | :
    | +\<<\@
    | :7  9
    = Result: 14

    | :
    | $
    | +\<<\@
    | :7  9
    = Result: 16

Input and Output
----------------

Flobnar supports input and output of ASCII characters, although
because the Falderal test framework doesn't handle tests with
input very well (and because I would have to refactor my beautiful
implementation in a major way, either threading an IO monad
through all the evaluation functions, or converting those
functions to continuation-passing style), they are only briefly
covered here, with only plain examples.  My apologies if they are
not very well defined; a future version of the language and the
test suite may attempt to rectify that.

The `,` term evaluates what is on the other side of it and
outputs the character with that ASCII value to standard output.
The `,` term itself evaluates to zero.  So, the following
example should output the two-character string 'Hi', and evaluate
to a result of zero.

    8
    *,<  5
    9 +@>*
      >,*7
        3

Note that the convention of the result of each program being
printed after "Result: ", in the tests here, is merely a convention.
What the implementation does with the result of the main Flobnar
expression is outside the domain of Flobnar proper.  (Of course,
it is extremely useful if it can make this value available to the
outside world somehow, for example by outputting it after the
string "Result: ".)

In similar vein, attempting to output and integer outside the range
of ASCII is, as of this writing, undefined.

The `~` term reads a character from standard input and evaluates
to the ASCII value of that character.  So, the following program
reads two characters, and evaluates to 1 if they are the same
character, and 0 if they are not.

    ~
    -!@
    ~

Putting these two together, the following program should be the
virtual equivalent of the Unix `cat` utility:

    ~,<
      +<@
      >^

Other Things
------------

The terms denoted by all characters not mentioned in the above
sections are undefined.  For maximum compatibility with future
versions of Flobnar, they should not appear in a Flobnar program.

Specifically, I have a vague idea that extensions to Flobnar
may be indicated by the presence of a certain characters or
combination of characters immediately and non-wrappingly to
the east of the `@` term.  So, best to leave that cell blank or
make it an arrow.

As you've probably noticed, I've referred to the character set
as ASCII in this entire document.  I actually mean "printable
ASCII" -- control characters and whitespace (aside from space
and linefeed) are not defined, and (except for specific cases
addressed in this document) an implementation is not expected
to load them into the playfield.  If at some point Flobnar is
ever extended into the realm of Unicode, source files will be
expected to be encoded in UTF-8.

To be really true to Befunge-93, Flobnar should support `.` for
outputting integers formatted in conventional decimal notation,
and `&` for inputting integers in that format too.  They may
appear in a future version of the language.  On the other hand,
they may not.  I can't see the future.

After all that, the only thing from Befunge-93 that's missing a
counterpart in Flobnar is stringmode.  I originally added it to
Flobnar, having each string evaluate to a string value, but that
complicated evaluation rules by adding a new type that would have
to be handled everywhere.  I afterwards considered making it more
like ':', pushing the ASCII value of each character onto the call
stack, but decided that was a little awkward too.  So, for
simplicity, I just left it out of this version.

That's All
----------

Happy bar-hopping!  
Chris Pressey  
Evanston, Illinois  
October 28, 2011