MShrimp4 commented 5 years ago

현재 BOJ에서는 Scheme 인터프리터로 SCM을 사용하고 있는데, 좋은 Scheme 인터프리터 / 컴파일러와 비교했을 때 성능 차이가 상당히 큽니다. SCM에서 실행했을 때 10초 정도 소요하는 코드가 MIT scheme 이나 Gambit Scheme, Chez Scheme에서는 1초도 소요하지 않는 코드란 점에서 지금 인터프리터는 꽤 느린 편입니다. 그래서 for문 단계에 속하는 빠른 A+B 문제도 푸는 것이 불가능합니다. 그리고 현재 인터프리터에서는 입력을 다 받지 않고 종료하면 에러가 나고, 이를 수동으로 처리할 기본 procedure도 현재 인터프리터 구현에서는 제가 아는 한 없습니다. 수치형에서는 Windows SCM 기준으로 2^30 범위를 넘어가는 정수가 float으로 자동변환되고, 큰 정수의 경우 SQRT (제곱근) 가 제대로 동작하지 않는데, 이럴 경우 큰 숫자를 이용하는 문제를 풀기 어려울 것이라고 생각됩니다. 다른 언어의 스트링 포매팅 기능을 하는 format procedure도 없어서 문제 7510 같은 출력을 하기에 너무나도 불편합니다. 마지막으로, SCM Scheme 은 Documentation이 제대로 되어 있지 않아 간단한 코드를 작성하기에도 힘듭니다.

이러한 이유로, 지금의 SCM 인터프리터 대신 다른 인터프리터를 사용하고 추가 시간을 줄였으면 합니다. 다만 인터프리터/컴파일러를 교체할 경우 구현된 함수가 달라 재채점 시 런타임 에러가 나는 소스가 있습니다. (R5RS 표준에 없는 함수를 사용한 경우)

Chez Scheme 제작년까지만 해도 상용 컴파일러였으나 오픈소스로 전향했습니다. 속도가 가장 빠릅니다. 실행 : chez-scheme --script ~~~.scm

Chicken Scheme Compiler

가장 활성적인 커뮤니티를 가진 스킴입니다. 먼저 Scheme 코드를 C 코드로 변환하고 GCC로 컴파일합니다. C 코드로 변환한 후 C 채점 방식을 그대로 적용하면 채점 시스템과의 호환성도 높을 것으로 보입니다.

C 코드 생성 : chicken ~~~.scm -optimize-level 3 -output-file ~~~.c

C 코드 생성 + 컴파일 : csc ~~~.scm

#참고 링크

Gambit Scheme Compiler 이것도 빠른 Scheme Compiler입니다. 먼저 C 코드로 변환하고 GCC로 컴파일합니다. 컴파일 : gsc -exe ~~~.scm (C 코드만 생성 : gsc ~~~.scm) 실행 : ./~~~

인터프리터도 있습니다. 실행 : gsi ~~~.scm

MIT/GNU Scheme 실행 : mit-scheme --quiet --load ~~~.scm

tpdns90321 commented 5 years ago

스킴 구현체 뭐 쓰는지 몰라서 r5rs 기준으로 짜는데 돌아가지 않네요.

Baekjoon commented 5 years ago

아마 당시에 글을 보고 이것 저것 해보다가 채점이 안되서 변경하지 않았던 것 같습니다.

다음 언어 추가 및 컴파일러 업데이트 때 시도해보겠습니다.

Baekjoon commented 5 years ago

Chez Scheme

연산 속도는 빠른데, 입/출력 속도가 매우 오래 걸리는 것 같습니다.

1048576 줄을 출력해야 하는 11729번 문제가 1192ms -> 40752ms 가 걸려서 시간 초고롸르 받았습니다.

Chicken Scheme Compiler

이 컴파일러로 변경했습니다

그런데, 빠른 A+B 소스를 실행해보니 Error: segmentation violation가 뜨는데 제가 Scheme을 할 줄 몰라서 원인은 나중에 찾아봐야 겠습니다.

Startlink / BOJ-Feature-Request

Scheme 인터프리터를 교체했으면 합니다. #160

Chez Scheme

Chicken Scheme Compiler