Peter Sestoft
email: sestoft@itu.dk

Early Nordic Compilers and Autocodes

The early development of compilers for high-level programming languages, and of so-called autocoding systems, is well documented at the international level but not as regards the Nordic countries. The goal of this paper is to provide a survey of compiler and autocode development in the Nordic countries in the early years, roughly 1953 to 1965, and to relate it to international developments. We also touch on some of the historical societal context.

Introduction

A compiler translates a high-level, programmer-friendly programming language into the machine code that computer hardware can execute. An "autocode" is a term used in the 1950s to denote a combination of simple compiler, assembler, linker and loader; in general, a program that made loading another program into a computer more convenient than using binary or hexadecimal codes.

Whereas the history of computer hardware and the history of programming languages both are well described, the history of compilers, tying the two other subjects together as it were, is not as thoroughly charted. Nevertheless, surveys by Bauer [START_REF] Bauer | Historical remarks on compiler construction[END_REF], Ershov [START_REF] Ershov | Compiler construction, an advanced course[END_REF] and Knuth [START_REF] Knuth | The early development of programming languages[END_REF] give interesting descriptions of the history of compiler development at the international level. However, they mostly neglect the particular developments in the Nordic countries, especially those before 1960.

In this paper we describe the development of early compilers and autocodes in the Nordic countries in the period 1953-1965. This includes in particular the FA-5 and Alfakod autocodes for BESK in Stockholm; the Mercury Autocode (MAC) for Ferranti Mercury in Oslo; the DASK loader and the Algol compilers for DASK and GIER in Copenhagen; the Algol compilers for various copies of BESK in Sweden; and the Simula language and compiler developed in Oslo.

We describe the features of these compilers and compiler-like systems and how they compare to contemporary international developments such as Brooker's Autocode for the Mercury, Backus's Fortran I compiler for IBM 704, and the Algol compilers by Bauer & Samelson, Dijkstra, Hoare, Randell and others.

We mention, but only to a limited degree, the societal and historical background and motivation for these technological developments.

Early International Development of Compilers

Surveys and Other Secondary Sources

The earliest survey of autocodes we have found is given by a 1954 MIT MSc thesis by Jones [START_REF] Jones | A survey of automatic coding techniques for digital computers[END_REF]. A brief history of compiler development which focuses mostly on US developments but with few names and dates was given in 1962 by Knuth [START_REF] Knuth | A history of writing compilers[END_REF]. A history with much better international coverage and references was given in 1974 by Bauer [START_REF] Bauer | Historical remarks on compiler construction[END_REF] in his compiler construction book, with Soviet developments described separately by Ershov in an addendum to the second printing [START_REF] Ershov | Compiler construction, an advanced course[END_REF]. In 1977 Knuth and Pardo surveyed the early development of autocodes and compilers [START_REF] Knuth | The early development of programming languages[END_REF] beautifully and quite comprehensively up until the 1957 Fortran I compiler, although with no coverage of Nordic developments.

Naur conducted a survey [START_REF] Naur | The questionnaire[END_REF] of completed and ongoing Algol-related compiler development worldwide in January 1962 and reported the results in June [START_REF] Naur | The replies to the AB14 questionnaire[END_REF]. Bromberg in 1963 published a list of almost all existing autocodes and compilers [START_REF] Bromberg | Survey of programming languages and processors[END_REF] though still missing the Oslo and Stockholm autocodes described in sections 3.3 and 3.4.

Early Nordic Computer Hardware

The focus of this paper is the development of compilers, not the development of computer hardware or programming languages, both of which are amply documented and discussed, for instance in the History of Programming Languages symposia, the Annals of the History of Computing, and several books. Nevertheless Figure 1 presents some early Nordic computers and their international relatives for context.

The IAS machine design from the Institute of Advanced Studies in Princeton was described in a series of reports by Goldstine, von Neumann and others 1945-1954. These were quite widely circulated and strongly influenced many other computers even before the IAS machine itself was actually completed. In particular, the IAS machine, BESK, DASK and Manchester Mark I all have 40-bit word length, 20-bit one-address instructions and fixed-point binary arithmetics. The Manchester Mark I was the first computer to have index registers (called B-tubes), and DASK adopted this idea. The Mercury had binary floating-point arithmetics, like several earlier machines developed in the US.

Early Nordic Autocodes

Figure 2 summarizes in chronological order the development of Nordic autocodes and compilers, together with some international developments for context. To give an impression of the various autocodes and compilers, we show how a small computing problem can be solved in each of them.

An Example Program

Assume we want to compute the value of this polynomial p(x) of degree 8:

p(x) = a 0 x 8 + a 1 x 7 + • • • + a 6 x 2 + a 7 x + a 8
If the coefficients a i are stored in an array a[i], we could compute p(x) using Horner's rule with a C-style for-loop like this: res = 0.0; for (i = 0; i <= 8; i++) res = a[i] + x * res;

The "Initial Orders" for EDSAC in Cambridge

The so-called "initial orders" for the EDSAC computer at Cambridge University was a set of software routines to load programs in quasi-symbolic form, and link and relocate subroutines, and hence probably constituted the very first autocode; it is included in Bauer's survey [START_REF] Bauer | Historical remarks on compiler construction[END_REF] but not in Knuth's [START_REF] Knuth | The early development of programming languages[END_REF]. It was developed by Wilkes, Wheeler and Gill, was in practical use for years from September 1950, and was the subject of the very first practical book on programming [START_REF] Wilkes | The preparation of programs for an electronic digital computer, with special reference to the EDSAC and the use of a library of subroutines[END_REF] in 1951.

The design was clever and pragmatic. The EDSAC computer read programs from a 5-channel paper tape (as used in telex machines), and Wilkes had arranged the instruction codes so that the character code for an "A" on the tape was also the EDSAC instruction code for addition, "S" also the code for subtraction, and so on. Hence the programmer could work with mnemonic instruction names instead of hexadecimal instruction numbers, say, yet almost no translation was needed. The chief task of the "initial orders" was to interpret various load-time relocation directives on the program tape, thus achieving relocatable subroutine code on a machine without index registers and relative addressing, and to convert decimal constants and addresses into binary.

Autocodes for BESK in Stockholm

