nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 09:20



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

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

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

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

_________________
:dj: https://mastodon.social/@Shaos


29 Apr 2010 16:59
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
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. Отрицательные числа не воспринимаются парсером - буду смотреть почему...

_________________
:dj: https://mastodon.social/@Shaos


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



29 Apr 2010 18:52
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
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))));


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

_________________
:dj: https://mastodon.social/@Shaos


29 Apr 2010 19:07
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
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

_________________
:dj: https://mastodon.social/@Shaos


29 Apr 2010 20:22
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
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

_________________
:dj: https://mastodon.social/@Shaos


02 May 2010 14:43
Profile WWW
Admin
User avatar

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

_________________
:dj: https://mastodon.social/@Shaos


03 May 2010 17:29
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Надо чтоли троичность попробовать помоделировать на HOPE...

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

_________________
:dj: https://mastodon.social/@Shaos


29 Nov 2017 04:14
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post Re:
Shaos wrote:
Вообще в будущем можно сделать надстройку для моделирования дискретных событий (транзакций) с привязкой к шкале времени (по типу GPSS)

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

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

_________________
:dj: https://mastodon.social/@Shaos


22 Aug 2018 17:44
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 8 posts ] 

Who is online

Users browsing this forum: No registered users and 22 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.