Squigol(ID:2527/squ005)for the squiggly symbols it uses functional programming language based on the Bird-Meertens Formalism People: Related languages
References: The SQUIGOL notation is concise, inspired by algebra, APL and FP, and very amenable to hand manipulation. A SQUIGOL program can be rather dense, but spreading it out over more characters would not make it any clearer. Bird has developed an interesting theory of sequences. Sequences are ubiquitous in computing, so computer scientists should develop a theory that helps solve problems that involve sequences, just as mathematicians have developed a theory of numbers that helps to solve problems that involve numbers. The derivation shows the power of defining appropriate domain-specific operators, such as segs, and studying their properties. Squigol is the popular name given to the Bird-Meertens formalism, a concise mathematical methodology for program derivation. In essence, Squigol is a functional calculus based on map and reduce. This chapter explores how Squigol may be used to derive parallel functional programs. Much of this chapter applies existing Squigol work to the derivation of parallel algorithms. Previously Squigol has only been used for deriving sequential algorithms and hardware descriptions. In some respects Squigol is similar to Backus's FP [7]; they are both algebraic approaches to program transformation. However, unlike FP, Squigol is typed and it is in general more flexible than FP. Bird and Meertens jointly developed Squigol and the following references are highly recommended: [14, 80]. Many people are currently working on Squigol and although there is a consensus on most of Squigol, some aspects are treated differently by different people: notably non-determinism. Thus Squigol should not be regarded as a standardised calculus; usually it is customised to suit the particular class of problems being solved. Here Bird's flavour of Squigol from [14] will be used. The next section describes some basic Squigol; the following section looks at the parallel aspects of Squigol and finally three examples are developed: a parallel shortest paths algorithm, a parallel n-queens algorithm and a parallel greedy algorithm. It should be noted that it is unclear just how general Squigol is for sequential or parallel program derivation. However, certainly a large class of optimisation algorithms are amenable to derivation using Squigol. Extract: Basics Basics This section describes some basic Squigol concepts. Much of what is described is general to sequential and parallel program derivation. A Squigol derivation starts with an inefficient specification. The specification is repeatedly transformed by applying algebraic identities and theorems, until an efficient algorithm is derived. Often the initial specification and final program are quite simple, and the derivation is quite complex. Since programs are derived using algebraic identities and theorems, programs will be correct with respect to the specification from which they were derived. One of the Squigol goals is to calculate algorithms without using induction. Like FP. the language used for Squigolling is based on combinators. Thus, it is rather like functional programming using combinators as much as possible. Unlike functional programming, functions are assumed to be total, to facilitate algebraic manipulation. A consequence of this is that data structures are finite. Despite this the language does not specify any evaluation order. A drawback of this approach is that the language does not have a formal semantics, unlike functional programming or FP. In particular derivations only guarantee partial correctness. Squigol is not even necessarily constructive; in particular function inverses may be used to specify other functions. Also fictitious values may be used[...]. The notation used is similar to that of a curried functional language; functions are curried and composition is denoted by an infix dot for example [...]. Function application binds more tightly than other operators[...] |