Topics

Simple REPL Implementation

Scott Rostrup
 

Hey Patrick,

was just messing around with getting a basic repl for a toy language using S-expressions going and was hoping you could suggest improvements.  I just kind of did things until it worked but this seems like something you've probably done already and I'd imagine there are better ways to do it in stanza.  I would love to hear about them :)


defpackage repl :
    import core
    import reader


defn eval (s-exp) :
    println("s-exp = %_" % [s-exp])
    val tag = s-exp[0]
    println("tag = %_" % [tag])

    if to-symbol(tag) == to-symbol('+'):
        println("%_ + %_ = %_" % [s-exp[1], s-exp[2], s-exp[1] + s-exp[2]])
    else:
        println("Not +")

println("Hello there!  Welcome to the repl!")

val stdin = STANDARD-INPUT-STREAM

; This input mechanism isn't quite right, should be read until S-exp is complete
; instead of waiting for newline
defn read-char () -> Maybe<Char> :
    ; You get False when you hit Ctrl-D, will give an exception
    val c = get-char(stdin) as Char
    One(c) when c != '\n' else None()
   

while true:
    print("(\\\")> ")
    val s:String = String(repeat-while(read-char))
    try:
        val tokens = read-all(s)
        eval(unwrap-all(tokens[0]))
    catch (e) :
        println("Not S exp. e = %_" % [e])

Thanks,

Scott

 

Hi Scott.

Your implementation is along the same lines as what I would write if I were writing a fresh s-expression parser and I wanted complete control over the syntax.

The only line that stands out as suspicious is the

to-symbol(tag) == to-symbol('+'):

line. If you assume that your s-expression has been parsed into symbols already, then the line should probably just read

tag == `+

. If you didn't need absolute control over the syntax, and was willing to accept Stanza's s-expression syntax (e.g. indentation structuring, literals, escaped characters, etc.) then the reader package does contain a function called read-line which will read in an s-expression for you. You can call it like this:

val form = unwrap-all(read-line(STANDARD-INPUT-STREAM))

. If you want to keep the line information around, then you can remove the call to unwrap-all.

val form = read-line(STANDARD-INPUT-STREAM)

Cheers.

-Patrick

Scott Rostrup
 

Thanks Patrick, I don't need complete control over the syntax actually, I would be happy to reuse stanza's and take any shortcuts I can.  The read-line sounds like was going for with the unwrap, thanks for the suggestion.

follow up question, is there a way to print type information manually for debugging/comprehension purposes?  Like a typeof function or something?

~Scott

 

Hi Scott.

Hmm there is an internal object-type function in core.stanza that returns a String that describes the type of an object. I don't have it exposed publicly however. I'll make a note to make the function public in the next version.

For now, you can copy and paste it into your own code, for quick and dirty debugging purposes. (Don't fret about how it works though. It's essentially black magic.)

lostanza deftype ObjectMap :
   name: ptr<byte>
   base-size: int
   tail-size: int
   bits: long ...

lostanza defn object-map (tag:long) -> ptr<ObjectMap> :
   val table = call-prim object-table() as ptr<ptr<ObjectMap>>
   return table[tag]

lostanza defn object-type (x:ref<?>) -> ref<String> :
  match(x) :
    ;Primitive Tags
    (x:ref<Byte>) : return String("Byte")
    (x:ref<Int>) : return String("Int")
    (x:ref<Char>) : return String("Char")
    (x:ref<Float>) : return String("Float")
    (x:ref<?>) :
      val tagbits = (x as long) & 0x7L
      ;Retrieve tag
      var tag:long
      if tagbits == 2L :
        tag = (x as long) >> 3L
      else :
        tag = [x as ptr<long> - tagbits]
      ;Retrieve name in object table
      return String(object-map(tag).name)

Scott Rostrup
 

Thanks! That was exactly the kind of thing I was looking for.

For context, myself and some friends are implementing our own microkanren's this week (http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf) and I thought it was a good opportunity to use stanza.

Cheers,
Scott

 

Thanks for the great reference. I've been interested in Kanren since I went through The Reasoned Schemer. It's great that they've condensed the implementation down so far.

Scott Rostrup
 

Yes it's pretty remarkable, but you still need scheme :)

So basically a super basic scheme interpreter is where I have gotten with my implementation.  I decided the fastest course of action was to build a scheme interpreter and then just run the scheme version in it, then migrate things over once I understand them better.

I'm still a stanza beginner so I've found that I get tripped up on basic things sometimes.  I thought it might be useful for you if I try to document them:
  - I got confused about variable number of arguments to a function, there is only an anonymous multiarg function in the docs
  - I got confused about manipulating lists for function args, I think I'm just used to dedicated syntax like in racket with pattern matching or in python with *args or kwargs and my brain basically didn't move to using direct calls to head or tail on lists for just a little bit too long.
  - I got confused about how to deal with functions that return `T|False`, once I hit on match being the counterpoint to them it helped me a lot.  The union types are prevalent in how the data structures return things, but how to deal with the union types isn't discussed a lot in the docs.
  - Can I do type aliases?  I ended up repeating long union types in a few places in the code because I couldn't figure out how to do type aliases.  I tried a few variations on subtypes to do the trick but never quite hit on how to do it.

I really like the way the type system in Stanza interacts with the development process.  My experience was that I got something running without any type annotations and then as I started fleshing out the functionality the type system identified useful bugs and pushed me down the path of being more precise about what exactly things are in my program.  I think that is exactly your intent and I think it really works and it is very cool :)

~Scott

 

Hi Scott.

Thank you very much for taking the time to document your learning process. It's very helpful for us!

You have a very good point about the union types. It's not a common language feature and it is used so prevalently in Stanza that it should be explained in more detail.

Type aliases are on the very top of our implementation priority list for the next version. So hold tight! I also feel your pain when the type annotations themselves start to get too long. This will be fixed before long.

And I'm glad that you found the optional type system helpful for making your development process more incremental. That is exactly what we were hoping for and we're glad that it worked out!

-Patrick

Scott Rostrup
 

Just an update been plugging away at this a bit more, it seems to have turned into an sicp style meta circular interpreter implementation, https://github.com/sarostru/doggerel/blob/master/skanren/scheme.stanza .  It's passed the size of being able to just kind of hack on so I'm starting to go through and add tests to solidify the functionality.  

I wanted to add quoting but wasn't sure of the best way to do it, is there a way I could inherit stanza's quoting?  I'm using the reader package already to get the s expressions.

~Scott

 

Looks pretty cool. The meta circular interpreter is certainly a work of art.

You can inherit Stanza's quoting by just looking for the automatically-inserted @quote symbol, which I see that you're already doing.

So, if the user types something like this:

(define x `(a b c))

