Hopeless - функциональное моделирование электронных схем

[Shaos]

Я некоторе время назад размышлял на тему того как можно на функциональном языке моделировать электронные схемы - имея лишь чистые функции без побочных эффектов. Предполагал использовать список для хранения состояний автоматов, однако всё оказалось проще, когда я наткнулся на статью Сергея Зефирова и Владислава Балина во втором номере электронного журнала Практика Функционального Программирования:

http://fprog.ru/2009/issue2/serguey-zef ... languages/

Они описали такой подход, когда входы и выходы описываются ленивыми списками, причём так, что симулятору не страшны обратные связи. В качестве примеров использовались программы на языке Haskell. А я решил попробовать и взял HOPE в лице Hopeless

[Shaos]

Вот реализация первого примера с сумматором на языке HOPE:

Code: Select all

dec zip_with : (alpha # alpha -> beta) # list alpha # list alpha -> list beta;
--- zip_with (f, nil, _) <= nil;
--- zip_with (f, _, nil) <= nil;
--- zip_with (f, a :: b, c :: d) <= f (a, c) :: zip_with (f, b, d);

dec sum : list num -> list num;
--- sum l <= s whererec s == 0 :: zip_with ((+), s, l);

Простой пример работы:

Code: Select all

sum([ 1, 2, 3, 0-1, 0-2, 5]);
>> [0, 1, 3, 6, 5, 3, 8] : list num

P.S. Отрицательные числа не воспринимаются парсером - буду смотреть почему...

[Shaos]

А вот полноценная программа для теста "вручную":

Code: Select all

#!/usr/local/bin/hopeless -f

uses lines,system;

dec str2numl : list (list char) -> list num;
--- str2numl nil <= nil;
--- str2numl (h :: t) <= str2num h :: str2numl t;

dec zip_with : (alpha # alpha -> beta) # list alpha # list alpha -> list beta;
--- zip_with (f, nil, _) <= nil;
--- zip_with (f, _, nil) <= nil;
--- zip_with (f, a :: b, c :: d) <= f (a, c) :: zip_with (f, b, d);

dec sum : list num -> list num;
--- sum l <= s whererec s == 0 :: zip_with ((+), s, l);

write sum(str2numl(lines(read(stdin))));

При запуске она берёт с клавиатуры числа и засылает их по одному в сумматор, который точно также по одному выдаёт ответ - всё на ленивых списках

[Shaos]

Со вторым примером (RS-триггер) посложнее - дословная реализация работает, как написано в статье:

Code: Select all

dec zip_with : (alpha # alpha -> beta) # list alpha # list alpha -> list beta;
--- zip_with (f, nil, _) <= nil;
--- zip_with (f, _, nil) <= nil;
--- zip_with (f, a :: b, c :: d) <= f (a, c) :: zip_with (f, b, d);

dec nor : list(bool) # list(bool) -> list(bool);
--- nor (a,b) <= false :: zip_with(\(x,y)=>not(x or y),a,b);

dec rs_trig : list(bool) # list(bool) -> list(bool) # list(bool);
--- rs_trig (r,s) <= ( q,q') whererec ( q,q') == ( nor( s,q'), nor( r,q ));

1) пример самовозбуждения:

Code: Select all

rs_trig([false, false, false, false],
        [false, false, false, false]);

>> ([false, true, false, true, false], [false, true, false, true, false]) : list bool # list bool

2) пример взвода:

Code: Select all

rs_trig([true,  false, false, false],
        [false, false, false, false]);

>> ([false, true, true, true, true], [false, false, false, false, false]) : list bool # list bool

3) пример сброса:

Code: Select all

rs_trig([false, false, false, false],
        [true,  false, false, false]);

>> ([false, false, false, false, false], [false, true, true, true, true]) : list bool # list bool

А вот последовательности посложнее уже не проходят (после переключения состояния схема самовозбуждается):

Code: Select all

rs_trig([true,  false, false, false, false, false, false, false],
        [false, false, false, false, true,  false, false, false]);

>> ([false, true, true, true, true, false, true, false, true], [false, false, false, false, false, false, true, false, true]) : list bool # list bool

Хотя если сделать "импульсы" длинее (два такта вместо одного), то становится похоже на правду:

Code: Select all

rs_trig([true,  true,  false, false, false, false, false, false, false, false],
        [false, false, false, false, false, true,  true,  false, false, false]);

>> ([false, true, true, true, true, true, false, false, false, false, false], [false, false, false, false, false, false, false, true, true, true, true]) : list bool # list bool

[Shaos]

Вот пример переписанный на новый тип данных, у которого кроме True и False ещё есть Z-состояние:

Code: Select all

#!/usr/local/bin/hopeless -f

dec map : list alpha # (alpha -> beta) -> list beta;
--- map (nil, f) <= nil;
--- map (h :: t, f) <= f(h) :: map(t, f);

dec reduce : list alpha # (alpha#beta -> beta) # beta -> beta;
--- reduce (nil, f, b) <= b;
--- reduce (h :: t, f, b) <= f(h,reduce(t,f,b));

dec zip_with : (alpha # alpha -> beta) # list alpha # list alpha -> list beta;
--- zip_with (f, nil, _) <= nil;
--- zip_with (f, _, nil) <= nil;
--- zip_with (f, a :: b, c :: d) <= f (a, c) :: zip_with (f, b, d);

data he2 == T ++ F ++ Z;

type he2seq == list(he2);

dec he2inv : he2 -> he2;
--- he2inv(T) <= F;
--- he2inv(F) <= T;
--- he2inv(Z) <= F;

dec he2or : he2 # he2 -> he2;
--- he2or(T,_) <= T;
--- he2or(_,T) <= T;
--- he2or(Z,_) <= T;
--- he2or(_,Z) <= T;
--- he2or(_,_) <= F;

dec he2and : he2 # he2 -> he2;
--- he2and(F,_) <= F;
--- he2and(_,F) <= F;
--- he2and(_,_) <= T;

dec inv : he2seq -> he2seq;
--- inv (a) <= F :: map(a,\(x)=>he2inv(x));

dec nor : he2seq # he2seq -> he2seq;
--- nor (a,b) <= F :: zip_with(\(x,y)=>he2inv(he2or(x,y)),a,b);

dec nand : he2seq # he2seq -> he2seq;
--- nand (a,b) <= F :: zip_with(\(x,y)=>he2inv(he2and(x,y)),a,b);

dec rs_trig : he2seq # he2seq -> he2seq # he2seq;
--- rs_trig (s,r) <= ( q,q') whererec ( q,q') == ( nor( r,q'), nor( s,q ) );

dec _rs_trig : he2seq # he2seq -> he2seq # he2seq;
--- _rs_trig (_s,_r) <= ( q,q') whererec ( q,q') == ( nand( _s,q'), nand( _r,q ) );

rs_trig(
  [T,T,F,F,F,F,F,F,F,F],
  [F,F,F,F,F,T,T,F,F,F]);

_rs_trig(
  [F,F,T,T,T,T,T,T,T,T],
  [T,T,T,T,T,F,F,T,T,T]);

вывод генерируемый этой программой:

Code: Select all

> ./hopemul2.hop
>> ([F, T, T, T, T, T, F, F, F, F, F], [F, F, F, F, F, F, F, T, T, T, T]) : he2seq # he2seq
>> ([F, T, T, T, T, T, T, F, F, F, F], [F, T, F, F, F, F, T, T, T, T, T]) : he2seq # he2seq

[Shaos]

Вообще в будущем можно сделать надстройку для моделирования дискретных событий (транзакций) с привязкой к шкале времени (по типу GPSS)

[Shaos]

Надо чтоли троичность попробовать помоделировать на HOPE...

Вот блин - больше 7 лет прошло с тех пор, а как вчера было

[Shaos]

Вообще в будущем можно сделать надстройку для моделирования дискретных событий (транзакций) с привязкой к шкале времени (по типу GPSS)

А вот это мысль здравая меня посетила в 2010 году - если времени хватит, то сделаю такое в TRCM v2.0 - оно должно СИЛЬНО ускорить симуляцию

P.S. С тех пор я упустил домен hopelog.com - его перехватили какие-то китайские жулики...