[ planet-factor ]

John Benediktsson: Stack Complexity

We had a recent discussion on the Factor Discord server about how to deal with stack shuffling, and when and how you might use the various dataflow combinators that are available in Factor. Some of the impetus for this discussion was my article about intersecting ranges and the contrasting implementations that it presented.

The question that started it all:

Overall very complex stack states.

How do you write code like that?

Are you in the listener or debugger making these changes one by one?

When I write even simple code I get lost when there’s 3+ things on the stack I have to work with and spend more time figuring out stack order and correct combinators than with the actual problem. I wonder if there’s a good workflow where I can write the code iteratively.

Let’s go over some of the advice that came up in that conversation:

Mockups

I often write Factor code iteratively lately. Usually I come up with a tiny increment that preserves the stack effect, then reload the code to compile it.

For example, if I need to create a word with effect ( a b -- ), I will start with the minimal implementation like

: word ( a b -- )
    2drop ;

Mocking stuff every step of the way, compiling after each step.

For stuff inside a word that seems to be complex from the outset, I would create a mock (word) with defined stack effect. I will inline it later if it turns out to be simpler than expected (because I find something in the standard library that would do most of the work).

Combinators

Some things come with practice, that’s true. But some tips:

  1. Keep the stack shallow, 1-3 things and it often works best.
  2. More than that and don’t worry about using named local variables.
  3. Try and use spread / apply / cleave combinators to represent your logic as dataflow.

Monoliths

I like writing monoliths, so sometimes i write a :: version first and refactor to : later, especially if I don’t know how the data will flow exactly.

When I’m porting code from other languages, I start with locals to keep the code blocks similar. Structure starts to become obvious once you have a big block working.

Practice

Sometimes writing inline comments showing what the stack effect is after each block of code, is useful to visualize the stack effects of the intermediate parts.

Sometimes there are words like vector operations that clean up an iterative piece of code.

But mostly, keep practicing. Ask questions. Maybe get feedback on your code from us here or other devs you like to work with.

And sometimes despite trying; it stays a big block of code that works, you shrug and move on to the next thing.

Variables

One way to reduce stack depth is, for example, to put some state on the namestack as a variable. That is how our stream words work (e.g., read, write, print). It’s how some words that accumulate output work – either using the make vocabulary or an equivalent vector or hash-set variable to accumulate into.

Reordering

Oh, and one advanced tip: sometimes reordering the arguments on the stack to avoid shuffles or allow using with / map / curry / fry things helps a lot.

It takes a long time to “get” it, but there are some rules that help; the order of your arguments to your words matter a lot. If you find yourself juggling a lot, consider a different argument order of your word. Stuff new context “under” your arguments with dip, e.g. a vector to collect stuff in. Look at accessors and see why they’re designed with a specific word order; typically things that are “parameters” go on the top of the stack (e.g. quotations). Also assocs have a certain logical order to them. If you understand that, it becomes more natural, with the occasional stack shuffle still needed.

And don’t forget about tuples; that quickly reduces the amount of things on the stack

Good luck and happy coding!

Thu, 11 Jul 2024 14:00:00

Doug Coleman: Magic Combinator

Magic Combinator

In response to a blog post about Stack Complexity in Factor, I figured I would add one way that I structure programs when possible.

Suppose you want to make a server that runs sql queries where a route name is a filename. Some requirements of this are connecting to a database, opening a directory of sql templates, loading them all into a hashtable to query by filename, handling incoming connections, doing the query, writing the results back out–you obviously can’t reason about all of this state on the stack at the same time. It would be ten items deep, and we want to keep the stack depth to 3-4 things at once in the same stack effect. (Of course the stack keeps growing deeper, but we need to reason about only a few things at any time.)

You can imagine a magic combinator, composed of other combinators, that will do most of this for you. Suppose you start with a with-database combinator that will connect and tear down the connection and handle exceptions. Next, you need to read the templates–with-template-directory to the rescue! To handle all the incoming requests you will need a with-server combinator. We should also set up some routes that map to the filenames, maybe call it with-routes.

Now that we have all the parts, let’s combine them into a combinator that works with dynamic variables and you have your magic combinator!

! some setup variables
SYMBOL: db-settings   ! initial settings for db
SYMBOL: server-port   ! port