The lexer returns the s-expression:

(define x (@quote (a b c)))

Thus the quoted s-expression is always the second element in the list that starts with @quote. If your Kanren implementation directly uses Stanza values to represent its internal values (which it seems like it does), then you can just use this second element directly. Otherwise you have to write your own function to convert Stanza values into your internal values.

-Patrick

Scott Rostrup
 

Thanks Patrick,

 

So it seems like I'm doing ok for the quoting, but what about doing quasi quoting?  e.g. something like this:

 

```

`(1 ,(+ 1 1) 3)

```

 

Another thing I was wondering about, how to define a struct such that equality on it only returns whether the objects reference the same object without inspecting any of the fields?

In the reference it says:

> values of immutable types are defined to be equal if their subfields are equal. Different mutable values, such as arrays, are never defined to be equal unless they refer to the same object.

How can I define my own struct such that it is treated like the mutable values?

Cheers,
Scott

 

Hi Scott.

For quasiquoting, you need to do two things:

  • Choose appropriate symbols for representing unquote and unquote-splice.
  • Write a quasiquote evaluator that interprets the quoted value.

For the first step, you have to choose something other than comma as Stanza's reader treats commas as whitespace. Stanza uses ~ and ~@ like Clojure, but you can use anything.

For the second step, you should write a function that looks something like this:

defn eval-qq (value) :
  match(value) :
    (v:List) :
      if not empty?(v) :
        switch(head(v)) :
          `~ : cons(eval(v[1]), eval-qq(tailn(v,2)))
          `~@ : append(eval(v[1]), eval-qq(tailn(v,2)))
          else : map(eval-qq, v)
      else : v
    (v) : v

For defining a struct that has a fast equality check, you have to give an integer ID field to the struct. For example:

defstruct MyCar <: Equalable :
  id: Int
  name: String
  color: String
with :
  constructor => make-MyCar

defn MyCar (name:String, color:String) :
  make-MyCar(genid(), name, color)

defmethod equal? (a:MyCar, b:MyCar) :
  id(a) == id(b)

The above assumes that genid returns a unique integer, and thus cars can be compared simply by comparing their id. It's designed this way (instead of providing a identity-comparison operator) to allow the Stanza optimizer to inline MyCar objects for speed.

Cheers.

-Patrick

Scott Rostrup
 

I really appreciate your detailed answers Patrick, this is super helpful, thanks!

 

No problem at all Scott. Hope you're enjoying your time with Stanza!

Previous Topic Next Topic