Entries tagged forth

Four years ago somebody posted a comment-thread describing how you could start writing a little reverse-polish calculator, in C, and slowly improve it until you had written a minimal FORTH-like system:

• https://news.ycombinator.com/item?id=13082825

At the time I read that comment I'd just hacked up a simple FORTH REPL of my own, in Perl, and I said "thanks for posting". I was recently reminded of this discussion, and decided to work through the process.

Using only minimal outside resources the recipe worked as expected!

The end-result is I have a working FORTH-lite, or FORTH-like, interpreter written in around 2000 lines of golang! Features include:

• Reverse-Polish mathematical operations.
• Comments between ( and ) are ignored, as expected.
  • Single-line comments \ to the end of the line are also supported.
• Support for floating-point numbers (anything that will fit inside a float64).
• Support for printing the top-most stack element (., or print).
• Support for outputting ASCII characters (emit).
• Support for outputting strings (." Hello, World ").
• Support for basic stack operations (drop, dup, over, swap)
• Support for loops, via do/loop.
• Support for conditional-execution, via if, else, and then.
• Load any files specified on the command-line
  • If no arguments are included run the REPL
• A standard library is loaded, from the present directory, if it is present.

To give a flavour here we define a word called star which just outputs a single start-character:

: star 42 emit ;

Now we can call that (NOTE: We didn't add a newline here, so the REPL prompt follows it, that's expected):

> star
*>

To make it more useful we define the word "stars" which shows N stars:

> : stars dup 0 > if 0 do star loop else drop then ;
> 0 stars
> 1 stars
*> 2 stars
**> 10 stars
**********>

This example uses both if to test that the parameter on the stack was greater than zero, as well as do/loop to handle the repetition.

Finally we use that to draw a box:

> : squares 0 do over stars cr loop ;
> 4 squares
****
****
****
****

> 10 squares
**********
**********
**********
**********
**********
**********
**********
**********
**********
**********

For fun we allow decompiling the words too:

> #words 0 do dup dump loop
..
Word 'square'
 0: dup
 1: *
Word 'cube'
 0: dup
 1: square
 2: *
Word '1+'
 0: store 1.000000
 2: +
Word 'test_hot'
  0: store 0.000000
  2: >
  3: if
  4: [cond-jmp 7.000000]
  6: hot
  7: then
..

Anyway if that is at all interesting feel free to take a peak. There's a bit of hackery there to avoid the use of return-stacks, etc. Compared to gforth this is actually more featureful in some areas:

• I allow you to use conditionals in the REPL - outside a word-definition.
• I allow you to use loops in the REPL - outside a word-definition.

Find the code here:

• https://github.com/skx/foth

Tags: forth, github, go, golang, hackernews | No comments

So my previous post was all about implementing a simple FORTH-like language. Of course the obvious question is then "What do you do with it"?

So I present one possible use - turtle-graphics:

\ Draw a square of the given length/width
: square
  dup dup dup dup
  4 0 do
    forward
    90 turn
  loop
;

\ pen down
1 pen

\ move to the given pixel
100 100 move

\ draw a square of width 50 pixels
50 square

\ save the result (png + gif)
save

Exciting times!

• https://github.com/skx/turtle

Tags: forth, github, go, golang, turtle | No comments

In my previous post I introduced yet another Lisp interpreter. When it was posted there was no support for macros.

Since I've recently returned from a visit to the UK, and caught COVID-19 while I was there, I figured I'd see if my brain was fried by adding macro support.

I know lisp macros are awesome, it's one of those things that everybody is told. Repeatedly. I've used macros in my emacs programming off and on for a good few years, but despite that I'd not really given them too much thought.

