DEV Community: Remo Dentato

Finite States Machines (in C)

Remo Dentato — Sat, 30 Aug 2025 06:03:23 +0000

Most of us learn to write state machines in C with a big while + switch and a tangle of breaks. It works—until it doesn’t: fall-through bugs, nested loops, and “what happens if I forget a break here?”

Alternative methods use a transition table, possibly with pointers to functions encoding states. Or just plain code with if and state variables to control the flow of execution.

The fsm macro library takes a different, extremely simple approach: it turns each state into a labeled block and each transition into an explicit goto. The result is readable, predictable control flow and straight-line, optimizer-friendly code—no runtime framework, no heap, no state tables, just C code.

The key benefit of this approach is that it maps one-to-one the code with state machine diagrams, meaning that it's very simple to code an FSM starting from a diagram and, conversely, derive the diagram from the code, with great improvement of maintainability. (see the example at the end of the post)

🗃️ Source & repository: repo.dentato.com/fsm

What it looks like

#include <ctype.h>
#include <stdio.h>
#include "fsm.h"

void classify(const char *s) {
  size_t i = 0;

  fsm {
    fsmstate(START) {
      if (!s[i]) fsmexit;
      int c = (unsigned char)s[i++];
      if (!isalpha(c)) fsmgoto(START);
      if (strchr("AEIOUaeiou", c)) fsmgoto(VOWEL);
      fsmgoto(CONSONANT);
    }

    fsmstate(VOWEL)     { puts("vowel");     fsmgoto(START); }
    fsmstate(CONSONANT) { puts("consonant"); fsmgoto(START); }
  }
}

Four macros do the job:

fsm { … } — open an FSM in a function (one per function).
fsmstate(NAME) { … } — define a state.
fsmgoto(NAME); — transition.
fsmexit; — stop the machine (continue after the fsm { … } block).

How it works (and why it’s safe)

This is the code for the library (the commented version is in the repo)

#define fsm if (1) {goto fsm_state_START; fsm_exit: ;} else 
#define fsmstate(s) for(;;) for(;;) if (1) goto fsm_exit; else fsm_state_ ## s:
#define fsmgoto(s)  goto fsm_state_ ## s
#define fsmexit     goto fsm_exit

Under the hood:

fsm expands to an if (1) { goto fsm_state_START; fsm_exit: ; } else { … }.
Execution jumps directly to START. A shared fsm_exit label is defined.
Each fsmstate(NAME) expands to for(;;) for(;;) if (1) goto fsm_exit; else fsm_state_NAME: followed by your block.
Each macro is a single statement from the compiler's point of view (no issue with dangling else or missing ;)
No double evaluation of arguments is possible.

That design guarantees:

If control ever reaches the top of a state by accident, it exits the FSM.
If your state falls off the end, the next loop tick forces an exit—no silent fall-through.
A bare break/continue inside a state exits the FSM (prefer explicit fsmexit for clarity).
Only the code within the fsmstate() blocks will be executed.

Constraints you should know

One FSM per function (labels like fsm_exit, fsm_state_* are reserved).
Exactly one START state.
Only valid identifiers as state names.
Don’t put executable code between states inside the fsm { … } block; it won’t run.
Be mindful of VLAs: never goto into a scope that introduces a VLA per C11 rules. Declare VLAs either before fsm or inside a state.

Why this beats the usual switch

No hidden fall-through. You must say where you go next.
Lean codegen. Compilers emit direct branches; there’s no framework cost nor the cost to access data in memory (transition tables).
Readable control flow. Each state is a labeled block you can jump to and grep for. You can very easily reconstruct the FSM diagram just by inspecting the code (see the "comment stripper" example below).
Debugger-friendly. You literally step between fsm_state_* labels.

Where `fsm` shines

Tokenizers and scanners (comments, strings, numbers).
Protocol and message parsers.
Little interpreters and command dispatchers.

A tiny real-world sketch: comment stripper

This example strips comments from a C source file:

void strip_comment(FILE *in, FILE *out)
{
  fsm {
    int c;

    fsmstate(START) {
      fsmgoto(code);
    }

    fsmstate(code) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if (c == '/') fsmgoto(slash);
      fsmgoto(code_char);
    }

    fsmstate(code_char) { // Doesn't read from in
      fputc(c, out); 
      if (c == '"')  fsmgoto(string);
      if (c == '\'') fsmgoto(literal);
      fsmgoto(code); 
    }

    fsmstate(slash) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if (c == '/') fsmgoto(line_comment);
      if (c == '*') fsmgoto(block_comment);
      fputc('/',out); 
      fsmgoto(code_char);
    }

    fsmstate(string) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if ((c == '\\')) fsmgoto(escaped_str);
      fputc(c,out);
      if (c == '"') fsmgoto(code);
      fsmgoto(string);
    }

    fsmstate(escaped_str) {
      fputc(c,out);
      if ((c = fgetc(in)) == EOF) fsmexit; 
      fputc(c,out);
      fsmgoto(string);
    }

    fsmstate(literal) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if ((c == '\\')) fsmgoto(escaped_lit);
      fputc(c,out);
      if (c == '\'') fsmgoto(code);
      fsmgoto(literal);
    }

    fsmstate(escaped_lit) {
      fputc(c,out);
      if ((c = fgetc(in)) == EOF) fsmexit; 
      fputc(c,out);
      fsmgoto(literal);
    }

    fsmstate(line_comment) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if (c == '\n') fsmgoto(code);
      fsmgoto(line_comment);
    }

    fsmstate(block_comment) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if (c == '*') fsmgoto(star);
      fsmgoto(block_comment);
    }

    fsmstate(star) {
      if ((c = fgetc(in)) == EOF) fsmexit; 
      if (c == '/') fsmgoto(code);
      fsmgoto(block_comment);
    }
  }
}

Thanks to the explicit nature of fsm states and transactions, I've been able to quickly generate a state diagram directly from the code using an LLM (ChatGPT, in this case) and then edit it for clarity. This wouldn't have been easy (or even possible) if the FSM had been a tangled mess of switch and state variables.

Getting started

Browse or clone the repository: repo.dentato.com
Drop dist/fsm.h into your project and #include it.
Define one fsm per function, with exactly one START state.
Keep only states inside the fsm { … } block; transition with fsmgoto(State); leave with fsmexit.

For deeper patterns (error funnels, re-entrancy, tracing, diagrams), see docs/fsm.md.

Credits

I took the original idea for these macros from the May 1991 issue of the glorious "Computer Language" magazine. The article "Goto? Yes, Goto!" by Tim Cooper exposed me to the idea of using macros to discipline the use of goto in implementing Finite State Machines. Those macros were simple, and I used them in some form or another on various occasions. Since then, my macromancy has improved, and this is the result, almost 35 years after I read that article on a train on my way home.

Polymorphic C (2/2)

Remo Dentato — Sun, 08 Jun 2025 19:08:40 +0000

Introduction
Default to 0
- Pointers to NULL
Supply missing arguments
- Skipping arguments
- A Microsoft quirk
Counting arguments
- Multiuse example
Zero arguments
Conclusion

Introduction

To complete the recap of how we can implement Polymorphism in C, let's review how we can handle different function signatures.

Note that I did not invent these techniques; I found them over the years here and there (a site, a book, a magazine, ...), then I adopted and massaged them to make them useful to me.

Since we all build on someone else's previous work, I'm sharing them here in the hope they might be of help.

Default to 0

A very simple case is when the last optional argument drives the behaviour of your function, and it can be defaulted to 0

// Example:   move(steps [, offset]) where offset is 0 if unspecified:
// The actual function is move_f()
#define move(s,...) move_f(s, __VA__ARGS__ + 0)
void move_f(int steps, int offset)

If called with move(10,3) it will expand to move_f(10, 3 + 0).
If called with move(10), it will expand to move(10, +0), which is perfectly fine for the compiler.

Now, in move_f() you can check for offset and behave accordingly.

Pointers to NULL

The same can be done for pointers, but since they are dangerous beasts, it is better to put some more effort into it:

// Example: transfer(items [, aux_info])
#define transfer(i,...) transfer_g(i, __VA_ARGS__ +0)
#define transfer_g(i,a) _Generic((a), \
                           info_t *: transfer_f(i,(info_t *)(a)),\
                                int: transfer_f(i,(info_t *)NULL) \
                        )
int transfer_f(int items, info_t *aux);

Here we use _Generic to ensure that the second argument is of the proper type and that defaults to NULL.

Note that the C standard does not guarantee that (void *)0 is equal to NULL, even if it is very often the case, so we can't count on the fact that (info_t *)0 will be equal to NULL.

When called as transfer(32, new_info), it will expand to transfer_g(32, new_info + 0). Assuming that new_info is of type info_t * (as it should be) also the value (new_info + 0) is of type info_t *. So, the macro transfer_g() will convert it to transfer_f(32,(info_t *)(new_info+0)).

When called as transfer(32), it will expand to transfer_f(32, +0). The second argument is an int (as per the C standard), and the macro will be expanded to transfer_f(32,(info_t * )NULL) by the second branch of generic.

If the second argument is of any other type, there will be a syntax error.

Note that in the info_t *: branch of _Generic, casting a is mandatory, otherwise the compiler will complain when the second argument is missing an int.

Supply missing arguments

Say you have a function where more than one last argument can be optional: f(a [,j [,k]]).

A simple method to implement it involves augmenting the list of arguments to ensure the proper number of arguments is always provided to the function:

// Select the n-th argument (0-based count)
#define arg_0( x,...)           x
#define arg_1(_0, x,...)        x
#define arg_2(_0,_1, x, ...)    x

// Example:   move(steps [, offset [, direction]]) :
#define move(...) move_f(arg_0(__VA_ARGS__),\
                         arg_1(__VA_ARGS__ , 0), \
                         arg_2(__VA_ARGS__ ,'N',`N`), \
                        )
void move_f(int steps, int offset, int direction);

The expansion of move(13, -3, 'S') will be:

move_f( arg_0(13, -3, 'S') , arg_1(13, -3, 'S', 0) , arg_2(13, -3, 'S', 'N', 'N'))
              ╰────╮                 ╭──╯                  ╭────────╯
move_f(            13       ,       -3         ,          'S' )

The expansion of move(13, -3) will be:

move_f( arg_0(13, -3) , arg_1(13, -3, 0) , arg_2(13, -3, 'N', 'N'))
           ╭──╯               ╭────╯             ╭────────╯
move_f(    13         ,      -3          ,      'N' )

The expansion of move(13) will be:

move_f( arg_0(13)      , arg_1(13, 0)  , arg_2(13, 'N', 'N'))
              ╰───╮                ╰──╮           ╭──────╯
move_f(           13   ,              0   ,      'N' )

Note how the default for the last argument ('N' in the example) must be repeated twice to ensure it is properly expanded.

Skipping arguments

A noticeable drawback is that if you want to provide the third argument, you must provide the second argument. It would be nice if we could just omit the ones we are not interested in.

Providing the types are different, we can ask _Generic for help:

#define arg_0( x,...)           x
#define arg_1(_0, x,...)        x
#define arg_2(_0,_1, x, ...)    x

// We need a different type than int for the direction
#define N ((char)'N')
#define S ((char)'S')
#define E ((char)'E')
#define W ((char)'W')

// Example:   move(steps [, offset [, direction]]) :
#define move(...) move_g(arg_0(__VA_ARGS__),\
                         arg_1(__VA_ARGS__ , N), \
                         arg_2(__VA_ARGS__ , N, N), \
                        )

