{"id":11049,"date":"2025-07-10T01:09:00","date_gmt":"2025-07-10T05:09:00","guid":{"rendered":"https:\/\/www.both.org\/?p=11049"},"modified":"2025-07-09T13:11:42","modified_gmt":"2025-07-09T17:11:42","slug":"a-small-algol-68-project-part-1","status":"publish","type":"post","link":"https:\/\/www.both.org\/?p=11049","title":{"rendered":"A Small Algol 68 Project, Part 1"},"content":{"rendered":"
\r\n
\r\n \r\n <\/i>\r\n <\/a>\r\n <\/span>\r\n<\/div><\/div>\n

In memory of J. Kevin Douglas, a good friend and fellow fan of Algol 68<\/em><\/p>\n\n\n\n

In the last article in this series<\/a>, we looked at our first simple Algol 68 program:<\/p>\n\n\n\n

\n

     1    BEGIN<\/code><\/p>\n\n\n\n

     2        first random(42);<\/code><\/p>\n\n\n\n

     3        REAL sum of randoms := 0.0;<\/code><\/p>\n\n\n\n

     4        WHILE sum of randoms < 10.0 DO <\/code><\/p>\n\n\n\n

     5            REAL r := next random;<\/code><\/p>\n\n\n\n

     6            sum of randoms +:= r;<\/code><\/p>\n\n\n\n

     7            print((\"random number = \",r,\"; sum = \",sum of randoms,new line))<\/code><\/p>\n\n\n\n

     8        OD<\/code><\/p>\n\n\n\n

     9    END<\/code><\/p>\n<\/div>\n\n\n\n

As we  reviewed the program line-by-line to understand its meaning, we learned some Algol 68 terminology to describe what is going on in those nine lines of code.<\/p>\n\n\n\n

And, I know I said \u201cIn the next article, we\u2019ll dig into a few of the less obvious but still important details that make this all work.  Then we can move on to see some more cool things that we can do in Algol 68<\/em>\u201d, but I\u2019m going to postpone that until we have some more useful code examples developed.<\/p>\n\n\n\n

Because in the end, this little program is about as  interesting a demo of Algol 68 as a \u201cHello World\u201d.  Let\u2019s  do something a bit more useful for now.<\/p>\n\n\n\n

I think it\u2019s fair to say that Algol 68 reflects some of the interests of computer scientists of the 1960s.  In particular, with its interest in handling arrays and looping, we can see the interest in numerical computation.  So why not look at a simple approximation problem through the Algol 68 lens?<\/p>\n\n\n\n

Vectors, matrices and least squares estimation<\/strong><\/h2>\n\n\n\n

A common problem to solve for anyone handling data in the real world is using least squares estimation to produce a \u201cbest fit\u201d of an equation to a set of data.  Of course, in 2025, we can use a special purpose language like R or numerical statistics libraries called from general purpose languages like C  or Java to solve this kind of problem; but for really simple problems, it\u2019s kind of cool to know how to \u201cdo it yourself\u201d.<\/p>\n\n\n

[pmath size=12]S(f)(t)=a_{0}+sum{n=1}{+infty}{a_{n} cos(n omega t)+b_{n} sin(n omega t)}[\/pmath]<\/p>\n\n\n\n

Let\u2019s imagine we have a text file in CSV format, with two columns containing x<\/em> and y<\/em> values, and we want to fit those values with a straight line so that we minimize the error of approximating the point values with the straight line.<\/p>\n\n\n\n

We know the equation of a line is:<\/p>\n\n\n\n

y = m \u00b7 x + b<\/em><\/p>\n\n\n\n

where m<\/em> is the slope of the line and b<\/em> is the y-intercept.<\/p>\n\n\n\n

If there are only two points in our CSV file, we know we can fit a line to them exactly.  However, if there are three or more points, then we need to choose values for m<\/em> and b<\/em> to \u201cbest fit\u201d those x<\/em> and y<\/em> values.  If we rewrite the above equation slightly as:<\/p>\n\n\n\n

m \u00b7 x + b \u00b7 1 = y<\/em><\/p>\n\n\n\n

That is, m<\/em> is the coefficient of x<\/em>, b<\/em> the coefficient of 1 (I know that might sound a bit weird but bear with me here).<\/p>\n\n\n\n

And we think of our CSV file as having n+1 lines, looking like:<\/p>\n\n\n\n

\n

X-value,Y-value<\/code><\/p>\n\n\n\n

x1<\/sub>,y1<\/sub><\/code><\/p>\n\n\n\n

x2<\/sub>,y2<\/sub><\/code><\/p>\n\n\n\n

x3<\/sub>,y3<\/sub><\/code><\/p>\n\n\n\n

\u2026<\/code><\/p>\n\n\n\n

xn<\/sub>,yn<\/sub><\/code><\/p>\n<\/div>\n\n\n\n

then we can see that this leads to a system of linear equations that looks like:<\/p>\n\n\n\n

\n

m \u00b7 x1<\/sub> + b \u00b7 <\/em>1 = y1<\/sub><\/em><\/p>\n\n\n\n

m \u00b7 x2<\/sub> + b \u00b7 <\/em>1 = y2<\/sub><\/em><\/p>\n\n\n\n

m \u00b7 x3 + b \u00b7 <\/em>1 = y3<\/sub><\/em><\/p>\n\n\n\n

\u2026<\/p>\n\n\n\n

m \u00b7 xn<\/sub> + b \u00b7 <\/em>1 = yn<\/sub><\/em><\/p>\n<\/div>\n\n\n\n

which we can write in matrix form as<\/p>\n\n\n\n

X <\/em>c<\/u> = y<\/u><\/p>\n\n\n\n

where X<\/em> is the matrix:<\/p>\n\n\n\n\n \n \n \n \n \n \n \n \n \n
\n <\/td>\n \n x1<\/sub><\/em>\n <\/td>\n \n 1\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n x2<\/sub><\/em>\n <\/td>\n \n 1\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n x3<\/sub><\/em>\n <\/td>\n \n 1\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n …\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n xn<\/sub><\/em>\n <\/td>\n \n 1\n <\/td>\n \n <\/td>\n <\/tr>\n<\/table>\n\n\n\n

c<\/u><\/em> is the vector of coefficients we\u2019re solving for:<\/p>\n\n\n\n\n \n \n \n \n \n
\n <\/td>\n \n m<\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n c<\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n<\/table>\n\n\n\n

and y<\/u><\/em> is the vector:<\/p>\n\n\n\n\n \n \n \n \n \n \n \n \n
\n <\/td>\n \n y1<\/sub><\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n y2<\/sub><\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n y3<\/sub><\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n …\n <\/td>\n \n <\/td>\n <\/tr>\n
\n <\/td>\n \n yn<\/sub><\/em>\n <\/td>\n \n <\/td>\n <\/tr>\n<\/table>\n\n\n\n

You remember this from your high school or undergrad linear algebra course, right? The hard part is done, now I just have to wave my hands a bit and tell you that:<\/p>\n\n\n\n

    \n
  1. This is what is called an \u201coverdetermined\u201d system of equations;<\/li>\n\n\n\n
  2. We can solve this problem in a least squares fashion by premultiplying both sides of the equation by the transpose of the matrix X<\/em>, which we denote as XT<\/sup><\/em><\/li>\n<\/ol>\n\n\n\n

    That is,<\/p>\n\n\n\n

    XT<\/sup> X c<\/u> = XT<\/sup> y<\/u><\/em><\/p>\n\n\n\n

    What this means is that, by forming the products of XT<\/sup>X <\/em>and  XT<\/sup>y<\/u><\/em>, we will end up with a two-rows by two-columns matrix and a two-row vector respectively, with which we can solve for the two-row vector c<\/u>.<\/p>\n\n\n\n

    Good so far?  Awesome, let\u2019s plan the tasks we need to handle.  I should mention that this excellent article from Oxford University Press<\/a> will dispel the hand-waving used in my explanation above.<\/p>\n\n\n\n

    Steps to solve the linear least squares matrix formulation<\/strong><\/h2>\n\n\n\n

    We need t the following:<\/p>\n\n\n\n

      \n
    1. A test data set;<\/li>\n\n\n\n
    2. Some utilities to let us read CSV files;<\/li>\n\n\n\n
    3. The least squares approximation program that reads the CSV file, calculates X<\/em>T<\/em>X<\/em> and  X<\/em>T<\/em>y<\/em> and solves for c<\/li>\n<\/ol>\n\n\n\n

      We\u2019ll finish up this article by writing a test data set generator.<\/p>\n\n\n\n

      Test data generator<\/strong><\/h2>\n\n\n\n

      Recall the equation of a line given previously:<\/p>\n\n\n\n

      y = m \u00b7 x + b<\/em><\/p>\n\n\n\n

      Let\u2019s create a set of points that lie along the line that joins x = 0, y = 1 with x = 9, y = 10.  This corresponds to a specific line with the equation:<\/p>\n\n\n\n

      y = x + <\/em>1<\/p>\n\n\n\n

      Furthermore, let\u2019s use the random number generator described in the last article and shown at the top of this article to add a small random offset to the y value in our generated points.  With enough points, we intuitively feel that the least squares fit to the points should give values to m and b similar to the above.<\/p>\n\n\n\n

      Here\u2019s the code:<\/p>\n\n\n\n

      \n

           1    BEGIN<\/code><\/p>\n\n\n\n

           2        first random(42);<\/code><\/p>\n\n\n\n

           3        REAL x1 = 0.0, y1 = 1.0, x2 = 9.0, delta = 1.0 \/ 64;<\/code><\/p>\n\n\n\n

           4        REAL x := x1, y := y1;<\/code><\/p>\n\n\n\n

           5        print((\"X-value\", \",\", \"Y-value\", new line));<\/code><\/p>\n\n\n\n

           6        WHILE x <= x2 DO<\/code><\/p>\n\n\n\n

           7            REAL y adj = y + (next random - 0.5) \/ 8.0;<\/code><\/p>\n\n\n\n

           8            print((fixed(x,7,5), \",\", fixed(y adj,7,5), new line));<\/code><\/p>\n\n\n\n

           9            x +:= delta;<\/code><\/p>\n\n\n\n

          10            y +:= delta<\/code><\/p>\n\n\n\n

          11        OD<\/code><\/p>\n\n\n\n

          12    END<\/code><\/p>\n<\/div>\n\n\n\n

      We won\u2019t go through this line by line as there isn\u2019t much that is different than in the previous program.  However:<\/p>\n\n\n\n

      In line 3, we see the beginning x and y values and the end x value (we don\u2019t need the end y value as we\u2019re going to just test for x reaching the end), and a delta value, used to increment x and y, of 1\/64.  These are all constants.<\/p>\n\n\n\n

      In line 7 we see the y value being adjusted by the \u201cnext random\u201d value, which falls between 0 and 1, less -0.5, which then falls between -0.5 and +0.5, and finally divided by 8 so that the random adjustment is never greater than 1\/16 or less than -1\/16. <\/p>\n\n\n\n

      We can run this with Algol 68 Genie in a Linux terminal window as:<\/p>\n\n\n\n

      \n

      $ a68g a2.a68<\/kbd><\/p>\n\n\n\n

      X-value,Y-value<\/kbd><\/p>\n\n\n\n

      +.00000,+.97022<\/kbd><\/p>\n\n\n\n

      +.01562,+.95618<\/kbd><\/p>\n\n\n\n

      +.03125,+1.0211<\/kbd><\/p>\n\n\n\n

      \u2026<\/kbd><\/p>\n\n\n\n

      +8.9688,+9.9956<\/kbd><\/p>\n\n\n\n

      +8.9844,+10.012<\/kbd><\/p>\n\n\n\n

      +9.0000,+10.057<\/kbd><\/p>\n\n\n\n

      $<\/kbd><\/p>\n<\/div>\n\n\n\n

      Of course, we\u2019ll want to redirect this to a file such as \u201ctest_data.txt\u201d.<\/p>\n\n\n\n

      In the next article, we\u2019ll work on a few useful utilities to handle CSV files.<\/p>\n","protected":false},"excerpt":{"rendered":"

      In memory of J. Kevin Douglas, a good friend and fellow fan of Algol 68 In the last<\/p>\n","protected":false},"author":430,"featured_media":2725,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[5,150],"tags":[783],"class_list":["post-11049","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linux","category-programming","tag-algol-68"],"modified_by":"David Both","_links":{"self":[{"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/posts\/11049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/users\/430"}],"replies":[{"embeddable":true,"href":"https:\/\/www.both.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11049"}],"version-history":[{"count":8,"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/posts\/11049\/revisions"}],"predecessor-version":[{"id":11109,"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/posts\/11049\/revisions\/11109"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.both.org\/index.php?rest_route=\/wp\/v2\/media\/2725"}],"wp:attachment":[{"href":"https:\/\/www.both.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.both.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.both.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}