If you know anything about lisp you know that it's all about the lists, the parenthesis, and the macros. Here's a simple macro I wrote:

 (define if2 (macro (pred one two)
    `(if ~pred (begin ~one ~two))))

The standard lisp if function allows you to write:

 (if (= 1 a) (print "a == 1") (print "a != 1"))

There are three arguments supplied to the if form:

• The test to perform.
• A single statement to execute if the test was true.
• A single statement to execute if the test was not true.

My if2 macro instead has three arguments:

• The test to perform.
• The first statement to execute if the test was true.
• The second statement to execute if the test was true.
• i.e. There is no "else", or failure, clause.

This means I can write:

 (if2 blah
    (one..)
    (two..))

Rather than:

 (if blah
    (begin
       (one..)
       (two..)))

It is simple, clear, and easy to understand and a good building-block for writing a while function:

 (define while-fun (lambda (predicate body)
    (if2 (predicate)
       (body)
       (while-fun predicate body))))

There you see that if the condition is true then we call the supplied body, and then recurse. Doing two actions as a result of the single if test is a neat shortcut.

Of course we need to wrap that up in a macro, for neatness:

(define while (macro (expression body)
                 (list 'while-fun
                       (list 'lambda '() expression)
                       (list 'lambda '() body))))

Now we're done, and we can run a loop five times like so:

(let ((a 5))
  (while (> a 0)
     (begin
        (print "(while) loop - iteration %s" a)
        (set! a (- a 1) true))))

Output:

(while) loop - iteration 5
(while) loop - iteration 4
(while) loop - iteration 3
(while) loop - iteration 2
(while) loop - iteration 1

We've gone from using lists to having a while-loop, with a couple of simple macros and one neat recursive function.

There are a lot of cute things you can do with macros, and now I'm starting to appreciate them a little more. Of course it's not quite as magical as FORTH, but damn close!

Tags: forth, github, lisp | No comments

Over the past few months (years?) I've posted on my blog about the various toy interpreters I've written.

I've used a couple of scripting languages/engines in my professional career, but in public I think I've implemented

• BASIC
  • https://github.com/skx/gobasic
• evalfilter
  • https://github.com/skx/evalfilter
  • (Basically the same as the bytecode VM of Monkey).
• FORTH
  • https://github.com/skx/foth
• Lisp
  • https://github.com/skx/yal
• Monkey
  • https://github.com/skx/monkey
• TCL
  • https://github.com/skx/critical

Each of these works in similar ways, and each of these filled a minor niche, or helped me learn something new. But of course there's always a question:

• Which is fastest?

In the real world? It just doesn't matter. For me. But I was curious, so I hacked up a simple benchmark of calculating 12! (i.e. The factorial of 12).

The specific timings will vary based on the system which runs the test(s), but there's no threading involved so the relative performance is probably comparable.

Anyway the benchmark is simple, and I did it "fairly". By that I mean that I didn't try to optimize any particular test-implementation, I just wrote it in a way that felt natural.

The results? Evalfilter wins, because it compiles the program into bytecode, which can be executed pretty quickly. But I was actually shocked ("I wrote a benchmark; The results will blow your mind!") at the second and third result:

BenchmarkEvalFilterFactorial-4      61542     17458 ns/op
BenchmarkFothFactorial-4            44751     26275 ns/op
BenchmarkBASICFactorial-4           36735     32090 ns/op
BenchmarkMonkeyFactorial-4          14446     85061 ns/op
BenchmarkYALFactorial-4              2607    456757 ns/op
BenchmarkTCLFactorial-4               292   4085301 ns/op

here we see that FOTH, my FORTH implementation, comes second. I guess this is an efficient interpreter too, bacause that too is essentially "bytecode". (Looking up words in a dictionary, which really maps to indexes to other words. The stack operations are reasonably simple and fast too.)

Number three? BASIC? I expected better from the other implementations to be honest. BASIC doesn't even use an AST (in my implementation), just walks tokens. I figured the TCO implemented by my lisp would make that number three.

Anyway the numbers mean nothing. Really. But still interesting.

Tags: basic, forth, github, lisp, tcl | No comments