#define move_g(s, t, d) _Generic( (t) \
                            int: move_f(s, (int)(t), d), \
                           char: move_f(s, 0, (char)(t))  \
                         ) 

void move_f(int steps, int offset, char direction);

To better understand how it works, let's check the macro expansion of move(13, -3, S):

move_g( arg_0(13, -3, S) , arg_1(13, -3, S, N) , arg_2(13, -3, S, N, N))
              ╰────╮               ╭──╯               ╭────────╯
move_g(            13    ,        -3           ,      S )
                   │               │                  │
move_f(            13    ,        -3           ,      S )

For move(13, -3) :

move_g( arg_0(13, -3)    , arg_1(13, -3, N) , arg_2(13, -3, N, N))
              ╰────╮               ╭──╯            ╭────────╯
move_g(            13    ,        -3        ,      N )  // -3 is an int
                   │               │               │
move_f(            13    ,        -3        ,      N )

For move(13, E) :

move_g( arg_0(13, E)   , arg_1(13, E, N) , arg_2(13, E, N, N))
              ╰────╮               │             ╭──────╯
move_g(            13  ,           E     ,       N )  // E is a char
                   │               ╰─────────────╮
move_f(            13  ,           0     ,       E )

And for move(13) :

move( arg_0(13)   , arg_1(13, N) , arg_2(13, N, N))
            ╰──╮              │          ╭──────╯
move_g(        13  ,          N  ,       N )  // E is a char.
               │              ╰──────────╮
move_f(        13  ,          0  ,       N )

This technique allows for more flexibility, but it's a little bit more complicated. For example, the default for the third argument is repeated three times, and the default for the second parameter (0) is in the move_f() function, not in the original move() macro.

A Microsoft quirk

The Microsoft compiler cl preprocessor might need an extra level of macro expansion to ensure everything works correctly. To stay safe, you may want to add the macro arg_x that will ensure the end value will be expanded one more time:

#define arg_x(...)           __VA_ARGS__
#define arg_0( x,...)        x
#define arg_1(_0, x,...)     x
#define arg_3(_0,_1, x, ...) x

// Example:   move(steps [, offset [, direction]]) :

#define move(...) move_f(arg_x(arg_0(__VA_ARGS__)),\
                         arg_x(arg_1(__VA_ARGS__ , 0)), \
                         arg_x(arg_1(__VA_ARGS__ , 0, 'N')), \
                        )
void move_f(int steps, int offset, char direction);

I didn't check if the latest version of cl still requires this, but arg_x is harmless and will keep you safe from possible bugs.

Counting arguments

The most flexible way to handle a variable number of arguments is to count how many of them there are.
This allows for specifying entirely different functions for each signature (with the help of _Generics, if needed).

Unfortunately, the C preprocessor still lacks a way to count the number of arguments passed to a macro, and, to stay within C11 boundaries, we have to resort to some additional macros.

This is the most common way to count the number of arguments (up to a maximum of 4):

#define ARG_CNT(_1,_2,_3,_4,_N, ...) _N
#define ARG_COUNT(...)   ARG_CNT(__VA_ARGS__, 4, 3, 2, 1, 0)

For example, the macro ARG_COUNT(a,b,c,d) will be expanded to:

ARG_COUNT(a, b, c, d)

  ARG_CNT(a, b, c, d, 4, 3, 2, 1, 0)
          │  │  │  │  │
         _1,_2,_3,_4,_N
                      |
                      4

The macro ARG_COUNT(a,b) will be expanded to:

ARG_COUNT(a, b)

  ARG_CNT(a, b, 4, 3, 2, 1, 0)
          │  │  │  │  │
         _1,_2,_3,_4,_N
                      |
                      2

As long as there are fewer than 5 arguments, _N will match the number of passed arguments.

The limit here is that we can only count up to a predefined number (4 in the example above) but this is not a real limitation: the number of arguments of a function should not be too high, and, in any case, you can extend the list of numbers in ARG_COUNT() and the list of arguments in ARG_CNT() to match your needs.

Now we need to map our function so that, for example, move(14) maps to move_1(14), and move(14,5) to move_2(14,5):

#define ARG_JOIN(x ,y)   x ## y
#define ARG_VRG(x, y)    ARG_JOIN(x, y)

The macro ARG_VRG() creates a new identifier from two pieces. The process needs to be completed with the help of the ARG_JOIN() to ensure proper macro expansion. For example, the expansion of ARG_VRG(move_,2) is the identifier move_2.

Let's put everything together:

#define ARG_CNT(_1,_2,_3,_4,_N, ...) _N
#define ARG_COUNT(...)   ARG_CNT(__VA_ARGS__, 4, 3, 2, 1, 0)
#define ARG_JOIN(x ,y)   x ## y
#define ARG_VRG(x, y)    ARG_JOIN(x, y)

#define N ((char)'N')
#define S ((char)'S')
#define E ((char)'E')
#define W ((char)'W')

// A specific macro for each function is needed to avoid possible conflicts with other functions using `ARG_VRG()`.
#define move_arg(f,...) ARG_VRG(f, ARG_COUNT(__VA_ARGS__))(__VA_ARGS__)

#define move(...)       move_arg(move_, __VA_ARGS__)     
#define move_1(s)       move_f(x,0,N)
#define move_2(s, t)   _Generic( (t) \
                            int: move_f(s, (int)(t), N), \
                           char: move_f(s, 0, (char)(t))  \
                        )
#define move_3(s,t,d)   move_f(s,t,d)
void move_f(int steps, int offset, char direction);

Multiuse example

Let's look at another example around the following object:

  typedef struct {
    int x;
    int y;
    int RGB;
  } obj_t;

Let's focus on the setters/getters for RGB, we want to be able to:

Get the current value of the RGB field
Set the RGB value passing an integer (e.g. 0xFFE0A0)
Set the RGB value passing the three components R, G, and B separately
Set the RGB value passing the name of the color (e.g. "White", "Pink", ...)

Normally, one would create the following API:

  int get_rgb(obj_t *obj);
  int set_rgb_from_int(obj_t *obj, int rgb );
  int set_rgb_from_str(obj_t *obj, char *);
  int set_rgb_from_rgb(obj_t *obj, int r, int g, int b );

and will call the appropriate function depending on what we need.

But let's say we want to create a sort of "super function" that can do all of the above:

  int obj_rgb(obj_t *obj, ...);

and will select the proper function for us. Here's how we can make it:

#define ARG_CNT(_1,_2,_3,_4,_N, ...) _N
#define ARG_COUNT(...)   ARG_cnt(__VA_ARGS__, 4, 3, 2, 1, 0)
#define ARG_JOIN(x ,y)   x ## y
#define ARG_VRG(x, y)    ARG_JOIN(x, y)

#define obj_rgb_arg(f,...)  ARG_VRG(f, ARG_COUNT(__VA_ARGS__))(__VA_ARGS__)

#define obj_rgb(...)        obj_rgb_arg(obj_rgb_, __VA_ARGS__)     

#define obj_rgb_1(o)        get_rgb(o)

#define obj_rgb_2(o, c)    _Generic( (c) \
                                 int: obj_rgb_from_int(o, (int)((uintptr_t)(t))), \
                              char *: obj_rgb_from_str(o, (char *)((uintptr_t)(t))), \
                            )

#define obj_rgb_4(o,r,g,b)  obj_rgb_from_rgb(o,r,g,b)

Armed with these, we can write something like:

   int old rgb = obj_rgb(my_obj);

   obj_rgb(my_obj, "Black");

   obj_rgb(my_obj, 255,255,255);

   obj_rgb(my_obj, old_rgb);

Don't be distracted by the fact that mixing getters and setters might be seen as bad design. The point here is to show what is possible to do, the actual API design must follow sane principles of usability, understandability, and maintainability.

Zero arguments

All the techniques above have one thing in common: they assume there is at least one argument. Sometimes it would be nice to be able to call f() or f(x), but it is not very common.

My vrg library allows for zero arguments in a C11-compatible way, you can have a look at it if you are interested.

However, I feel it is too complicated and, frankly, the cases for zero arguments are very few.

The actual solution for handling zero arguments is to use the new __VA_OPT__ keyword introduced by C23 (and already available in some form as an extension in gcc, for example).

Let's wait for C23 support to be more widespread in C compilers and we'll revisit these techniques.

Conclusion

We showed what C allows us to do about polymorphism. As it often happens with C, it only offers the basic building blocks, it's up to the programmer to put them together in the correct way.

Mixing the techniques described here to handle function signatures and the techniques described in the previous article, you can achieve most of the (good) things modern object oriented languages can do.

Just one caveat about complexity. It's far too easy to be tempted to write long, complex macros just to allow for some little nicer function definition. One should always balance the complexity of the code with the actual benefit it provides.

Remember: since there is no bug in non-existent code, the less the code the better!

If you find yourself staring at a series of complicated, indirect macro expansions, you might have gone too far with your polymorphic desires.

Polymorphic C (1/2)

Remo Dentato — Mon, 26 May 2025 20:16:44 +0000

Polymorphism, the ability to write functions whose behavior depends on the type and number of their arguments (i.e., their signature), is a feature of many modern programming languages.

In the C world, this concept is especially relevant to library writers and developers implementing the backend of a complex system: fellow programmers prefer a clean, consistent API over dozens or hundreds of closely related functions that differ only by name and signature.

Too often, APIs end up littered with near-identical functions such as:

result_type mixdown_integer_and_string(int x, char *y);
result_type mixdown_unsigned_integer_and_string(unsigned int x, char *y);
result_type mixdown_string_and_float(char *x, float *y);
// and so on ...

each variant must be remembered and called explicitly, making the interface hard to learn and easy to misuse.

How much better would it be to hide those functions (which you, still, have to write) under a single function mixdown(x,y) that would select the appropriate function based on the type of its arguments?

While C doesn’t provide built-in support for method overloading or virtual dispatch tables, you can still craft polymorphic interfaces using a handful of idioms.

In this article, I’ll focus on argument types. See the next article, on how to handle functions signatures.

I’ll explore four approaches:

void pointers to tagged structures,
function‑pointer tables,
tagged pointers,
the C11 _Generic keyword,

using a running example of graphical objects (points, rectangles, circles, ...) that implement operations such as scale() and translate(). I’ll try to highlight the trade-offs in safety, performance, and memory usage, and point out common pitfalls you’ll want to avoid.

1. Void Pointers to Tagged Structures

Concept

Store a type tag in each object’s struct so that functions can inspect the tag at runtime and dispatch to the correct implementation.

#define OBJ_POINT  0
#define OBJ_RECT   1
#define OBJ_CIRCLE 2

typedef struct {
    int tag;
} GraphicObject;

typedef struct {
    int tag;  // must be OBJ_POINT
    int x, y;
} Point;

typedef struct {
    int tag;  // must be OBJ_RECT
    int x, y;
    int width, height;
} Rectangle;

typedef struct {
    int tag;  // must be OBJ_CIRCLE
    int x, y;
    float radius;
} Circle;

// All structs must have the same initial sequence for this to work correctly
// The C standard only guarantees it in the context of accessing the fields
// of structures with unions but, in practice, this is often unnecessary.
typedef union {
  GraphicObject object;
  Point         point;
  Circle        circle;
  Rectangle     rectangle;
} ObjectType;

static inline int get_tag(void *p)
{
  return ((ObjectType *)p)->object.tag;
}

