nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 16 Aug 2018 00:06



Reply to topic  [ 7 posts ] 
Hopeless - функциональное моделирование электронных схем 
Author Message
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Я некоторе время назад размышлял на тему того как можно на функциональном языке моделировать электронные схемы - имея лишь чистые функции без побочных эффектов. Предполагал использовать список для хранения состояний автоматов, однако всё оказалось проще, когда я наткнулся на статью Сергея Зефирова и Владислава Балина во втором номере электронного журнала Практика Функционального Программирования:

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

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

_________________
:eugeek: https://twitter.com/Shaos1973


29 Apr 2010 17:59
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Post 
Вот реализация первого примера с сумматором на языке HOPE:
Code:
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:
sum([ 1, 2, 3, 0-1, 0-2, 5]);
>> [0, 1, 3, 6, 5, 3, 8] : list num


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

_________________
:eugeek: https://twitter.com/Shaos1973


Last edited by Shaos on 29 Apr 2010 20:16, edited 2 times in total.



29 Apr 2010 19:52
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Post 
А вот полноценная программа для теста "вручную":
Code:
#!/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))));


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

_________________
:eugeek: https://twitter.com/Shaos1973


29 Apr 2010 20:07
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Post 
Со вторым примером (RS-триггер) посложнее - дословная реализация работает, как написано в статье:
Code:
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:
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:
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:
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:
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:
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

_________________
:eugeek: https://twitter.com/Shaos1973


29 Apr 2010 21:22
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Post 
Вот пример переписанный на новый тип данных, у которого кроме True и False ещё есть Z-состояние:
Code:
#!/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:
> ./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

_________________
:eugeek: https://twitter.com/Shaos1973


02 May 2010 15:43
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Post 
Вообще в будущем можно сделать надстройку для моделирования дискретных событий (транзакций) с привязкой к шкале времени (по типу GPSS)

_________________
:eugeek: https://twitter.com/Shaos1973


03 May 2010 18:29
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 16829
Location: Colorado
Reply with quote
Надо чтоли троичность попробовать помоделировать на HOPE...

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

_________________
:eugeek: https://twitter.com/Shaos1973


29 Nov 2017 05:14
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 7 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.