Задача вычисления первых двух десятков чисел Фибоначчи давно потеряла практическую ценность для программистов и используется преимущественно для иллюстрации базовых принципов программирования — рекурсии и итерации. Я же использую ее для демонстрации нескольких языков программирования, в которых она приобретает необычный и местами даже нездоровый вид.
Итак, мой рейтинг десяти наиболее противоестественных способов вычисления чисел Фибоначчи из написанных мной за последние полгода в рамках проекта Progopedia. Для уточнения задачи потребуем, чтобы выводом программы были первые 16 чисел в виде
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,…
Визуальный язык программирования, в котором все элементы языка представлены в виде элементарных блоков, из которых составляется собственно «код», именуемый диаграммой потоков (flowgram). Место в рейтинге этот язык заслужил размером диаграмм (два, ну три десятка элементов — максимум, который можно использовать на одной диаграмме без скроллинга и окончательного запутывания в связях между блоками) и неудобством использования ключевых структур языка (каждый цикл или условный переход требует для своего описания одной или нескольких отдельных диаграмм, которые мгновенно загромождают логику программы многоуровневой вложенностью и передачей глобальных переменных в виде параметров цикла). Ну, и собственно визуальностью — программа не пишется, а рисуется, и клавиатура как таковая используется только для ввода значений констант и (опционально) переименования элементарных блоков и написания комментариев.
Главная диаграмма потоков
Тело цикла
Особенность этого языка (до версии 4.4.0) — отсутствие циклов как таковых. Впрочем, это можно простить — все-таки gnuplot не язык общего назначения, а программа для построения графиков. А цикл можно сымитировать, создав отдельный интерпретируемый файл с телом цикла, который «читается» для начала цикла и «перечитывается» для каждой итерации.
Файл run.gp (главный)
Файл fibonacci.gp (имитация цикла)
Ленивые вычисления в комплекте с бесконечными списками — одна из самых известных фишек Haskell — позволяют определить (но не вычислить) числа Фибоначчи в одну строчку кода, остальной код запрашивает нужные числа и выводит их в нужном формате. А все-таки для программиста, получившего классическое воспитание в рамках процедурной парадигмы, этот способ далеко не очевиден и уж точно не естественен.
Конечно, SQL сам по себе языком программирования не является, и в большинстве реализаций к нему прилагается процедурное расширение, с использованием которого поставленная задача решается вполне классическим образом. Интерес представляет решение без расширений, на «чистом» SQL. Впрочем, на «чистом» SQL решить не получится — по стандарту язык запросов не содержит ничего, что можно было бы использовать в качестве цикла. Решения получаются зависимыми от конкретной реализации и прилагающихся к ней плюшек.
Во внутреннем запросе генерируются индексы чисел (с 1 до 16) при помощи псевдостолбца level и конструкции connect by. В следующем запросе вычисляются сами числа Фибоначчи по их индексам при помощи формулы Бине. Оставшиеся два запроса упорядочивают числа по их индексам и соединяют их в одну строку нужного формата.
Удобный, но редко применяемый и поэтому малоизвестный оператор model позволяет реализовать цикл внутри SQL-запроса.
Возможность вычисления результатов запроса в цикле реализована более лаконично, чем в Oracle.
Еще одна достаточно лаконичная реализация циклов, на этот раз с помощью рекурсивного запроса.
FP — прототип всех существующих языков программирования, использующих парадигму программирование на уровне функций (function-level, не путать с functional, то есть просто функциональной). Изобретенный в 1977 году, он является скорее математической моделью, чем настоящим языком программирования: у него не было даже официального стандарта (кроме единственной статьи, в которой он описан), не говоря уже о реализации! Тем не менее, в наше время существуют интерпретаторы этого языка, обычно написанные в рамках студенческой работы. Одним из них является Furry Paws, и его уютное название совершенно не соответствует «комфортности» его использования.
Программирование на уровне функций предполагает построение программы из элементарных функций, комбинируемых при помощи функционалов (функциональных форм). Так, ~1 — элементарная функция, всегда возвращающая значение 1; id — функция, возвращающая переданное ей значение, [] — функциональная форма, объединяющая свои аргументы в последовательность и т.д.
Еще один язык, использующий «программирование на уровне функций», достойный преемник FP. Интересен тем, что практически любое выражение на нем можно записать несколькими способами, от почти традиционного до совершенно противоестественного (что и требовалось в данной статье). Так, например, вычисление чисел Фибоначчи при помощи формулы Бине можно записать вполне цивильно:
А можно заменить практически все математические операции на их эквиваленты, специфичные для J:
И едва ли кому-то будет очевидно, что %: — это извлечение квадратного корня, >: — инкремент, -: — деление на два, а %~ — деление, причем при записи делимое и делитель меняются местами.
Вычисление с использованием рекурсии:
Малоизвестный эзотерический язык, интересный своим минимализмом и использованием стековой модели памяти. В отличие от следующего языка, основная сложность заключается не в выполнении арифметических действий, а в получении содержимого именно тех элементов стеков, которые нужны на каждом шаге. Вывод на печать, впрочем, так же неприятен, поэтому вычисляется и выводится только первая шестерка чисел.
Описание языка и комментарии к приведенному коду можно найти на странице Hanoi Love.
Классика жанра эзотерического программирования — Brainfuck. Язык, в котором даже копирование или сложение не является элементарной операцией, вывод на печать
трехзначного числа достоин отдельной оды, а уж использование его для решения какой-то конкретной задачи — ну просто мечта мазохиста :-)
В авторском интерпретаторе (Muller's Brainfuck) содержимое ячеек памяти хранится в переменных типа byte, и числа Фибоначчи с 14-го по 16-ое вызвали бы переполнение памяти. Реализация длинной арифметики на Brainfuck — это уже не симптом, а практически диагноз, поэтому при написании решения предполагалось, что ячейка памяти может хранить числа до 1000 (во многих реализациях языка для хранения используются достаточно вместительные типы данных).
Описание языка и комментарии к приведенному коду можно найти на странице Brainfuck.
Cамый простой из графических диалектов Brainfuck, придуманный Lode Vandevenne.
Программы читаются с картинок PNG, команды записываются пикселями разных цветов, и к имеющимся в Brainfuck восьми командам добавляются еще две — управление указателем на текущий пиксель. Ко всем прелестям Brainfuck добавляется еще полная нечитабельность «кода» и полная невозможность
«кодировать» без вспомогательных средств (например, конвертера программ и картинок).
Авторский интерпретатор языка канул в лету, поэтому для генерации «программы» пришлось писать свой. «Программа» приведена в десятикратном увеличении.
Куда уж хуже? — подумает читатель, листая экран дрогнувшей рукой. Да, бывает еще хуже. В предыдущих языках программу можно было хотя бы объять взглядом, а это уже немало.
Встречайте победителя рейтинга — Unary. Диалект Brainfuck, придуманный тем же Lode Vandevenne (о, мсье знает толк в извращениях!), предполагает, что команды Brainfuck преобразуются в двоичные коды и конкатенируются в одно двоичное число, унарная запись которого и является программой на Unary. Программа генерации чисел Фибоначчи представляет собой строку из
167967665105731198557055496639385943332278803897935697536099438828197
665241403160165880863622431582784595268769268183940269756210147305655
704025762911607244068691728105306566342622386432823429136972542304655
647901781271798433263001837026612851345264031562174039657802748245705
398528237993320520942720239597540583536934220029626573406470088757427
393143000966310611249037587993216365993804186165097620168960460854977
571944373603975793034586829061577464233522714007498991416860375267535
193648636795096472789203729505034887001634966681420589637468649908257
407260923590831776308356684326657774592110098643361324426156431864437
942781495979555960608253552679248495326880775320385281559763269974848
026839024530519989287202261977272377723622502479809174132505837648641
033569945906182518892142219706483917757108086522763280388915772444727
238483811923456440363260610571471034139736312976255142288379411989404
9017738035 (то есть примерно 1.68*10^906) нулей.
Я уверена, что перечисленные здесь языки — далеко не самое страшное, с чем может столкнуться программист (во всяком случае, не все из них :-) ), но я не волшебник, я только учусь.
Итак, мой рейтинг десяти наиболее противоестественных способов вычисления чисел Фибоначчи из написанных мной за последние полгода в рамках проекта Progopedia. Для уточнения задачи потребуем, чтобы выводом программы были первые 16 чисел в виде
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,…
10. Sanscript
Визуальный язык программирования, в котором все элементы языка представлены в виде элементарных блоков, из которых составляется собственно «код», именуемый диаграммой потоков (flowgram). Место в рейтинге этот язык заслужил размером диаграмм (два, ну три десятка элементов — максимум, который можно использовать на одной диаграмме без скроллинга и окончательного запутывания в связях между блоками) и неудобством использования ключевых структур языка (каждый цикл или условный переход требует для своего описания одной или нескольких отдельных диаграмм, которые мгновенно загромождают логику программы многоуровневой вложенностью и передачей глобальных переменных в виде параметров цикла). Ну, и собственно визуальностью — программа не пишется, а рисуется, и клавиатура как таковая используется только для ввода значений констант и (опционально) переименования элементарных блоков и написания комментариев.
Главная диаграмма потоков
Тело цикла
9. gnuplot
Особенность этого языка (до версии 4.4.0) — отсутствие циклов как таковых. Впрочем, это можно простить — все-таки gnuplot не язык общего назначения, а программа для построения графиков. А цикл можно сымитировать, создав отдельный интерпретируемый файл с телом цикла, который «читается» для начала цикла и «перечитывается» для каждой итерации.
Файл run.gp (главный)
#!/usr/bin/env gnuplot
i = 1
a = 1
b = 1
res = ''
load "fibonacci.gp"
print res, '...'
Файл fibonacci.gp (имитация цикла)
res = res . a . ', '
c = a
a = b
b = b+c
i = i+1
if (i <= 16) reread
8. Haskell
Ленивые вычисления в комплекте с бесконечными списками — одна из самых известных фишек Haskell — позволяют определить (но не вычислить) числа Фибоначчи в одну строчку кода, остальной код запрашивает нужные числа и выводит их в нужном формате. А все-таки для программиста, получившего классическое воспитание в рамках процедурной парадигмы, этот способ далеко не очевиден и уж точно не естественен.
module Main where
import Text.Printf
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
line n = printf "%d, " $ fibs !! n
main = do
sequence_ $ map line [1..16]
putStrLn "..."
7. SQL
Конечно, SQL сам по себе языком программирования не является, и в большинстве реализаций к нему прилагается процедурное расширение, с использованием которого поставленная задача решается вполне классическим образом. Интерес представляет решение без расширений, на «чистом» SQL. Впрочем, на «чистом» SQL решить не получится — по стандарту язык запросов не содержит ничего, что можно было бы использовать в качестве цикла. Решения получаются зависимыми от конкретной реализации и прилагающихся к ней плюшек.
7.1. Oracle SQL (с версии 9i)
Во внутреннем запросе генерируются индексы чисел (с 1 до 16) при помощи псевдостолбца level и конструкции connect by. В следующем запросе вычисляются сами числа Фибоначчи по их индексам при помощи формулы Бине. Оставшиеся два запроса упорядочивают числа по их индексам и соединяют их в одну строку нужного формата.
SELECT REPLACE(MAX(SYS_CONNECT_BY_PATH(fib||', ', '/')),'/','')||'...'
FROM ( SELECT n, fib, ROW_NUMBER()
OVER (ORDER BY n) r
FROM (select n, round((power((1+sqrt(5))*0.5, n)
-power((1-sqrt(5))*0.5, n))/sqrt(5)) fib
from (select level n
from dual
connect by level <= 16) t1) t2
)
START WITH r=1
CONNECT BY PRIOR r = r-1;
7.2. Oracle SQL (с версии 10g)
Удобный, но редко применяемый и поэтому малоизвестный оператор model позволяет реализовать цикл внутри SQL-запроса.
select max(s) || ', ...'
from
(select s
from dual
model
return all rows
dimension by ( 0 d )
measures ( cast(' ' as varchar2(200)) s, 0 f)
rules iterate (16)
( f[iteration_number] = decode(iteration_number,
0, 1, 1, 1, f[iteration_number-1] + f[iteration_number-2]),
s[iteration_number] = decode(iteration_number,
0, to_char(f[iteration_number]),
s[iteration_number-1] || ', ' || to_char(f[iteration_number]))
)
);
7.3. MySQL
Возможность вычисления результатов запроса в цикле реализована более лаконично, чем в Oracle.
select concat(group_concat(f separator ', '), ', ...')
from (select @f := @i + @j as f, @i := @j, @j := @f
from information_schema.tables, (select @i := 1, @j := 0) sel1
limit 16) t
7.4. Microsoft SQL Server (с версии 2005)
Еще одна достаточно лаконичная реализация циклов, на этот раз с помощью рекурсивного запроса.
with fibonacci(a, b) as
(
select 1, 1
union all
select b, a+b from fibonacci where b < 1000
)
SELECT cast(a as varchar)+', ' AS [text()]
FROM fibonacci
FOR XML PATH ('')
6. FP
FP — прототип всех существующих языков программирования, использующих парадигму программирование на уровне функций (function-level, не путать с functional, то есть просто функциональной). Изобретенный в 1977 году, он является скорее математической моделью, чем настоящим языком программирования: у него не было даже официального стандарта (кроме единственной статьи, в которой он описан), не говоря уже о реализации! Тем не менее, в наше время существуют интерпретаторы этого языка, обычно написанные в рамках студенческой работы. Одним из них является Furry Paws, и его уютное название совершенно не соответствует «комфортности» его использования.
Программирование на уровне функций предполагает построение программы из элементарных функций, комбинируемых при помощи функционалов (функциональных форм). Так, ~1 — элементарная функция, всегда возвращающая значение 1; id — функция, возвращающая переданное ей значение, [] — функциональная форма, объединяющая свои аргументы в последовательность и т.д.
one = eq.[id, ~1]
dec = sub.[id, ~1]
seq = one -> [~1] ; cat.[seq.dec, [id]]
fibonacci = lt.[id, ~3] -> ~1 ; add.[fibonacci.sub.[id, ~1], fibonacci.sub.[id, ~2]]
main = show.(return @fibonacci.(seq.~16))
5. J
Еще один язык, использующий «программирование на уровне функций», достойный преемник FP. Интересен тем, что практически любое выражение на нем можно записать несколькими способами, от почти традиционного до совершенно противоестественного (что и требовалось в данной статье). Так, например, вычисление чисел Фибоначчи при помощи формулы Бине можно записать вполне цивильно:
load 'printf'
g =: 0.5 * (1 + 5 ^ 0.5)
fib =: (0.2 ^ 0.5) * (g &^ - (1-g) &^)
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fib 1+i.16
А можно заменить практически все математические операции на их эквиваленты, специфичные для J:
load 'printf'
g =: -: >: %:5
fib =: (%:5) %~ g&^ - (1-g)&^
fstr =: '...' ,~ ,~^:4 '%d, '
fstr printf fib"0 >:i.16
И едва ли кому-то будет очевидно, что %: — это извлечение квадратного корня, >: — инкремент, -: — деление на два, а %~ — деление, причем при записи делимое и делитель меняются местами.
Вычисление с использованием рекурсии:
load 'printf'
fibr=: 1:`(-&2 + &fibr -&1) @.(2&<)"0
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibr 1+i.16
4. Hanoi Love
Малоизвестный эзотерический язык, интересный своим минимализмом и использованием стековой модели памяти. В отличие от следующего языка, основная сложность заключается не в выполнении арифметических действий, а в получении содержимого именно тех элементов стеков, которые нужны на каждом шаге. Вывод на печать, впрочем, так же неприятен, поэтому вычисляется и выводится только первая шестерка чисел.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;.'...;;;;;;;;;;;;.'...,..''''''..`.'.
..;.'.,.'...:...,.'..;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
"'.,.'...,"'.'...,"''.,...'.,..'..,...'...;.'.,.,!...,,,...;;"'"'"'
Описание языка и комментарии к приведенному коду можно найти на странице Hanoi Love.
3. Brainfuck
Классика жанра эзотерического программирования — Brainfuck. Язык, в котором даже копирование или сложение не является элементарной операцией, вывод на печать
трехзначного числа достоин отдельной оды, а уж использование его для решения какой-то конкретной задачи — ну просто мечта мазохиста :-)
В авторском интерпретаторе (Muller's Brainfuck) содержимое ячеек памяти хранится в переменных типа byte, и числа Фибоначчи с 14-го по 16-ое вызвали бы переполнение памяти. Реализация длинной арифметики на Brainfuck — это уже не симптом, а практически диагноз, поэтому при написании решения предполагалось, что ячейка памяти может хранить числа до 1000 (во многих реализациях языка для хранения используются достаточно вместительные типы данных).
++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++
++++++++>++++++++++++++++>>+<<[>>>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>
+>>]<<<<<<]>[<+>-]>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-
]>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]<[++++++++++
++++++++++++++++++++++++++++++++++++++.[-]]<<<+++++++++++++++++++++++
+++++++++++++++++++++++++.[-]<<<<<<<.>.>>[>>+<<-]>[>+<<+>-]>[<+>-]<<<
-]<<++...
Описание языка и комментарии к приведенному коду можно найти на странице Brainfuck.
2. Brainloller
Cамый простой из графических диалектов Brainfuck, придуманный Lode Vandevenne.
Программы читаются с картинок PNG, команды записываются пикселями разных цветов, и к имеющимся в Brainfuck восьми командам добавляются еще две — управление указателем на текущий пиксель. Ко всем прелестям Brainfuck добавляется еще полная нечитабельность «кода» и полная невозможность
«кодировать» без вспомогательных средств (например, конвертера программ и картинок).
Авторский интерпретатор языка канул в лету, поэтому для генерации «программы» пришлось писать свой. «Программа» приведена в десятикратном увеличении.
1. Unary
Куда уж хуже? — подумает читатель, листая экран дрогнувшей рукой. Да, бывает еще хуже. В предыдущих языках программу можно было хотя бы объять взглядом, а это уже немало.
Встречайте победителя рейтинга — Unary. Диалект Brainfuck, придуманный тем же Lode Vandevenne (о, мсье знает толк в извращениях!), предполагает, что команды Brainfuck преобразуются в двоичные коды и конкатенируются в одно двоичное число, унарная запись которого и является программой на Unary. Программа генерации чисел Фибоначчи представляет собой строку из
167967665105731198557055496639385943332278803897935697536099438828197
665241403160165880863622431582784595268769268183940269756210147305655
704025762911607244068691728105306566342622386432823429136972542304655
647901781271798433263001837026612851345264031562174039657802748245705
398528237993320520942720239597540583536934220029626573406470088757427
393143000966310611249037587993216365993804186165097620168960460854977
571944373603975793034586829061577464233522714007498991416860375267535
193648636795096472789203729505034887001634966681420589637468649908257
407260923590831776308356684326657774592110098643361324426156431864437
942781495979555960608253552679248495326880775320385281559763269974848
026839024530519989287202261977272377723622502479809174132505837648641
033569945906182518892142219706483917757108086522763280388915772444727
238483811923456440363260610571471034139736312976255142288379411989404
9017738035 (то есть примерно 1.68*10^906) нулей.
Я уверена, что перечисленные здесь языки — далеко не самое страшное, с чем может столкнуться программист (во всяком случае, не все из них :-) ), но я не волшебник, я только учусь.