Stack-based programming languages
Functional programming is back in fashion. Depending on whether you prefer classic or hardcore, suffer from imposed industry standards or are you just a hipster, your favorite preference may be Scala, Haskell, F#, or even good old Lisp. Such combination of words as a higher-order function, no side effects, and even monads, caress the ear all the "fragile young minds", whether it's the guys from JetBrains or student who first saw SICP.
But there is one more programming, in a literal sense, even more functional, based on their having rather than the lambda calculus, and function composition. And I want to talk a little bit.
the
What is a concatenative programming
Concatenation is the joining of several lines. The language in which the conventional connection of the two code snippets is their composition, is called concatenative[1]. Each of these pieces of code — a function that takes as argument a stack and as a result, the stack and returns. Therefore, most such languages are called the stack (stack-based).
Stack-based languages are alive and exist. Thanks to the speed and lightness of the translators they are applied in the real world. JVM, most probably, a common virtual machine in the world; CPython, another stack-based virtual machine[2], which is used in many heavy projects, such as Youtube and BitTorrent; in the PostScript language, now used in high-performance top-end printers finally, the good old Forth, is still occurring for programming microcontrollers and embedded systems. They are all wonderful in their own way, but it is worth noting that although the General principles are similar, but by and large we will focus on languages of a higher level, such as Faсtor, Joy or Cat.
the
Functions
In concatenative languages, everything is a function, but for comparison with other languages let's look at an example of a function squared with determination. Unwavering imperative :
the
int square(int x)
{
return x * x;
}
Functional Scheme:
the
(define square
(lambda (x)
(* x x)))
Concatenative Joy:
the
DEFINE square == dup * .
Concatenative Factor:
the
: square ( x -- y ) dup *;
Concatenative Cat:
the
define square {
dup *
}
Here dup creates a copy of the argument, on top of the stack, and puts that copy there.
* is just a function of the multiplication
*:: (int) → (int) → (int)3::() → (int)In concatenative languages are not used (or rather not recommended, but if you really want, you can) variables and lambdas, and this fact makes it quite concise. Instead aplicativos approach here the composition is written in Postfix (reverse Polish) notation, which corresponds to a data sequence that we work with in the stack, and hence in some ways easier to read stack-based code. Let's look at two examples. First, this is the usual Hello world, looking in this notation a bit unusual:
the
"Hello world" printWe put on the stack the string "Hello World", and then the print function of the extracted element with the top of the stack and displays it on the screen.
the
10 [ "Hello," "Factor" append print ] times
Here we use operations on quotes, which will be discussed later, but it's quite obvious that the stack 10 is placed and quote and times executes the code of the quotes specified number of times. The code inside the quotes just consistently puts on the stack the two strings, then joins and displays on the screen.
To try a small concatenative language directly in the browser it is possible to trybrief.com. It is easy to notice the interpreter is written in javascript and fairly simple you can look at ./Engine.js. Cat, the interpreter of which was originally implemented in C#, and now in many other languages, there are also online js interpreter.
the
Quotes and combinators.
The ability to take pieces of code in quotes ([ ]), gives the possibility to write your own control structures. Quotes are functions that return the contents of the quoted expression. The function of the citation in this case would be the following type.
the
quote :: (T) → (() → T). For example, [5] in square brackets will return the number 5 integer type, and its quotation. Clearer when it comes to expression, for example [5 6 +]. Without citation will occur calculate the number of 11 and placing it in the stack, the citation will be placed on the stack the expression 5 6 +, with which you can interact in many different ways.
Combinators are functions that expect one or more of the stack and applies them in a special way to the rest of the stack.
In fact the quote — it's the usual lists. You can connect them with other quotes, to make various manipulations on the stack, and then apply with the help of different combinators. For example, the fold Combinator turns a list into a value, example summing the elements of the list (Joy):
the
[2 5 3] 0 [+] fold
Quick sort with recursive binrec Combinator in Joy:
the
DEFINE qsort ==
[small]
[]
[uncons [ > ] split]
[[swap] dip cons concat]
binrec .Nothing prevents to implement monads Factor and Yes, Faсtor, for example, is able to optimize tail recursion.
the
management structure.
Through the quotation and combinators, you can use current or create your own control structures. For example if (Factor):
the
= [ 23 ] [ 17 ] if
To understand how this works, I recommend to brush up on definition of Boolean functions in the lambda calculus. A slightly more complex example for Factor:
the
: sign-test ( n -- )
dup 0 < [
drop the "negative"
] [
zero? [ "zero" ] [ "positive" ] if
] if print ;
The function determines the sign of the number. if operates with two quotations, square brackets and allocated on the stack higher than the expression dup 0 <. If the number lying on top of the stack when you call the sign-test (i.e. the function argument) is less than zero — use the first quote that pushes "negative" (throwing out the test number that was copied). If the number is greater than the second quote, inside contains another condition. After that, the stack is a string denoting the sign of the number, that string is displayed by the print function.
the
Advantages:
the Speed and optimizermemory.
the
:A 1 2 + print
:add2 2 + ;
:B a add2 print
In this case, A = B due to the associativity of the composition. Program concatenative language is divided into pieces, which are collected after compilation. In fact it is a normal map-reduce, fast and allow you to compile every piece of code in parallel.
the Refactor. If you see two of the same piece of code to pass them a separate function. Use combinators, quoting and your own control structures. Examples of optimizations in the language of the Cat:
the
f map g map = > [f g] map
[f] map x [g] fold = > x [[f' f] g] fold
[f] filter x [g] fold = > x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold = > x [f g [h] [pop] if] fold
the
Complexity
All the disadvantages of stack-based languages clearly derive from their characteristics. This composition is of an application is point-free notation, is the lack of variables and the complexity of some expressions. Imagine a simple expression in a concatenative language 'a b c d'. If the c function takes two arguments, the applicative form of the expression will be written as d(c(b, a)) if b and c take a single argument, d(c(b(a))); if d a function of two arguments, b one, and c the function does not take arguments, the applicative form of the expression will be d(c, b(a)). Very carefully to write code in a concatenative language because you have to understand absolutely everything in it. This is helped by the strong typing to Cat, the alleged support from the IDE, various methods and mechanisms that allow us to change the thinking. But this problem can overtake you and in your favorite Haskell with its point-free notation of compositions of functions (which are points). Record in the Postfix form, without named variables some complex algebraic expression is also not possible in the same way as we are accustomed from childhood. And this is the main problem with these languages is that they are like a classic functional, you require a little thinking. In terms of production, and the story of Scala has not yet subsided, required languages, familiar to all, because everything depends on human resources.
Each function in a concatenative language operates on a stack, and although this in itself may be no side effects, there are no assignments of variables, but it changes the stack, i.e., global state, so the question of purity for many not obvious. However, for those higher-level language in question is not really fair, because it is rather an implementation issue. And in order to be applicable in the real world they have variables for those rare occasions when they are needed (for example, SYMBOL: Factor or function declarations to improve code readability), they can be clean enough in mathematical terms (as Joy[4]) and as many conceptual differences between the approaches, paradigms and platforms in the end to be just a matter of taste. With adequate selection tool for the task. This is why Forth is used for embedded systems, its translator is very easy to implement and it will be very small in size.
I hope someone discovered something new. Personally, I was inspired by the text "Why concatenative programming is important"[5] and now, a few days can not break away from this topic, and even being in a dream state unable many times to say the word "concatenative".
1. Wikipedia: Concatenative programming
2. the Pypy interpreter
3. http://docs.factorcode.org/content/article-cookbook-philosophy.html
4. Functional Programming in Joy and K
5. Why Concatenative Programming Matters?
6. Objects and Aspects: Row Portmanteau
Комментарии
Отправить комментарий