This relies on the C standard's guarantee that if a union contains several structures that share a common initial sequence it is permitted to inspect the common initial part of any of them. (C11 §6.5.2.3)

Dispatch Function

Each "high-level" functions will inspect the tag field and call the proper function.

void scale(void *obj, float sx, float sy) {
    switch (get_tag(obj)) {
        case OBJ_POINT:// Ignore            
            break;
        case OBJ_RECT:
            scale_rectangle((Rectangle *)obj, sx, sy);
            break;
        case OBJ_CIRCLE:
            scale_circle((Circle *)obj, sx, sy);
            break;
        default:
            // handle error
            break;
    }
}

Pros & Cons

Pros
- Simple to implement.
- Works with any pointer type uniformly.
Cons
- No compile-time type checks: passing the wrong pointer (e.g. scale(stdout, ...)) compiles fine but has undefined behavior.
- Every call incurs a switch‐dispatch overhead.
- Tags consume extra space in every object.

2. Function Pointers in Object Tables (“Manual V-tables”)

Concept

Embed pointers to each operation directly in the object (or point to a shared function‐pointer table), mimicking C++’s virtual table.

typedef struct GraphicOps {
    void (*translate)(void *self, int dx, int dy);
    void (*scale)(void *self, float sx, float sy);
    // … other ops
} GraphicOps;

typedef struct {
    const GraphicOps *ops;
    int x, y;
} Point;

typedef struct {
    const GraphicOps *ops;
    int x, y;
    float width, height;
} Rectangle;

typedef struct {
    const GraphicOps *ops;
    int x, y;
    float radius;
} Circle;

Initialize per-type tables once:

static const GraphicOps point_ops = {
    .translate = (void (*)(void*,int,int))translate_point,
    .scale     = (void (*)(void*,float,float))scale_point,
};

static const GraphicOps circle_ops = {
    .translate = (void (*)(void*,int,int))translate_circle,
    .scale     = (void (*)(void*,float,float))scale_circle,
};

// similarly for Rectangle

Usage via Macros

#define translate(obj, dx, dy) ((obj)->ops.translate(obj, dx, dy))
#define scale(obj, sx, sy)     ((obj)->ops.scale(obj, sx, sy))

Circle *new_circle(float radius) {
    Circle *c = aligned_alloc(MAX_TAGS, sizeof *c); // C11 standard
    if (c == NULL) return NULL;
    c->x = c->y = 0;
    c->radius = radius;
    c->ops = &circle_ops; // point to the function table
    return c;
}

Pros & Cons

Pros
- No runtime switch; dispatch is a single indirect call.
- Compile‐time type safety: if you pass a "wrong" argument to the high level function, it will give an error.
Cons
- Objects contains an additional pointer (which is usually larger that an int) per instance.
- Macro wrappers double‐evaluate the obj argument (beware side effects).
- Slightly more boilerplate on initialization (for example, you will need a scale-point() funtction even if it does nothing).

3. Tagged Pointers

Concept

Use the low (least significant) bits of a pointer which are zero (to guarantee proper memory alignment) to store the tag instead of allocating space in every object.

#include <stdint.h>
#include <stdlib.h>
#include <stdalign.h>
#include <stddef.h>

// Determine the max tags allowed by the alignment requirements
// This is guaranteed to work by the C11 standard
#define MAX_TAGS   alignof(max_align_t)
#define TAG_MASK   ((uintptr_t)(MAX_TAGS-1))
#define PTR_MASK   (~TAG_MASK)

// Check we have room for at least four tags
static_assert(alignof(max_align_t) >= 4);

#define OBJ_POINT  0
#define OBJ_RECT   1
#define OBJ_CIRCLE 2

typedef struct {
    int x, y;
} Point;

typedef struct {
    int x, y;
    float width, height;
} Rectangle;

typedef struct {
    int x, y;
    float radius;
} Circle;

// The type is defined as a structure to ensure that GraphicObject
// is different from any other type.
typedef struct { uintptr_t ptr; } TaggedPtr;
#define TAGGED_PTR_NULL ((TaggedPtr){0})

// We'll use the TaggedPtr to represen a generic objec
#define GraphicObject TaggedPtr

static inline TaggedPtr tag_ptr(void *p, int tag) {
    TaggedPtr tp;
    tp.ptr = (uintptr_t)p | tag ;
    return tp;
}
static inline void *untag_ptr(TaggedPtr tp) {
    return (void *)(tp.ptr & PTR_MASK);
}
static inline int get_tag(TaggedPtr tp) {
    return (int)(tp.ptr & TAG_MASK);
}

The allocation and tagging :

GraphicObject new_circle(float radius) {
    Circle *c = aligned_alloc(MAX_TAGS, sizeof *c);
    if (!c) return TAGGED_PTR_NULL;
    c->x = c->y = 0;
    c->radius = radius;
    return tag_ptr(c, OBJ_CIRCLE);
}

Dispatch:

void scale(GraphicObject obj, float sx, float sy) {
    void *obj_ptr = untag_ptr(obj);
    switch (get_tag(obj)) {
        case OBJ_POINT:  break; // ignore
        case OBJ_RECT:   scale_rectangle(obj_ptr, sx, sy); break;
        case OBJ_CIRCLE: scale_circle(obj_ptr, sx, sy);    break;
        default:         /* handle error */                break; 
    }
}

Pros & Cons

Pros
- No per‐object tag field → smaller objects.
- Compile‐time enforcement of pointer types (no scale(stdout) issue).
Cons
- Limited number of tags (bits used by alignment).
- Still a runtime switch.

Adding more tags

