Differences

This shows you the differences between two versions of the page.

--- cs330_f2016:tmp [2016/10/12 14:13]
wingated
+++ cs330_f2016:tmp [2021/06/30 23:42] (current)
@@ Line 1: / Line 1: @@
 ====Objective:====
-This lab is designed to transition our interpreter to a more powerful image processing engine, and to give you experience in creating new data types.
+This lab is designed to transition our interpreter to a more powerful image processing engine by binding in new data types, high performance primitives, and automatic parallelization of interpretation.
 ----
@@ Line 14: / Line 14: @@
 ''Pkg.add("Images")''
-**Note:** Julia uses Git as the foundation of their package management system.  This can create problems if your system can't access Git using a ''git://'' protocol -- this is manifest by Julia hanging when trying to install packages.  To alleviate this, please check out the following links:
+**Note:** Julia uses Git as the foundation of their package management system.  This can create problems if your system can't access Git using a <code>git://</code> protocol -- this is manifest by Julia hanging when trying to install packages.  To alleviate this, please check out the following links:
 [[https://github.com/JuliaLang/julia/issues/7005|]]
@@ Line 20: / Line 20: @@
 [[https://github.com/JuliaLang/julia/blob/master/README.md#source-download-and-compilation|]]
+When I installed my Julia packages, it took a long time, but it worked.  Be patient.  :)
 ----
 ====Deliverable:====
-For this lab, you will expand the interpreter that you have already built, and add in a new "analysis" function that performs three different flavors of syntactic de-sugaring.
+For this lab, you will expand the interpreter that we have already built in three ways: with new data types, new high performance primitives, and automatic parallelization.
-The primary deliverable for this lab is a new Julia module.  Your module should export ''parse'', ''calc'' **and ''analyze''** functions, and two return types, ''NumVal'' and ''ClosureVal''.
+The primary deliverable for this lab is a new Julia module.  Your module should export ''parse'', ''calc''  ''analyze'' functions, and three return types, ''NumVal'', ''ClosureVal'', and ''MatrixVal''.
-Your module should be able to do everything that your simple interpreter could do and everything that your extended interpreter can do.  However, you will use program analysis to both eliminate ''With'' nodes, and to add two new simple features.
+Your module should be able to do everything that the three previous interpreters.  You are welcome to examine the code we developed in class.  The ''CI8.jl'' module is available on LearningSuite, under "Content -> Julia -> High Performance Primitives".
-The ''CI7.jl'' module is available on LearningSuite, under "Content -> Julia -> Program analysis".
+Please name your module ''HPInt''.
-Please name your module TransInt.
 ----
 ====Description:====
-For this lab, you will implement an ''analyze'' function similar to what we covered in class.  The ''analyze'' function accepts as input an AST, rewrites it, and returns a new AST.
+For this lab, you will implement several new features:
-There are three rewrites you must implement:
-  - You must rewrite multi-argument ''with'' nodes to be multi-argument ''lambda'' nodes.
+  - You must create a new ''MatrixVal'' data type.
-  - You must create a new multi-argument ''+'' operation that is implemented with only binary ''+'' operations.
+  - You must bind in several new primitives (listed in the grammar below)
-  - You must create a new multi-argument ''and'' operation that is implemented with only ''if0'' operations.
+  - You must put in automatic parallelization statements.
 Each is discussed in more detail in the following sections.
@@ Line 51: / Line 48: @@
 <code BNF>
 <OWL> ::= number
-          | (+ <OWL> <OWL> <OWL>*)   # at least two parameters, possibly infinity.  note extra star!
+          | (+ <OWL> <OWL> <OWL>*)    # all owls could be a MatrixVal or a NumVal
           | (- <OWL> <OWL>)
           | (* <OWL> <OWL>)
@@ Line 62: / Line 59: @@
           | (with ( (id <OWL>)* ) <OWL>)
           | (lambda (id*) <OWL>)
-          | (and <OWL> <OWL> <OWL>*)  # new operation 'and'
+          | (and <OWL> <OWL> <OWL>*)
           | (<OWL> <OWL>*)
+          #
+          # new primitives here
+          #
+          | (simple_load <string>)
+          | (simple_save <OWL> <string>)        # this owl should evaluate to a MatrixVal
+          | (render_text <string> <OWL> <OWL>)  # these owls should evaluate to NumVals
+          | (emboss <OWL>)                      # this owl should evaluate to a MatrixVal
+          | (drop_shadow <OWL>)                 # this owl should evaluate to a MatrixVal
+          | (inner_shadow <OWL>)                # this owl should evaluate to a MatrixVal
+          | (min <OWL> <OWL>)                   # boths owls could be a MatrixVal or a NumVal
+          | (max <OWL> <OWL>)
 </code>
 ----
-===Expanded functionality:===
+===New functions:===
-Here we discuss the three new features you must support in our language.
+The new productions in our language map directly to the primitive functions of the same name.  For each, you will need to do the following:
-**Part 1: Multi-site ''with'' -> multi-site ''lambda''**
+  - Create a new node in the AST
+  - Parse the parameter properly
+  - Recursively analyze any ''<OWL>'' subexpressions
+  - Implement a calc function for each AST node type
-In class we showed how to implement ''with'' expressions using ''lambda'' expressions, but only for ''with'' and ''lambda'' expressions that involve one parameter.  For the first part of the lab, you must rewrite the AST of a program to eliminate all ''with'' nodes, even with multiple parameters, and replace them with equivalent function creation / function calls.
+We've been through this process several times in class, so we won't belabor it here.
-Remember from class that
+You must also ensure that the ''+'', ''-'', ''*'' and ''/'' operators work any combination of ''NumVal'' or ''MatrixVal''.  I showed you my solution to this problem in class, but the reference code does not contain that, because your implementation (using ''BinOp'') is likely quite different.
-<code lisp>
+A few notes:
-(with (x 5) (+ x 1))
-</code>
-becomes
+  - The ''min,max,+,-,/,*'' functions all must work with any combination of ''NumVal'' and ''MatrixVal''s.
+  - Remember that when multiplying a MatrixVal by a MatrixVal, we want to use the ''.*'' operation (element-wise matrix multiply) instead of ''*'' (matrix-matrix multiply).
-<code lisp>
+----
-((lambda x (+ x 1)) 5)
+===Error handling:===
-</code>
-Your code should make a similar transformation for multiple-identifier ''with'' expressions to applying multiple-parameter ''lambda'' expressions.
+The new primitives create new opportunities for error handling.  You should bullet-proof them!
-No changes to the grammar are necessary to support this change, and therefore, no changes to your parser from the Extended Interpreter are necessary to implement this under-the-hood syntactic rewrite. The transformation should happen in the ''analyze'' function.
+In particular, you should carefully check the number and type of all subexpressions and strings.  For example, operations such as ''min'' or ''max'' should operate on ''NumVal'' or ''MatrixVal'' objects, but should throw an error if handed something like a ''ClosureVal''.
-**Part 2: Addition operation with arbitrary number of parameters**
+----
+===Parallelization:===
-For the second feature, you must implement a more flexible ''+'' operator.
+We discussed several opportunities for parallelization in class.  You must use the proper combination of ''@spawn'' and ''fetch'' to parallelize as many of the ''calc'' functions as possible by spawning for each sub-call to ''calc''.  You do not need to parallelize the analyze functions.
-Specifically, instead of only two operands, the new ''+'' operator should support an arbitrary number of operands, as long as there are more than two.
-However, this will be syntactic sugar -- you should implement this using your existing binary operations.
+----
+====Hints:====
-So, we would essentially rewrite this:
+Once all is said and done, the following program:
 <code lisp>
-(+ a b c d)
+(with base_img (render_text "Hello" 25 100)
+  (with swirl (simple_load "/Users/wingated/Desktop/swirl_256.png")
+    (with ds (drop_shadow base_img)
+      (with tmp4 (+ (* (+ (min ds base_img) (- 1 base_img)) base_img) (* (- 1 base_img) swirl) )
+        (with tmp5 (- 1 (emboss tmp4))
+          (with base_img2 (render_text "world!" 5 200)
+	    (with is (inner_shadow base_img2)
+              (with tmp6 (max base_img2 (* (- 1 base_img2) is) )
+                (with output (min tmp5 tmp6 )
+		  (simple_save output "output.png")
+		)
+              )
+	    )
+	  )
+	)
+      )
+    )
+  )
+)
 </code>
-into this:
+should generate the image shown below, using the ''swirl_256.png'' image shown at the right:
-<code lisp>
-(+ a (+ b (+ c d)))
-</code>
-Note that this involves a change to the grammar, and therefore you will need to change your parser!  You may need to change the definition of the plus node -- it can no longer by implemented as a BinOp.  The ''analyze'' function should eventually convert it to a sequence of BinOp operations only, and your ''calc'' function should handle this without change.
-**Part 3: A simple ''and'' operator**
-For the final part of this lab you will implement a simple short-circuited ''and'' operation in terms of ''if0'' calls.  The semantics of the ''and'' node is that it should return 1 iff all subexpressions evaluate to nonzero, and return 0 otherwise.  Or in other words, it should return 0 if any subexpression evaluates to zero.
-As an example, we will transform this:
-<code lisp>
-(and (+ 4 0) (- 3 3) (* 4 3))
-</code>
-into this:
-<code lisp>
-(if0 (+ 4 0)
-     (if0 (- 3 3)
-          (if0 (* 4 3)
-)))
-</code>
-Note that this is a new construct in our grammar, so you will need to create a new AST node type (call it ''And'') and parse it appropriately.  However, because it is being implemented in terms of ''if0'' calls, you will not need to modify your ''calc'' function to support it. The transformation from the ''And'' node to the ''if0'' nodes should happen in the ''analyze'' function.
+{{:cs330_f2016:sample_text.png?direct|}}
+{{ :cs330_f2016:swirl_256.png?direct|}}

BYU CS classes

User Tools

Site Tools

Differences

Page Tools