2024-07-22-Paradigms For Thinking About Problems And Programs

Jul 23, 2024

Programs are, ultimately, assembler.

Programming does not need to be functional.

Example: Prolog is a style of programming, you need to build an engine in assembler to use Prolog.

Functional programming is a style of programming, you need to build an engine in assembler to use functional programming. “Context-switching” and “traps” and “protection rings” are part of the engine, but, we tend not to recognize these as being auxiliary parts of software.

The epitome of FP is not Haskell, it’s Sector Lisp.

Sector Lisp uses FP to its advantage to reduce the size of the Garbage Collector (40 bytes)

Haskell uses a heap-based - i.e. non-FP style - GC.

Text-to-text transpilation is pure FP.

Macros in Lisp, without the non-functional baubles, like mutation, are text-to-text-transpilers (t2t).

I think that pure t2t should be done as a separate pass, and, not be wound into a PL that violates the basic principles of FP.

In 1981, most production code was written in assembler.

In 1981, the cost of layering engines on top of subroutines was obvious and “in your face”.

I was laughed at for suggesting that a high level language be used instead of assembler (in this case, the high level language was C)

In early programming, there was a pre-Cambrian explosion of ideas.

SNOBOL, Icon, Prolog, Smalltalk, ALGOL, Lisp, FORTRAN, Pascal, BASIC, Forth.

It was generaly understood that none of these covered all of programming.

Later, though, only one sub-style of programming became accepted as being The form of programming - function-based programming. It was “forgotten” that function-based programming requires an engine to support that style of programming.

Note that early FORTRAN did not use a call-stack and, thus, was “closer” to the hardware than later FORTRANs and PLs that support recursion. Recursion is a feature of function-based programming and requires the use of a call-stack, and, usually requires a context-switching engine.

There was no such thing as “open source” at the time.

You could legally view Unix source code and C source code if you were a student in University, but, in most cases source code was kept secret and hidden from view.

A big break-through was the publishing of the source code for Small-C in Dr. Dobb’s Journal for all to see what was going on in a compiler (just t2t, nothing to see, move on).

Butchering the Functional Programming Paradigm

We butchered the functional style by forcing distinctly non-functional ideas into it, like assignment and memory sharing.

We, incorrectly, think that this butchered form of functional programming is programming.

CPUs Are Interpreters. Programs Are Interpreters.

A CPU is just a simple chip that interprets data in memory.

A rasterizer is a different interpretation of data in memory.

A data structure representing rooms in a game gets interpreted by the game program.

Premature Functionalization

Bane of our existence: assuming a function-based mindset before designing and building the software, instead of using the most appropriate paradigm(s)/notation(s) to handle the given problem.

For example, I’d bet that Hest is developed using a 3GL, like Python, Javascript, Haskell, Scala, etc. These all force one to adopt the function-based mindset at the outset, even though the function-based paradigm is probably not the most appropriate for thinking about Hest. If so, I would bet that development is progressing slower than was hoped.

VPLs - Visual Programming Languages - have gotten a bad name, because most VPLs suffer from premature functionalization.

Likewise, implementations of Actors tend to suffer from premature functionalization. Actors are often implemented using threads, which are just epicycles bolted onto the functional programming paradigm. Threads don’t serve the concept of Actors very well.

The function-based paradigm is not suitable for true concurrency.

Most modern problems involve true concurrency, e.g. internet, GUIs, robotics, blockchain, etc.

We see tells of such non-suitability with the development of epicycles such as promises, futures, monads, etc.

Smallness vs. Bigness

Early programs used to be understandable and debuggable. When programs became larger, problems began occurring.

It was decided / backed-into to make programs larger by gluing more code together in a flat manner. Such programs tend to use text.

The real problem is that developers can’t see enough of the big program at once, hence, can’t keep all of the inter-dependencies in mind.

Solutions to the problem of bigness evolved in epicyclic form, e.g. hand-wringing about global variables, hand-wringing about free variables, strong typing, etc., etc.

In my opinion, a better solution to bigness is the heavy use of layering, and, what I call The Rule of 71. Keep each layer simple-enough to understand, don’t throw details away, just push details aside onto several other layers.

Layering encourages loose coupling.

Clockwork encourages tight coupling.

The function-based mindset is the idea of making clockwork. To make bigger programs this way, you devise more gears, without using “clutches”, and, shove them into the clockwork to make bigger programs.

Global variables are not a problem

Screen real-estate is the problem.

Too many niggly details, presented as walls of detail, is the problem.

True async needs loose coupling.

True async cannot be described by synchronous programs.

By definition.

“Synchronous” is the antithesis to “asynchronous”.

Software is just soft hardware.

Yet, software is designed very differently from hardware.

Over-use of Synchronization

Over-use of synchronization was not a big deal on single CPU systems, but, causes pain-points when applied to async problems and distributed problems, like internet, GUIs, robotics, etc.

Subroutines are a code-saving measure. Subroutines were not invented to support functions.

Support for recursive functions needs to be faked on top of subroutines.

Another phrase for the over-use of synchronization is “micro-management”.

