Module 3: Parsing and Unparsing: Assembly Language and Virtual Object Code

elmiinated unparse1 from interface. Explain the plan! Note that LOADFUNC needs a terminator in the concrete syntax. EOF , end , $ , anything that won’t ever be mistaken for an instruction.

start with optional , not many (at this stage, the recursion is too much)

other combinator: bracketed?

outcome 4, “use your unparser as evidence” not strong enough. We need to ask for line numbers.

(This module is also available in PDF, in two-column and one-column formats.)

This week you’ll design your assembly language and implement an unparser for it. And you’ll start learning about parsing combinators and about the Universal Forward Translator. The parsing stuff is a lot to swallow, but you’ll have two weeks to assimilate it; your full parser isn’t due until module 4.

The theme for the week is designing concrete syntax that promotes readability.

• What am I doing?
  • Learn the representation of assembly code that is used inside the Universal Forward Translator (it’s a superset of virtual object code).
  • Design your own concrete syntax for the assembly language.
  • Unparse internal representations into your concrete syntax.
  • Start learning to program with monads: an error monad and a parsing monad.
  • You’ll tighten your grip on our layered design strategy for language implementation: assembly language is one more language layer. It adds just two new features: readable concrete syntax plus the ability to use labels.
  • You’ll prepare your system to be easy to debug: the concrete syntax you choose will be what you read as you enhance and debug your translator in modules 5 through 10. By designing a syntax that you find easy to read, you will help your future self.
  • You’ll deepen your parsing skills by generalizing them to the higher-order, monadic setting. Unless you someday find yourself in a situation where you must squeeze the last drop of performance out of a parser, monadic functions for parsing will be all you will ever need. They are powerful and fun to use. After the course, you will be able to use them for any task that involves textual data, not just programming languages. And you won’t be dependent on somebody else’s parsing library—you’ll have enough experience that you can create your own library of parsing combinators. All you need is λ!.
  • Throughout your translator, a transformation that might fail will return a result in the error monad. That means that unlike with exceptions or assertions, the possibility of failure is explicit in the type. Programming with the error monad will raise your functional-programming game.
  • You’ll spend substantial time studying concepts of error management and combinator parsing. You’ll also learn a number of representations and interfaces inside the UFT. You’ll write a little bit of code, not a lot.
  • Before lab, you’ll be introduced to interfaces for two monads: an error monad and a parsing monad. Because they are both monads, these interfaces have important functions in common. For the error monad, you’ll have a short handout; for the parsing monad, you’ll have a short video and a longer handout.
  • To prepare for lab, you’ll come up with algebraic laws for the “baby error monad.” You’ll also develop a grammar for a fragment of your assembly language. At this stage your grammar needn’t be complete; if it can express a few instructions during lab, that will be enough.
  • In lab, you’ll use either code or algebraic laws to implement a couple of functions in the parsing monad. Then you’ll use the parsing monad to write a parser for one form of the concrete syntax of your assembly language. That will be all the parsing you need to do this week.
  • After lab, you’ll write an unparsing function that renders your complete SVM instruction set exactly the way you wish it to appear in your concrete syntax. You’ll extend my “escape-hatch” parser for assembly code so that it recognizes the one form you did in lab. And you’ll learn how to command the Universal Forward Translator to parse assembly code and to translate it to virtual object code.

  The module step by step

  Before lab

  1. Review ML. Review your knowledge of Standard ML. Or if you are preparing to write the UFT in Haskell or in some other functional language, review that. Especially review pattern matching, Curried function application, lists, and the option type with its SOME and NONE constructors.
  2. Learn about error monads. Read about the baby error monad and complete the algebraic laws. We’ll look at your laws before other lab work. If you want to maximize your lab time, DM your laws to me before lab starts (by 1:00, please).
  3. Start your syntax design. Design concrete syntax for a fragment of your assembly language. Following the design guidelines, write a grammar that can express at least these three instructions:
     • Add two registers and put the sum in a third
     • Load a literal value in a register
     • Print a register
  4. Learn what parsing combinators can do for us. To learn what problems parsing combinators solve for us, you have your choice of two videos. Each will give you a different perspective. Watching both would be reasonable, but a single one suffices.
     • Watch a my short demonstration video made for you.
     • Watch a lightning introduction made for a professional audience.

  The professional video, which starts at 28:14, needs a little explanation:

  • Although higher-order functions have been used for parsing for almost thirty years, new techniques are still being developed. This presentation, from the 2020 International Conference on Functional Programming, describes a new technique that is used to make combinator parsers very, very efficient.
  • The talk begins with a great, accessible introduction, which runs for about three and a half minutes. Then around 31:44 it accelerates into hyperspace (a parsing machine based on continuations). In my opinion, the typed machine at 35:00 is very cool.
  • If you want to follow along with the talk, here is a translation table:

  Talk code	Our code
  pure	succeed
  (:)	curry op ::
  runParser	produce (roughly)
  some	many1
  satisfy	sat

  Lab

  Lab proceeds in three parts. Course staff will keep time and will move people along in lock step.

  1. Combinators as functions. From the parsing handout, review the type of 'a producer and the three possible forms of its result type:
     • Failure: NONE
     • Success: SOME (OK a, remaining_inputs)
     • Error: SOME (ERROR msg, remaining_inputs)

  Now define the parsing combinator for choice:

  val <|>: 'a producer * 'a producer -> 'a producer

  You may define an ML function using fun , or you may complete this algebraic law:

  (p1 <|>p2) ts == . 

  Plan on writing one case for each form of result from p1 ts .

  If you finish before the course staff moves the group to step 7, define the parsing combinator for satisfaction:

  val sat : ('a -> bool) -> 'a producer -> 'a producer

  Again you may write code or you may complete this law:

  sat predicate p ts = . 

  Again you will have to consider all possible forms of p ts .

  val many : 'a producer -> 'a list producer (* zero or more *) val many1 : 'a producer -> 'a list producer (* one or more *) val optional : 'a producer -> 'a option producer (* zero or one *)

  Looking ahead to step 8, here’s an example use of many to capture the arguments to a function application in Scheme: 1

  the "(" >> curry APPLY exp many exp the ")"

  And here’s an example of optional to get the optional else clause in a C if statement:

  the "if" >> curry3 C_IF (the "(" >> exp the ")") statement optional (the "else" >> statement)

  Complete these algebraic laws:

  many p == . many1 p == . optional p == . 

  Analogously with many and many1 , define a count combinator that produces a list of exactly N values of type 'a :

  val count : int -> 'a producer -> 'a list producer (* exactly N *) count 0 p == . count (n+1) p == . 

  val : 'a producer * 'b producer -> 'a producer val >> : 'a producer * 'b producer -> 'b producer

  In the first combinator, the result from the 'a producer is ignored is used and the result from the 'b producer is ignored ; in the second combinator, the result from the 'b producer is ignored is used and the result from the 'a producer is ignored . Using , , and curry , among other functions, complete the following algebraic laws:

  p q == . p >> q == . 

  type reg = int val reg : reg producer (* parses a register number *) val int : int producer (* parses an integer literal *) val string : string producer (* parses a string literal *) val name : string producer (* parses a name *) val the : string -> unit producer (* one token, like a comma or bracket *)

  As functions you can use with , I provide these encoders:

  type opcode = string type instr (* instruction *) val eR0 : opcode -> instr val eR1 : opcode -> reg -> instr val eR2 : opcode -> reg -> reg -> instr val eR3 : opcode -> reg -> reg -> reg -> instr

  The parsers and functions above are meant to be combined with , , , <|>, and the other parsing combinators. As an example, here’s a parser that recognizes the assembly-language instruction r3 := r1 + r2 :

  eR3 "add" reg the ":=" reg the "+" reg

  After lab

  Setup

  1. Set up your computer for ML programming. Read the handout on “Software development in Standard ML”, and get set up with some ML compilers. (It sounds crazy, but I recommend that you use a mix of three ML compilers. If this sounds awful, you can limp along with just Moscow ML or MLton.) If you’re comfortable working on the department servers, you can skip this step.
  2. Download infrastructure for universal forward translation. Update your git repository in two steps:
     1. Be sure all your own code is committed. Confirm using git status .
     2. Update your working tree by running git pull (or you might possibly need git pull origin master ).

     If git gives you trouble, please post on the #git-fu channel in Slack.

     > make . > ../../bin/uft Usage: ../../bin/uft - [file] where and are one of these languages: ho! Higher-order vScheme with mutation ho Pure, higher-order vScheme fo Pure, first-order vScheme cl Pure, first-order vScheme with closure and capture forms kn K-Normal form vs VM assembly language vo VM object code

     Verify that you can use my escape-hatch parser to translate some assembly code into object code:

     > echo '@ print 33' | uft vs-vo | svm nil

     > echo '@ print 33' | uft vs-vs an unknown assembly-code instruction

     If you compiled with MLton, you’ll use uft.opt instead of uft .

     Syntax design

     1. Decide on concrete syntax for register names. I ship a lexical analyzer that accepts both $r k and r k as register numbers, where k is an integer literal in the range 0 to 255. If that works for you, you’re done. Otherwise, you’ll have to edit asmlex.sml (the registerNum function, the token parser, or both).
     2. Decide if you want floating-point literals. If so, you’ll need to extend asmlex.sml . If not, you can live nicely without them.
     3. Finish your grammar. In this step, which can be interleaved with with step 17, you finish designing the assembly-language syntax you started in step 3.
        • Make sure there is concrete syntax for each of the five forms of assembly-language instruction defined in file asm.sml .
        • Make sure there is concrete syntax for each of the instructions your VM recognizes (all of which will take the OBJECT_CODE form in asm.sml ).
        • Follow the design guidelines.

     For the LOADFUNC form, I recommend that you not require persons to count the number of instructions in the instruction list. Instead, try bracketing the instructions in some way.

     Unparsing

     1. Write unparsers for your assembly language. Using the grammar you defined in steps 3 and 16, and possibly concurrently with step 16, define unparsing functions so that every instruction and every assembly-language form can be rendered in the concrete syntax you have chosen. In file asmparse.sml , replace my placeholders unparse and unparse1 with a real unparser for assembly code.
        • Write unparse1 , which should handle every case except LOADFUNC . (Each of those cases produces one line of output.)
        • Write unparse , which handles both cases of LOADFUNC . 2 A function load generally requires multiple lines of assembly code.

     Function unparse1 requires a ton of case analysis: pattern matching on opcode names. Every instruction your VM accepts must unparse to a readable assembly-language syntax.

     Test your unparser by creating a test file unparse.vs . In this file, using my “passthrough parser”, or using your own parser if you have completed step 18, write at least half the instructions that your VM recognizes. (If you use my passthrough parser, you will be limited to instructions in formats R0 through R3 , like halt and print but not loadliteral or check .) Test that these instructions unparse correctly by running

     uft vs-vs unparse.vs

     and comparing the output with what you expect from your grammar.

     The other half of your instructions should be implemented in your unparser, but they can remain untested until next week.

     One step toward parsing

     1. Extend my placeholder parser with at least one new syntactic form. In file asmparse.sml , I define a simple parser for assembly instructions. This parser, instr , recognizes only two forms:
        • From the form reg := reg + reg , it generates an add instruction (opcode + ).
        • From the form @ opcode< int > , it generates an object-code instruction with the given opcode and registers. This form basically works as a “passthrough” to be able to write some virtual object code after the @ sign.

     Extend instr with at least one case of concrete syntax in your assembly language. A good case to implement would be concrete syntax for loading a literal value into a register. You’ll add more cases next week.

     What and how to submit

     1. On Sunday, submit the homework. In the src/uft directory you’ll find a file SUBMIT.03 . That file needs to be edited to answer the same questions you answer every week. (A duplicate question from last week has been eliminated.) From now on, you’ll be submitting your full src tree, including both the UFT and the SVM. To submit, you’ll need to copy your working tree to the department servers. We recommend using rsync , but scp also works. Now log into a department server, change to your working tree, and submit your entire src directory:

     provide comp150vm hw03 src

     provide comp150vm reflection03 REFLECTION

     Reading in depth

     Occasionally I’ll suggest reading that may enrich your view of programming-language implementation. Here are three works on combinator parsing:

     • Graham Hutton, Higher-Order Functions for Parsing (1992). The work is somewhat primitive, and the notation is obsolete, but Hutton was first, and in academia, we honor those who came first. And it’s a good paper.
     • Graham Hutton and Erik Miejer, Monadic Parser Combinators (1996). Parsing brought up to date with Haskell. Also a decent introduction to monads. A shorter version was published in the Journal of Functional Programming in 1998.
     • Doaitse Swierstra, Combinator Parsing: A Short Tutorial (2008). Swierstra has done more than anyone else to develop the art and science of combinator parsing.

     Overview of the code

     Code you will write or edit

     asmparse.sml

     Toy parser and unparser for assembly code. You will build a real unparser this week and a real parser next week.

     Before looking at this file, look at and understand asm.sml and object-code.sml .

     Code you will look at and understand

     The internal representation of assembly code.

     The internal representation of virtual object code, plus a module that unparses this representation to its on-disk form.

     The interface to our version of the error monad.

     The interface to our library of parsing combinators.

     Exports function StringEscapes.quote , which will be useful for unparsing string literals.

     Defines function Impossible.impossible , which you’ll call if you ever need to signify an assertion failure.

     Code you may look at, but not deeply

     This file lists, directly or by reference, all the ML code used to build the UFT, except main.sml . It’s worth looking at now because it will give you some sense of the pieces that make up the UFT.

     My lexical analyzer for assembly language: it uses a combinator parser to convert a sequence of characters into a sequence of tokens. It may be worth looking at as an example of combinator parsing. And if you are ambitious, you may wish to modify it.

     Code you will look at eventually, but maybe not this week

     assembler.sml

     The heart of the assembler. Function Assembler.translate translates an assembly-language program into object code. Right now it’s just a stub: it extracts object-code instructions embedded in assembly language, and if it encounters anything else, it barfs. It will suffice to allow you to assemble code that doesn’t use labels.

     Next week you will write a real version of Assembler.translate .

     Lists all the languages the UFT will eventually understand.

     The Universal Forward Translator. It is given a source language and a target language, and it figures out how to translate the source to the target.

     An environment abstraction. You’ll use it next week to save the meanings of assembly-language labels.

     Code you may never look at

     File error-module.sml implements the error monad, and producer-functor.sml implements our parsing combinators. You will have learned all the good stuff either in lab (parsing combinators) or preparing for lab (error monad).

     File main.sml reads the command line and calls the UFT; main.cm builds it.

     File impossible.cm works around an annoyance in Moscow ML’s build process.

     File ioutil.sml defines a few convenience functions that I wish were in the Standard ML basis library, but aren’t.

     Learning outcomes

     Outcomes available for points

     Learning outcomes available for project points:

     1. Algebraic laws. You can write algebraic laws for particular monads.
     2. Parsing combinators. You can write new parsing combinators.
     3. Syntax design. You can explain how the design of your concrete syntax promotes readability.
     4. Costs of design. You can argue whether a well-designed concrete syntax is unreasonably expensive.
     5. Unparsing. At least half the instructions your VM recognizes can be unparsed by your UFT.
     6. Parsing in theory. You understand when your parser needs to see multiple tokens before making a choice.
     7. Parsing in practice. Using a parser you wrote yourself, your UFT can successfully parse one assembly-language instruction.
     8. Embedding and projection. You understand how assembly-language abstract syntax and concrete syntax are related by embedding and projection.

     Learning outcome available for depth points:

     1. Assembler macro [1 point]. You make check-expect look like a single assembly instruction, but it expands to multiple VM instructions. You can assemble and run a .vs file that contains a check-expect . The point can be redeemed with this module or the next module; after that, it expires.

     How to claim the project points

     Each of the numbered learning outcomes 1 to N is worth one point, and the points can be claimed as follows:

     1. In lab you wrote algebraic laws for Kleisli composition using the baby error monad. To claim this point, write algebraic laws for Kleisli composition using the full error monad.
     2. To claim this point, define this parsing combinator:

     val commaSep : 'a producer -> 'a list producer (* `commaSep p` returns a parser that parser a sequence of zero or more p's separated by commas *)

     • These are competing concerns.
     • Both can be accomplished in a single design.

     > echo "r1 := r2 + r3" | uft vs-vs r1 := r2 + r3

     • Explain whether and how the embedding/projection concept applies to the abstract syntax and concrete syntax of assembly language.
     • Point to where in your code embedding and/or projection are implemented.
     • If projection is implemented, say how projection failure is manifested.

     Syntax of the week

     Your most interesting design choice will probably be the notation you want to use for global variables. Here are your options:

     • A global variable is just a name. This is a lovely choice, but it’s hard to make work. What if some joker gives you a Scheme program with a global variable called $r0 ? How are you going to distinguish it from register 0?
     • A global variable is a name with a prefix. This choice was used in C compilers and linkers for many years: the C compiler slapped an underscore in front of every global name, and that made sure that a global name wouldn’t conflict with other things. You could consider some other character as a prefix or “sigil,” like Perl’s @ or % characters.
     • A global variable is a table lookup. This choice is faithful to the dynamic semantics of the SVM, so if you’re comfortable having a global variable look like a table reference, all you need is to invent a concrete syntax for table references.
     1. Examples not typechecked!↩
     2. There is not only Asm.LOADFUNC , but also Asm.OBJECT_CODE applied to ObjectCode.LOADFUNC .↩