Haskell에서 Haskell 인터프리터 작성

Haskell에서 Haskell 인터프리터 작성

---

고전적인 프로그래밍 연습은 Lisp / Scheme에서 Lisp / Scheme 인터프리터를 작성하는 것입니다. 전체 언어의 힘을 활용하여 언어의 하위 집합에 대한 인터프리터를 생성 할 수 있습니다.

Haskell에 대한 유사한 운동이 있습니까? Haskell을 엔진으로 사용하여 Haskell의 하위 집합을 구현하고 싶습니다. 물론 할 수 있지만 볼 수있는 온라인 리소스가 있습니까?

---

여기 뒷이야기가 있습니다.

저는 제가 가르치는 이산 구조 과정 의 개념 중 일부를 탐구하기 위해 Haskell을 언어로 사용하는 아이디어를 탐구하고 있습니다 . 이번 학기 동안 저는 Haskell에 영감을 준 작은 언어 인 Miranda에 정착했습니다 . Miranda는 내가 원하는 작업의 약 90 %를 수행하지만 Haskell은 약 2000 %를 수행합니다. :)

그래서 내 생각은 내가 원하고 다른 모든 것을 허용하지 않는 Haskell의 기능을 정확히 가진 언어를 만드는 것입니다. 학생들이 발전함에 따라 기본 사항을 익히면 다양한 기능을 선택적으로 "켜기"수 있습니다.

Java 및 Scheme 을 가르치는 데 교육 학적 "언어 수준"이 성공적으로 사용되었습니다 . 그들이 할 수있는 일을 제한함으로써, 그들이 가르치고 자하는 구문과 개념을 마스터하는 동안 그들이 발에 총을 쏘는 것을 막을 수 있습니다. 또한 더 나은 오류 메시지를 제공 할 수 있습니다.

---

나는 당신의 목표를 사랑하지만 그것은 큰 일입니다. 몇 가지 힌트 :

• 나는 GHC에서 일했고 당신은 소스의 어떤 부분도 원하지 않습니다. Hugs 는 훨씬 더 간단하고 깔끔한 구현이지만 불행히도 C에 있습니다.

• 그것은 퍼즐의 작은 조각이지만 Mark Jones는 Haskell에서 Typing Haskell 이라는 아름다운 논문을 썼습니다. 이것은 당신의 프론트 엔드를위한 훌륭한 출발점이 될 것입니다.

행운을 빕니다! 교실에서 얻은 증거와 함께 Haskell의 언어 수준을 식별하는 것은 커뮤니티에 큰 도움이 될 것이며 확실히 게시 가능한 결과입니다!

---

완전한 Haskell 파서가 있습니다 : http://hackage.haskell.org/package/haskell-src-exts

파싱을 마치면 특정 항목을 제거하거나 허용하지 않는 것은 쉽습니다. 나는 tryhaskell.org에서 import 문을 허용하지 않고 최상위 정의를 지원하는 등의 작업을 수행했습니다.

모듈을 구문 분석하십시오.

parseModule :: String -> ParseResult Module

그런 다음 모듈에 대한 AST가 있습니다.

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

Decl 유형은 광범위합니다 : http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

여러분이해야 할 일은 선언, 임포트, 심볼, 구문을 사용할 수있는 화이트리스트를 정의한 다음 AST를 살펴보고 아직 알기를 원하지 않는 항목에 대해 "파싱 오류"를 발생시키는 것입니다. AST의 모든 노드에 연결된 SrcLoc 값을 사용할 수 있습니다.

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

Haskell을 다시 구현할 필요가 없습니다. 보다 친숙한 컴파일 오류를 제공하려면 코드를 구문 분석하고 필터링 한 다음 컴파일러로 전송하고 컴파일러 출력을 구문 분석하면됩니다. "추론 된 유형에 대해 예상 유형 a와 일치 할 수 없음 a -> b"이면 함수에 대한 인수가 너무 적다는 것을 알 수 있습니다.

실제로 Haskell을 처음부터 구현하거나 Hugs의 내부 또는 멍청한 구현을 엉망으로 만드는 데 시간을 소비하고 싶지 않다면 GHC에 전달되는 내용을 필터링해야한다고 생각합니다. 이렇게하면 학생들이 코드 기반을 가져 와서 다음 단계로 이동하여 완전한 Haskell 코드를 작성하려는 경우 전환이 투명합니다.

---

통역사를 처음부터 만들고 싶습니까? 람다 미적분 또는 lisp 변형과 같은 더 쉬운 기능적 언어를 구현하는 것으로 시작하십시오. 후자의 경우 구문 분석 및 해석 기술에 대한 멋지고 실용적인 소개를 제공하는 Write yourself a Scheme 이라는 아주 멋진 위키 북이 있습니다.

Haskell을 손으로 해석하는 것은 타입 클래스, 매우 강력한 타입 시스템 (타입 추론!), 지연 평가 (감소 기술)와 같은 매우 복잡한 기능을 다루어야하기 때문에 훨씬 더 복잡 할 것입니다.

따라서 작업 할 Haskell의 아주 작은 하위 집합을 정의한 다음 Scheme-example을 단계적으로 확장하여 시작할 수 있습니다.

덧셈:

Haskell에서는 파서, 컴파일러 및 물론 인터프리터를 포함한 인터프리터 API (적어도 GHC에서)에 대한 전체 액세스 권한이 있습니다.

사용할 패키지는 hint (Language.Haskell. *) 입니다. 나는 불행히도 이것에 대한 온라인 튜토리얼을 찾지 못했고 혼자서 시도하지 않았지만 꽤 유망 해 보입니다.

