예, 문학이 존재, 나는, 나는 단순히 기억하지 않는을 인용 할 수없고 단지 ... 단지 당신이 할 수있는 의존성과 사이클 분석을위한
기본 algos을 구글 것이다 미안 정말 간단합니다. 나는. 다음
inps expr outs
cell_A6, cell_B7 -> expr3 -> cell_A7
cell_A1, cell_B4 -> expr1 -> cell_A5
cell_A1, cell_A5 -> expr2 -> cell_A6
와 비교 반복적으로 확대/입력/출력의 세트를 대체하여 : 형태의 표현과 종속의 집합을 구축, 표현의 심볼을 감지 마지막으로
step0:
cell_A6, cell_B7 -> expr3 -> cell_A7
cell_A1, cell_B4 -> expr1 -> cell_A5 <--1 note that cell_A5 ~ (A1,B4)
cell_A1, cell_A5 -> expr2 -> cell_A6 <--1 apply that knowledge here
so dependency
cell_A1, cell_A5 -> expr2 -> cell_A6
morphs into
cell_A1, cell_B4 -> expr2 -> cell_A6 <--2 note that cell_A6 ~ (A1,B4) and so on
을, 당신은 얻을 것이다 당신은 안전 증가를 확인할 수있을 것입니다 - 아무것도 발견되지 않을 경우,
cell_A1, cell_D6, cell_F7 -> exprN -> cell_D6
또는 : 쉽게 예를 들어 같은 순환 종속성을 감지 할 수있는 전체 종속의 집합 중 실행 명령.
'반환 값'이외의 분기 나 부작용이 표현에 포함되어있는 경우 다양한 변형을 적용하여 표현식을 새로운 표현식으로 축소/확장하거나 위 양식의 새 표현식 그룹으로 확장 할 수 있습니다. 예를 들어 :
B5 = { if(A5 + A3 > 0) A3-1 else A5+1 }
so
inps ... outs
A3, A5 -> theExpr -> B5
the condition can be 'lifted' and form two conditional rules:
A5 + A3 > 0 : A3 -> reducedexpr "A3-1" -> B5
A5 + A3 <= 0 : A5 -> reducedexpr "A5-1" -> B5
하지만 지금, 당신의 실행/분석은 규칙을 적용하기 전에 조건을주의해야합니다. 리프팅은 가능한 변형 중 하나 일뿐입니다.
그러나 그보다 더 많은 것을 필요로합니다. 적어도 그 중 일부는 '확장'입니다. 문제의 어려운 부분은 표현식이 복잡하고 분기가 있고 분기를 해결하기 위해 사용자 임의 입력을 포함 시켜서 죽은 분기를 제거하고 죽은 종속성을 중단해야한다는 것입니다.
키가 죽은 종속성을 제거하므로 죽은 분기를 어떻게 든 감지해야합니다. 조건은 임의의 복잡성이있을 수 있으며 사용자 입력은 무작위이므로 완전히 정적으로 작업 할 수는 없습니다. 변환으로 재생 한 후에도 조건을 분석하고 이에 따라 코드를 생성해야합니다. 이렇게하려면 조건의 결과와 모든 결과 분기 및 규칙 조합의 가능한 모든 조합에 대한 코드를 생성해야합니다.이 분기 및 규칙 조합은 사소한 경우를 제외하고는 단지 실행 불가능합니다. 미지의 수와 함께 잎의 수는 기하 급수적으로 증가 할 수 있습니다 (2^N). Bools에 따라 조건을 분석하는 것은, 당신이 분석 할 수 있습니다, 그룹 ..) (a & b & !a처럼
을 충돌하는 조건을 제거 ..하지만 동안 물론
사용자의 입력 값과 조건은 정수 또는 부동 같은 비 BOOL 데이터를 포함하는 경우 또는 문자열, 그냥 당신의 상태가 일부 이상한 통계 기능을 실행하고 그 결과를 확인하는 조건이 있다고 상상해보십시오.'이상한'부분을 무시하고 '외부'에 집중하십시오. AVG 또는 MAX와 같은 복잡한 기능을 사용하는 표현식을 만난다면 정적으로 (*)와 같은 것을 씹을 수 없습니다. 심지어 간단한 산술 분석하기 어렵다 : (a+b)*(c+d)을 - 당신이 A + B == 0,하지만 정말 힘든 작업이 완벽하게 커버하는 경우 c+d이 무시 될 수 있다는 사실을 도출 할 수 ..
IIRC하는 satisfiability 분석을하고 (SAT)는 기본 연산자를 사용하는 부울 표현식에 대해 NP 하드 문제입니다. 정수 또는 부동 소수점을 모든 수학과 함께 언급하지 않습니다. 표현의 결과 계산은 실제로 어떤 값이 의존하는지보다 훨씬 쉽습니다 !!
입력 값은 하드 코드 (cool) 또는 런타임시 사용자 제공 (doh!) 일 수 있으므로, 컴파일러는 입력 값을 완전히 분석 할 수 없을 가능성이 높습니다. 이제 (*)로 표시된 사실과 연결하면 정적 분석을 포함하고 컴파일 시간에 일부 분기를 제거 할 수 있지만 사용자가 제공 할 때까지 지연되어야하는 부분이있을 수 있습니다. 실제 입력.
분석의 일부를 런타임에 완료해야하는 경우 모든 분기 제거는 선택적인 최적화 일 뿐이므로 이제 런타임 부분에 집중해야한다고 생각합니다.
최소 최적화되지 않은 버전에서는 생성 된 프로그램이 모든 Excel 표현식을 기억하고 입력 데이터를 기다릴 수 있습니다. 일단 프로그램이 실행되고 입력이 주어지면, 프로그램은 표현식에서 입력을 대체 한 다음 출력값을 반복적으로 줄여야합니다.
이러한 명령을 명령형 언어로 작성하는 것은 완전히 가능합니다. 실제로, 당신은 그것을 한 번 쓰고 나중에 셀 수식에서 파생 된 다른 규칙 세트와 병합하면됩니다. 프로그램의 런타임 부분은 동일 할 것이고 수식은 바뀔 것입니다.
그런 다음 '컴파일러'쪽을 확장하여 종속성을 부분적으로 부분적으로 분석하고 나중에 "더 좋은 순서"로 체크인하거나 상수를 미리 계산하거나 인라인으로 규칙을 재정렬하려고 할 수 있습니다. 일부 표현식 등등하지만 내가 말했듯이, 그것은 핵심 기능이 아닌 모든 최적화입니다.
슬프게도 "기능적 언어"에 대해 진지한 것을 많이 말할 수는 없지만 일반적으로 런타임이 '매우 역동적이어서'기호와 변환의 측면에서 코드를 실행하기 때문에 복잡성을 줄일 수 있습니다. 귀하의 '컴파일러'와 '엔진'부분. 여기서 가장 가치있는 자산은 역 동성입니다. 그래서 루비조차도 C보다 훨씬 잘 할 것입니다 - 그러나 결코 당신이 말하는 것처럼 "컴파일 된"언어는 아닙니다.
예를 들어,이 기능에 직접 엑셀 규칙 변환을 시도 할 수 있습니다 :
def cell_A5 = expr1(cell_A1, cell_B4)
def cell_A7 = expr3(cell_A6, cell_B7)
def cell_A6 = expr2(cell_A1, cell_A5)
쓰기를 아래로 프로그램의 일환으로, 다음 사용자가 어떤 값을 제공 런타임에, 당신은 그는 것입니다 거라고 때 여기 아주 '기능'프로그램 동적 플랫폼의 힘을의
cell_B7 = 11.2 // filling up undefined variable
cell_A1 = 23 // filling up undefined variable
cell_A5 = 13 // overwriting the function with a value
, 아무것도의 일부 부품을 재정의. 동적 플랫폼을 사용하면 비트를 채우거나 재정의하는 것이 쉽습니다. 그러나 일단 사용자가 비트를 제공하고 프로그램이 "즉시 수정"되면 어떤 기능을 먼저 호출 할 것인가?
대답은 다소 슬프다. 당신은 모른다.
동적 언어에 규칙 엔진이 내장되어있는 경우 함수 대신 규칙을 생성하고 나중에 해당 엔진을 사용하여 계산할 수있는 모든 것을 "채울"수 있습니다.
하지만 규칙 엔진이없는 경우, 다시 점 하나입니다 ..
군더더기 :
흠 .. 미안 해요, 난 그냥 너무 너무 막연/수다스러운 썼다 생각합니다. 도움이된다고 생각한다면 제게 의견을 남겨주세요. 그렇지 않으면 며칠 또는 일주일 후에 삭제할 것입니다.
"나는 그것을 (클래스 컴파일러 최적화) 해제하여 조건부 전파"생각합니다. 모든 참고 문헌이 도움이 될 것입니다. 당신은 내가하려는 알고리즘을 정확히 설명하기 때문에 대답을 받아 들였습니다. – n00b101
이 "리프팅"은 실제로 프로그래밍 언어의 연산자를 사용하여 a * b + a * c ==> a * (b + c)라는 분배 법칙입니다. –