If more than few tags (let's say, more than 16) are needed, a good alternative is available if we are ready to accept some portability constraint.

Counting on the fact the the vast majority of the current CPU architecture only use 48 bits for addressing virtual memory, we can store the tag in the most significant (highest) 16 bits of the pointer.

The functions get_tag(), tag_ptr(), and untag_ptr() are conceptually similar and only shift the tag from/to the highest bits.

The impact on portability and, possibly, software longevity needs to be assessed before using this method.

4. Compile-Time Dispatch with `_Generic`

Concept

Use C11’s _Generic keyword to select the correct function based on the static type of the expression—no runtime overhead for dispatch.

#define scale(obj, sx, sy) \
    _Generic((obj),        \
        Circle*:   scale_circle,    \
        Rectangle*:scale_rectangle, \
        Point*:    scale_point      \
    )(obj, sx, sy)

Now calls like:

Point *p = new_point(5, 5);
scale(p, 2.0f, 2.0f);

are resolved at compile time to scale_point(p,2,2).

Caveats

Static‐only: _Generic cannot dispatch on runtime data; you cannot use it to iterate a heterogeneous list of GraphicObject, for example.
Verbosity: Every operation needs its own _Generic macro.
Limited flexibility: _Generic() has its own quirks and sometimes need extra care in how the functions are designed to accomodate its rules on the arguments type.

5. Type-Safe Void Pointers

You can combine _Generic with void pointers to get compile-time type check:

#define scale(obj, sx, sy)         \
    _Generic((obj),                \
        GraphicObject *: scale_dispatch,\
        Point *:         scale_dispatch,\
        Rectangle *:     scale_dispatch,\
        Circle *:        scale_dispatch \
    )(obj, sx, sy)

void scale_dispatch(void *obj, float sx, float sy) {
    switch (get_tag(obj)) {
        case OBJ_POINT:// Ignore            
            break;
        case OBJ_RECT:   scale_rectangle((Rectangle *)obj, sx, sy);
            break;
        case OBJ_CIRCLE: scale_circle((Circle *)obj, sx, sy);
            break;
        default:  // handle error
            break;
    }
}

It requires some more boilerplate, but completely remove the biggest weakness of using void pointers: the scale() macro ensures that scale_dispatch() can be called only on valid pointers.

The GraphicObject * will serve as a pointer to an object of unknown type instead of using void * and this will reinforce type-checking.

Conclusion

While C lacks built-in polymorphism, thoughtful application of void‐pointer tagging, function pointers, tagged pointers, and _Generic can yield flexible, type-safe, and reasonably efficient polymorphic APIs. Each approach carries its own trade-offs between binary size, runtime cost, and safety:

Void pointers + tags: simplest, but no compile-time checks.
Function pointers: mirrors C++ v-tables, moderate overhead.
Tagged pointers: memory‐efficient, but fragile portability.
_Generic: zero‐cost dispatch, compile-time only.

As I mostly write libraries and back-end software, I believe my duty is to balance these considerations, polishing an API so that the "real" programmer can write clear, concise, and correct code without worrying about too many underlying details.

Polymorphism in C is entirely possible—just plan for it!

A very minimal base for Concatenative Combinators

Remo Dentato — Sun, 15 Sep 2024 07:41:34 +0000

Introduction

In a previous article I described an abstraction algorithm for Concatenative Combinatory Logic (CCL) which uses a quite large base for convenience.

The reason was practical: the bigger the base, the shorter the abstracted expressions will be.

In 1, Brent Kirby provided examples of much smaller bases for CCL up to just two combinators and we might ask ourselves: "Does a smaller base exists?".

In other words, we are looking for a single combinator (let's call it 𝗯) from which we can derive any other concatenative combinator.

Of course, such combinator, if it exists, will equivalent to an expression using any of the other known bases.

In search of the single one

For our search, let's use the two-combinators base {𝘀',𝗸}:

          (𝑦) (𝑥) 𝗸  = 𝑥
  (𝑧) (𝑣) (𝑦) (𝑥) 𝘀' = ((𝑧) 𝑣) 𝑥 (𝑧) 𝑦

We are looing for a combinator 𝗯 from which we can calculate the two base combinators 𝘀' and 𝗸:

      𝗸  = (𝗯) 𝗯
      𝘀' = ((𝗯) 𝗯) 𝗯 = (𝗸) 𝗯

If such combinator exists, it is a base for the Concatenative Combinatory Logic.

Using an helping hand

Before starting, let's assume that the 𝗯 has a certain structure:

    𝗯 = (𝛾) (𝛽) (𝛼) 𝘁

where 𝘁 is a combinator such that:

  (𝑧) (𝑣) (𝑦) (𝑥) 𝘁 = (𝑣) (𝑦) (𝑥) 𝑧

Since {𝘀', 𝗸} is a base, we could abstract the free variables 𝑧, 𝑣, 𝑦, and 𝑥 from the left side expression and obtain a definition for 𝘁 which only contains 𝘀' and 𝗸 and no free variables. Due to the length of such definition, for convenience, we'll keep using 𝘁 in the following.

For the same reason, we'll use 𝗶 as a shorthand for the equivalent expression () (𝗸) () 𝘀' .

Searching ...

Let's start by finding combinators 𝛾, 𝛽, and 𝛼 such that (𝗸) 𝗯 = 𝘀':

  (𝗸) 𝗯 = (𝗸) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛼) 𝗸 
        = (𝛾) 𝛼 
        = 𝘀'

In other words, we need to find 𝛼 and 𝛾 such that (𝛾) 𝛼 = 𝘀'.

This can be simply achieved by choosing: 𝛼 = 𝗶 and 𝛾 = 𝘀':

   (𝛾) 𝛼 = (𝘀') 𝗶 = 𝘀'

We also need (𝗯) 𝗯 = 𝗸, which means:

  (𝗯) 𝗯 = ((𝛾) (𝛽) (𝛼) 𝘁) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛼) (𝛾) (𝛽) (𝛼) 𝘁
        = (𝛾) (𝛽) (𝛾) (𝛽) (𝛼) 𝛼
        = 𝗸

Lookin at the last equality, it means that 𝛼, 𝛽, and 𝛾 must be such that:

  𝗸 = (𝛾) (𝛽) (𝛾) (𝛽) (𝛼) 𝛼

We already found 𝛼 and 𝛾, we can substitute them in the expression to obtain:

  𝗸 = (𝛾)  (𝛽) (𝛾)  (𝛽) (𝛼) 𝛼
    = (𝘀') (𝛽) (𝘀') (𝛽) (𝗶) 𝗶
    = (𝘀') (𝛽) (𝘀') (𝛽) 𝗶
    = (𝘀') (𝛽) (𝘀') 𝛽

Now, to satisfy the equality

  𝗸 = (𝘀') (𝛽) (𝘀') 𝛽

we need 𝛽 to be a combinator that deletes three arguments and replaces them with 𝗸.

It's easy to see that the following combinator does the trick:

  𝛽 = (((𝗸) 𝗸) 𝗸) 𝗸

In fact:

  (𝑧) (𝑦) (𝑥) 𝛽 = (𝑧) (𝑦) (𝑥) (((𝗸) 𝗸) 𝗸) 𝗸
                = (𝑧) (𝑦) ((𝗸) 𝗸) 𝗸
                = (𝑧) (𝗸) 𝗸
                = 𝗸

Which gives us a definition for 𝗯:

   𝗯 = (𝘀') ((((𝗸) 𝗸) 𝗸) 𝗸) (𝗶) 𝘁

Since, by definition, any expression using only combinators, is a combinator itself, we have found our single-combinator base.

Conclusion

We have proved that there exist a base {𝗯} for the Concatenative Combinatory Logic that is formed by a single combinator.

The result is not surprising as the same result is valid in the standard Combinatory Logic and comes from the fact that the two computational model are equivalent.

For how impractical it may be to use a single combinator as a base, this results may be of interest in some specific context.

Bibliography

(1) The Theory of Concatenative Combinators,
Brent Kerby (bkerby at byu dot net).
Completed June 19, 2002. Updated February 5, 2007.
((link)(http://tunes.org/~iepos/joy.html))

Church-Rosser proof for CCL

Remo Dentato — Sat, 14 Sep 2024 15:29:24 +0000

In my previous article, I argued that the Church-Rosser theorem holds for Concatenative Combinators.

Providing rigorous proof was behind my abilities and I just presented a reasoning to convince you readers that it was true.

However, a few days ago, the new OpenAI model o1 was made available and I took it as an opportunity to check a key principle that I believe is true:

AI is here to augment our abilities and allow us to explore further, not to replace us!

So, I passed my entire article to the new o1 model in ChatGPT and ask it to create a proof for the Church-Rosser theorem.

It did it in 28 seconds and, beside the proof itself, it also provided me with the reasoning that it followed to create the proof:

Constructing clarity

Clarifying definitions and assumptions, and presenting a rigorous proof for the Church-Rosser theorem within Concatenative Combinators Logic, ensuring accuracy and compliance throughout the discussion.

Clarifying key concepts

I’m diving into terms, defining reduction rules, and ensuring clarity on confluence, leading to a precise statement of the Church-Rosser theorem.

Crafting reduction clarity

I’m working through the rules and language of concatenative combinator logic, including expressions, reduction rules, and their relations, to streamline the proof.

Taking a closer look

I’m exploring the Church-Rosser Theorem for concatenative combinator logic, demonstrating the confluent nature of the reduction system. This involves showing that any expression E reducible to both E1 and E2 can be further reduced to a common expression E3.

Tackling the reduction

I’m laying out the proof by first establishing that the reduction relation is locally confluent. This involves verifying that expressions reduce to distinct forms in one step and can be further reduced to a common form.

Pinpointing overlaps

I’m examining critical pairs in concatenative combinator logic, focusing on overlapping redexes caused by overlapping arguments (quotes). This narrows down the possible overlaps to specific cases.

Analyzing overlapping reductions

I’m examining the scenario where combinators share arguments, allowing one redex to overlap with another. This helps understand the limits of such overlaps in concatenative combinator logic.

Assessing termination and confluence

I’m mapping out that the reduction system is locally confluent. Now, I need to demonstrate it’s terminating to conclude that it’s confluent using Newman’s Lemma.

Defining a measure

I’m piecing together a well-founded measure M(E) on expressions E, ensuring that reductions consistently decrease this measure to establish termination in concatenative combinatory logic.

Pondering weak confluence

Hmm, I’m thinking about how weak confluence aligns with non-terminating reductions, like in lambda calculus, where Church-Rosser theorem steps in without assuming termination.

Defining critical pairs

I'm nearing the concept of critical pairs, essential for ensuring all potential overlaps in concatenative combinator logic are Joinable. This involves examining all possible overlaps and confirming joinability in each scenario.

Analyzing redex scenarios

I’m thinking through two redex cases. Let me see. First, no multiple reduction rules for a single redex. Second, nested redexes only reduce immediate quotes.

Confirming convergence

I’m piecing together that nested redexes don’t overlap, so the reduction system avoids divergence. Independent redexes are good, and the Church-Rosser theorem holds.

which allowed me to understand the proof itself better.

Below you'll find the unedited result. It looks correct to me and further reassures me of the correctness of the abstraction algorithm I described in the other article.

I deem this to be a successful example of how these new LLM models can help us fill the gaps in our knowledge and allow us to progress.

I would love to hear your thoughts in the comments.

WARNING: AI Generated content below.

The proof

The Church-Rosser theorem is a fundamental result in rewriting systems, including combinatory logic and lambda calculus. It asserts that if an expression can be reduced to two different expressions, then there exists a common expression to which both can be further reduced. In the context of concatenative combinator logic, we aim to prove that the reduction system is confluent, meaning the Church-Rosser property holds.

Definitions

Expressions

An expression in concatenative combinator logic is defined recursively:

Terminals:
- Variable: A symbol from a predefined set (e.g., 𝑎, 𝑏, 𝑐, ..., 𝑥, 𝑦, 𝑧).
- Combinator: A function that manipulates quotations (e.g., i, zap, dup, cons, dip, etc.).
- Quote: An expression enclosed in parentheses ( ... ).
Expressions: A sequence of terms (including quotes and combinators).

Reduction Rules

Each combinator has a specific reduction rule, defining how it transforms its arguments:

Identity (i):

   (𝑥) i → 𝑥

Zap (zap):

   (𝑥) zap → ε   (where `ε` denotes the empty expression)

Duplication (dup):

   (𝑥) dup → (𝑥) (𝑥)

Dip (dip):

   (𝑦) (𝑥) dip → (𝑥) (𝑦)

Cons (cons):

   (𝑦) (𝑥) cons → ((𝑦) 𝑥)

Run (run):

   (𝑥) run → 𝑥 (𝑥)

**Other combinators are defined similarly.

Reduction Relation

One-Step Reduction (→): Expression E reduces to E' in one step if E contains a redex (reducible expression) that matches a reduction rule, and E' is obtained by replacing that redex with its contractum (result of the reduction).
Multi-Step Reduction (→*): The transitive and reflexive closure of →. Expression E reduces to E' in zero or more steps.

Confluence

A rewriting system is confluent if for all expressions E, E1, and E2, whenever E →* E1 and E →* E2, there exists an expression E3 such that E1 →* E3 and E2 →* E3.

Statement of the Church-Rosser Theorem

Theorem (Church-Rosser):

In concatenative combinator logic, the reduction system is confluent; that is, for any expression E, if E →* E1 and E →* E2, then there exists an expression E3 such that E1 →* E3 and E2 →* E3.

Proof

We will prove the Church-Rosser theorem by demonstrating that the reduction system in concatenative combinator logic is confluent. The proof involves the following steps:

Establish that the reduction system is locally confluent.
Show that every reduction sequence is terminating for finite expressions.
Conclude confluence using Newman's Lemma.

Step 1: Local Confluence

A reduction system is locally confluent if, whenever an expression E reduces to E1 and E2 in one step (i.e., E → E1 and E → E2), there exists an expression E3 such that E1 →* E3 and E2 →* E3.

Critical Pairs and Overlaps

In concatenative combinator logic, critical pairs arise when two reduction rules overlap, potentially leading to different reductions from the same expression. To prove local confluence, we need to examine all possible overlaps of redexes and show that their reductions can be joined.

However, in our system:

Combinators act only on their immediate preceding quotes.
Each combinator consumes a fixed number of quotes.
Reductions are deterministic based on the combinator and its arguments.

Thus, overlapping redexes can only occur in limited and well-defined situations.

Case Analysis

We consider all possible cases where overlaps might occur.

Case 1: Independent Redexes

When two redexes are completely disjoint:

Expression: E = A B, where A and B are independent redexes.
Reductions:
- E → A' B by reducing A to A'.
- E → A B' by reducing B to B'.
Confluence:
- Since A' and B' do not interfere, we can further reduce A' B to A' B', and similarly, reduce A B' to A' B'.
- Conclusion: The reductions can be joined at A' B'.

Case 2: Nested Redexes

When one redex is inside another:

Expression: E = (E1) C, where E1 contains a redex.
Reductions:
- E → (E1') C by reducing inside the quote.
- E → E2 by applying the combinator C to (E1).
Confluence:
- After applying C, we get E2, which may contain E1 in its expanded form.
- We need to show that both reduction paths can be further reduced to a common expression.

However, in concatenative combinator logic, combinators do not reduce inside quotes unless explicitly applied. Since quotes are considered atomic with respect to outer combinators, reductions inside quotes do not interfere with reductions outside.

Conclusion: The reductions are independent and can be joined.

Case 3: Overlapping Redexes Due to Associativity

Associativity is not inherent in concatenative combinator logic; the application of combinators depends on the exact structure of the expression.

Conclusion: Overlapping redexes that could cause divergence do not exist in this system.

Conclusion of Local Confluence

Since in all possible cases the reductions can be joined, the reduction system is locally confluent.

Step 2: Termination

For finite expressions, the reduction system is strongly normalizing, meaning that all reduction sequences terminate.

Justification

Finite Expressions: The number of combinators and quotes in any finite expression is finite.
Reduction Rules: Each reduction either reduces the number of combinators or restructures the expression in a way that eventually leads to no further reductions.
No Infinite Expansion: Although some combinators (like dup) can duplicate quotes, the nesting of quotes is finite, preventing infinite expansion in finite expressions.

Note: For expressions involving recursion or infinite constructs, termination may not hold. However, for the purposes of proving confluence in the finite case, termination is sufficient.

Step 3: Applying Newman's Lemma

Newman's Lemma states that if a reduction system is terminating and locally confluent, then it is confluent.

Since we have established:

Termination: All reduction sequences for finite expressions terminate.
Local Confluence: The reduction system is locally confluent.

Therefore, by Newman's Lemma, the reduction system in concatenative combinator logic is confluent.

Conclusion

We have proven that concatenative combinator logic satisfies the Church-Rosser theorem for finite expressions. The key points are:

Deterministic Reduction Rules: Each combinator has a unique reduction rule that applies in a well-defined manner.
No Overlapping Redexes Causing Divergence: Due to the nature of the combinators and their fixed arity, overlapping redexes that could lead to non-confluence do not occur.
Termination and Local Confluence: Established for finite expressions, allowing us to apply Newman's Lemma.

Therefore, the reduction system is confluent, meaning that the order of reductions does not affect the final result. Any expression can be reduced to a unique normal form (if it exists), regardless of the reduction path taken.

Remarks

Infinite Expressions: For expressions that can lead to infinite reduction sequences (e.g., due to recursive combinators), the termination property does not hold. In such cases, more advanced methods are required to establish confluence.
Practical Implications: The confluence property ensures that the abstraction algorithm and other computations in concatenative combinator logic are consistent and reliable.

Literate Programming style for AI-Supported Coding

Remo Dentato — Tue, 23 Jul 2024 14:40:17 +0000

Introduction

I recently rewrote (for the n-th time) a small literate programming tool.
The concept always fascinated me: writing software structuring the code as an explanation of why it does what it does (as opposed to just setting up a bunch of classes, functions, variables, in the order the programming language forces me to do) always seemed a "good thing" to me.

Just have a look at the source code for my tng tool (of course, it is written using itself) and tell me how much easier it is to find your way in how the code works. A blessing for maintainers!

Reality, however, is much harsher. Very few programmers are also good writers, and I, for one, am no exception. Creating a document that is easy to read, well structured, and engaging is not a simple task. Literate Programming, for how interesting an idea it may be, never became mainstream and was left relegated to some small circle writing scientific software.

But then came AI. Whoever tried to use one of the many "copilots" around knows that to get any decent code out of them you have to go a great length in describing what you want, to get the proper logic, and create the right context to avoid the AI will hallucinate or re-invent functions that already existed.

This article explores the idea that Literate Programming, when combined with AI, could revolutionize the way we write and understand code. By leveraging AI to fill in the gaps, developers can focus more on the conceptual and design aspects of programming, potentially enhancing productivity and code quality.

What is Literate Programming?

Literate Programming, introduced by Donald Knuth in the 1980s, is a programming paradigm that intertwines code and documentation. Instead of writing code first and then documenting it later, developers write their programs as an exposition of logic in a natural language, interspersed with source code snippets. This approach aims to make the code more understandable and maintainable, as the documentation explains the thought process behind the code's structure and functionality.

In a traditional Literate Programming setup, a developer might describe the problem and solution in plain English, gradually introducing code snippets to illustrate specific points. This results in a comprehensive document that serves both as the program itself and its documentation, providing a clear narrative that can be followed by other developers or even the original author at a later date.

Literate Programming Meets AI

With the advent of sophisticated AI models, there's an exciting opportunity to enhance Literate Programming. By using a literate style, developers can describe the high-level structure and functionality of a program in natural language, leaving the AI to generate detailed code snippets or, vice-versa, write a snippet of code and ask for a comprehensive description of the way it works.

The key point is that code and documentation go hand in hand. They evolve together while the software is developed, the text part captures the reasoning behind the code and the code provides an implementation of what the text described. They are kept together to maximize the chance that code and text stay in sync.

This approach can significantly reduce the time spent on boilerplate code and help developers focus on the overarching design and logic of their programs.

Describing Programs to AI

Imagine you are tasked with creating a web application. Instead of jumping straight into coding, you start by outlining the application's features and functionalities in a literate programming style. For instance:

Introduction and Setup:
- We need a web application that allows users to register, log in, and manage their profiles.
- The application will use a standard MVC framework.
User Registration:
- The registration form should capture user details like name, email, and password.
- On submission, the data will be validated and stored in the database.
User Login:
- The login form should authenticate users using their email and password.
- Upon successful login, users will be redirected to their profile page.

By refining these descriptions, the developer provides a clear narrative for what the program should do. The AI can then take these descriptions and generate the necessary code, filling in the blanks with specific implementations. For example, given the description of the registration process, the AI might generate the HTML form, the validation logic, and the database interaction code.

Benefits of AI-Assisted Literate Programming

Enhanced Productivity: By offloading routine coding tasks to the AI, developers can focus on more complex and creative aspects of software design.
Improved Documentation: Literate Programming inherently produces better-documented code, which is further enhanced by the AI's ability to generate comprehensive and consistent descriptions of the code.
Learning and Collaboration: This approach can serve as an educational tool, helping new developers understand the rationale behind code structures and decisions. It also facilitates better collaboration among team members by providing a clear and detailed narrative of the code.

Conclusion

Literate Programming, when combined with AI, offers a promising new way to approach software development. By focusing on describing the program's functionality and structure in natural language, developers can leverage AI to handle the detailed coding tasks.

Also, AI can improve the quality of documentation by rewriting (in better English) sketchy or roughly outlined descriptions of the code. As pointed out earlier, great programmers are not necessarily great writers.

This synergy between human creativity and machine precision can lead to more efficient, error-free, and well-documented code.

To fully grasp the benefits of AI in this context, we must shift our focus.
I believe we should try this new approach; using one of the many LitProg tools available (of course, I'm using my tng tool but I'm biased :) try to establish a new workflow that mixes writing, prompting, coding, cut, and paste. I'm quite sure there's something to gain.

In conclusion, the integration of Literate Programming with AI support holds the potential to significantly enhance the software development process. By shifting some of the workload to AI, developers can focus on innovation and design, ultimately leading to better software and a more enjoyable programming experience. Embracing this shift in mindset can prove itself crucial to unlocking the full potential of AI-assisted programming.

Choose Your Own Coding Assistant

Remo Dentato — Sun, 11 Feb 2024 16:39:26 +0000

Introduction

In the ever-evolving landscape of AI-powered tools, assistants for software development have carved a niche for themselves, especially in the realm of coding.

This post reports the results of experimenting with four leading Large Language Models (plus a bonus guest star at the end of the article).

OpenAI's GPT-4, Meta CodeLlama70B, Meta CodeLlama7B, and Mistral Mixtral8x7B were tasked with coding challenges to evaluate which one reigns supreme as a coding assistant. The aim is to get an assessment of their capabilities and discern which LLM could be most beneficial for various coding tasks.

For GPT-4, I've selected the last release of GTP-4 Turbo (gpt-4-0125-preview) as it corrects some "laziness" that its predecessor had.

Testing Setup

The battleground for this comparison was set up in Visual Studio Code, enhanced by the "Continue" plugin, allowing for direct interaction with each LLM.

This setup mirrors the functionality of other coding assistants like GitHub Copilot and AWS Codewhisperer and offers more privacy control over your code (for example by running the LLM on private servers) and the option of switching to the best (or less expensive) LLM for the task at hand.

Here is how my setup appears:

Note, on the right end side, the answer I just got from CodeLlama70B.

The Tests

The LLMs were evaluated across eight critical areas in coding:

Code Generation: Their prowess in crafting code snippets or full modules from scratch based on requirements.
Code Explanation and Documentation: How well they could elucidate existing code and create meaningful documentation.
Unit Test Generation: Their ability to autonomously generate unit tests for existing code.
Debugging and Error Correction: Efficiency in identifying, explaining, and rectifying code bugs or errors.
Refactoring / Optimization Recommendations: The LLMs' capacity to suggest and implement code improvements for better quality and performance.
Code Review Assistance: Their ability to aid in code reviews by spotting potential issues and suggesting enhancements.
Security and Best Practices: Proficiency in detecting security vulnerabilities and enforcing best practices.
Requirements Analysis: The capability to comprehend software requirements in natural language and translate them into technical specifications. While this not being exactly "coding", it is quite related to that as there might be the need to further refine unclear requirements or somehow transform them (for example, to derive a Finite State Machine that will be further coded in a programming language).

The performance of each LLM has been rated on a scale from 0 to 3, with multiple tests, 19 in total, conducted in each area to ensure fair competition across tasks of the same area.

Throughout the tests, the system prompt has been kept very simple: it just sets up the role of the LLM as a coding assistant and instructs it to be concise and straight to the point (to avoid using too many tokens in lengthy and possibly useless explanations).

This has been done to assess the LLMs' native abilities and opens up the possibility of further increasing their abilities through specific system prompting.

The Results

Here is the summary of the tests:

GPT-4, not surprisingly, emerged as the overall victor, offering the most accurate and comprehensive assistance across all tasks.
CodeLlama70B and Mixtral8x7B were close competitors, being on par with GPT-4 in some specific areas.
CodeLlama7B, despite ranking last, showed potential in certain tasks, indicating that tailored prompting could enhance its performance. Its appeal is in its small size which allows it to run on consumer-grade hardware.

Here are the results for each category:

Some Task Examples

You can find the full list of tasks used for this test, with prompts and the output for each LLM, on Github. Note that I'll update it from time to time with new tests and, possibly, new LLMs.

Here are just a few examples of tasks used in the test.

FEN Counting: This task tested the models' knowledge of FEN strings for chessboard positions. While all four LLMs had some knowledge of what FEN was, only GPT-4 managed to generate completely accurate code. This might be one of those cases when having more "unrelated knowledge" could result in better performance.
Guideline Compliance: Surprisingly, none of the LLMs detected all deviations from a set of coding style guidelines, revealing an area where more work is due to ensure an LLMs can assist. Better prompting or even a RAG approach to ensure the proper guidelines are fully "understood" by the LLM might be needed.
Ambiguity Analysis: Sometimes requirements clash with each other, possibly generating confusion, rework, or bugs. This specific task was aimed to check if the LLM were able to identify conflicting or overlapping requirements. Interestingly, Mixtral8x7B ended up being better than CodeLlama70B at this task.

Conclusions

Setting up a personal coding assistant using these LLMs can mitigate concerns regarding data and code privacy issues, common with cloud-based solutions.

There are also cost factors to be considered, like the costs of hosting your own LLM, the benefits of the higher cost per token of GPT-4 (when compared with other cloud API solutions), and so on.

In conclusion, while GPT-4 stands out for its comprehensive support, smaller models may present viable alternatives depending on your specific needs.

The tests used for this assessment are meant to cover a wide area of tasks and get a feeling of how the different LLMs would perform. Take them as a first cut and conduct specific tests tailored to your use cases to make an informed choice.

One thing is sure: whoever is not using an AI assistant for coding, will need to do so very soon to avoid being left behind.

Now is the time to determine which task should benefit from using an AI assistant for coding and to what extent.

Bonus section

During the preparation of this post, Google launched their new LLM Gemini Advance, showing significant improvements over Google Bard.

I've quickly compared it with GPT-4 across the 8 categories. Further tests are surely needed but, in the meantime, here is a first cut view of how Gemini Advanced scored against GPT-4 overall:

and across the eight areas:

The two LLMs are quite close! Clearly Google's new LLM is a serious contender to the crown of "best LLM overall".

Crafting GPTs to Power Up Your Toolbox

Remo Dentato — Sat, 27 Jan 2024 09:05:52 +0000

Despite OpenAI GPTs, and their marketplace, are not really ready for widespread adoption, they present a unique opportunity to create powerful, AI-powered applications tailored to individual needs.

Creating a domain-specific tool using GPTs doesn't require complex programming skills or deep AI knowledge. The concept revolves around leveraging basic techniques to craft tools that may significantly enhance your work efficiency and productivity.

In this article, I want to show a concrete example of the steps needed to add domain knowledge to these tools and how easy is to do it.

Utilizing the Knowledge Base

The most flexible way to provide specific capabilities to GPTs is through defining "Actions" (calls to unrestricted APIs) that can offer dynamic information retrieval and interaction with other systems.

For many applications, however, the extensive capabilities provided by Actions might be overkill and not worth the hassle of setting up servers, dealing with security and authorizations, worrying about network bandwidth, and so on.

In this article, we'll use solely GPTs's "Knowledge Base" as a simpler, yet incredibly effective, alternative. By uploading a few files to the knowledge base, users can significantly enhance GPTs's ability to generate relevant, context-aware responses. Although there are limits to the number of files and their sizes, most use cases won't bump into these constraints.

You need to have the *Code Interpreter" enabled in your GPTs to have everything working:

Case Study: The Creative Bartender

To illustrate how we can do it, let's consider the creation of a tool to support a creative bartender. This AI-powered bartender has access to the book "Drinks of all Kinds - HOT AND COLD - FOR ALL SEASONS", published in 1896, containing an extensive collection of drink recipes and is tasked to generate new recipes based on user input (for example, a set of ingredients or the name of the drink to create).

Please don't try those drinks at home! Their taste and healtiness is, to say the least, dubious!

Bartender GPTs architecture

To better understand how these types of GPTs are structured, let's look at the overall architecture:

To construct our Bartender tool, we start with structuring its knowledge. Nothing good will come by just throwing a bunch of PDFs at it. It's like teaching to humans: one thing is to provide relevant, and structured, material to learn from, and another one is to just tell them to read hundreds of pages hoping they'll pick up what we intended them to learn.

Let's organize the knowledge this way:

Keywords.txt: This file contains indexed keywords, acting as a Retrieval-Augmented Generation (RAG) component, providing the Bartender's ability to suggest recipes that are related to the user input. This is the static knowledge of our AI: just a set of keywords and the information in which recipes they are mentioned:

          ....
          egg is 13.
          gin is 14.
          japanese is 15.
          jersey is 16.
          jersey is 17.
          crystal is 17.
          ice is 17.
          ....

The prompt will instruct the LLM to use this static knowledge to identify keywords in user's input and determine the recipes that are related to these keywords (identified by a number).

recipes.py: This script handles the extraction from the recipes database of those recipes identified by the LLM as related to the user's input. If there are less than two recipes identified, it will select random recipes to provide enough material to create novel concoctions. In our example the task is simple but you can imagine to have a script that performs more complicated tasks.
recipes.db and offsets.ndx: The actual database with recipes data extracted from the book. It could have been a SQL database (for example, using sqlite) or any other suitable format.
prompts.md: Everything is governed by the prompt which is reported here verbatim:

## Role 
You are a creative bartender whose task is to create new recipes 
based on existing recipes.

## Instructions
  - Based on your knowledge, choose words that are related to the
    user prompt and take their associated {numbers}
  - Execute the `recipes.py` script passing as arguments the {numbers}:
      `%run /mnt/data/recipes.py {number} {number} ...`
  - Use the information in the {title} and {recipe} to create a new
    recipe.

## Constraints
  - Do not use any other information than the recipes 
  - Write the description of the recipe in a discoursive style,
    do not use lists or bullet point
  - Use the same writing style as the original recipes

The directions given in the Instructions and Constraints sections work together to ensure that the LLM will stay within the boundary of its knowledge.

The way to execute the script is also explicitly mentioned to avoid the LLM, hallucinating, would create his own Python script (it tried to do so a couple of times before I included this specific instruction).

This is an example of the activation of recipes.py on the prompt

Make an "Imperial Dog Apple Drink"

Note how the output of the script is structured as two quoted strings, one labeled title and the other labeled recipe. These labels are referred to in the prompt as {title} and {recipe} to guide the final LLM step and make it produce a text based on the script output.

The AI/UI Pattern

This Bartender example also shows a common pattern in AI tool design, which I call AI/UI, where an LLM is used to process user input and determine the actual parameters to be passed to a program, and it is used again to humanize the program's output.

This is one of the most common uses for LLMs: being a human-friendly User Interface for programs.

Conclusion

This "Creative Bartender" example highlights the simplicity and the potential of using GPTs to create domain-specific AI-powered tools.

As GPTs, or similar developers-friendly platforms, evolve making it easier to deploy such custom tools, we can anticipate a rapid growth of innovative AI-powered applications. To be ready for that time, now is the right time to experiment, exploring how AI can enhance our efficiency and creativity across various domains.

If you have access to GPTs marketplace, you can directly interact with the "Creative Bartender".

The full code and text files are available on Github.

Are small AI better for programming?

Remo Dentato — Sat, 20 Jan 2024 22:16:44 +0000

Introduction

I've been immersed in the world of computer programming since the era of 8-bit computers, witnessing its evolution firsthand. Back then, programming was about the intricacies of hardware, meticulous manipulation of bits and bytes and using GOTO. Over time, we got the various programming styles: functional, procedural, object oriented, using higher and higher level of abstractions, and now, we hear talks of its "end of life" due to the rise of AI.

What is "Programming"?

I do not really agree with this view. I firmly believe that the essence of programming will always remain relevant:

Computer programming is the task of understanding a problem and articulating, in an extremely clear way, how a computer system must operate to provide a solution to that problem.

Just as we transitioned from dealing with individual CPU instructions to working with abstract data types and classes, we are now advancing towards a paradigm that aligns even more closely with natural language. This evolution doesn't signify the end of programming; rather, it represents a transformation in how we conceptualize the problems we want to solve and how we articulate their solutions.

The role of AI

And for this, the role of AI, especially Large Language Models (LLMs), has become increasingly significant. My journey through this landscape has been one of exploration and discovery, focusing on how AI can enhance the programming process.
Many see, and use, AI as a sort of glorified autocorrect in coding, offering suggestions and corrections up to entire, fully developed, functions. That's a fair and productive way to use it but I believe that the true potential of AI in programming lies far beyond these basic applications.

I often use the term "RubberGrokking" to describe the process of conversing with an AI to progressively clarify and refine the problem at hand, and to elucidate the most appropriate solution. That poor yellow plastic duck that used to silently stare at us while hearing our rants, is now able to get back at us with feedback, hints, and, sometimes, even useful artifacts.

The role of AI in programming is to engage the developer in conversations that will help clarify the problem and find the proper solution.

Take a walk on the Small side

After the intial tests with large LLM, my intrigue led me to consider smaller, fine-tuned AIs. The idea stemmed from the consideration that while large AIs know a lot about a wide array of topics, such extensive knowledge might not be necessary for specific programming tasks and might just be a waste of time and money. I mean, GPT-4 may know a lot about kittens, but when will I ever need that knowledge?

Using compact models promises several advantages: they're faster during inference, easier to fine-tune, and could potentially be hosted locally, addressing privacy concerns. Rather than using a single large model to rule them all, I could have many smaller, custom tailored models.

Initially, this smaller AI seemed like the perfect solution. But as I delved deeper, integrating both small and large models into my work, I could appreciate the major drawback: it's hard to get an adequate return on the time (and money) spent to create your perfect fitting model. By the time you've created the model you need, something else popped up: a new LLM, a new tool, a new need to fulfill.

The advantage of being heavy-weight

Besides the advantage of being just one API call away, large models showed me something I was not properly considering: the value of unrelated knowledge. Solving real world problems, like programming is meant to do, requires quite some knowledge of the world: we don't need just technical knowledge to do our job, we also need to know, depending on the type of application we are developing, what a mortgage is, what a grocery store is, and the fact that kittens will make your video tons on view on YouTube.

Large models, with their vast database of information, allow for exploring solutions on a higher level. They enable us to draw parallels and insights from seemingly unrelated fields. This broad knowledge base provides a rich context for problem-solving in programming.

Relying solely on a smaller model could mean constantly fine-tuning or retraining it to incorporate a wide range of knowledge. The effort involved in this process made me currently gravitate more toward larger models.

Conclusions (and moving forward)

With all that said, the idea of harnessing the benefits of smaller models (faster inference, privacy, …) still lingers in my mind. Maybe a properly trained model with the right balance of technical and world knowledge could be used as a base tool and then supplemented with the proper knowledge to handle the problem at hand.
Many research efforts are aimed at integrating Large Language Models (LLMs) with more structured representations of knowledge, such as Ontologies. This integration may bring new opportunities to re-evaluate the use of small models. Alternatively, in the meantime, some major breakthroughs could completely change our perspective on what 'small' and 'large' mean in this context.
My exploration into the optimal use of small versus large AI models in programming is still ongoing, and it's an exciting time to be part of this technological revolution. The field of AI-assisted programming is evolving rapidly and while traditional programming isn't disappearing, its future iteration will undoubtedly be transformed by AI, possibly in ways we can't yet fully comprehend.

A Concatenative Combinators abstraction algorithm

Remo Dentato — Mon, 04 Dec 2023 18:19:01 +0000

Abstract

Concatenative programming languages like Forth or Joy have their theoretical foundation in a computational model that is equivalent to 𝜆-calculus and Combinatory Logic: the Concatenative Combinatory Logic. This article shows a simple abstraction algorithm that is akin to the process of compilation.

In [1], Kerby discusses abstraction by converting expressions containing concatenative combinators to lambda expressions with variables and then proceeds by abstracting variables from the lambda expressions.

This article follows a more direct approach and provides abstraction rules that are aimed at making the algorithm easier to apply and implement.

Even if we are mostly interested in showing that such algorithm exists we have made an effort to choose a base of combinators that will keep the resulting expression as short as possible (abstraction usually leads to very long and complex expressions). Further improvements can be made while implementing the algorithm, but we won't discuss them here.

Expressions

The language of concatenative combinators is defined by the following EBNF:

   expression := term+
   term := combinator | var | quote
   quote := '(' expression? ')'
   combinator := [A-Za-z_][A-Za-z_0-9]*
   var := [𝑎𝑏𝑐-𝑥𝑦𝑧]

That can be summarized as:

An expression is a list of terms
A combinator is a term
A variable is a term
A quote (an expression enclosed in parenthesis) is a term
The nil quote () is a term

Note that variables are notated with a different set of symbols.

Some examples:

   (𝑦) dup
   (cons (𝑧)) sip (𝑦)
   (alpha) (beta) dip

The evaluation of an expression proceeds from left to right by finding the first combinator that can be successfully reduced (i.e. the one that has enough quotes at its left) and replacing it and its arguments with the result of its application to the arguments.

We assume that, as in classical Combinatory Logic, the Church-Rosser theorem holds. While not a real proof, at the end of this paper we'll provide a reasoning that reassures us on the validity of the Church-Rosser theorem.

Concatenative Combinators

Let's use an intuitive definition of what a concatenative combinator is:

A combinator is an operator that shuffles, duplicates or removes
quotes there are at their left in an expression.

The behavior of a combinator is defined as an equivalence like this:

    (𝑦) (𝑥) swap  = (𝑥) (𝑦)

You can interpret the definition of swap above by saying that in any given expression you can replace any occurrence of:

    (𝑦) (𝑥) swap

with:

    (𝑥) (𝑦)

For the sake of reasoning (and as a possible strategy of implementation) we can think of a combinator as a program that operates on a stack:

A combinator is a program that pulls a certain number of quoted expressions from a stack and pushes back in the stack a number of expressions containing any number of them (even zero), possibily in a different order

(Non minimal) Base for concatenative combinators

To simplify the abstraction algorithm we'll use the following combinators:

                    (𝑥) i    = 𝑥
                    (𝑥) zap  = 
                    (𝑥) run  = 𝑥 (𝑥)
                    (𝑥) dup  = (𝑥) (𝑥)
                (𝑦) (𝑥) cons = ((𝑦) 𝑥)
                (𝑦) (𝑥) cosp = ((𝑦) 𝑥) (𝑦)
                (𝑦) (𝑥) dip  = 𝑥 (𝑦)
                (𝑦) (𝑥) sip  = (𝑦) 𝑥 (𝑦)

which are a superset of the bases defined in [1] and, hence, ensure that every possible expression can be represented using those combinators.

We'll extend the concept of combinator defintions by allowing a combinator to add other elements that were not in the original arguments.

For example:

              (𝑦) (𝑥) add = (𝑦) (succ) 𝑥
             (𝑦) (𝑥) mult = (zero) ((𝑦) add) 𝑥

Abstraction

The abstraction of an expression 𝓕 with respect to the variable 𝑥 is denoted with {𝓕}[(𝑥)].

The result of the abstraction of the variable 𝑥 from the expression 𝓕 is an expression 𝓖 that does not contain 𝑥 and that, when applied to (𝑥). will return 𝓕:

           𝓖 = {𝓕}[(𝑥)]  ->  (𝑥) 𝓖 = 𝓕

In a sense, abstraction is similar to compilation. Given an expression 𝓕 containing a variable 𝑥 (the source code) we can see {𝓕}[(𝑥)] as a program that when applied to a quoted expression (𝓡) will result in the original expression where any occurence of the variable 𝑥 is replaced by 𝓡.

When abstracting multiple variable we'll have:

         {𝓕}[(𝑦) (𝑥)] = {{𝓕}[(𝑥)]}[(𝑦)] = 𝓖

In other words, we first abstract wrt 𝑥, then 𝑦 and the result 𝓖 is such that (𝑦) (𝑥) 𝓖 = 𝓕.

Note that abstraction is defined with respect to a quoted variable as concatenative combinators are defined to only operate on quotes.

Abstraction rules

We'll use the following definitions:

𝑥 is a generic variable
𝓖 is a non empty expression that does not contain 𝑥 (i.e. 𝑥 does not occur in 𝓖)
𝓜 is an expressions that may contain 𝑥 (𝑥 may occur in 𝓜)
𝓝 is an expressions that do contain 𝑥 (𝑥 occurs in 𝓝)

Given an expression, looking at the list of terms from left to right there can only be the following cases:

The expression is empty;
The expression can be split in two parts with first terms containing the variable 𝑥 followed by other terms not containing 𝑥;
The expression can be split in two parts with first terms not containing the variable 𝑥 followed by other terms containing 𝑥;
The first term is a quote containing 𝑥 (otherwise it would have been accounted for in case 3) followed by an expression containing 𝑥 (otherwise it would have been accounted for in case 0);
The first term is the variable 𝑥 (unquoted).

This leads to the following abstraction rules:

     1           {}[(𝑥)] = zap
     2       {𝓝 𝓖}[(𝑥)] = {𝓝}[(𝑥)] 𝓖
     3       {𝓖 𝓝}[(𝑥)] = (𝓖) dip {𝓝}[(𝑥)]
     4    {(𝓝) 𝓜}[(𝑥)] = ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]
     5       {𝑥 𝓜}[(𝑥)] = run {𝓜}[(𝑥)]

Note that the expressions on the right side can't be reduced further without being applied to a quote.

It's easy to prove, by induction on the length of the expressions, that the algorithm converges: at each step the expressions to be abstracted become smaller and smaller.

In the following subsection we'll show that the rules do hold by applying them to (𝑥) and checking that the result is, indeed, the original expression.

Rule 1

This is the base case for when the expression is empty.

     1           {}[(𝑥)] = zap

Let's check that applying the result to (𝑥) we got the empty expression:

       (𝑥) zap
       ╰─────╯            by def. of zap
                      ◄── empty expression
       ╰╯                 by def. of abstraction
       (𝑥) {}[(𝑥)]

Rule 2

This rule allows us to stop earlier in the abstraction process: trailing terms not containing 𝑥 can be left untouched.

This is implied by the fact that the combinators are concatenative.

     2      {𝓝 𝓖}[(𝑥)] = {𝓝}[(𝑥)] 𝓖

Let's check that rule 2 holds:

     (𝑥) {𝓝}[(𝑥)] 𝓖
     ╰───────────╯        by definition of abstraction
     𝓝 𝓖
     ╰──╯                 by definition of abstraction
     (𝑥) {𝓝 𝓖}[(𝑥)]

Rule 3

This rule is to be applied when the expression consists of a list of terms which do not contain 𝑥 followed by a list of terms which contain 𝑥.

     3      {𝓖 𝓝}[(𝑥)] = (𝓖) dip {𝓝}[(𝑥)]

To prove that this rule holds, let's apply it to (𝑥) and check that the result is 𝓖 𝓝.

       (𝑥) (𝓖) dip {𝓝}[(𝑥)]
       ╰─────────╯                by def. of dip
       𝓖 (𝑥) {𝓝}[(𝑥)]
         ╰───────────╯            by def of abstraction
       𝓖 𝓝
       ╰──╯                       by def of abstraction
       (𝑥) {𝓖 𝓝}[(𝑥)]

Rule 4

This rule is to be applied when the expression consist of a quote that contains 𝑥 followed by a list of terms which contain 𝑥 (if they didn't we would have used rule 0).

     4    {(𝓝) 𝓜}[(𝑥)] = ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]

Let's apply it to (𝑥):

       (𝑥) ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]
       ╰──────────────────╯                by def. of cosp
       ((𝑥) {𝓝}[(𝑥)]) (𝑥) {𝓜}[(𝑥)]
        ╰───────────╯                      by def. of abstraction
       (𝓝) (𝑥) {𝓜}[(𝑥)]
           ╰────────────╯                  by def. of abstraction
       (𝓝) 𝓜
       ╰─────╯                             by def. of abstraction
       (𝑥) {(𝓝) 𝓜}[(𝑥)]

Rule 5

This is the rule to apply when the first term is 𝑥.

     5         {𝑥 𝓜}[(𝑥)] = run {𝓜}[(𝑥)]

To show that rules 5 holds, let's apply it to (𝑥):

               (𝑥) run {𝓜}[(𝑥)]
               ╰─────╯              by def. of run
               𝑥 (𝑥) {𝓜}[(𝑥)]
                 ╰───────────╯      by def. of abstraction
               𝑥 𝓜
               ╰──╯                 by def. of abstraction
               (𝑥) {𝑥 𝓜}[(𝑥)]

Optimization

The only optimization we mention here is the possibility of simplifying some special cases:

     3a         {𝓖}[(𝑥)] = zap 𝓖
     4a    {(𝑥) 𝓜}[(𝑥)] = dup {𝓜}[(𝑥)]
     4b      {(𝓝)}[(𝑥)] = ({𝓝}[(𝑥)]) cons
     4c       {(𝑥)}[(𝑥)] = 
     5a         {𝑥}[(𝑥)] = i

They can be easily checked as we did in the previous section.

Note that those special cases are included in the general case when one of the expressions is empty or has a special form.

Let's give just one example that shows that rule 4b is implied in rule 4 when the expression 𝓜 is empty.

     4    {(𝓝) 𝓜}[(𝑥)] = ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]
     4b      {(𝓝)}[(𝑥)] = ({𝓝}[(𝑥)]) cons

It's easy to see that, under the assumption of 𝓜 being empty, the two are equivalent:


  (𝑥) {(𝓝) 𝓜}[(𝑥)]
      ╰────────────╯                 by rule 4
  (𝑥) ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]
                      ╰────────╯     by hypotesis that 𝓜 is empty
  (𝑥) ({𝓝}[(𝑥)]) cosp {}[(𝑥)]
  ╰──────────────────╯               by def. of cosp
  ((𝑥) ({𝓝}[(𝑥)])) (𝑥) {}[(𝑥)]
                       ╰──────╯      by rule 1
  ((𝑥) ({𝓝}[(𝑥)])) (𝑥) zap
                   ╰──────╯          by def. of zap
  ((𝑥) ({𝓝}[(𝑥)]))
  ╰───────────────╯                  by def. of cons
  (𝑥) ({𝓝}[(𝑥)]) cons
  ╰──────────────────╯               by rule 4b
  (𝑥) {(𝓝)}[(𝑥)]

Quotes

As said at the beginning. combinators only operate on quotes.

This is needed since (as in CL and 𝜆-calculus) there is no distinction between functions (programs) and data. Quotes are what make this distinction.

Note that we have assumed that quotes are transparent. i.e. that reductions may happen within a quote. This has the advantage that all expressions are reduced to their minimal form but also has the disadvantage of having to compute any single quotes even if they might be discarded at a later time. Opaque quotes allow for lazy evaluation and the content of a quote is evaluated only when (and if) it is really needed, not before.

From the abstraction algorithm there is no difference as the two type of quotes are equivalent.

The Church-Rosser theorem

The Church-Rosser theorem, plays a key role in the evaluation of an expression and the fact that it holds for concatenative combinators is an assumption for the abstraction algorithm to work. It is also essential for the discussion on transparent/opaque quotes in the preceding section.

It can be formulated in many different ways, this is one of them:

Let 𝓐 ⊳ 𝓑 be the reduction of the expression 𝓐 to the expression 𝓑; then
𝓤 ⊳ 𝓧 ∧ 𝓤 ⊳ 𝓨 ⇒ ∃𝓩: 𝓧 ⊳ 𝓩 ∧ 𝓨 ⊳ 𝓩

In plain words, if an expression 𝓤 can be reduced to two different expressions 𝓧 and 𝓨, then there is an expression 𝓩 to whom both 𝓧 and 𝓨 can be reduced.

Which means that the strategy of reductions is irrelevant as any of them will lead to the same expression 𝓩.

While the general proof of this theorem is quite complex, in our specific case (concatenative combinators that only act on quotes) it's pretty straightforwad to convince ourselves that the theorem holds.

Let's consider the following expression:

          (𝓊) A (𝓋) B

where A and B are combinators and 𝓊 and 𝓋 are generic expressions.

The only interesting case is when both of them can be reduced (i.e. they both are a redex). Let's consider one step of reduction.

If we reduce (𝓊) A, there will be no consequence on (𝓋) B, since it is already a redex.

If we reduce (𝓋) B the result can be:

a redex itself, which brings us in the same situation we were before the reduction,
a non reducible expression like (𝓈) (𝓉) C.

The resulting expression (𝓊) A (𝓈) (𝓉) C now contains only one redex ((𝓊) A) because the combinator C only operates on quotes and A is unquoted.

This reasoning can be repeated for a more general case but it's easy to see that the redex in an expression to do not interfere with each other and, hence, the order in which they are reduced is irrelevant for the end result.

UPDATE: An AI-generated proof is now available here. Please check it and provide your feedback if you feel inclined to do so.

Conclusion

We have defined an abstraction algorithm for Concatenative combinators that is simple enough to be implemented and even applied by hand

This frees us from the need to handle variables when using Concatenative Combinators.

We have also argued around the validity of the Church-Rosser theorem that is an assumption for the abstraction algorithm to work.

Here are the list of all the abstraction rules (including the special cases):

     1           {}[(𝑥)] = zap
     2       {𝓝 𝓖}[(𝑥)] = {𝓝}[(𝑥)] 𝓖
     3       {𝓖 𝓝}[(𝑥)] = (𝓖) dip {𝓝}[(𝑥)]
     3a         {𝓖}[(𝑥)] = zap 𝓖
     4    {(𝓝) 𝓜}[(𝑥)] = ({𝓝}[(𝑥)]) cosp {𝓜}[(𝑥)]
     4a    {(𝑥) 𝓜}[(𝑥)] = dup {𝓜}[(𝑥)]
     4b      {(𝓝)}[(𝑥)] = ({𝓝}[(𝑥)]) cons
     4c       {(𝑥)}[(𝑥)] = 
     5       {𝑥 𝓜}[(𝑥)] = run {𝓜}[(𝑥)]
     5a         {𝑥}[(𝑥)] = i

where

𝑥 is a generic variable
𝓖 is a non empty expression that does not contain 𝑥 (i.e. 𝑥 does not occur in 𝓖)
𝓜 is an expressions that may contain 𝑥 (𝑥 may occur in 𝓜)
𝓝 is an expressions that do contain 𝑥 (𝑥 occurs in 𝓝)

Bibliography

[1] The Theory of Concatenative Combinators,
Brent Kerby (bkerby at byu dot net).
Completed June 19, 2002. Updated February 5, 2007.
(link)

[2] Lambda-Calculus and Combinators, an introduction,
J. Roger Hindley, Jonathan P. Seldin
(link)

A Simple Unit Test Framework for C

Remo Dentato — Thu, 12 Oct 2023 19:29:10 +0000

`tst`: A Simple Unit Testing Framework for C

Every developer understands the undeniable importance of unit testing. While crafting a piece of software, it's equally crucial to ensure that it functions as intended. For those working in C, a myriad of testing frameworks abound, but I found them quite complex to use and had to write my own, single header unit testing framework.

You can find the entire project on GitHub.

Why `tst`?

At first glance, tst might seem like just another testing tool in an ocean of options. However, a closer look reveals its carefully thought out features:

Minimalistic Design: One of tst's standout features is its no-nonsense, clean design. There aren't any complicated configurations to wrestle with or convoluted syntaxes to learn. Everything is straightforward, making it an ideal choice for developers who appreciate simplicity and efficiency.
Flexibility in Grouping and Tagging: With tst, you can effortlessly tag and group tests, allowing for selective test executions. You can select which group of tests to execute via argument on the command line, this becomes an invaluable asset for large projects where running the entire test suite can be time-consuming.
Ease of Integration: Incorporating tst into your project couldn't be simpler. Just create a dedicated test directory, place the tst.h header and you're done. Each test will be a single program designed to check that some aspect of the program is working properly.
I've added a makefile to simplify the management of test. If you add a file named t_xxx.c in the test directory, it will be assumed to be a test and you can compile it with make t_xxx. With make runtest you will compile and execute all the tests in the directory that follow the naming convention.
Expressive Reporting: The framework produces a clear, concise, and informative reports. Each test outcome is reported, making it easy to pinpoint issues.

Function Highlights

Tst comes packed with intuitive functions:

tstrun( ... ): Groups and begins test execution, often used to enclose all tests.
tstcase( ... ): Define individual test cases with descriptive titles.
tstcheck(int test, ... ): Performs a test check and reports pass/fail status.
tstassert(int test, ... ): Similar to tstcheck, but halts the entire test suite upon a failure.
tstgroup(int test, ... ): A conditional test group. If the initial test is false, the entire group is skipped.
tstclk( ... ): Times and reports how long a block of code takes to execute.
tstdata( ... ) and tstnote( ... ): Provide additional data or notes for context within your test report.
tsttags( ... ): Specify the tags that are defined for selective disabling/enabling of groups of tests.
tstsettags(int argc, char **argv): Enable/Disable the tags according to what specified on the command line. For example, to disable tests that are related to MongoDB or files:

  my_test -UseMongDB -UseFiles

tsttag(tag): checks if a group of tests is enabled. For example:

   tstgroup(tsttag(UseMongoDB)) {
      // To be executed if the `UseMongoDB` group is enabled
   }

   tstgroup(!tsttag(UseFiles)) {
      // To be executed if the `UseFiles` group is disabled
   }

A Practical Dive

Let's dive into a practical example:

tstrun() {
  tstcase("Basic Arithmetic Checks") {
    tstcheck(1 + 1 == 2, "Addition seems off!");
    tstcheck(2 * 3 == 6, "Multiplication isn't working as expected");
    tstcheck(2 - 2 == 1, "Subtraction has an issue!");  // This will fail!
  }
}

Upon executing the above, tst produces a clean output like:

FILE ▷ basic_arith.c 
CASE┬── Basic Arithmetic Checks » basic_arith.c:4
PASS│  1 + 1 == 2 » basic_arith.c:5
PASS│  2 * 3 == 6 » basic_arith.c:6
FAIL├┬ 2 - 2 == 1 » basic_arith.c:7
    │╰  Subtraction has an issue!
    ╰── 1 KO | 2 OK | 0 SKIP
RSLT ▷ 1 KO | 2 OK | 0 SKIP

The report is crystal clear in identifying the problem. The failing test is flagged, and its associated message pinpoints the issue, all while indicating the precise file and line number.

Conclusion

Tst goes beyond just being a testing framework; it’s an advocate for efficient and effective software development. It strips away complexities, leaving developers with a pure, straightforward testing experience. Whether you're a seasoned C developer or just beginning your coding journey, tst has something valuable to offer. Dive into it, and you might soon find it becoming an indispensable part of your development process.

Happy testing!

What's in a C (NaN)box?

Remo Dentato — Sun, 01 Oct 2023 10:16:27 +0000

Most modern scripting languages use dynamic types: values carry a type (an integer, a decimal number, a string, ...) but variables don't. So you can write code like:

   x = 2.3
   x = "my string"

This is especially useful when you have an array whose elements can be of different types:

   arr[0] = 2.3
   arr[1] = "my string"

Alas, we C programmers do not have this luxury. Variables are typed and if, for example, your array need to contain values that can be integers, doubles or pointers, you are on your own.

Typically, this is solved by squeezing multiple values into a union:

  typedef union {
     double d;   // 8 bytes
     int    i;   // 4 bytes (most likely)
     void  *p;   // 8 bytes on 64-bits arch
  } myval_t;     // The entire union will occupy 8 bytes

  myval_t x;
  x.d = 2.3;
  x.i = 9; // The previous value is overwritten

The union will be big enough to contain the biggest type it needs to contain; in the example above the union will be (most likely) 8 bytes. I say "most likely" because the C standard does not mandate how unions will be packed but overlapping the values it's the common way to go.

To set or get a value, you will access the proper field: v.d for the double, v.p for the pointer and so on.

The problem is: "How can I know the type of the value?" The answer is simple: "You can't!"

If you need to do it, usually the type is stored explictly together with the value:

  #define VALTYPE_DOUBLE  1
  #define VALTYPE_INTEGER 2
  #define VALTYPE_POINTER 3

  typedef struct {
     int t;  // type
     union {
       double d;
       int    i;
       void  *p;
     } v;   // value
  } myval_t;

  myval_t x;
  x.v.d = 2.3;
  x.t = VALTYPE_DOUBLE;
  ...

The issue with this approach, besides having to update multiple fields, is that it's way to wasteful! An additional integer for each value you want to store!

In fact, this is not the way modern scripting languages do it. They use a neat trick called NaNBoxing which, to my shame, I was completely ignorant of until recently!

Once I got to know it, I had to implement a small header library C (available on Github).
It allows writing code like this:

  val_t A[10]; 

  A[0] = val(2.3);
  A[1] = val("my string"); // of course just the pointer, this is C!
  A[2] = val(35);

And later:

  if (valisdouble(A[k]))  {
    // do some double-y thing
  }
  else if (valisinteger(A[k])) {
    // do some int-ey thing
  }

I'll describe here how the library is used, the implementation details will come on a future post (hopefully).

The `val_t` type

After including the header:

  #include "val.h"

you will have a new data type val_t that can store a value of different types:

Signed or unsigned integers (up to 48 bits)
Double-precision floating-point numbers
Booleans. There are two constants defined: valtrue and valfalse which are different from any integer.
Nil. A constant different from any integer or boolean.
Generic pointers
Pointers to strings (char *)

The library provides a val() function to store values into a val_t variable:

val_t f = val(3.2);          // Stores a double value
val_t s = val("a string");   // Stores a pointer to a string

All the details on storing the type, etc are handled by val().

Retrieve values

Once your data is safely stored inside a val_t variable, you can retrieve it utilizing specific type conversion functions:

void * valtopointer(val_t v);
double valtodouble(val_t v);
float valtofloat(val_t v);
_Bool valtobool(val_t v);
long valtointeger(val_t v);
char * valtostring(val_t v);

and cast it as needed. For example:

  float a = 3.14;
  float b = 0.0;
  val_t x;

  s = val(a);                 // stored a float
  b = (float)valtodouble(s); // retrieved a float

Constants for Common Scenarios

The val library defines certain constants of type val_t to handle common scenarios and default values gracefully:

valfalse
valtrue
valnil
valnilpointer
valnilstr

Identifying the Stored Type

Determining the type of data stored within a val_t variable can be done using the valtype() function:

int valtype(val_t);

It returns one of these constants, each indicative of the nature of the stored data:

VALDOUBLE
VALINTEGER
VALBOOL
VALNIL
VALPOINTER
VALSTRING

For more context-specific checks, you might utilize a suite of helper functions:

int valisnil(val_t v);
int valisinteger(val_t v);
int valissigned(val_t v);
int valisbool(val_t v);
int valisdouble(val_t v);
int valispointer(val_t v);
int valisstring(val_t v);

Conclusion

The val library opens the doors to a world where C programmers can bask in the flexibility that is common of dynamically-typed languages like JavaScript.

Through utilization of the val library, developers can store and manage diverse data types without the need for complex, memory-consuming data structures, thereby achieving more with less.

Next post will deep dive into the NaNboxing details.

DEV Community: Remo Dentato

Finite States Machines (in C)

What it looks like

How it works (and why it’s safe)

Why this beats the usual switch

Where fsm shines

A tiny real-world sketch: comment stripper

Getting started

Credits

Polymorphic C (2/2)

Introduction

Default to 0

Pointers to NULL

Supply missing arguments

Skipping arguments

A Microsoft quirk

Counting arguments

Multiuse example

Zero arguments

Conclusion

Polymorphic C (1/2)

1. Void Pointers to Tagged Structures

Concept

Dispatch Function

Pros & Cons

2. Function Pointers in Object Tables (“Manual V-tables”)

Concept

Usage via Macros

Pros & Cons

3. Tagged Pointers

Concept

Pros & Cons

Adding more tags

4. Compile-Time Dispatch with _Generic

Concept

Caveats

5. Type-Safe Void Pointers

Conclusion

A very minimal base for Concatenative Combinators

Introduction

In search of the single one

Using an helping hand

Searching ...

Conclusion

Bibliography

Church-Rosser proof for CCL

The proof

Definitions

Expressions

Reduction Rules

Reduction Relation

Confluence

Statement of the Church-Rosser Theorem

Proof

Step 1: Local Confluence

Critical Pairs and Overlaps

Case Analysis

Case 1: Independent Redexes

Case 2: Nested Redexes

Case 3: Overlapping Redexes Due to Associativity

Conclusion of Local Confluence

Step 2: Termination

Justification

Step 3: Applying Newman's Lemma

Conclusion

Remarks

Literate Programming style for AI-Supported Coding

Introduction

What is Literate Programming?

Literate Programming Meets AI

Describing Programs to AI

Benefits of AI-Assisted Literate Programming

Conclusion

Choose Your Own Coding Assistant

Introduction

Testing Setup

The Tests

The Results

Some Task Examples

Conclusions

Where `fsm` shines

4. Compile-Time Dispatch with `_Generic`

`tst`: A Simple Unit Testing Framework for C

Why `tst`?

The `val_t` type