Initially the BESK computer read programs from 5-channel telex tape, but used only 4 of the channels, so all programs had to be loaded in hexadecimal code (called sedecimal at the time). According to Dahlquist [17, The first column contains the instruction addresses aaa. The second column contains the five hexadecimal digits constituting a 20-bit instruction, where AAA is the address part and OO is the operation part. All addresses and constants are in hexadecimal. This assumes that the nine coefficients a[i] are stored at hexadecimal memory addresses 100-112, using two adjacent 20-bit cells for each coefficient; that cell 180 holds 10000; that cell 182 holds 11300; that x is at address 008; and that the result must be stored in cell 184. The address and comment parts above are included for explanatory purposes only.

The indexing into the coefficient array is performed by the instruction at 204, and the instructions at 201 and 205 modify the address part of that instruction. Because BESK had no index registers, self-modifying code was essential for array accesses. Clearly, working with such code must have been extremely cumbersome. For instance, if the above code were part of a subroutine, then every time it had to be included in a new program one would have to change the instruction addresses. This would involve not only changing the target addresses of jump instructions (such as 207 above), but also changing the address part of any instructions that edit the address of other instructions (such as 201 and 205 above).

The simple FA-4 and FA-5 autocodes, where FA is an acronym for "fiktiva adresser" or "fictitious addresses", were developed by G. Hellström for BESK for exactly for this purpose [START_REF] Dahlstrand | To sort things out[END_REF][START_REF] Hellström | Kodning med FA5 för BESK och FACIT EDB[END_REF]. The idea was quite simple: on the program tape one could prefix an instruction with a "fictitious address" such as A204, essentially a symbolic label. Then the FA loader program would change any instruction with address part 204 to instead contain the actual address at which the labelled instruction occurs after loading.

Hence (to the best of our belief) the above example code could be written like this in FA-5:

18050 20407 00648 A203 00863 A204 FFF28 20446 1820B 2034E 00001 18431 3000C
where all the instructions are exactly as before, but the two instructions previously fixed at addresses 203 and 204 have now been given labels A203 and A204. Hence this code can be relocated by FA-5 to any desirable address; no manual adjustments are needed. This is a big improvement, but the code itself is still very low-level: the programmer must express his intentions in hexadecimal instruction codes and addresses.

The purpose of Alfakod, developed by Riesel, Jonason and von Sydow and commercialized through the company Autocode AB in Stockholm, was to improve on this situation [START_REF] Riesel | Alfakodning for matematikmaskiner. allmän del (preliminär version)[END_REF][START_REF] Riesel | Alfakodning, ett lättkodsystem för EDB-maskiner[END_REF][START_REF] Dahlstrand | To sort things out[END_REF]. Alfakod required use of all five channels in the telex tape, and hence was not limited to hexadecimal codes. It provided brief symbolic instruction names (in Swedish) such as NOL for "set to zero"; symbolic variable names such as X, Y and I; program labels such as 1 below; subscripting operations such as Y/I which means Y[I] in modern notation; and tests ("villkor") such as VMX 1,I,8 which says "go to label 1 if I<8"; and more.

Hence the polynomial example could be expressed like this in Alfakod, assuming appropriate declarations:

NOL AR FIX 0,I 1 MUL X ADD Y/I ADX 1,I VMX 1,I,8
According to Dahlstrand [19, page 33], Alfakod did not see widespread use even in Sweden, perhaps because the concept of externally developed commercial software was still very unusual in the second half of the 1950s.

Dahl's MAC Autocode in Oslo

Unlike Sweden and Denmark, Norway did not build its own computer, apart from the small Nusse machine in the early 1950s. Instead Forsvarets Forskningsinstitutt (Norwegian Defense Research Establishment, NDRE) in Oslo acquired the very first copy of the commercial Ferranti Mercury computer from the UK. It cost almost 1 million Norwegian kroner and was far more powerful than both BESK and DASK, with binary floating-point arithmetics and 8 index registers. At first Jan V. Garwick (see Section 5.1) and Ole-Johan Dahl developed a relatively simple loader program and library of standard routines [START_REF] Dahl | Programmer's handbook for the Ferranti Mercury computer Frederick[END_REF]. Apparently there had been hopes that it would be distributed and used at other Mercury installations, but it was not [START_REF] Olle | Ferranti Mercury at the Norwegian Defense Research Establishment[END_REF].

Then, under the supervision of Garwick, Ole-Johan Dahl in 1958 developed a very advanced autocoding system MAC for that machine [START_REF] Dahl | Autocoding for the Ferranti Mercury Computer (MAC)[END_REF]. Although the Ferranti Mercury computer was sold commercially, and Dahl's report describing the system was reviewed in the US the same year [START_REF] Hume | Review of O. J. Dahl: Autocoding for the Ferranti Mercury computer (MAC) [12[END_REF], there is no evidence that MAC was used outside NDRE, and it is not mentioned in a 1961 list of Ferranti computer literature [START_REF] Ltd | Classified index of Ferranti computer literature[END_REF]. After NDRE bought a CDC 3600 computer with a Fortran compiler in the fall 1964, MAC saw little use1 .

Dahl's MAC system supported symbolic variable names, real and complex numbers, 1-, 2-and 3-dimensional arrays, declarations, symbolic labels, composite arithmetic expressions with infix operators and parentheses, efficient code generation for multidimensional array indexing, including replacement of slow multiplications by faster additions (reduction in strength) [START_REF] Dahl | Multiple index countings on the Ferranti Mercury computer[END_REF], and many more facilities.

The polynomial evaluation code might look like this in MAC:

0 -> A 0 -> n1 Un1 + X A -> A (1 n1 + 1 -> n1 n1 < 9 ? JUMP1
Here A holds the result, U is the array of coefficients, and n1 an index variable. The notation was meant to resemble mathematics, so Un1 means the value of U at index n1, and X A is X times A with an implied multiplication sign. The "(1" is a label, and JUMP1 a goto statement targeting that label. Note that assignment "->" is from left to right, as was quite common in the 1950s.

Dahl's MAC was not the only autocode for the Ferranti Mercury. At Manchester University, R. A. Brooker had developed an autocode system for the Manchester Mark I [START_REF] Brooker | The programming strategy used with the Manchester University Mark I computer[END_REF][START_REF] Knuth | The early development of programming languages[END_REF] and a more elaborate one for its successor, the Mercury [START_REF] Brooker | The autocode programs developed for the Manchester University computers[END_REF][START_REF] Brooker | Further autocode facilities for the Manchester (Mercury) computer[END_REF]. Neither Brooker nor Dahl refer to each other's systems, but likely have known about them, since Jan V. Garwick at NDRE had good connections at Manchester and even contributed to the design of the Mercury computer [START_REF] Holmevik | Compiling Simula: a historical study of technological genesis[END_REF][START_REF] Nygaard | In Norsk biografisk leksikon[END_REF].

Indeed there are many similarities between Brooker's and Dahl's systems: they have the same distinction between ordinary variables and index quantities, the same indexing notation Un1, the ability to denote multiplication by juxtaposition X A, and the support for both real and complex numbers [START_REF] Brooker | The programming strategy used with the Manchester University Mark I computer[END_REF]. However, Dahl's MAC is the more powerful one, with more general arithmetic expressions, including parentheses, and declaration of 2D and 3D array variables.

The BESK team in Stockholm knew of Brooker's Autocode around 1955 according to Kjellberg [49, pages 8 and 18].

DASK in Copenhagen

Peter Naur had used the EDSAC computer in Cambridge and its "initial orders" software extensively February-June 1951 and May-August 1953 for astronomical calculations, and had also visited numerous other computer installations, including BESK in November 1953 [START_REF] Naur | A view of computers of[END_REF][START_REF] Naur | Impressions of the early days of programming[END_REF]. In early 1957, when the DASK computer was being built at Regnecentralen in Copenhagen, he proposed an "external order code" and a similar simple loader routine for it. All of this, including the full (one-page) code of the loader routine, was described in a brief letter to DASK hardware designer Scharøe and project leader Bech [START_REF] Naur | Contributions to the design of the dask instruction set, program loader and diagnostics. Letters to Scharøe and Bech at Regnecentralen[END_REF].

Most of Naur's proposal was adopted, judging from the 1958 DASK programming manual [START_REF] Andersen | Laerebog i kodning for DASK[END_REF], and a comprehensive suite of EDSAC-inspired debugging tools etc. was developed by Jørn Jensen and Per Mondrup [START_REF] Jensen | DASK kontrolprogrammer[END_REF][START_REF] Naur | [END_REF]. Using the DASK external order code, the polynomial evaluation example might look like this [ The general layout of the code is similar to that of the BESK binary code (Section 3.3), but the instruction's address (or immediate) field AAAA is now in decimal notation, there is an index register field I where A means no indexing, B indicates index register IRB, and so on. The operation code OO is still in hexadecimal, but the instruction codes are somewhat simplified from BESK's.

Moreover the DASK loader routine also supported a form of EDSAC-inspired relative addressing and relocation, not illustrated above, obviating the need for a separate fictitious addressing mechanism [1, chapter 9].

In Retrospect

It seems plausible that several factors saved the team at Regnecentralen in Copenhagen much effort on the development of autocodes and other auxiliary software, so that it could instead focus on the development of compilers for a proper high-level language, Algol 60, as described in Section 4.

First, the Copenhagen team drew much inspiration from the pioneering but pragmatic and simple "initial orders" for EDSAC; second, since the Stockholm developments started much earlier, the Copenhagen team could learn from them; and third, while the DASK computer was based on BESK, it had index registers, more reliable memory hardware (using ferrite cores), and a simplified and cleaned up instruction set, a much more convenient target for code generation.

Early Nordic High-Level Language Compilers

Here we give a brief account of Nordic high-level language compilers, chiefly for Algol 60 and Simula, and some of the international context. For broader context, see the surveys by Bauer [START_REF] Bauer | Historical remarks on compiler construction[END_REF], Bromberg [START_REF] Bromberg | Survey of programming languages and processors[END_REF], Knuth [START_REF] Knuth | The early development of programming languages[END_REF] and Naur [START_REF] Naur | The replies to the AB14 questionnaire[END_REF].

The Fortran I Compiler at IBM

The first compiler in the modern sense for a high-level language is the Fortran I compiler developed by Backus and others at IBM and completed in 1957 [START_REF] Backus | The FORTRAN automatic coding system[END_REF]. The Fortran I programming language had arithmetic expressions with infix operators, precedence and parentheses, like every language today, but otherwise was very simple by modern standards, lacking block structure, nested scopes, procedures, recursion, and so on. Therefore the run-time management of data and programs was nearly trivial, as all variables could be statically allocated at compile-time.

By contrast the Fortran I compiler was remarkably ambitious and advanced. It performed constant folding and common subexpression elimination, optimized index computations (with reduction in strength), and cleverly allocated index registers. The compiler could even perform a Monte Carlo simulation of execution frequencies to optimize the order of branches [START_REF] Backus | The FORTRAN automatic coding system[END_REF]. Even so, some basic parts, such as the translation of expressions, were implemented in a rather impenetrable manner [START_REF] Sheridan | The arithmetic translator-compiler of the IBM FORTRAN automatic coding system[END_REF].

The Fortran language is still widely used, and over the years has acquired a large number of features from other languages, including many from Algol.

International Algol 60 Compilers

Unlike Fortran I, the Algol 60 language was extremely sophisticated, yet by modern standards a small and elegant language. It had block structure, nested scope, type declarations, recursive functions and procedures, procedures as parameters, and call-by-name as well as call-by-value parameter passing. It did not have user-defined data types, unlike the contemporary COBOL and later Pascal.

Algol provided a large number of hitherto unknown implementation challenges. Bauer and Samelson in 1959 showed how to compile expressions using stacks, much more cleanly than the Fortran I compiler, and also optimize index calculations in a systematic way [START_REF] Samelson | Sequentielle Formelübersetzung[END_REF][START_REF] Samelson | Sequential formula translation[END_REF].

A major new challenge in Algol implementation was the run-time allocation and management of data. Dijkstra in 1960 showed how recursive procedures could be executed using a run-time stack of activation records, and how to efficiently access identifiers from statically enclosing scopes using the so-called display [START_REF] Dijkstra | Recursive programming[END_REF]. Irons in 1961 created a syntax-directed table-driven compiler, showing that compiler development could be a highly systematic activity [START_REF] Irons | A syntax directed compiler for Algol 60[END_REF]. Hoare in 1962 demonstrated how a compiler could be written as a collection of mutually recursive procedures, one for each language construct [START_REF] Hoare | Report on the Elliott Algol translator[END_REF][START_REF] Hoare | The emperor's old clothes. Turing award lecture[END_REF], thereby inventing recursive-descent compilation. Randell and Russell's 1964 book on Algol compiler construction crisply presents many of these techniques [START_REF] Randell | Algol 60 implementation[END_REF].

Nordic Algol 60 Compilers

The early development of Nordic compilers in the modern sense is dominated by the Algol 60 compilers developed in Copenhagen, Gothenburg, Lund and Stockholm, and the subsequent development of compilers for Simula in Oslo. In February 1959 Peter Naur from Regnecentralen in Copenhagen became involved in the ongoing international effort to design a common high-level programming language (called International Algebraic Language or Algol 58), and was chosen as one of the seven European members on the Algol 60 committee. He was the only Scandinavian member of the committee, but Ingemar Dahlstrand and others from Sweden, and Jan V. Garwick from Norway, took part in the wider meetings and discussions. The same month Naur also created and became editor of the Algol Bulletin (distributed from Regnecentralen in Copenhagen) as a medium for making and discussing proposals about the language design. Naur realized that the core problem was to describe this future programming language precisely and clearly, and found that John Backus's recently proposed "Normal Form" was ideal for the purpose. Prior to the January 1960 committee meeting in Paris, he wrote a draft of the entire Algol 60 language description in this style and precise English. This draft was chosen as the basis for the committee's work, and Naur was chosen as editor of the Algol 60 report [START_REF] Backus | Report on the algorithmic language ALGOL 60[END_REF]. There is no doubt that this gave him an intimate knowledge of the language design and of implementation considerations, as well as a strong network of international colleagues, that benefited the compiler development at Regnecentralen in Copenhagen. These developments, and the somewhat conflicting recollections and interpretations of them, are thoroughly documented elsewhere [START_REF] Naur | The European side of the last phase of the development of Algol 60[END_REF][START_REF] Perlis | The American side of the development of Algol[END_REF].

The first high-level language compiler in the Nordic countries was the Algol 60 compiler (without recursive procedures) developed by Jørn Jensen, Per Mondrup and Peter Naur for the DASK computer at Regnecentralen in Copenhagen [START_REF] Jensen | An implementation of Algol 60 procedures[END_REF]. The same team developed a full Algol 60 compiler for the GIER computer, a transistor-based successor to DASK, also at Regnecentralen [START_REF] Naur | The design of the Gier Algol compiler, part I[END_REF][START_REF] Naur | The design of the Gier Algol compiler, part II[END_REF].

Ingemar Dahlstrand and Sture Laryd developed an Algol 60 compiler (without recursive procedures) for the Facit EDB computer, a clone of BESK, in Gothenburg [START_REF] Dahlstrand | The early Nordic software effort[END_REF][START_REF] Dahlstrand | To sort things out[END_REF], and later for a Datasaab computer. Dahlstrand's memoirs say that this work drew on papers from Bauer's group in Germany, and on invaluable support and advice from the Copenhagen team [19, page 58].

Torgil Ekman developed an Algol 60 compiler (without recursive procedures) for the SMIL computer, a clone of BESK, in Lund [START_REF] Ekman | Konstruktion och struktur av en Algol 60-översättare för datamaskinen SMIL[END_REF]. His supervisor was Carl-Erik Fröberg and his work was furthered by interactions with the Gothenburg and Copenhagen teams [22, page 2].

Börje Langefors at Saab developed the Algol Genius compiler, which supported some COBOL features convenient for administrative data processing [START_REF] Asker | Algol-genius: An early success for high-level languages[END_REF]. It generated code for for the Datasaab D21 computer, a descendant of BESK, and was based on Dahlstrand's Algol compiler. Later Algol Genius was ported to Univac 1100, based on the Univac Algol compiler from Trondheim [START_REF] Asker | Algol-genius: An early success for high-level languages[END_REF].

In retrospect the Nordic Algol implementation efforts do not seem to have had a wider international influence, unlike the work by Bauer, Dijkstra, Irons and Hoare cited above. Even so, the developers of compilers and autocodes faced very nontrivial problems and came up with novel solutions. For instance, the multipass architecture of the Copenhagen Algol compilers provided a clean and efficient way to use the small core memory in combination with the chiefly sequential drum backing store. Similarly, the dynamic two-level virtual memory (core and drum) run-time management of program fragments in GIER Algol [START_REF] Naur | The design of the Gier Algol compiler, part I[END_REF] seems original and very effective. The 1963 GIER Algol papers [START_REF] Naur | The design of the Gier Algol compiler, part I[END_REF][START_REF] Naur | The design of the Gier Algol compiler, part II[END_REF] described not only technical details but also design rationale, the development team's knowledge sharing, and systematic compiler test. The attention to these aspects paid off: the GIER Algol compiler gained a reputation as highly reliable and usable [START_REF] Sanders | Making computing available[END_REF], and the Regnecentralen GIER computer (which sold around 50 copies) came to be seen as an "Algol machine". Low-level machine-oriented debugging tools were not needed and thus never developed for GIER [START_REF] Naur | [END_REF].

The Simula Language and Compiler

In a highly original development with wide-ranging implications, Ole-Johan Dahl and Kristen Nygaard in Oslo designed the Simula I language and developed a compiler for it on the Univac 1107 computer at the Norwegian Computation Center (Norsk Regnesentral) [START_REF] Dahl | Simula, an Algol-based simulation language[END_REF][START_REF] Nygaard | The development of the Simula languages[END_REF]. The Simula compiler was based on the Univac 1107 Algol compiler, developed at the Case Institute of Technology by Joseph Speroni and others [16, page 678]. The Simula work was the origin of concepts such as class and object, and later strongly influenced the design of widely used languages such as Smalltalk, C++, Java, C#, and many others.

Two Nordic Digressions

The history of early digital computers is particularly interesting because it coincides with the development of nuclear technology and with the cold war, so exciting side tracks present themselves with every new document discovered.

The Norwegian Nuclear Program

Norway's nuclear ambitions are well documented by Forland [START_REF] Forland | På leiting etter uran: Institutt for atomenergi og internasjonalt samarbeid 1945-51. Forsvarsstudier 3[END_REF][START_REF] Forland | Norway's nuclear odyssey: from optimistic proponent to nonproliferator[END_REF] and their relation to computer science are documented by Holmevik [START_REF] Holmevik | Compiling Simula: a historical study of technological genesis[END_REF][START_REF] Holmevik | Inside Innovation: The History of the SIMULA Programming Languages[END_REF] and briefly by Nygaard and Dahl themselves [63, section 1] [START_REF] Dahl | The birth of object orientation: the simula languages[END_REF]. Nevertheless we briefly summarize the history here, also because recently declassified material [START_REF] Randers | Rapport til forsvarsministeren[END_REF] shows the close ties between defense goals and the nuclear programme.

In the summer of 1946 Gunnar Randers and Odd Dahl (no relation to Ole-Johan Dahl) travelled extensively in the United States to study nuclear technology, including the effect of nuclear weapons, after which Randers wrote a frank report to the Norwegian minister of defense [START_REF] Randers | Rapport til forsvarsministeren[END_REF], declassified in 2013. Randers was head of the newly established Forsvarets Forskningsinstitutt (Norwegian Defense Research Establishment, NDRE) and he and Odd Dahl designed and built an experimental nuclear reactor that became critical in November 1951 [START_REF] Forland | På leiting etter uran: Institutt for atomenergi og internasjonalt samarbeid 1945-51. Forsvarsstudier 3[END_REF][START_REF] Forland | Norway's nuclear odyssey: from optimistic proponent to nonproliferator[END_REF]. Thus, quite spectacularly, Norway was only the sixth country in the world to have a working reactor.

The computations for the reactor design were led by Jan V. Garwick, as documented in contemporary technical reports [START_REF] Garwick | Beregning av kritisk størrelse for en sfaerisk uranmile, delvis omgitt av en reflektor[END_REF][START_REF] Garwick | Beregning av resonansabsorbsjonen i en uranmile hvor uranet er anbragt i parallelle cylindriske staver[END_REF][START_REF] Garwick | Beregning av resonansabsorpsjonen i en uranmile[END_REF][START_REF] Garwick | Beregning av temperaturen i de fissile staver i en uranmile[END_REF] and in Holmevik's papers [START_REF] Holmevik | Compiling Simula: a historical study of technological genesis[END_REF][START_REF] Holmevik | Inside Innovation: The History of the SIMULA Programming Languages[END_REF], and were performed manually and with mechanical calculators. Garwick had succeeded Randers as research assistant to professor of astrophysics Svein Rosseland in 1940 and came to NDRE in 1947. In his reactor computations Garwick was assisted by Kristen Nygaard (at NDRE 1948-1959) who performed Monte Carlo simulations [START_REF] Nygaard | On the solution of integral equations by Monte Carlo methods[END_REF]. Later Ole-Johan Dahl, like Nygaard, joined NDRE as a part of his military service and remained there 1952-1961, during which time his MSc thesis [START_REF] Dahl | Multiple index countings on the Ferranti Mercury computer[END_REF] and his work on the Mercury Autocode (see Section 3.4) was supervised by Garwick.

From 1962 both Nygaard and Dahl were at the Norwegian Computation Center where they continued to work on simulations and developed the Simula language, object-oriented programming, and now-ubiquitous concepts such as class and object [START_REF] Holmevik | Inside Innovation: The History of the SIMULA Programming Languages[END_REF][START_REF] Nygaard | The development of the Simula languages[END_REF]. Hence object-orientation, like much of early computing, has roots in nuclear technology. It is also clear that Jan V. Garwick played a central role in establishing digital computing in Norway; Dahl and Nygaard call him "the father of computer science in Norway" [63, page 245], yet little is written about him, maybe because he moved to the USA in 1967.

The Origins of the Soviet Computer BESM

The origins of the first usable Soviet computer BESM-I, constructed by Sergei A. Lebedev in 1953 [START_REF] Lebedev | The high-speed electronic calculating machine of the Academy of Sciences of the U.S.S.R[END_REF], are somewhat murky. Some sources, including Nordic ones, claim that it descends from the IAS design or even from BESK (which itself descends from the IAS, see Figure 1 Another lead, closer to Sweden, similarly goes nowhere. Annerstedt writes in 1970 "Besk kom att stå fadder för flera andra datorer: [. . . ] två utländska, den danska Dask och den sovjetiska Besm" [2, page 104], citing page 82 of the Swedish translation of a book by Peter Naur [START_REF] Naur | Datamaskinerna och samhället[END_REF] for this information. However, that page is in an appendix added by the translator, and neither Naur's text nor the appendix mentions BESM or other Soviet computers anywhere at all. Moreover, whereas the IAS machine, BESK and DASK all have 40-bit word length, 20-bit one-address instructions and fixed-point binary arithmetics, BESM-I has 39-bit word length, 39-bit three-address instructions and floating-point binary arithmetics [START_REF] Lebedev | The high-speed electronic calculating machine of the Academy of Sciences of the U.S.S.R[END_REF], so it is certainly not a close copy of the IAS design. Some modern Russian sources in possession of Lebedev's scientific notebooks appear to claim that Lebedev invented everything himself [START_REF] Karpova | History of the creation of BESM: The first computer of S.A. Lebedev institute of precise mechanics and computer engineering[END_REF]. Although Lebedev clearly was an extraordinarily resourceful designer and constructor, and successful despite difficult circumstances, this seems highly implausible. According to top secret minutes from a closed meeting of the Academy of Sciences in January 1951, Lebedev says "I have data on 18 machines developed by the Americans. This data has the character of an advertisement, without any kind of information on how the machines are built" [50, page 5], thus not admitting the availability of any concrete Western designs. But presumably in 1951, under Stalin, it would be unwise of Lebedev to disclose the Western sources, if any, for Soviet technologies, even in a closed meeting. This is the view also of other biographers of Lebedev [START_REF] Crowe | Lebedev and the birth of Soviet computing[END_REF], and Goodman says "None of Lebedev's designs was based on close copying of foreign machines" [31, page 25]. Hence the origins of BESM-I remain obscure for now, but it is clearly not a direct copy of the IAS machine or BESK.

Conclusion and Future Work

We have given a brief overview of the development 1955-1965 of autocodes and compilers in the Nordic countries, and some of the international and historical context. It is reasonable to conclude that the Nordic autocodes did not attract much international attention, whereas the contributions to Algol 60 language design and description, and the Simula language design, did have considerable international impact.

Later Nordic developments, showing the region's considerable contributions to the area, include Brinch Hansen's Concurrent Pascal and monitors; Hejlsberg's Turbo Pascal, Delphi, C# and TypeScript; the Ada and CHILL compilers from Dansk Datamatik Center; Stroustrup's C++; Augustsson and Johnsson's Lazy ML; Armstrong's Erlang; the Sicstus Prolog and Turbo Prolog/Visual Prolog systems; contributions to Java (by Torgersen and others) and to Standard ML (by Tofte); the virtual machines for Java Hotspot and for Google Chrome by Bak; and much more, both in the industrial and academic spheres.

There is a lot more to say about the general development of compiler technology: lexing and parsing techniques, scope mechanisms, code generation, intermediate languages, type systems and type checking, code optimization, dataflow analysis, run-time organization, abstract machines, garbage collection, linkers and loaders, compiler generators, and much more.

Also, one might investigate how the associated concepts and terminology develops. For instance, who first thought of expressions as trees -abstract syntax -instead of symbol strings? For another example, Backus's Fortran I paper [START_REF] Backus | The FORTRAN automatic coding system[END_REF] does not use the term "type" in connection with program variables in the 1957, but Perlis's Algol 58 paper [START_REF] Perlis | Preliminary report, international algebraic language[END_REF] in 1958 does; is this the first such use?

  AR := x * MR 204 118 B 00 AR := AR + [118+IRB] 205 202 A 33 if IRB<>0 goto 202

  ). For instance, an IAS Archives webpage says "Copies of the IAS machine appeared nationally: [. . . ]; and internationally: BESK in Stockholm; BESM in Moscow; DASK in Denmark; [. . . ] to mention a few " [38]. It seems 2 that this claim is inspired by Dyson "The Institute for Advanced Study computer was duplicated, with variation, by [. . . ] BESK in Stockholm, DASK in Denmark, SILLIAC in Sydney, BESM in Moscow [. . . ] " [21, page 287], but apparently there is no further source for this 3 .

Dag Belsnes, Oslo, personal communication,

May 2014.

Christine Di Bella, IAS Archives, personal communication 18 February 2014.

George Dyson, personal communication 22 February 2014.

Acknowledgements I want to thank all those who helped tracking down and scanning or mailing old documents, who answered my queries about obscure details, or in general discussed the matters here: Christian Gram, Dansk Datahistorisk Forening; Robert Glück, Copenhagen University; Birger Møller-Petersen, University of Oslo; Knut Hegna, University of Oslo Library; Bjørg Asphaug, NDRE Library; Ingemar Dahlstrand and Torgil Ekman, Lund University; Mikhail Bulyonkov, Russian Academy of Sciences, Novosibirsk; Christine di Bella, IAS Archives, Princeton; George Dyson, Bellingham WA, USA; Peter du Rietz, Tekniska Museet, Stockholm; Hans Riesel, Uppsala University; Dag Belsnes, Oslo; Henrik Kragh Sørensen, Aarhus University; and Peter Naur, Copenhagen University. Thanks also to David Christiansen, Olaf Owe and Kasper Østerbye for comments on a draft.


Olli Simula
email: olli.simula@aalto.fi

Yrjö Neuvo
email: yrjo.neuvo@aalto.fi

A Fast Microprogrammed Digital Filter Supporting Early Signal Processing Research

Keywords: Digital filters, low-sensitivity realizations, computational efficiency, digital signal processors, bit-sliced architecture, microprogramming

In the 1970s research and teaching of digital signal processing was started in several universities in Scandinavia. Special emphasis in the research was on digital filter structures implementable on emerging digital hardware. On the theoretical side, the development of computationally efficient, low-sensitivity digital filter structures was widely investigated. Realization of these novel transfer functions was also important in order to verify the efficiency of the filters in practice. The latest commercial microprocessors indicated that real time signal processing covering the audio range of signals was becoming realistic. A microprogrammable digital signal processor based on high speed bit-sliced architecture was designed at Helsinki University of Technology. With this hardware, the performance of computationally efficient, lowsensitivity digital filter structures was tested. Algorithm research with emphasis on implementation aspects had a great impact on the readiness of Finnish electronics and telecommunications industry to start using programmable digital hardware. Early DSP applications in telecommunications industry were released already in late 1970s. Ten years later, when the first GSM phones were under development, Finnish industry was on the leading edge of applying digital signal processors in a number of applications.

Introduction

In the late 1970s, digital signal processing (DSP) had been a rapidly growing and dynamic field of research for more than a decade. The first text book in DSP was Digital Processing of Signals by Gold and Rader in 1969 [START_REF] Gold | Digital Processing of Signals[END_REF]. It was followed the widely used Digital Signal Processing by Oppenheim and Schafer in 1975 [START_REF] Oppenheim | Digital Signal Processing[END_REF].

In the 1970s, DSP research was concentrating on the development of computationally efficient digital filters transfer functions. Due to the limited computational resources, special attention was paid to the coefficient sensitivities of the filter structures. It was, however, important to verify the theoretical results in practice and to demonstrate the advantages of DSP using real applications. Audio signal processing was an excellent example field. These early implementations formed the background for the utilization of advanced DSP algorithms later in the communications applications, e.g., in mobile phones as well as in various image processing tasks.

Among the most active universities in Scandinavia were Linköping University in Sweden, Norwegian Institute of Technology in Trondheim and Helsinki University of Technology (TKK) in Finland. Professor Tore Fjällbrant's group in Linköping did research on wave digital filters and their implementations. The group members, Professor Lars Wanhammar and Dr. Sven Eriksson even wrote a Swedish textbook entitled Tidsdiskreta filter (Discrete-time filters) in 1978 [START_REF] Eriksson | [END_REF]. The first DSP course at TKK in Helsinki was based on the manuscript of Oppenheim's and Schafer's textbook in 1974, one year before the publication of the book. In mid 1970s, the DSP research group at TKK consisted of the authors of this paper.

Nordic cooperation in research and education was strong in the 1970s and 1980s. The first DSP conference in the Nordic countries was probably the Symposium on Digital Filtering and Related Algorithmic Problems held in Stockholm, Sweden, April 2-4, 1974. The organizer of the symposium was Professor Lars Zetterberg from Royal Institute of Technology (KTH). The highlights of the symposium were the famous speakers: Dr. James W. Cooley, the co-inventor of the Fast Fourier Transform (FFT) algorithm1 , Dr. Jorma Rissanen one of the pioneers of information theory, and Prof. Teuvo Kohonen, the developer of neural networks algorithms. This conference was followed by several Nordic symposia in the 1980s in DSP and related fields, e.g., in image processing and VLSI implementations of DSP algorithms. The greatest success was the 1988 IEEE International Symposium on Circuits and Systems held in Espoo in June 1988. It was organized as a joint Nordic effort. With its 1100 participants it was by then the largest ISCAS ever. In addition, two Nordic intensive courses on DSP algorithms were organized in Trondheim in 1986 for doctoral students. Professor Tor Ramstad was the responsible organizer of these quite successful events.

The early DSP research in Finland was focused on the development of lowsensitivity digital filter transfer functions with small number of multiplications. Main theoretical results were the so-called MUCRO filters which were based on MUltiple CRitical ROot polynomials [START_REF] Neuvo | MUCROMAF and MUCROER Polynomials in Digital Filter Design[END_REF]. These polynomials were originally intended for analog filter design by Dr. A. Premoli [START_REF] Premoli | The MUCROMAF Polynomials: An Approach to the Maximally Flat Approximation of RC Active Filters with Low Sensitivity[END_REF], [START_REF] Premoli | A New Class of Equal-Ripple Filtering Functions with Low Q-Factors: The MUCROER Polynomials[END_REF]. In addition, low-sensitivity digital filter transfer functions were developed based on the ladder and lattice structures [START_REF] Gray | Digital Lattice and Ladder Filter Synthesis[END_REF]. It was proven that the coefficient sensitivity on the lattice structure was equal to zero at zero frequency [START_REF] Neuvo | Coefficient Sensitivities of Cascaded Lattices at Zero Frequency[END_REF]. Reducing the number of zeroes in the transfer function resulted in computationally efficient realizations, the so-called one-zero lattice structures [START_REF] Neuvo | An Iterative Method for Designing Digital Filters with Reduced Number of Zeroes[END_REF].

In order to support DSP research and education but also to create industrial interest on DSP applications, a real time hardware implementation was desirable. First microprocessor circuits suitable for signal processor implementations came into the market in the 1970s. The Am2900 family of integrated circuits (ICs) was released by Advanced Micro Devices (AMD) in 1975 [START_REF]The Am2900 Family Data Book with Related Support Circuits[END_REF]. It was constructed using bipolar devices, in a bit-slice topology. This was the fastest bit-slice TTL microprocessor in the market. Bit-slicing techniques allowed the design of a processor with data, addresses, and instructions to be any multiple of 4 bits by multiplying the number of ICs. The Am2901 chip was the arithmetic-logic unit (ALU), and the "core" of the Am2900 series. It performed arithmetic and binary operations with 4 bit accuracy and could also implement various bit-shifting operations.

Based on this chip set a microprogrammable digital signal processor, named NRS 290, was designed. The design objective was to have a very flexible system in order to test and demonstrate the capabilities and limitations of signal processing algorithms and their hardware implementations. The letters NRS stand for the original design team: Neuvo, Ropponen, and Simula while numbers 290 stand for Am2900 circuit family.

NRS 290 Microprogrammable Digital Filter

The key design objectives of NRS 290 were high performance and ease of programming a variety of modular DSP algorithms. Building this kind of leading edge hardware in a university environment was expected to be challenging but also educational.

The NRS 290 hardware was able to implement a basic digital filter module which then could be multiplexed up to 16 parallel channels. The basic filter module was realized by a microprogram block which could be looped to implement, e.g., a higher order filter or a filter bank. The structure of the digital filter could be changed by changing the microprogram defining the realization form of the basic module. The filter parameters as well as the order and number of filters were stored in the data memory and registers, and could be externally controlled. The performance of NRS 290 was well comparable to the high-speed digital filters of that time.

Hardware Organization of NRS 290

The hardware organization and register configuration of NRS 290 digital filter are shown in Fig. 1. It followed the Harvard architecture principle where the instructions and data were physically separated. The microprogram memory and the data RAM were connected to separate control and data buses, respectively. The maximum number of input/output channels in the filter bank was 16. The word length of the filter was chosen to be 12 bits. This was a compromise between the computational speed and accuracy. However, for low-sensitivity filter structures the word length was satisfactory.

According to Fig. 1, the processor hardware was divided into four parts: Central processing element (CPE), memory (DATA RAM), multiplier, and external control unit. Internal communications as well as connections to AD-(ADC) and DA-(DAC) converters were performed via the 12 bit data bus. Arithmetic operations were carried out in the CPE ALU and in the multiplier. Intermediate results and constants were stored in the CPE RAM and in the DATA RAM. The Am2901 microprocessor formed the CPE. The 12-bit word length required three 4-bit slices. The estimated maximum microinstruction cycle time was 230 ns due to the microprogram sequencer and control circuitry throughput. For computationally efficient multiplication a separate hardware array multiplier was included. The multiplier unit was built using Am25S05 4-by-2 bit two's complement multiplier circuits. The maximum multiply time for 12 bit numbers was about 200 ns which was roughly equal to the microinstruction cycle time.

The size of the data RAM was 256 words divided into 32 blocks of 8 words. Each block contained the parameters, including fixed filter coefficients, of one filter module, e.g., a second order block. The RAM addressing was performed directly under the microprogram control. The block address register, BAR, shown in Fig. 1 was implemented as a five bit up/down counter containing the address of one memory block. BAR could be incremented and decremented under the microprogram control. The memory location within a block was addressed directly from the microprogram with three bits of the microinstruction word. More details about the NRS 290 hardware can be found in [START_REF] Neuvo | A Fast Microprogrammable Digital Filter Design[END_REF].

The

Microinstruction word

The microinstruction word length of NRS 290 was 40 bits (including 2 free bits) shown in Fig. 3. All control signals required for the external devices were generated in the microprogram. These signals were completely independent of each other allowing the external devices operate simultaneously, if desired. The only restriction in the operation was that only one data transfer in the bus was possible during one microinstruction cycle. Therefore, the only encoded parts of the microinstruction word were the source and destination of the data bus. This allowed the control of all hardware modules independently, resulting in flexible implementations of filter structures. The CPE RAM addresses (R A and R B ) as well as the DATA RAM address were also defined in the microprogram. To reduce the microinstruction word length the same bits were used to address the DATA RAM and to read from the CPE RAM (R A ). This did not affect the processing time because no register-to-register operations were normally needed simultaneously with the DATA RAM operations.

Programming

A special register transfer language (RTL) was developed to describe the operations executed by the microprogram [START_REF] Neuvo | A Fast Microprogrammable Digital Filter Design[END_REF]. The instruction set is defined in Table 1. RTL instructions considerably simplified the microprogramming which is shown in the examples below. The performance of the digital filter bank can be exemplified by the following RTL program. The program implements a cascade form realization of 2 nd order blocks in direct form II [2, p. 150]. The block diagram of the program is shown in Fig. 4. Cascading of 2 nd order blocks is realized in the loop from step 9 to 29. The instructions from 0 to 8 and 21 to 29 realize the same computations, the only difference being the source of the input signal, i.e., whether it is the AD-converter or the preceding filter block. Scaling is performed with one scaling coefficient and a shift operation. The parameters of a 2 nd order digital filter block in direct form II are shown in Fig. 5.

The RTL program corresponding to the block diagram of Fig. 4 is given in Fig. 6 below. From the program it can be seen that the data bus really is busy most of the computation time. About 77% of the microinstructions are performing data bus transfers. The corresponding load percentages for the CPE and DATA RAM are only 43% and 47%, respectively. The performance measurements clearly showed that the computation speed of NRS 290 was on the level of fastest digital filter implementations of its time. The initial design specifications of NRS 290 were fully reached and even in some respect exceeded. The measured microinstruction execution time was 195 ns which was 35 ns less than originally estimated. The performance of different digital filter implementations was compared on the basis of attenuation and computation time. However, the computation time was strongly dependent of the filter type, degree, and realization form.

For comparison, the number of microinstructions as a function of degree is shown in Table 2 for different filter structures. The traditional 2 nd order block realizations and low-sensitivity digital lattice forms were compared. The computation times and the corresponding maximum sampling rates can be calculated using the measured microinstruction cycle time 195 ns. Details of all comparisons can be found in [START_REF] Bärling | Microprogrammable Digital Filter, Programming and Performance[END_REF].

Using the microinstruction cycle time of 195 ns, the computation times of 4.1 μs for a standard 2 nd order digital filter block (row 1 in Table 2) was obtained. Similarly, for a full filter bank of 16 4 th order filters the computation time of 131 μs was achieved. The corresponding sampling rates were 244 kHz and 7.63 kHz, respectively.

To make comparisons easier, a figure of merit was introduced to measure the attenuation efficiency, η A Attenuation in dB Number of microinstructions [START_REF] Gold | Digital Processing of Signals[END_REF] In the above equation, attenuation was measured at the stopband edge frequency. For bandpass filters the minimum attenuation at the edge frequencies was used. Table 3 shows the measured computation times and attenuation efficiencies of different filter structures. A 4 th order elliptic filter was used as a reference structure. It was compared with both 4 th and 6 th order filters with reduced number of zeroes but equal passband specifications. It can be seen that the attenuation is slightly increased in the realizations with reduced number of zeroes with some increase in computation time, too. However, the attenuation efficiency remains about the same. In Fig. 7, the measured amplitude response of a 4 th order elliptic bandpass filter realized using all-pole 2 nd order blocks is shown. The passband ripple is 1 dB and the center frequency 13.2 kHz with lower and upper cutoff frequencies 12.7 kHz and 13.6 kHz, respectively. The sampling frequency of 75.2 kHz was used. The computation speed of NRS 290 can be compared with similar hardware architectures of late 1970s. In 1980 a signal processor architecture based on distributed arithmetic (SDA) was reported in [START_REF] Zeman | A High-Speed Microprogrammable Digital Signal Processor Employing Distributed Arithmetic[END_REF]. The SDA hardware built at ETH Zurich was also based on Am2900 circuit family. It was microprogrammable and had 16 bit word length using, thus, 4 Am2901 bit-slices. The basic cycle time of the SDA architecture was 300 ns. Another TTL based implementation of a 4800 bit/s microprocessor data modem was reported already in 1978 in [START_REF] Watanabe | A 4800 bit/s Microprocessor Data Modem[END_REF]. The microprogrammable hardware was also using bit-sliced microprocessors of 4 bits. With 12 bit word length the cycle time of 230 ns was achieved. Thus, it can be seen that the computation speed of NRS 290 hardware was very well comparable, or even better than that of similar implementations based on the latest microprocessor technology of 1970s.

Conclusions

In the 1970s, digital signal processing was rapidly maturing for real time applications. Although the design of filters was laborious due to the lack of CAD programs, digital filters were designed for practical applications. Also the implementation was difficult because there were no chips or chip sets tailored for DSP. The development was, however, fast. Ironically, as soon as the NRS 290 hardware multiplier unit had been built and tested, TRW released a 16 bit multiplier on a single chip. Similar progress was also seen in the DSP software development tools in the 1980s.

In Finland, the pioneering work in DSP was very successful. The telecommunications industry was especially enthusiastic of modern DSP implementations. One of the first industrial applications was started in the middle of 1970s. A state-owned telecommunications company Televa, later part of Nokia Telecommunications, was investigating digital filter implementations for detecting touch tone dialing signals.

The filter bank was designed as a master's thesis project at TKK. At that time digital filter design tools did not exist. However, the designed filters worked properly and were computationally extremely efficient.

This kind of early research cooperation with industry was very important for the future development of the telecommunications and mobile phone industry. Nokia introduced the world's first GSM handset Nokia 1011 in early 1990's. At that time commercial 16 bit signal processors with hardware multiplier were available. In the beginning the GSM speech coder needed two signal processor chips in parallel in order to meet the real time processing requirements. Nokia in partnership with Texas Instruments had a strong role in pushing digital signal processing first to speech coding and later to many other demanding mobile applications including image and video compression. Nokia was thus one of the leading companies utilizing signal processors in the mobile phones starting from 2G. Much of the signal processing expertise required can be traced back to the research and education activities where NRS 290 had played an important role.

Fig. 1 .

 1 Fig. 1. Hardware organization and register configuration of NRS 290

  NRS 290 hardware consisted of six circuit boards of size 234 mm x 160 mm. They were: (1) Microprogram memory and sequencer, (2) CPE ALU and DATA RAM, (3) external control, (4) MUX + ADC, (5) DAC + DEMUX, and (6) multiplier. The circuit boards were constructed using the wire-wrap techniques with all circuits installed into sockets. The NRS 290 front panel and the multiplier circuit board are shown in Fig. 2.

Fig. 2 .

 2 Fig. 2. NRS 290 front panel and the multiplier circuit board

Fig. 3 .

 3 Fig. 3. Microinstruction word

Fig. 4 . 5 .Fig. 6 .

 456 Fig. 4. Block diagram of the program Fig. 5. Contents of the memory block

Fig. 7 .

 7 Fig. 7. Measured amplitude response of a 4 th order all-pole bandpass filter

Table 1 .

 1 Instruction set of the RTL language.

Table 3 .

 3 Comparison of filter implementations.

Fast Fourier Transform (FFT) algorithm reduces the arithmetic operations from N

to Nlog 2 N, e.g., for N=1000 from 10 6 to 10 4 . Invention of FFT is often considered as one of the starting points of digital signal processing as a discipline of its own.

Table 2. The number of microinstructions as a function of degree in different filter programs.


Tangible Encoding of Temporal Data in Air Traffic Control

Keywords: Tangible interaction, Augmented paper, Distributed cognition, Representations of time, Security. ACM Classification H.5.m. Information interfaces and presentation (e.g., HCI): Miscellaneous

In this position paper, we describe a tangible design to support temporal processes in Air Traffic Control. We discuss how we balanced between physical and digital allocation of time-related features, relying on cognitive studies that show how physical space and physical objects manipulation support the encoding of real-time and planification concerns.

Introduction

For air traffic controllers, safety means managing realtime events: planes arrive at their destination or takeoff at given times. A critical part of the controller's task is to manage these events in real-time by talking to the pilots to give clearances. Another critical task is full preparation in order to ensure that these real-time actions will unfold properly and effectively. Cognitive approaches have explained how these tasks may be supported through an intelligent use of space and physical objects [START_REF] Kirsh | The intelligent use of space[END_REF]. In this paper, we briefly describes the ATC activity involving critical time management, and a tangible system, Strip'TIC [START_REF] Hurter | Strip'TIC: exploring augmented paper strips for air traffic controllers[END_REF], that supports ATC work by keeping the advantages of physical features. We then describe how we designed features to support temporal processes management, relying on these cognitive studies

Related Work

Our work relates to interface approaches that employ physical means of interaction: tangible user interfaces (TUIs) [START_REF] Ullmer | Emerging frameworks for tangible user interfaces[END_REF] and augmented-reality [START_REF] Mackay | Augmented reality: dangerous liaisons or the best of both worlds?[END_REF]. Tangible interface research aims to explain properties and Copyright is held by the author/owner(s). affordances of the physical world these interfaces rely on (e.g [START_REF] Hornecker | Getting a grip on tangible interaction: a framework on physical space and social interaction[END_REF]). For designers, a general issue thus becomes the allocation problem to either virtual vs physical objects according to performance or interaction needs. Interestingly, few TUI approaches have addressed time-related data, except for logging or controlling data streams, maybe due to the fact that these data are relatively abstract [START_REF] Klemmer | How bodies matter: five themes for interaction design[END_REF]. For instance, ChronoTape [START_REF] Bennett | ChronoTape: tangible timelines for family history[END_REF] is a temporal tangible interface, which enables the tangible representation and control of time for supporting family history research. This approach differs from ours: air traffic controllers do not control time (i.e they cannot pause or rewind!), instead, as explained in the paper, they need to manage it.

ATC Activity and its instrumentation

Air traffic controllers (ATCo) maintain a safe distance between aircraft and optimize traffic fluidity, usually working by pair. The planner controller predicts potential conflicts between aircraft. The tactical controller devises solutions to the conflicts, implements them by giving instructions to the pilots by radio, and monitors the traffic. Air traffic controllers currently use a combination of computer-based visualization (e.g. radar image) and tangible artifacts (paper strips) to manage traffic. In approach mode (Fig. 2) aircraft are most likely ascending or descending, with 2 minutes between two consecutive planes. Therefore the time of analysis and action decreases rapidly as the aircraft get closer to the field. When the runway capacity is exceeded, controllers can delay the arrival of aircraft by piling them up into a 'stack' and making them perform horizontal loops (Fig. 1). Since controllers do not feed the system with the instructions they give to the pilot and write onto paper, authorities have decided to replace paper with digital devices. However, there is still reluctance to the adoption of Electronic stripping, either prospective [START_REF] Mertz | The influence of design techniques on user interfaces: the DigiStrips experiment for air traffic control[END_REF], or operational (Frequentis SmartStrips or NAVCANStrips). This is partly due to the fact that screens do not offer the same level of interactivity as paper. Mixed interaction may be an appropriate approach to the improvement of the ATC environment.

Visualization of the past present and future aircraft positions

Air traffic controllers currently use a comet to display the current past and future aircraft position. The comet indicates a heading and its shape indicates its turn and degree of veering (Fig. 3). The design of the comet is built with squares, whose size varies with the proximity in time of the aircraft's position. This provides an efficient visualization of temporal data, with the possibility to interpret naturally emergent information such as speed, tendency and acceleration [START_REF] Harper | What a fing system! Send 'em all to the same place and then expect us to stop 'em hitting[END_REF].

Prototype description

We have designed Strip'TIC, a novel system for ATC that mixes augmented paper and digital pens, visionbased tracking and augmented rear and front projection [START_REF] Hurter | Strip'TIC: exploring augmented paper strips for air traffic controllers[END_REF]. The paper strips, the strip board and the radar screen are all covered with Anoto Digital Pen patterns (DP-patterns). Users' actions with the digital pen are sent in real-time to IT systems wherever they write or point. Bottom and top projection on the stripboard and strips display dynamic information. Controllers can manipulate paper strips as they are used to with the regular system.

Tangible encoding of ATC temporal processes

We explored whether augmentation could provide useful support to time-related features.

Structure of temporal processes in ATC

In [START_REF] Loft | Modeling and predicting mental workload in en route air traffic control: critical review and broader implications[END_REF] Loft et al describes ATC activity as a subtle combination of two modes of control: a proactive mode that consists -often for the planner -in building an efficient encoding of the problems so that they can be resolved very quickly and without errors, and a reactive mode which is often performed by the tactical through reactions to events (pilot calls, clearances, potential conflicts). The two parallel modes occur at different timescales, as explained by a controller: «the tactical […] is dealing with a problem at 15 nautical miles and we speak here about a conflict that will happen in 15 minutes». ATC activity thus involves constant phasing between two timescales: that of the controllers, during which they organize their work, and real time, where real traffic occurs.

Temporal processes physical encoding

In [START_REF] Kirsh | The intelligent use of space[END_REF], Kirsh describes how spatial arrangements support expert activities involving a preparation phase, and a high tempo execution phase. For instance, experts ensure that information needed to act quickly is available locally, and that actions can be performed almost automatically. To achieve this, they prestructure their workspace physically to simplify choices, discard unrelated decisions, encode pre-conditions, and highlight the next action to take. For Kirsh, space also naturally encodes linear orders: items arranged in a sequence can be read off as the order they are to be used in. We observed similar orders in approach control with stacks and arrival sequences. In [START_REF] Harper | What a fing system! Send 'em all to the same place and then expect us to stop 'em hitting[END_REF], Harper et al highlight how these arrangements encode an ordered set of tasks to perform: "ATCO work is not like an assembly line in which a recurrent sequence of steps has to be followed through, but one in which the work consists of putting the tasks to be done into a sequence of steps that can be followed through". These spatial orderings implicitly connect the two timescales we mentioned above: taken as traffic sequences, they correspond to the planes flying in real-time, but as tasks to perform, they also correspond to the control timescale. To be as precisely on time as possible, controllers also rely on their knowledge of action duration according to various contexts (including their own cognitive load): «It's your internal clock, you know how long it takes you to perform standard actions.»

Experimentation of time-based mixed tools

Based on this analysis, we explored how to turn these implicit relationships into a more explicit design of virtual temporal objects. Some tools enable computation (Fig. 4), others facilitate conflict management (Fig. 7a) [START_REF] Grau | Dynastrip: a time-line approach for improving the air traffic picture of Controllers[END_REF]. Interactive tools enable to evaluate time and distance directly from the radar screen (Fig. 7b). Such tools are meant to add explicit time-related information to the already spatially structured linear orders. Time can also be visualized as dynamic, providing a sense of passing time through information that evolves visually, such as a timer to manage wake turbulence (Fig. 8), or progress bars (Fig. 5). We see these tools as complementary instruments to support phasing between the two timescales that we described above. What we observed however is that while controllers quite efficiently rely on their own skills, using physical and spatial tools both to adapt to real time and to schedule their actions, they also liked realtime, tactical control oriented tools that help program timing or actions, such as countdown timers [START_REF] Bennett | ChronoTape: tangible timelines for family history[END_REF]. In

Conclusion

Through the design of the Strip'TIC prototype, we were able to experiment various designs for the support of temporal processes in ATC. Main needs include the ability to anticipate events by being able to figure out their time or location. Complementary real-time and tactical features help the controller to improve its feeling of passing time to trigger actions accordingly

CHI' 13 ,

 13 April 27 -May 2, 2013, Paris, France. ACM 978-1-XXXX-XXXX-X/XX/XX. catherine.letondal@enac.fr Jean-Luc Vinot ENAC, 7 avenue Edouard Belin 31055 Toulouse, France jean-luc.vinot@enac.fr Stéphane Conversy ENAC, 7 avenue Edouard Belin 31055 Toulouse, France stephane.conversy@enac.fr

Figure 2 :

 2 Figure 2: phases of flight and associated control areas. Final approach control manages aircraft from the stack and the IAF (Indicated Approach Fix) point before landing.

Figure 1 :

 1 Figure 1: A stack and calculation of the Estimated Approach Time (EAT)

Figure 3 :

 3 Figure 3: The shape decreases in intensity over time on a scope (top picture). ODS comet metaphor (bottom picture).

Figure 4 :

 4 Figure 4: tangible computation of an arrival sequence: allocation within projected time slots (blue), computed stack exit times (red), strips linked to their projected stack level (whitecrossing links show a misordering). This was inspired by a kind of paper ruler that is used by Orly approach controllers as rough paper that helps visualize free time slots and calculate mentally (Fig 6).

Figure 6 :

 6 Figure 6: a) a rough paper ruler on the back of a strip to allocate an arrival sequence; b) the paper ruler contains stack exit times as mentally computed by the approch controller.

Figure 5 :

 5 Figure 5: colors (light grey, yellow, dark grey) indicate past, present and future flight levels.

Figure 7 :

 7 Figure 7: a) a timeline representing several flights heading to a common beacon to analyze potential conflicts; b) computation of the time needed for the drawn trajectory. The controller draws a polyline with the pen onto the radar screen where the estimation of time and distance to reach it is displayed next to the related nodes.

Figure 8 :

 8 Figure 8: wake turbulence take-off timer (green circle): the next departing plane has to wait for the AFR608 (indicated as heavy (H)) to move away.