• foth
  • Features
  • Installation
  • Embedded Usage
  • Anti-Features
  • Implementation Approach
  • Implementation Overview
    • Part 1 - Minimal initial-implementation.
    • Part 2 - Hard-coded recursive word definitions.
    • Part 3 - Allow defining minimal words via the REPL.
    • Part 4 - Allow defining improved words via the REPL.
    • Part 5 - Allow executing loops via do/loop.
    • Part 6 - Allow conditional execution via if/then.
    • Part 7 - Added minimal support for strings.
    • Final Revision - Idiomatic Go, test-cases, and many new words
  • BUGS
    • loops - zero expected-iterations actually runs once
  • See Also
  • Github Setup

foth

A simple implementation of a FORTH-like language, hence foth which is close to forth.

If you're new to FORTH then the wikipedia page is a good starting point, and there are more good reads online such as:

• Forth in 7 easy steps
  • Just ignore any mention of the return-stack!
• Starting FORTH
  • A complete book, but the navigation of this site is non-obvious.

In brief FORTH is a stack-based language, which uses Reverse Polish notation. The basic thing in Forth is the "word", which is a named data item, subroutine, or operator. Programming consists largely of defining new words, which are stored in a so-called "dictionary", in terms of existing ones. Iteratively building up a local DSL suited to your particular task.

This repository was created by following the brief tutorial posted within the following Hacker News thread, designed to demonstrate how you could implement something like FORTH, in a series of simple steps:

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

The comment-thread shows example-code and pseudo-code in C, of course this repository is written in Go.

Features

The end-result of this work is a simple scripting-language which you could easily embed within your golang application, allowing users to write simple FORTH-like scripts. We implement the kind of features a FORTH-user would expect:

• 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).
• Reverse-Polish mathematical operations.
  • Including support for abs, min, max, etc.
• Support for printing the top-most stack element (., or print).
• Support for outputting ASCII characters (emit).
• Support for outputting strings (." Hello, World ").
  • Some additional string-support for counting lengths, etc.
• Support for basic stack operations (clearstack, drop, dup, over, swap, .s)
• Support for loops, via do/loop.
• Support for conditional-execution, via if, else, and then.
• Support for declaring variables with variable, and getting/setting their values with @ and ! respectively.
• Execute files specified on the command-line.
  • If no arguments are supplied run a simple REPL instead.
• A standard library is loaded, from the present directory, if it is present.
  • See what we load by default in foth/foth.4th.
• The use of recursive definitions, for example:
  • : factorial recursive dup 1 > if dup 1 - factorial * then ;

Installation

You can find binary releases of the final-version upon the project release page, but if you prefer you can install from source easily.

Either run this to download and install the binary:

$ go get github.com/skx/foth/foth@v0.5.0

Or clone this repository, and build the executable like so:

cd foth
go build .
./foth

The executable will try to load foth.4th from the current-directory, so you'll want to fetch that too. But otherwise it should work as you'd expect - the startup-file defines several useful words, so running without it is a little annoying but it isn't impossible.

Embedded Usage

Although this is a minimal interpreter it can be embedded within a Golang host-application, allowing users to write scripts to control it.

As an example of this I put together a simple demo:

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

This embeds the interpreter within an application, and defines some new words to allow the user to create graphics - in the style of turtle.

Anti-Features

The obvious omission from this implementation is support for strings in the general case (string support is pretty limited to calling strlen, and printing strings which are constant and "inline").

We also lack the meta-programming facilities that FORTH users would expect, in a FORTH system it is possible to implement new control-flow systems, for example, by working with words and the control-flow directly. Instead in this system these things are unavailable, and the implementation of IF/DO/LOOP/ELSE/THEN are handled in the golang-code in a way users cannot modify.

Basically we ignore the common FORTH-approach of using a return-stack, and implementing a VM with "cells". Instead we just emulate the behaviour of the more advanced words:

• So we implement if or do/loop in a hard-coded fashion.
  • That means we can't allow a user to define while, or similar.
  • But otherwise our language is flexible enough to allow real work to be done with it.

Implementation Approach

The code evolves through a series of simple steps, contained in the comment-thread, ultimately ending with a final revision which is actually useful, usable, and pretty flexible.

While it would certainly be possible to further improve the implementation I'm going to declare this project as "almost complete" for my own tastes:

• I'll make minor changes, as they occur to me.
• Comments, test-cases, and similar are fair game.
• Outright crashes will be resolved, if I spot any.
• But no major new features will be added.

If you wanted to extend things further then there are some obvious things to work upon:

• Adding more of the "standard" FORTH-words.
  • For example we're missing pow, etc.
• Enhanced the string-support, to allow an input/read from the user, and other primitives.
  • strcat, strstr, and similar C-like operations would be useful.
• Simplify the conditional/loop handling.
  • Both of these probably involve using a proper return-stack.
  • This would have the side-effect of allowing new control-flow primitives to be added.
  • As well as more meta-programming.

Pull-requests adding additional functionality will be accepted with thanks.

Implementation Overview

Each subdirectory within this repository gets a bit further down the comment-chain.

In terms of implementation two files are largely unchanged in each example:

• stack.go, which contains a simple stack of float64 numbers.
• main.go, contains a simple REPL/driver.
  • The final few examples will also allow loading a startup-file, if present.

Each example builds upon the previous ones, with a pair of implementation files that change:

• builtins.go contains the forth-words implemented in golang.
• eval.go is the workhorse which implements to FORTH-like interpreter.
  • This allows executing existing words, and defining new ones.

Part 1

Part one of the implementation only deals with hard-coded execution of "words". It only supports the basic mathematical operations, along with the ability to print the top-most entry of the stack:

 cd part1
 go build .
 ./part1
 > 2 3 + 4 5 + * print
 45.000000
 ^D

See part1/ for details.

Part 2

Part two allows the definition of new words in terms of existing ones, which can even happen recursively.

We've added dup to pop an item off the stack, and push it back twice, which has the ultimate effect of duplicating it.

To demonstrate the self-definition there is the new function square which squares the number at the top of the stack.

 cd part2
 go build .
 ./part2
 > 3 square .
 9.000000
 > 3 dup + .
 6.000000
 ^D

See part2/ for details.

Part 3

Part three allows the user to define their own words, right from within the REPL!

This means we've removed the square implementation, because you can add your own:

 cd part3
 go build .
 ./part3
 > : square dup * ;
 > : cube dup square * ;
 > 3 cube .
 27.000000
 > 25 square .
 625.000000
 ^D

See part3/ for details.

NOTE: We don't support using numbers in definitions, yet. That will come in part4!

Part 4

Part four allows the user to define their own words, including the use of numbers, from within the REPL. Here the magic is handling the input of numbers when in "compiling mode".

To support this we switched our Words array from int to float64, specifically to ensure that we could continue to support floating-point numbers.

 cd part4
 go build .