Stanislaw Ambroszkiewicz


MSc and PhD degree from University of Warsaw, Dep. Mathematics & Informatics in 1982 and in 1991 respectively, Habilitation from Institute of Computer Science, Polish Academy of Sciences in 2004.  Affiliations: prof. nadzw. in the Institute of Computer Science, Polish Academy of Sciences, and a prof. nadzw. in the Institute of Computer Science of  Siedlce University of Natural Sciences and Humanities (teaching duties: courses on Computer Architectures and Computer Networking).

More on www.ipipan.waw.pl/mas/stan

Functional programming is a style of programming which models computations as the evaluation of expressions (from wiki.haskell.org).
Hence, the computations consist in symbolic manipulations, i.e. term rewriting according to a fixed syntactic rules. What are the expressions (terms)? Are they functions or merely denote the functions?

If the terms are functions, then functional programming is still "value-level programming", i.e. values are terms of data type String. Lazy evaluation is an additional processing (imperative on the von Neumann computer) of terms (strings).

Otherwise, the problem stated by John Backus 1977 ACM Turing Award lecture "Can Programming Be Liberated from the von Neumann Style" is still a challenge.

John Backus' famous von Neumann vicious circle:
"non-von Neumann computer architectures cannot be developed because of the lack of widely available and effective non-von Neumann languages. New languages cannot be created because of lack of conceptual foundations for non-von Neumann architectures".

The original idea of Backus function-level programming language was based on "programs as mathematical objects", where the objects (functions and higher order functions, i.e. functionals) are used directly in computations, that is, not by their names.

There is wide spread opinion that the functional programing languages (like Haskell and F#) are non-von Neumann. If it is true, then where is a corresponding non-von Neumann computer architecture?  Perhaps John Backus was not right. Perhaps the notion of functional (created by human intellect) is still far from being understood. However, it is remarkable that human brain is not built according to the von Neumann architecture.

The current paradigm in Computer Science (not only in programming) states that computations on higher order objects (functionals) can be done only symbolically, that is, these objects can be represented and manipulated only by using symbols. 
 
Although symbolic computations make sense (like algebraic calculations), and the computations on higher order object can be done (via some equations) if they are evaluated to the primitive data types, the intuition behind the functionals is that they are *objects* that can be constructed as concrete physical structures.
 
What about functionals as hardware?
Why not? Although, the hardware technology is still far from making possible to break the paradigm, functionals may be envisioned as programmable integrated circuits (FPGAs).

The idea is so novel.
The approach proposed by C$\lambda$aSH http://www.clash-lang.org/ to realize higher order functionals is interesting. It goes from Haskell and its high-level descriptions (syntax) and via term rewriting (lazy evaluation as semantics) to a standard HDL (Hardware Description Language). Actually, after rewriting term (denoting a functional) fully to its normal form, that is, to imperative code, it is translated to a HDL. Hence, this approach is still unsatisfactory. For a survey of functional HDL, see  Peter Gammie,  (2013). Synchronous digital circuits as functional programs. ACM Computing Surveys (CSUR), 46(2).

The notion of function as well as higher order objects (functionals) is based on the following more elementary notions:
-- type and object of type;
-- type constructors;
-- type of function and related input, function body, and output (the same for functionals);
--  application of an object to the input of a function (functional), especially if the input type is of higher order;
-- composition of two functions (functionals).

Can these elementary notions listed above be realized as hardware?
Perhaps a solution is something like dynamically configurable integrated circuits. So far FPGAs are limited to the first order functions, so that input as well as output of a FPGA circuit generally consist of a fixed number of bytes. 

Conclusion: Higher order computation can be envisioned as dynamic creation and reconfiguration of links between elementary circuits representing first order functions. It's only a matter of time for the technology to  reach the state when the functionals will be grounded in hardware.

For more on functionals as hardware, see arXiv and google arXiv Ambroszkiewicz.

Slides
Video ←Back