---

create a language that has exactly the features of Haskell that I'd like and disallows everything else. As the students progress, I can selectively "turn on" various features once they've mastered the basics.

I suggest a simpler (as in less work involved) solution to this problem. Instead of creating a Haskell implementation where you can turn features off, wrap a Haskell compiler with a program that first checks that the code doesn't use any feature you disallow, and then uses the ready-made compiler to compile it.

That would be similar to HLint (and also kind of its opposite):

HLint (formerly Dr. Haskell) reads Haskell programs and suggests changes that hopefully make them easier to read. HLint also makes it easy to disable unwanted suggestions, and to add your own custom suggestions.

• Implement your own HLint "suggestions" to not use the features you don't allow
• Disable all the standard HLint suggestions.
• Make your wrapper run your modified HLint as a first step
• Treat HLint suggestions as errors. That is, if HLint "complained" then the program doesn't proceed to compilation stage

---

Baskell is a teaching implementation, http://hackage.haskell.org/package/baskell

You might start by picking just, say, the type system to implement. That's about as complicated as an interpreter for Scheme, http://hackage.haskell.org/package/thih

---

The EHC series of compilers is probably the best bet: it's actively developed and seems to be exactly what you want - a series of small lambda calculi compilers/interpreters culminating in Haskell '98.

But you could also look at the various languages developed in Pierce's Types and Programming Languages, or the Helium interpreter (a crippled Haskell intended for students http://en.wikipedia.org/wiki/Helium_(Haskell)).

---

If you're looking for a subset of Haskell that's easy to implement, you can do away with type classes and type checking. Without type classes, you don't need type inference to evaluate Haskell code.

I wrote a self-compiling Haskell subset compiler for a Code Golf challenge. It takes Haskell subset code on input and produces C code on output. I'm sorry there isn't a more readable version available; I lifted nested definitions by hand in the process of making it self-compiling.

For a student interested in implementing an interpreter for a subset of Haskell, I would recommend starting with the following features:

• Lazy evaluation. If the interpreter is in Haskell, you might not have to do anything for this.

• Function definitions with pattern-matched arguments and guards. Only worry about variable, cons, nil, and _ patterns.

• Simple expression syntax:

  • Integer literals

  • Character literals

  • [] (nil)

  • Function application (left associative)

  • Infix : (cons, right associative)

  • Parenthesis

  • Variable names

  • Function names

More concretely, write an interpreter that can run this:

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

Type checking is a crucial feature of Haskell. However, going from nothing to a type-checking Haskell compiler is very difficult. If you start by writing an interpreter for the above, adding type checking to it should be less daunting.

---

You might look at Happy (a yacc-like parser in Haskell) which has a Haskell parser.

---

This might be a good idea - make a tiny version of NetLogo in Haskell. Here is the tiny interpreter.

---

see if helium would make a better base to build upon than standard haskell.

---

Uhc/Ehc is a series of compilers enabling/disabling various Haskell features. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

---

I've been told that Idris has a fairly compact parser, not sure if it's really suitable for alteration, but it's written in Haskell.

---

Andrej Bauer's Programming Language Zoo has a small implementation of a purely functional programming language somewhat cheekily named "minihaskell". It is about 700 lines of OCaml, so very easy to digest.

The site also contains toy versions of ML-style, Prolog-style and OO programming languages.

---

Don't you think it would be easier to take the GHC sources and strip out what you don't want, than it would be to write your own Haskell interpreter from scratch? Generally speaking, there should be a lot less effort involved in removing features as opposed to creating/adding features.

GHC is written in Haskell anyway, so technically that stays with your question of a Haskell interpreter written in Haskell.

It probably wouldn't be too hard to make the whole thing statically linked and then only distribute your customized GHCi, so that the students can't load other Haskell source modules. As to how much work it would take to prevent them from loading other Haskell object files, I have no idea. You might want to disable FFI too, if you have a bunch of cheaters in your classes :)

---

The reason why there are so many LISP interpreters is that LISP is basically a predecessor of JSON: a simple format to encode data. This makes the frontend part quite easy to handle. Compared to that, Haskell, especially with Language Extensions, is not the easiest language to parse. These are some syntactical constructs that sound tricky to get right:

• operators with configurable precedence, associativity, and fixity,
• nested comments
• layout rule
• pattern syntax
• do- blocks and desugaring to monadic code

Each of these, except maybe the operators, could be tackled by students after their Compiler Construction Course, but it would take the focus away from how Haskell actually works. In addition to that, you might not want to implement all syntactical constructs of Haskell directly, but instead implement passes to get rid of them. Which brings us to the literal core of the issue, pun fully intended.

My suggestion is to implement typechecking and an interpreter for Core instead of full Haskell. Both of these tasks are quite intricate by themselves already. This language, while still a strongly typed functional language, is way less complicated to deal with in terms of optimization and code generation. However, it is still independent from the underlying machine. Therefore, GHC uses it as an intermediary language and translates most syntaxical constructs of Haskell into it.

Additionally, you should not shy away from using GHC's (or another compiler's) frontend. I'd not consider that as cheating since custom LISPs use the host LISP system's parser (at least during bootstrapping). Cleaning up Core snippets and presenting them to students, along with the original code, should allow you to give an overview of what the frontend does, and why it is preferable to not reimplement it.

Here are a few links to the documentation of Core as used in GHC:

• System FC: equality constraints and coercions
• GHC/As a library
• The Core type

참고URL : https://stackoverflow.com/questions/1445827/write-a-haskell-interpreter-in-haskell