Stacks vs. Queues

Functions return values using a fake data structure - the (shared) stack.

We could, instead/in-addition, use a different fake data structure - the queue.

Worse, function return values are intermingled with subroutine bookmark storage.

The beauty of Lisp 1.5 was that it faked out a simple VM for function-based programming that was incredibly useful, but this was faked out, nonetheless. I suspect that McCarthy understood the difference, but a religion sprung up around Lisp’s functional programming and it became The One Way to program. Disciples forgot that this was just a paradigm built on top of a non-functional substrate and that compute-ing is only a subset of what reprogrammable electronic machines are capable of.

Virtual Machines - VMs

The concept of VMs was not pervasive in the early days of computers. Tiny Basic (2Kbytes in size) used a VM, but, didn’t call it a VM. Anyway, using an interpreter to interpret an interpreter (hardware interpreting Tiny Basic byte-codes) was laughed off as being too inefficient.

GC was considered to be ridiculously inefficient. Lisp 1.5 contained an explicit GC (heap-based, instead of FP-based) which led to the avoidance of Lisp. Later, Java popularized the concept of GC.

Backtracking (Early’s parser, Prolog) was considered to be ridiculously inefficient.

Programming in the early days, placed too much emphasis on co$t, instead of on a future which benefitted from economies of scale. The early phobias about inefficiency infect modern programming even today.

The Best CPUs

The best2 cpu was the NS16032, similar to PDP-11 and VAX but cleaner.

Motorola’s 6809 was better than Intel x86.

Motorola’s 6809 was better than Motorola’s 68000.

Intel won the “VHS vs. Beta” battle.

6502 architecture was used in a lot of game machines.

Intel architecture was painful to program, e.g. 286 and segment registers, a forerunner to cheapified, and more general, MMU technologies.

The Ideal IDE vs. Optimized Production Code

The ideal IDE would conjoin multiple paradigms to produce 1 program. This should be a feature of IDEs, not of runtimes.

Programs don’t need data structures in production code. Data structures are useful only for development.

Programs don’t need type checking in production code. Static type checking is useful only for development. Dynamic type checking is useful during development and for buggy production code.

Production Engineers should be optimizing-away all type checking, functional programming, scoping, etc. from production code. Those are tools for developers, not for end-users.

Context Switching Engine

I learned to program context-switching from https://www.amazon.com/Structured-Concurrent-Programming-Applications-Addison-Wesley/dp/0201029375 and https://www.amazon.ca/Concurrent-Euclid-Unix-System-Tunis/dp/0201106949.

Paradigms For Thinking About Problems And Programs

String creation with string interpolation (/bin/sh, JavaScript ‘+’, ${...}, Python f’{...}’, etc.)
PEG parsing of text. PEG uses backtracking. CFG and REGEX technologies don’t use backtracking. PEG is better. OhmJS is currently my favourite PEG.
Writing programs that write programs. T2t - text to text transpilation. Lisp macros (without the rest of Lisp or Scheme or Racket) are t2t.
Backtracking. Prolog. SWIPL is my current favourite Prolog. GNU Prolog uses WAM (Warren’s Abstract Machine - a Prolog VM) and is self-compiling and can be commanded to show the generated WAM code. (Kinda like ‘-E’ for C compilers).
Relational Logic. Prolog, miniKanren, Datalog. A non-functional, much more declarative way to express programs and to express one of the major activities of all programs, i.e.inhaling data and grokking it.
StateCharts, Drakon. Ways to express control flow without conflating control flow with data. Both are forms of Diagrammatic Programming Languages - DPLs.
Subroutine invocation without recursion.
Little networks.
Little languages.
Hybrids of visual and textual notations.
Sequenced vs. Recursive containerization. The lesson from Lisp is not how to silk-screen T-shirts, but, that recursively-defined data structures can be useful. In particular, when such data structures are interpreted as program instructions. Assembler is sequential and line-oriented due to the array nature of RAM, wheres Lisp has a recursive containerized syntax and interprets Lists as program instructions. In Lisp 1.5, there are only 2 types: Lists and Atoms. Lists are recursively defined and can contain Lists or Atoms. Atoms, though, are rock-bottom entities.

Various References

Rule of 7: https://guitarvydas.github.io/2023/04/03/Rule-of-7.html (the missing obsidian blogs are currently being ported to Github Pages)

Dr. Dobb’s Journal: https://en.wikipedia.org/wiki/Dr._Dobb's_Journal

WAM tutorial: https://direct.mit.edu/books/monograph/4253/Warren-s-Abstract-MachineA-Tutorial-Reconstruction

StateCharts: https://guitarvydas.github.io/2023/11/27/Statecharts-Papers-We-Love-Video.html

Drakon:

https://drakon-editor.sourceforge.net/

(actual rocket science ; the 3-part PDFs are very informative https://drakon-editor.sourceforge.net/language.html)

Blog

Videos: https://www.youtube.com/@programmingsimplicity2980

Discord: https://discord.gg/Jjx62ypR

Leanpub: https://leanpub.com/u/paul-tarvydas