F # - 시퀀스 변환을 적용 할 때 컨텍스트 변경 가능

Question

게시물의 이상한 제목에 사과드립니다. 설명하는 가장 좋은 방법은 무엇인지 모르겠습니다.

일반적인 문제 :

또한,리스트의 각 항목을 제외하고, Seq.map (또는 유사한 기능)의 순차적 인 응용 프로그램을 수행합니다 "상황"에 전달합니다. 각 반복은이 "컨텍스트"를 수정할 수 있으며 업데이트 된 버전은 목록의 다음 항목으로 전달되어야합니다.

특정 문제 :

나는 F #에서 컴파일러를 만들고 있습니다. 내가 현재하고있는 단계는 스택 기반 IL을 레지스터 기반 IL로 변환하는 것이다. 나는 스택 기반 일리노이를 "걸으며"현재의 "평가 스택"(.NET의 평가 스택과 유사)을 수행 할 수 있다고 생각했다. 각 스택 IL opcode는 분명히 스택을 변경합니다 (예 : "add"opcode가 스택에서 두 항목을 팝하고 결과를 푸시). 이 업데이트 된 스택은 다음 opcode의 방출주기로 전달됩니다.

나는 C# 배경에서 오는 기능 프로그래밍 (나는 1 주일 전에 배웠다)에 매우 익숙하다는 것에 주목한다. 나의 주요 질문은 "이것을하기위한 '기능적인'방법은 무엇인가?"

여기에 '기능적'접근 방식 (psudocode)이 무엇인지에 대한 가장 좋은 추측이 있습니다. 나는 "transformStackToRegisterIL"의 튜플 반환 값을 싫어한다. 불변 값의 표준을 유지하고 싶다면 필요합니까? 또한 과도하게 긴 일리노이 블록에 스택 오버플로가 생길까 걱정됩니다. 이것이 내 관심사입니까?

let rec translate evalStack inputIl = 
    match inputIl with 
     | singleOpcode :: tail -> 
      let (transformed, newEvalStack) = transformStackToRegisterIL evalStack singleOpcode 
      transformed :: translate newEvalStack tail 
     | [] -> [] 

편집 : List.scan은 내가 원하는 것의 내장 기능입니까? (비슷하지만 정확하지는 않지만 ... 올바른 것일 수도 있습니다.)

Answer 1

나는이 질문에 약간의 동기를 부여하는 아주 기본적인 예제를 사용하여 설명하려고 노력할 것입니다 (그러나 현실적인 것은 구현하지 않습니다).

자, 우리는 스택에 명명 된 변수를 밀어 스택에 마지막 두 항목을 추가 Add IL 명령 Push이 (간단하게의가 그냥 콘솔에 결과를 출력 말할 수 있도록)가 있다고 가정하자 . 타겟 Nop 두 변수 이름을 얻어 Add와 레지스트리 언어,이를 추가 (콘솔에 결과를 출력)

type IL = 
    | Push of string 
    | Add 

type Reg = 
    | Add of string * string 
    | Nop 

let input = [ IL.Push "a"; IL.Push "a"; IL.Push "b"; IL.Add; IL.Push "c"; IL.Add ] 

입력이 Reg.Add("b", "a") 및 Reg.Add("c", "a") 일부 NOPS로 변환한다. 변환 함수는 현재 스택 및 단일 명령어를 취

let transform stack = function 
    | IL.Push var -> Reg.Nop, var::stack 
    | IL.Add -> Add(stack.Head, stack.Tail.Head), stack.Tail.Tail 

, 우리는 현재의 "상태"를 유지 List.fold을 사용하여 전체리스트를 변환. 현재 상태와 단일 입력 명령어로 제공된 함수를 호출하고 제공된 함수는 새로운 상태를 반환해야합니다.

let endStack, regsReversed = 
    input |> Seq.fold (fun (stack, regs) il -> 
     // Transform current IL instruction, given current 'stack' 
     let reg, newStack = transform stack il 
     // Add new registry instruction to 'regs' and return new stack 
     (newStack, reg::regs)) ([], []) 

같은 재귀를 사용하여 수행 할 수 있습니다 : 여기에서 "상태"스택뿐만 아니라, 우리가 생산하는 레지스터 기계 명령어의 목록입니다. 우리가 매개 변수로 상태를 유지하고 재귀 호출하여 변경하는 것을 제외하고 구조가 매우 유사합니다

let rec compile (stack, regs) = function 
    | [] -> (stack, regs) 
    | il::ils -> 
     // Transform current IL instruction, given current 'stack' 
     let reg, newStack = transform stack il 
     // Add new registry instruction to 'regs' and return new stack 
     compile (newStack, reg::regs) ils 

let endStack, regs = compile ([], []) input 

이제 우리는 (주 스택 끝에 비어있는 것을 확인하고 레지스트리 기계 명령어를 인쇄 할 수 있습니다 우리는 전면을 추가, 그래서 우리는) ​​그 결과를 반전 할 필요가 : 잭이 언급 한

if endStack <> [] then printfn "Stack is not empty!" 
regs |> List.rev 

으로 - 당신은 또한이 같은 계산 식 (상태)을 처리하는 더 진보 된 방법을 사용할 수 있습니다. 심각한 컴파일러를 작성하는 것이 실제로 사용하는 것이 바람직하다고 생각하지만 F #을 배우면 접기와 재귀 같은 기본 개념으로 시작하는 것이 더 쉽습니다. 주위에 "상황"을 전달하고 돌연변이

Answer 2

List.reduce 또는 사용자 정의 computation expression으로 할 수 있습니다 (async 작동 방법과 유사). 자주 재사용하지 않거나 다른 이유로 인해 List.reduce을 수정하지 않았다면 아마 List.reduce을 사용할 것입니다.

Answer 3

은 - 당신은 state 워크 플로우에 대해 얘기하고; 거기에, 국가가 당신의 평가 스택이 될 것입니다. 당신이 state 워크 플로우를 사용합니까 (내가 당신이 할 것을 권 해드립니다) 경우

, 당신은 ExtCore에서 State.List.map 기능을 사용할 수 있습니다 - 그것은 또 다른 하나 개의 목록을 매핑, 하나 개의 요소에서 컨텍스트 값을 전달 다음에 처리하는 동안 그 목록.

긴 IL 블록 (즉, 큰 방법 기관)와 스택 오버 플로우에 대해 걱정하지 마십시오 - 스택 오버 플로우는 정말 단지 우려 당신이 정말로 깊은 호출 스택을 일단.