! state within the combinators
SYMBOL: db-connection
SYMBOL: templates
SYMBOL: routes
SYMBOL: client-connection

: with-networked-database-template-directory ( template-directory quot: ( args template -- ) -- )
    [ db-settings get ] 2dip '[
        _ [
             [
                 _ with-routes
            ] with-server
        ] with-template-directory
    ] with-database ; inline

Now your quot magically has the db connection, the templates, the routes, the client connection, and you can just concentrate on templating the query and getting the results, confident that this combinator takes care of the setup. You can access any of the state with code like db-connection get. If you need more state, just add another combinator. If there are problems, you can debug each combinator individually.

Hopefully this will help you handle state in your Factor programs, or even in python using the with keyword.

Thu, 11 Jul 2024 08:17:00

John Benediktsson: Random Distributions

As was the case when I got distracted by color support, I recently was distracted by random probability distributions. Other programming languages have these – for example the Python module numpy.random as well as the Julia module Distributions.jl.

In particular, I wanted to make sure we supported a bunch of the commonly used distributions, both continuous and discrete. I have added a few recently, and we now support quite a few in the random vocabulary:

TUPLE: bernoulli-distribution p ;
TUPLE: beta-distribution alpha beta ;
TUPLE: binomial-distribution n p ;
TUPLE: cauchy-distribution median scale ;
TUPLE: chi-square-distribution dof ;
TUPLE: exponential-distribution lambda ;
TUPLE: f-distribution dof-num dof-den ;
TUPLE: gamma-distribution alpha beta ;
TUPLE: geometric-distribution p ;
TUPLE: gumbel-distribution loc scale ;
TUPLE: inv-gamma-distribution shape scale ;
TUPLE: laplace-distribution mean scale ;
TUPLE: logistic-distribution loc scale ;
TUPLE: lognormal-distribution < normal-distribution ;
TUPLE: logseries-distribution p ;
TUPLE: normal-distribution mean sigma ;
TUPLE: pareto-distribution k alpha ;
TUPLE: poisson-distribution mean ;
TUPLE: power-distribution alpha ;
TUPLE: rayleigh-distribution mode ;
TUPLE: student-t-distribution dof ;
TUPLE: triangular-distribution low high ;
TUPLE: uniform-distribution min max ;
TUPLE: von-mises-distribution mu kappa ;
TUPLE: wald-distribution mean scale ;
TUPLE: weibull-distribution alpha beta ;
TUPLE: zipf-distribution a ;

For each of these, we define a convenient foo-random word, an implementation foo-random* that takes a random-generator, and a foo-distribution tuple that can be used as an object to take a faster number of samples using randoms from. For example, using the binomial distribution:

IN: scratchpad 100,000 [ 10 0.6 binomial-random ] replicate histogram .
H{
    { 0 21 }
    { 1 157 }
    { 2 1058 }
    { 3 4228 }
    { 4 11202 }
    { 5 20002 }
    { 6 25151 }
    { 7 21537 }
    { 8 11981 }
    { 9 4045 }
    { 10 618 }
}

IN: scratchpad 100,000
               T{ binomial-distribution { n 10 } { p 0.6 } }
               randoms histogram .
H{
    { 0 6 }
    { 1 164 }
    { 2 1044 }
    { 3 4255 }
    { 4 11169 }
    { 5 19928 }
    { 6 25103 }
    { 7 21414 }
    { 8 12335 }
    { 9 3973 }
    { 10 609 }
}

I would love to get some additional per-distribution generic methods to support calculating things like mean, variance, skewness, kurtosis, entropy, probability density/mass functions, etc. And, of course, would love more distributions to be available in Factor.

There’s always things to add!

Tue, 9 Jul 2024 17:00:00

John Benediktsson: Magic Forest

About ten years ago, there was a blog post about a Goats, Wolves, and Lions puzzle that was problem #30 from the 2014 Austrian “Math Kangaroo” contest. The puzzle was kind of fun and the implementation prompted some decent follow-up at the time.

There are three species of animals in a magic forest: lions, wolves and goats. Wolves can devour goats, and lions can devour wolves and goats. ("The stronger animal eats the weaker one".) As this is a magic forest, a wolf, after having devoured a goat, is transmuted into a lion; a lion, after having devoured a goat, is transmuted into a wolf; and a lion having devoured a wolf becomes a goat.

At the very beginning, there are 17 goats, 55 wolves and 6 lions in the forest. After every meal, there is one animal fewer than before; therefore after some time, there is no devouring possible any more.

What is the maximum number of animals who can live in the forest then?

There are two versions of this puzzle: one that doesn’t give any possible answers and the kangaroo version that gives these multiple choice options:

(A) 1
(B) 6
(C) 17
(D) 23
(E) 35

The original post followed up with a description of three ways to solve the Goats, Wolves, and Lions problem and then a brute-force solution in Fortran followed by a comparison of solutions in different programming languages of which the fastest was a C++ version and then someone else described some experiments and improvements in some other languages. The best answer, maybe, was the one that described using linear programming with lpsolve for an algorithmic solution that beats all the previous versions and even reduces to a simple formula that you can calculate by hand!

I had created a solution in Factor at the time, but had never written about it. Below, I want to go over that approach it and compare it with the performance of the “fastest” C++ version.

We are going to store our forest state as a tuple representing the number of goats, wolves, and lions.

TUPLE: forest goats wolves lions ;

C: <forest> forest

: >forest< ( forest -- goats wolves lions )
    [ goats>> ] [ wolves>> ] [ lions>> ] tri ;

We can build words to represent each possible next state, or f if that next state is not possible:

: wolf-devours-goat ( forest -- forest/f )
    >forest< { [ pick 0 > ] [ over 0 > ] } 0&&
    [ [ 1 - ] [ 1 - ] [ 1 + ] tri* <forest> ] [ 3drop f ] if ;

: lion-devours-goat ( forest -- forest/f )
    >forest< { [ pick 0 > ] [ dup 0 > ] } 0&&
    [ [ 1 - ] [ 1 + ] [ 1 - ] tri* <forest> ] [ 3drop f ] if ;

: lion-devours-wolf ( forest -- forest/f )
    >forest< { [ dup 0 > ] [ over 0 > ] } 0&&
    [ [ 1 + ] [ 1 - ] [ 1 - ] tri* <forest> ] [ 3drop f ] if ;

We can track the set of next states by adding them to a set:

: next-forests ( set forest -- set' )
    [ wolf-devours-goat [ over adjoin ] when* ]
    [ lion-devours-goat [ over adjoin ] when* ]
    [ lion-devours-wolf [ over adjoin ] when* ] tri ;

Given a sequence of forest states, we can produce the next states after a meal has occurred:

: meal ( forests -- forests' )
    [ length 3 * <hash-set> ] keep [ next-forests ] each members ;

A forest is stable if there are no goats and either no wolves or no lions, or goats and no wolves and no lions:

: stable? ( forest -- ? )
    >forest< rot zero? [ [ zero? ] either? ] [ [ zero? ] both? ] if ;

We can say that devouring is possible if there are no stable forests:

: devouring-possible? ( forests -- ? )
    [ stable? ] none? ;

And maybe we want to be able to get all the stable forests:

: stable-forests ( forests -- stable-forests )
    [ stable? ] filter ;

So, to find our answer, we can just iterate, until we find our first stable forest state:

: find-stable-forests ( forest -- forests )
    1array [ dup devouring-possible? ] [ meal ] while stable-forests ;

And, now we can answer the original question – which is (D):

IN: scratchpad T{ forest f 17 55 6 } find-stable-forests .
{ T{ forest { goats 0 } { wolves 0 } { lions 23 } } }

We can compare the performance of Factor with the C++ version from that earlier blog post and see that ours is around 5.5x slower:

IN: scratchpad [ T{ forest f 317 355 306 } find-stable-forests ] time .
Running time: 4.625607999 seconds
{ T{ forest { goats 0 } { wolves 0 } { lions 623 } } }

versus

$ time ./magic_forest 317 355 306
0, 0, 623
./magic_forest 317 355 306  0.80s user 0.04s system 99% cpu 0.848 total

One of the reasons for that is we’re doing a lot of generic dispatch, not specifying types anywhere, and passing tuples around that we are accessing and allocating frequently. We could fix some of these issues and make ours faster…

But, approaching this as a linear programming exercise beats all the iterative approaches anyway:

IN: scratchpad T{ forest f 17 55 6 } >forest< min + .
23

IN: scratchpad T{ forest f 317 355 306 } >forest< min + .
623

IN: scratchpad T{ forest f 900006 900055 900017 } >forest< min + .
1800023

Still, there are probably performance lessons to be learned here…

Sat, 29 Jun 2024 13:00:00

John Benediktsson: Man or Boy

The man or boy test was proposed by Donald Knuth:

“There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the man-compilers from the boy-compilers.”

— Donald Knuth

The Rosetta Code project has a list of implementations to compare with, and today we are going to contribute one in Factor. While the original was framed in ALGOL 60, let’s look at one contributed in Python, which is probably more readable for most of the audience:

#!/usr/bin/env python
import sys
sys.setrecursionlimit(1025)

def a(k, x1, x2, x3, x4, x5):
    def b():
        b.k -= 1
        return a(b.k, b, x1, x2, x3, x4)
    b.k = k
    return x4() + x5() if b.k <= 0 else b()

x = lambda i: lambda: i
print(a(10, x(1), x(-1), x(-1), x(1), x(0)))

In particular, this is challenging because it involves creating a “tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called.” And, as a result, many languages have difficulting calculating for large values of k due to recursion or depth limits.

In Factor, we have the ability to create inner computations by making quotations, which is essentially an anonymous version of the inner B function. These quotations are allowed to access the variables defined in their outer scope. Thus, we can implement the word reasonably simply by making a B quotation, binding it to a variable for reference, and then calling it:

:: a ( k! x1 x2 x3 x4 x5 -- n )
    k 0 <= [
        x4 call( -- n ) x5 call( -- n ) +
    ] [
        f :> b!
        [ k 1 - dup k! b x1 x2 x3 x4 a ] b!
        b call( -- n )
    ] if ;

The k argument is an integer, the others are quotations with stack effect of ( -- n ), meaning they take no arguments, and produce a number when called. We can call it and demonstrate that it works and produces the first few values of the output of Knuth’s “man or boy” test for varying k:

IN: scratchpad 13 [0..b] [
                   [ 1 ] [ -1 ] [ -1 ] [ 1 ] [ 0 ] a .
               ] each
1
0
-2
0
1
0
1
-1
-10
-30
-67
-138
-291
-642

Presently, larger values of k produce a “retain stack overflow” with the default Factor settings. I looked briefly into using our bend vocabulary, but it currently doesn’t support accessing the outer variable scope, and requires passing arguments on the stack. That would be a nice feature, and theoretically would then look like this simple example:

:: a ( k! x1 x2 x3 x4 x5 -- n )
    k 0 <= [
        x4 call( -- n ) x5 call( -- n ) +
    ] [
        BEND[ k 1 - dup k! [ fork ] x1 x2 x3 x4 a ]
    ] if ;

However, that doesn’t work at the moment. Maybe sometime in the future!

Wed, 26 Jun 2024 15:00:00

Doug Coleman: It's 2024 Already

We survived covid and we’re foolishly gearing up for WW3. What a great time to be a Factor blogger!

I got a job doing cmake and build systems in 2016 and since 2017 I’ve been doing JS/python/React/SOLR. I’m still working on Factor, so there should be a lot to post about.

Thanks to John for the sweet blogging setup!

Tue, 25 Jun 2024 08:17:00

John Benediktsson: Quit

There is a funny recurring meme that we are all living inside a simulation or maybe even a matrix-in-a-matrix. Some people have even taken this as far as selling funny computer simulation t-shirts:

Well, I have resisted for a long time adding a special end programquit – command to Factor. We have always supported Ctrl-D to end the listener session (which works in both the UI listener and in the command-line on most POSIX systems). You have also been able to exit with an error code, or even to stop after the last window has been closed. And if you really needed something, you could define your own end program word in your startup initialization file.

This came up again recently in a discussion with @nomennescio, one of our contributors, who has been pushing for a quit command that would be kind of like the Python version of How to Exit a Python Program in the Terminal:

Python 3.11.9 (main, Apr  2 2024, 08:25:04) [Clang 15.0.0 (clang-1500.3.9.4)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> quit
Use quit() or Ctrl-D (i.e. EOF) to exit
>>> quit()

This has become more important since they added saving listener history to the UI tools (currently saved to a history file when the listener window closes). This was paired with a couple of changes to make Factor attempt to close-all-windows and cleanup nicely using a shutdown hook and include the system vocabulary in the default list of interactive vocabularies.

This means that this works now, in both the command-line listener as well as the UI listener:

Factor 0.100 x86.64 (2271, heads/master-250db4215b, Jun  4 2024 18:08:03)
[Clang (GCC Homebrew Clang 18.1.6)] on macosx
IN: scratchpad quit

If you’re curious how it works, quit is an alias for calling exit with an error code of 0:

IN: system

: quit ( -- * ) 0 exit ;

This is available in a development version of Factor and will be in the next release.

Wed, 12 Jun 2024 15:00:00

John Benediktsson: Bend

The Bend programming language is a massively parallel, high-level programming language. It has some really neat dataflow concepts that make it inherently parallel because it infers the flow of variables and then naturally performs divide and conquer to utilize all available computing resources, both CPU and GPU.

This results in some impressive speedups:

Yet, since it uses a divide-and-conquer approach, which is inherently parallel, Bend will run it multi-threaded. Some benchmarks:

CPU, Apple M3 Max, 1 thread: 12.15 seconds

CPU, Apple M3 Max, 16 threads: 0.96 seconds

GPU, NVIDIA RTX 4090, 16k threads: 0.21 seconds

That’s a 57x speedup by doing nothing.

One of our current challenges in Factor is that we use green threads and are effectively single-threaded for computations. We have a non-blocking I/O implementation as well as integration with UI event loops, so it ends up feeling more concurrent than it actually is.

We hope to solve that in the future, both by supporting native threads and also by a multi-vm approach that is somewhat equivalent to the Python multiprocessing module. Some early ideas have been contributed towards this goal, but so far it is not complete.

Bend Example

One of the Bend examples that we are going to try and implement in Factor uses a bend and fork operations which creates concurrency points in a kind of fork-join model:

# given a shader, returns a square image
def render(depth, shader):
  bend d = 0, i = 0:
    when d < depth:
      color = (fork(d+1, i*2+0), fork(d+1, i*2+1))
    else:
      width = depth / 2
      color = shader(i % width, i / width)
  return color

# given a position, returns a color
# for this demo, it just busy loops
def demo_shader(x, y):
  bend i = 0:
    when i < 5000:
      color = fork(i + 1)
    else:
      color = 0x000001
  return color

# renders a 256x256 image using demo_shader
def main:
  return render(16, demo_shader)

Factor Syntax

A few days ago, Keldan Chapman contributed an early version of a bend vocabulary. And then, we spent some time working together on the Factor Discord server on some alternative implementations, one of which I want to go over below.

We are going to create a BEND[ quotation that provides support for a fork word that implicitly recurses (but not currently through CPU or GPU parallelism) and then joins the results together. We create an uninterned word to hold our computation and use with-words to make the fork word only valid in the parsing scope to recurse.

SYNTAX: BEND[
    gensym dup
    dup "fork" associate [ parse-quotation ] with-words
    dup infer define-declared suffix! ;

A simple use-case of this might be to compute the factorial through recursion:

: factorial ( n -- n! )
    BEND[ dup 1 > [ dup 1 - fork * ] when ] ;

Or, perhaps computing Fibonacci numbers through recursion:

: fibonacci ( n -- fib )
    BEND[ dup 1 > [ [ 1 - fork ] [ 2 - fork ] bi + ] when ] ;

Factor Example

With that syntax defined, we can now translate the above example to the following form:

: render ( depth shader -- color )
    0 0 BEND[
        [let :> ( depth shader d i )
            d depth < [
                depth shader d 1 + i 2 * fork
                depth shader d 1 + i 2 * 1 + fork
                2array
            ] [
                i depth 2/ /mod swap shader call( x y -- color )
            ] if
        ]
    ] ;

:: demo-shader ( x y -- color )
    0 BEND[ dup 5000 < [ 1 + fork ] [ drop 0x000001 ] if ] ;

: main ( -- color )
    16 [ demo-shader ] render ;

Obviously, this fork doesn’t (currently) increase performance, and it might shadow the fork from the unix.process vocabulary, but it could represent the start of a new computational approach in Factor.

I can’t wait to see more from the Bend programming language and I also hope to see more of these ideas appearing and improving in Factor!

Wed, 5 Jun 2024 15:00:00

Blogroll


planet-factor is an Atom/RSS aggregator that collects the contents of Factor-related blogs. It is inspired by Planet Lisp.

Syndicate